Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

SortableArray.h

Go to the documentation of this file.
00001 /***************************************************************************
00002  *cr                                                                       
00003  *cr            (C) Copyright 1995-2019 The Board of Trustees of the           
00004  *cr                        University of Illinois                       
00005  *cr                         All Rights Reserved                        
00006  *cr                                                                   
00007  ***************************************************************************/
00008 
00009 /***************************************************************************
00010  * RCS INFORMATION:
00011  *
00012  *      $RCSfile: SortableArray.h,v $
00013  *      $Author: johns $        $Locker:  $             $State: Exp $
00014  *      $Revision: 1.26 $       $Date: 2019/01/17 21:21:01 $
00015  *
00016  ***************************************************************************
00017  * DESCRIPTION:
00018  *   This is a variant of the Resizeable array class.  In addition to the
00019  * methods provided there, this template allows either quicksorting 
00020  * or insertion sorting of the elements in the array
00021  *
00022  ***************************************************************************/
00023 #ifndef SORTABLEARRAY_TEMPLATE_H
00024 #define SORTABLEARRAY_TEMPLATE_H
00025 
00026 #include <string.h>
00027 
00032 template<class T>
00033 class SortableArray {
00034 private:
00036   T *data;
00037 
00039   int sz;
00040   
00042   float resizeFactor;
00043   
00046   int currSize;
00047 
00048 
00049 public:
00050   SortableArray(int s = 10, float rsf = 2.0) {
00052     resizeFactor = rsf;
00053     
00055     currSize = 0;
00056     sz = (s > 0 ? s : 10);
00057     
00059     data = new T[sz];
00060   }
00061 
00062   ~SortableArray(void) {
00063     if(data)
00064       delete [] data; 
00065   }
00066 
00067   //
00068   // query routines about the state of the array
00069   //
00070     
00072   int num(void) { return currSize; }
00073 
00074   //
00075   // routines for accessing array elements
00076   //
00077 
00079   T& operator[](int N) { return item(N); }
00080 
00082   int append(const T& val) {
00083     item(currSize) = val;
00084     return currSize - 1;
00085   }
00086 
00088   T& item(int N) {
00089     // check and see if this is attempting to access an item larger than
00090     // the array.  If so, extend the max size of the array by resizeFactor,
00091     // and return the value at the Nth position (which will be basically
00092     // random).
00093     if(N >= sz) {                       // extend size of array if necessary
00094       // calc new size of array
00095       int newsize = (int)((float)N * resizeFactor + 0.5);
00096   
00097       // allocate new space, and copy over previous copy.  We only need to
00098       // copy over the first currSize elements, since currSize is the max
00099       // index that has been accessed (read OR write).  Then delete old
00100       // storage.
00101       T *newdata = new T[newsize];
00102       if(data) {
00103         memcpy((void *)newdata, (void *)data, currSize * sizeof(T));
00104         delete [] data;
00105       }
00106       
00107       // save new values
00108       data = newdata;
00109       sz = newsize;
00110     }
00111     
00112     // remember what the maximum index reached so far is
00113     if(N >= currSize)
00114       currSize = N + 1;
00115       
00116     // return element at Nth position
00117     return data[N];
00118   }
00119 
00124   void remove(int m = -1, int n = -1) {
00125     if(m < currSize && n < currSize) {
00126       if((m < 0 && n < 0) || (m >= 0 && n < 0) || (m > 0 && n > 0 && m <= n)) {
00127         int N = n, M = (m >= 0 ? m : 0);
00128         if(m < 0 && n < 0)
00129           N = (currSize - 1);
00130         else if(n < 0)
00131           N = M;
00132         else
00133           N = n;
00134         int removed = N - M + 1;
00135         for(int i=N+1; i < currSize; i++)
00136           data[i - removed] = data[i];
00137         currSize -= removed;
00138       }
00139     }
00140   }
00141 
00143   void swap (int i, int j) {
00144    T temp;
00145   
00146    temp = data[i];
00147    data[i]=data[j];
00148    data[j]=temp;
00149   }
00150 
00154   void qsort (int left, int right) {
00155     int i, last;
00156   
00157     if (left >= right)    // fewer than two elements
00158        return;
00159     swap (left, (left + right) /2);
00160     last = left;
00161     for (i = left+1; i <=right; i++)
00162       if (data[i] > data[left]) 
00163        swap (++last, i);
00164     swap (left, last);
00165     qsort (left, last-1);
00166     qsort (last+1, right);
00167   }
00168 
00170   void isort () {
00171      int i, j;
00172      T temp;
00173      for (i = currSize-2; i>=0; i--) {  // jan 16 added = to >=
00174        j = i+1;
00175        temp = data[i];
00176        while ((j < currSize) && (temp < data[j])) {
00177          data[j-1] = data[j];
00178          j = j+1;
00179        }
00180        data[j-1] = temp;
00181      }
00182   }
00183 };
00184 
00185 #endif

Generated on Thu Mar 28 02:44:10 2024 for VMD (current) by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002