1 /*
2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22 #ifndef __UTIL_LIST_H__
23 #define __UTIL_LIST_H__
24
25 #include <stdlib.h>
26 #include <assert.h>
27
28 template< class type >
29 class idList {
30 private:
31 int m_num;
32 int m_size;
33 int m_granularity;
34 type *m_list;
35
36 public:
37 idList( int granularity = 16 );
38 ~idList<type>();
39 void Clear( void );
40 int Num( void );
41 void SetNum( int num );
42 void SetGranularity( int granularity );
43 void Condense( void );
44 int Size( void );
45 void Resize( int size );
46 type operator[]( int index ) const;
47 type &operator[]( int index );
48 int Append( type const & obj );
49 int AddUnique( type const & obj );
50 type *Find( type const & obj, int *index = NULL );
51 bool RemoveIndex( int index );
52 bool Remove( type const & obj );
53 typedef int cmp_t ( const void *, const void * );
54 void Sort( cmp_t *compare );
55 };
56
57 /*
58 ================
59 idList<type>::idList( int )
60 ================
61 */
62 template< class type >
idList(int granularity)63 inline idList<type>::idList( int granularity ) {
64 assert( granularity > 0 );
65
66 m_list = NULL;
67 m_granularity = granularity;
68 Clear();
69 }
70
71 /*
72 ================
73 idList<type>::~idList<type>
74 ================
75 */
76 template< class type >
~idList()77 inline idList<type>::~idList() {
78 Clear();
79 }
80
81 /*
82 ================
83 idList<type>::Clear
84 ================
85 */
86 template< class type >
Clear(void)87 inline void idList<type>::Clear( void ) {
88 if ( m_list ) {
89 delete[] m_list;
90 }
91
92 m_list = NULL;
93 m_num = 0;
94 m_size = 0;
95 }
96
97 /*
98 ================
99 idList<type>::Num
100 ================
101 */
102 template< class type >
Num(void)103 inline int idList<type>::Num( void ) {
104 return m_num;
105 }
106
107 /*
108 ================
109 idList<type>::SetNum
110 ================
111 */
112 template< class type >
SetNum(int num)113 inline void idList<type>::SetNum( int num ) {
114 assert( num >= 0 );
115 if ( num > m_size ) {
116 // resize it up to the closest level of granularity
117 Resize( ( ( num + m_granularity - 1 ) / m_granularity ) * m_granularity );
118 }
119 m_num = num;
120 }
121
122 /*
123 ================
124 idList<type>::SetGranularity
125 ================
126 */
127 template< class type >
SetGranularity(int granularity)128 inline void idList<type>::SetGranularity( int granularity ) {
129 int newsize;
130
131 assert( granularity > 0 );
132 m_granularity = granularity;
133
134 if ( m_list ) {
135 // resize it to the closest level of granularity
136 newsize = ( ( m_num + m_granularity - 1 ) / m_granularity ) * m_granularity;
137 if ( newsize != m_size ) {
138 Resize( newsize );
139 }
140 }
141 }
142
143 /*
144 ================
145 idList<type>::Condense
146
147 Resizes the array to exactly the number of elements it contains
148 ================
149 */
150 template< class type >
Condense(void)151 inline void idList<type>::Condense( void ) {
152 if ( m_list ) {
153 if ( m_num ) {
154 Resize( m_num );
155 }
156 else {
157 Clear();
158 }
159 }
160 }
161
162 /*
163 ================
164 idList<type>::Size
165 ================
166 */
167 template< class type >
Size(void)168 inline int idList<type>::Size( void ) {
169 return m_size;
170 }
171
172 /*
173 ================
174 idList<type>::Resize
175 ================
176 */
177 template< class type >
Resize(int size)178 inline void idList<type>::Resize( int size ) {
179 type *temp;
180 int i;
181
182 assert( size > 0 );
183
184 if ( size <= 0 ) {
185 Clear();
186 return;
187 }
188
189 temp = m_list;
190 m_size = size;
191 if ( m_size < m_num ) {
192 m_num = m_size;
193 }
194
195 m_list = new type[ m_size ];
196 for ( i = 0; i < m_num; i++ ) {
197 m_list[ i ] = temp[ i ];
198 }
199
200 if ( temp ) {
201 delete[] temp;
202 }
203 }
204
205 /*
206 ================
207 idList<type>::operator[] const
208 ================
209 */
210 template< class type >
211 inline type idList<type>::operator[]( int index ) const {
212 assert( index >= 0 );
213 assert( index < m_num );
214
215 return m_list[ index ];
216 }
217
218 /*
219 ================
220 idList<type>::operator[]
221 ================
222 */
223 template< class type >
224 inline type &idList<type>::operator[]( int index ) {
225 assert( index >= 0 );
226 assert( index < m_num );
227
228 return m_list[ index ];
229 }
230
231 /*
232 ================
233 idList<type>::Append
234 ================
235 */
236 template< class type >
Append(type const & obj)237 inline int idList<type>::Append( type const & obj ) {
238 if ( !m_list ) {
239 Resize( m_granularity );
240 }
241
242 if ( m_num == m_size ) {
243 Resize( m_size + m_granularity );
244 }
245
246 m_list[ m_num ] = obj;
247 m_num++;
248
249 return m_num - 1;
250 }
251
252 /*
253 ================
254 idList<type>::AddUnique
255 ================
256 */
257 template< class type >
AddUnique(type const & obj)258 inline int idList<type>::AddUnique( type const & obj ) {
259 int index;
260
261 if ( !Find( obj, &index ) ) {
262 index = Append( obj );
263 }
264
265 return index;
266 }
267
268 /*
269 ================
270 idList<type>::Find
271 ================
272 */
273 template< class type >
Find(type const & obj,int * index)274 inline type *idList<type>::Find( type const & obj, int *index ) {
275 int i;
276
277 for ( i = 0; i < m_num; i++ ) {
278 if ( m_list[ i ] == obj ) {
279 if ( index ) {
280 *index = i;
281 }
282 return &m_list[ i ];
283 }
284 }
285
286 return NULL;
287 }
288
289 /*
290 ================
291 idList<type>::RemoveIndex
292 ================
293 */
294 template< class type >
RemoveIndex(int index)295 inline bool idList<type>::RemoveIndex( int index ) {
296 int i;
297
298 if ( !m_list || !m_num ) {
299 return false;
300 }
301
302 assert( index >= 0 );
303 assert( index < m_num );
304
305 if ( ( index < 0 ) || ( index >= m_num ) ) {
306 return false;
307 }
308
309 m_num--;
310 for ( i = index; i < m_num; i++ ) {
311 m_list[ i ] = m_list[ i + 1 ];
312 }
313
314 return true;
315 }
316
317 /*
318 ================
319 idList<type>::Remove
320 ================
321 */
322 template< class type >
Remove(type const & obj)323 inline bool idList<type>::Remove( type const & obj ) {
324 int index;
325
326 if ( Find( obj, &index ) ) {
327 return RemoveIndex( index );
328 }
329
330 return false;
331 }
332
333 /*
334 ================
335 idList<type>::Sort
336 ================
337 */
338 template< class type >
Sort(cmp_t * compare)339 inline void idList<type>::Sort( cmp_t *compare ) {
340 if ( !m_list ) {
341 return;
342 }
343
344 qsort( ( void * )m_list, ( size_t )m_num, sizeof( type ), compare );
345 }
346
347 #endif /* !__UTIL_LIST_H__ */
348