remove RSA's md4.c, replace by DP's
[xonotic/netradiant.git] / libs / splines / util_list.h
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 >
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 >
77 inline idList<type>::~idList() {
78         Clear();
79 }
80
81 /*
82 ================
83 idList<type>::Clear
84 ================
85 */
86 template< class type >
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 >
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 >
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 >
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 >
151 inline void idList<type>::Condense( void ) {
152         if ( m_list ) {
153                 if ( m_num ) {
154                         Resize( m_num );
155                 } else {
156                         Clear();
157                 }
158         }
159 }
160
161 /*
162 ================
163 idList<type>::Size
164 ================
165 */
166 template< class type >
167 inline int idList<type>::Size( void ) {
168         return m_size;
169 }
170
171 /*
172 ================
173 idList<type>::Resize
174 ================
175 */
176 template< class type >
177 inline void idList<type>::Resize( int size ) {
178         type    *temp;
179         int             i;
180
181         assert( size > 0 );
182
183         if ( size <= 0 ) {
184                 Clear();
185                 return;
186         }
187
188         temp    = m_list;
189         m_size  = size;
190         if ( m_size < m_num ) {
191                 m_num = m_size;
192         }
193
194         m_list = new type[ m_size ];
195         for( i = 0; i < m_num; i++ ) {
196                 m_list[ i ] = temp[ i ];
197         }
198
199         if ( temp ) {
200                 delete[] temp;
201         }
202 }
203
204 /*
205 ================
206 idList<type>::operator[] const
207 ================
208 */
209 template< class type >
210 inline type idList<type>::operator[]( int index ) const {
211         assert( index >= 0 );
212         assert( index < m_num );
213
214         return m_list[ index ];
215 }
216
217 /*
218 ================
219 idList<type>::operator[]
220 ================
221 */
222 template< class type >
223 inline type &idList<type>::operator[]( int index ) {
224         assert( index >= 0 );
225         assert( index < m_num );
226
227         return m_list[ index ];
228 }
229
230 /*
231 ================
232 idList<type>::Append
233 ================
234 */
235 template< class type >
236 inline int idList<type>::Append( type const & obj ) {
237         if ( !m_list ) {
238                 Resize( m_granularity );
239         }
240
241         if ( m_num == m_size ) {
242                 Resize( m_size + m_granularity );
243         }
244
245         m_list[ m_num ] = obj;
246         m_num++;
247
248         return m_num - 1;
249 }
250
251 /*
252 ================
253 idList<type>::AddUnique
254 ================
255 */
256 template< class type >
257 inline int idList<type>::AddUnique( type const & obj ) {
258         int index;
259
260         if ( !Find( obj, &index ) ) {
261                 index = Append( obj );
262         }
263
264         return index;
265 }
266
267 /*
268 ================
269 idList<type>::Find
270 ================
271 */
272 template< class type >
273 inline type *idList<type>::Find( type const & obj, int *index ) {
274         int i;
275
276         for( i = 0; i < m_num; i++ ) {
277                 if ( m_list[ i ] == obj ) {
278                         if ( index ) {
279                                 *index = i;
280                         }
281                         return &m_list[ i ];
282                 }
283         }
284
285         return NULL;
286 }
287
288 /*
289 ================
290 idList<type>::RemoveIndex
291 ================
292 */
293 template< class type >
294 inline bool idList<type>::RemoveIndex( int index ) {
295         int i;
296
297         if ( !m_list || !m_num ) {
298                 return false;
299         }
300
301         assert( index >= 0 );
302         assert( index < m_num );
303
304         if ( ( index < 0 ) || ( index >= m_num ) ) {
305                 return false;
306         }
307
308         m_num--;
309         for( i = index; i < m_num; i++ ) {
310                 m_list[ i ] = m_list[ i + 1 ];
311         }
312
313         return true;
314 }
315
316 /*
317 ================
318 idList<type>::Remove
319 ================
320 */
321 template< class type >
322 inline bool idList<type>::Remove( type const & obj ) {
323         int index;
324
325         if ( Find( obj, &index ) ) {
326                 return RemoveIndex( index );
327         }
328         
329         return false;
330 }
331
332 /*
333 ================
334 idList<type>::Sort
335 ================
336 */
337 template< class type >
338 inline void idList<type>::Sort( cmp_t *compare ) {
339         if ( !m_list ) {
340                 return;
341         }
342
343         qsort( ( void * )m_list, ( size_t )m_num, sizeof( type ), compare );
344 }
345
346 #endif /* !__UTIL_LIST_H__ */