SortableArray.h

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