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