SortableResizeArray.h

Go to the documentation of this file.
00001 
00007 #ifndef SRTABARRAY_H
00008 #define SRTABARRAY_H
00009 
00010 #include <string.h>
00011 #include "ResizeArray.h"
00012 
00013 template <class Elem> class SortableResizeArray : public ResizeArray<Elem> {
00014 
00015   private:
00016 
00017     inline void swap(int offset, int i, int j) {
00018       char tmp[sizeof(Elem)];
00019       register Elem *r = (this->rep.array+offset);
00020       memcpy(tmp, (char *)&r[i], sizeof(Elem));
00021       memcpy((char *)&(r[i]), (char *)&(r[j]), sizeof(Elem));
00022       memcpy((char *)&r[j], tmp, sizeof(Elem));
00023     }
00024 
00025 
00026     inline void siftup(int offset, int i, int size) {
00027       char tmp[sizeof(Elem)];
00028       register int j;
00029       register Elem *r = (this->rep.array+offset);
00030     
00031       while ((j = 2*i+1) < size) {
00032         if (j+1 < size) {
00033           if (r[j] < r[j+1])
00034             j = j+1;
00035           }
00036           if (r[i] < r[j]) {
00037             memcpy(tmp, (char *)&r[i], sizeof(Elem));
00038             memcpy((char *)&(r[i]), (char *)&(r[j]), sizeof(Elem));
00039             memcpy((char *)&r[j], tmp, sizeof(Elem));
00040             i = j;
00041           } else {
00042             break;
00043           }
00044       }
00045     }
00046 
00047   public:
00048 
00049     SortableResizeArray(void) : ResizeArray<Elem>() { init(); }
00050 
00051     SortableResizeArray(int size) : ResizeArray<Elem>(size) { init(); }
00052 
00053     SortableResizeArray(ResizeArray<Elem> &ra) : 
00054       ResizeArray<Elem>(ra) { init(); }
00055 
00056     SortableResizeArray(SortableResizeArray<Elem> &ra) :
00057       ResizeArray<Elem>(ra) { init(); }
00058 
00059     SortableResizeArray(const ResizeArray<Elem>* ra) : 
00060       ResizeArray<Elem>(ra) { init(); }
00061 
00062     SortableResizeArray(const SortableResizeArray<Elem>* ra) : 
00063       ResizeArray<Elem>(ra) { init(); }
00064 
00065     SortableResizeArray(Elem* * const r, int numElem, int maxElem) : 
00066       ResizeArray<Elem>(r,numElem,maxElem) { init(); }
00067 
00068     SortableResizeArray<Elem>& operator =(SortableResizeArray<Elem>& sa) {
00069       ResizeArray<Elem>::operator=(sa);
00070       return(*this);
00071     }
00072 
00073     ~SortableResizeArray(void) { }
00074   
00075     void init(void) { }
00076   
00077     void sort(void) { sort(0, this->rep.size()-1); }
00078 
00079     // Heap Sort - worst case is O(n log n)
00080     //      bot = bottom element of sort range
00081     //      top = top element of sort range
00082     void sort(int bot, int top) {
00083       int index, size;
00084       if (top > this->rep.size()) top = this->rep.size();
00085       size = top - bot + 1;
00086     
00087       // Make all sub-heaps
00088       for ( index = size/2-1; index > 0; index-- )
00089         siftup(bot, index, size);
00090     
00091       // Take top element of overall heap, and put on top
00092       for ( index = size; index > 1; index-- ) {
00093         siftup(bot, 0, index);
00094         swap(bot, 0, index-1);
00095       }
00096     }
00097 
00098     inline void uniq(void);
00099 
00100     // Search returns index of position where elem should be inserted.
00101     // This is equal to the first position equal to elem
00102     // or the first item greater than elem
00103     // if elem is larger than any item, it returns
00104     // the index just beyond the end of the list
00105     // We stick with the < operator only
00106     int bsearch(const Elem& elem) const {
00107       int test;
00108       int bot = -1;
00109       int top = this->size();
00110       if (this->size() == 0) return (-1);
00111       while (top - bot > 1) {
00112         if ( this->rep.array[test = (bot+top)/2] < elem )
00113           bot = test;
00114         else
00115           top = test;
00116       }
00117       return(top);
00118     }
00119 
00120 };
00121 
00122 template <class Elem>
00123 inline void SortableResizeArray<Elem>::uniq(void) {
00124   if (this->size()) {
00125     int oldIndex=0;
00126     int newIndex=0;
00127     while (++oldIndex < this->size()) {
00128       if ( ! ( this->rep.array[oldIndex] == this->rep.array[newIndex] ) ) {
00129         if (++newIndex != oldIndex)
00130           memcpy((void *)&(this->rep.array[newIndex]),
00131                  (void *)&(this->rep.array[oldIndex]),
00132                  sizeof(Elem));
00133       } else {
00134         this->rep.array[oldIndex].~Elem();
00135       }
00136     }
00137     this->rep.arraySize = ++newIndex;
00138   }
00139 }
00140 
00141 #endif

Generated on Fri Sep 22 01:17:15 2017 for NAMD by  doxygen 1.4.7