1 /* 2 * ppui/SimpleVector.h 3 * 4 * Copyright 2009 Peter Barth 5 * 6 * This file is part of Milkytracker. 7 * 8 * Milkytracker is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * Milkytracker is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU General Public License for more details. 17 * 18 * You should have received a copy of the GNU General Public License 19 * along with Milkytracker. If not, see <http://www.gnu.org/licenses/>. 20 * 21 */ 22 23 #ifndef SIMPLEVECTOR__H 24 #define SIMPLEVECTOR__H 25 26 #include "BasicTypes.h" 27 28 template<class Type> 29 class PPSimpleVector 30 { 31 private: 32 pp_int32 numValuesAllocated; 33 Type** values; 34 pp_int32 numValues; 35 bool destroy; 36 reallocate()37 void reallocate() 38 { 39 Type** values = new Type*[numValuesAllocated]; 40 for (pp_int32 i = 0; i < numValues; i++) 41 { 42 values[i] = this->values[i]; 43 } 44 delete[] this->values; 45 this->values = values; 46 } 47 48 // no copy construction please 49 PPSimpleVector(const PPSimpleVector&); 50 PPSimpleVector& operator=(const PPSimpleVector&); 51 52 public: 53 PPSimpleVector(pp_int32 initialSize = 0, bool destroy = true) 54 { 55 this->destroy = destroy; 56 57 if (initialSize == 0) 58 initialSize = 16; 59 60 numValuesAllocated = initialSize; 61 62 if (initialSize) 63 values = new Type*[initialSize]; 64 else 65 values = 0; 66 67 numValues = 0; 68 } 69 ~PPSimpleVector()70 ~PPSimpleVector() 71 { 72 if (values) 73 { 74 if (destroy) 75 for (pp_int32 i = 0; i < numValues; i++) 76 delete values[i]; 77 78 delete[] values; 79 } 80 } 81 clone()82 PPSimpleVector* clone() 83 { 84 PPSimpleVector* clonedVector = new PPSimpleVector(numValuesAllocated, true); 85 for (pp_int32 i = 0; i < numValues; i++) 86 { 87 clonedVector->values[i] = new Type(*values[i]); 88 } 89 clonedVector->numValues = numValues; 90 return clonedVector; 91 } 92 clear()93 void clear() 94 { 95 if (values) 96 { 97 if (destroy) 98 for (pp_int32 i = 0; i < numValues; i++) 99 delete values[i]; 100 101 numValues = 0; 102 } 103 } 104 removeNoDestroy(pp_int32 index)105 Type* removeNoDestroy(pp_int32 index) 106 { 107 if (!numValues) 108 return NULL; 109 110 if (index < 0 || index >= numValues) 111 return NULL; 112 113 Type* result = values[index]; 114 115 for (pp_int32 i = index; i < numValues-1; i++) 116 values[i] = values[i+1]; 117 118 numValues--; 119 120 if (numValuesAllocated - numValues > 16) 121 { 122 numValuesAllocated-=16; 123 reallocate(); 124 } 125 126 return result; 127 } 128 remove(pp_int32 index)129 bool remove(pp_int32 index) 130 { 131 if (!numValues) 132 return false; 133 134 if (index < 0 || index >= numValues) 135 return false; 136 137 if (destroy) 138 delete values[index]; 139 140 for (pp_int32 i = index; i < numValues-1; i++) 141 values[i] = values[i+1]; 142 143 numValues--; 144 145 if (numValuesAllocated - numValues > 16) 146 { 147 numValuesAllocated-=16; 148 reallocate(); 149 } 150 151 return true; 152 } 153 add(Type * value)154 void add(Type* value) 155 { 156 if (numValues >= numValuesAllocated) 157 { 158 numValuesAllocated += 16; 159 reallocate(); 160 } 161 values[numValues++] = value; 162 } 163 164 // handle with care replace(pp_int32 index,Type * value)165 void replace(pp_int32 index, Type* value) 166 { 167 if (index < 0 || index >= numValues) 168 return; 169 170 if (destroy) 171 delete values[index]; 172 173 values[index] = value; 174 } 175 get(pp_int32 index)176 Type* get(pp_int32 index) const 177 { 178 if (index < numValues) 179 { 180 return values[index]; 181 } 182 else 183 return 0; 184 } 185 size()186 pp_int32 size() const { return numValues; } 187 isEmpty()188 bool isEmpty() const { return numValues == 0; } 189 190 // -- sorting -------------------------------------------------------------- 191 struct SortRule 192 { 193 virtual pp_int32 compare(const Type& left, const Type& right) const = 0; 194 }; 195 196 private: 197 static pp_int32 partition(Type** a, pp_int32 left, pp_int32 right, const SortRule& sortRule, bool descending = false) 198 { 199 const pp_int32 sign = descending ? -1 : 1; 200 201 pp_int32 first=left, pivot=right--; 202 while(left<=right) 203 { 204 while(sortRule.compare(*a[left], *a[pivot])*sign < 0/*a[left]<a[pivot]*/) 205 left++; 206 207 while((right>=first)&&(sortRule.compare(*a[right], *a[pivot])*sign >= 0/*a[right]>=a[pivot]*/)) 208 right--; 209 210 if(left<right) 211 { 212 swap(a, left,right); 213 left++; 214 } 215 } 216 if(left!=pivot) 217 swap(a, left,pivot); 218 219 return left; 220 } 221 swap(Type ** a,pp_int32 i,pp_int32 j)222 static void swap(Type** a, pp_int32 i, pp_int32 j) 223 { 224 Type* temp=a[i]; 225 a[i]=a[j]; 226 a[j]=temp; 227 } 228 229 static void sortInternal(Type** array, pp_int32 left, pp_int32 right, const SortRule& sortRule, bool descending = false) 230 { 231 pp_int32 p; 232 233 if(left>=right) 234 return; 235 236 p = partition(array, left, right, sortRule, descending); 237 238 sortInternal(array, left,p-1, sortRule, descending); 239 sortInternal(array, p+1, right, sortRule, descending); 240 } 241 242 public: 243 void sort(const SortRule& sortRule, pp_int32 l = 0, pp_int32 r = -1, const bool descending = false) 244 { 245 if (r == -1) 246 r = size()-1; 247 248 // no need to sort 249 if (l == 0 && r <= 1) 250 return; 251 252 sortInternal(values, l, r, sortRule, descending); 253 } 254 }; 255 256 #endif 257