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