libs/splines/util_list.h

   1 /*
   2 Copyright (C) 1999-2007 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__ */