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