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