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                 }
 156                 else {
 157                         Clear();
 158                 }
 159         }
 160 }
 161
 162 /*
 163    ================
 164    idList<type>::Size
 165    ================
 166  */
 167 template< class type >
 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 >
 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 >
 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 >
 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 >
 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 >
 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 >
 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 >
 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__ */