neo/idlib/containers/VectorSet.h

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 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 Doom 3 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 Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 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 Doom 3 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 __VECTORSET_H__
  30 #define __VECTORSET_H__
  31
  32 /*
  33 ===============================================================================
  34
  35         Vector Set
  36
  37         Creates a set of vectors without duplicates.
  38
  39 ===============================================================================
  40 */
  41
  42 template< class type, int dimension >
  43 class idVectorSet : public idList<type> {
  44 public:
  45                                                         idVectorSet( void );
  46                                                         idVectorSet( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );
  47
  48                                                         // returns total size of allocated memory
  49         size_t                                  Allocated( void ) const { return idList<type>::Allocated() + hash.Allocated(); }
  50                                                         // returns total size of allocated memory including size of type
  51         size_t                                  Size( void ) const { return sizeof( *this ) + Allocated(); }
  52
  53         void                                    Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );
  54         void                                    ResizeIndex( const int newSize );
  55         void                                    Clear( void );
  56
  57         int                                             FindVector( const type &v, const float epsilon );
  58
  59 private:
  60         idHashIndex                             hash;
  61         type                                    mins;
  62         type                                    maxs;
  63         int                                             boxHashSize;
  64         float                                   boxInvSize[dimension];
  65         float                                   boxHalfSize[dimension];
  66 };
  67
  68 template< class type, int dimension >
  69 ID_INLINE idVectorSet<type,dimension>::idVectorSet( void ) {
  70         hash.Clear( idMath::IPow( boxHashSize, dimension ), 128 );
  71         boxHashSize = 16;
  72         memset( boxInvSize, 0, dimension * sizeof( boxInvSize[0] ) );
  73         memset( boxHalfSize, 0, dimension * sizeof( boxHalfSize[0] ) );
  74 }
  75
  76 template< class type, int dimension >
  77 ID_INLINE idVectorSet<type,dimension>::idVectorSet( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
  78         Init( mins, maxs, boxHashSize, initialSize );
  79 }
  80
  81 template< class type, int dimension >
  82 ID_INLINE void idVectorSet<type,dimension>::Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
  83         int i;
  84         float boxSize;
  85
  86         idList<type>::AssureSize( initialSize );
  87         idList<type>::SetNum( 0, false );
  88
  89         hash.Clear( idMath::IPow( boxHashSize, dimension ), initialSize );
  90
  91         this->mins = mins;
  92         this->maxs = maxs;
  93         this->boxHashSize = boxHashSize;
  94
  95         for ( i = 0; i < dimension; i++ ) {
  96                 boxSize = ( maxs[i] - mins[i] ) / (float) boxHashSize;
  97                 boxInvSize[i] = 1.0f / boxSize;
  98                 boxHalfSize[i] = boxSize * 0.5f;
  99         }
 100 }
 101
 102 template< class type, int dimension >
 103 ID_INLINE void idVectorSet<type,dimension>::ResizeIndex( const int newSize ) {
 104         idList<type>::Resize( newSize );
 105         hash.ResizeIndex( newSize );
 106 }
 107
 108 template< class type, int dimension >
 109 ID_INLINE void idVectorSet<type,dimension>::Clear( void ) {
 110         idList<type>::Clear();
 111         hash.Clear();
 112 }
 113
 114 template< class type, int dimension >
 115 ID_INLINE int idVectorSet<type,dimension>::FindVector( const type &v, const float epsilon ) {
 116         int i, j, k, hashKey, partialHashKey[dimension];
 117
 118         for ( i = 0; i < dimension; i++ ) {
 119                 assert( epsilon <= boxHalfSize[i] );
 120                 partialHashKey[i] = (int) ( ( v[i] - mins[i] - boxHalfSize[i] ) * boxInvSize[i] );
 121         }
 122
 123         for ( i = 0; i < ( 1 << dimension ); i++ ) {
 124
 125                 hashKey = 0;
 126                 for ( j = 0; j < dimension; j++ ) {
 127                         hashKey *= boxHashSize;
 128                         hashKey += partialHashKey[j] + ( ( i >> j ) & 1 );
 129                 }
 130
 131                 for ( j = hash.First( hashKey ); j >= 0; j = hash.Next( j ) ) {
 132                         const type &lv = (*this)[j];
 133                         for ( k = 0; k < dimension; k++ ) {
 134                                 if ( idMath::Fabs( lv[k] - v[k] ) > epsilon ) {
 135                                         break;
 136                                 }
 137                         }
 138                         if ( k >= dimension ) {
 139                                 return j;
 140                         }
 141                 }
 142         }
 143
 144         hashKey = 0;
 145         for ( i = 0; i < dimension; i++ ) {
 146                 hashKey *= boxHashSize;
 147                 hashKey += (int) ( ( v[i] - mins[i] ) * boxInvSize[i] );
 148         }
 149
 150         hash.Add( hashKey, idList<type>::Num() );
 151         Append( v );
 152         return idList<type>::Num()-1;
 153 }
 154
 155
 156 /*
 157 ===============================================================================
 158
 159         Vector Subset
 160
 161         Creates a subset without duplicates from an existing list with vectors.
 162
 163 ===============================================================================
 164 */
 165
 166 template< class type, int dimension >
 167 class idVectorSubset {
 168 public:
 169                                                         idVectorSubset( void );
 170                                                         idVectorSubset( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );
 171
 172                                                         // returns total size of allocated memory
 173         size_t                                  Allocated( void ) const { return idList<type>::Allocated() + hash.Allocated(); }
 174                                                         // returns total size of allocated memory including size of type
 175         size_t                                  Size( void ) const { return sizeof( *this ) + Allocated(); }
 176
 177         void                                    Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize );
 178         void                                    Clear( void );
 179
 180                                                         // returns either vectorNum or an index to a previously found vector
 181         int                                             FindVector( const type *vectorList, const int vectorNum, const float epsilon );
 182
 183 private:
 184         idHashIndex                             hash;
 185         type                                    mins;
 186         type                                    maxs;
 187         int                                             boxHashSize;
 188         float                                   boxInvSize[dimension];
 189         float                                   boxHalfSize[dimension];
 190 };
 191
 192 template< class type, int dimension >
 193 ID_INLINE idVectorSubset<type,dimension>::idVectorSubset( void ) {
 194         hash.Clear( idMath::IPow( boxHashSize, dimension ), 128 );
 195         boxHashSize = 16;
 196         memset( boxInvSize, 0, dimension * sizeof( boxInvSize[0] ) );
 197         memset( boxHalfSize, 0, dimension * sizeof( boxHalfSize[0] ) );
 198 }
 199
 200 template< class type, int dimension >
 201 ID_INLINE idVectorSubset<type,dimension>::idVectorSubset( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
 202         Init( mins, maxs, boxHashSize, initialSize );
 203 }
 204
 205 template< class type, int dimension >
 206 ID_INLINE void idVectorSubset<type,dimension>::Init( const type &mins, const type &maxs, const int boxHashSize, const int initialSize ) {
 207         int i;
 208         float boxSize;
 209
 210         hash.Clear( idMath::IPow( boxHashSize, dimension ), initialSize );
 211
 212         this->mins = mins;
 213         this->maxs = maxs;
 214         this->boxHashSize = boxHashSize;
 215
 216         for ( i = 0; i < dimension; i++ ) {
 217                 boxSize = ( maxs[i] - mins[i] ) / (float) boxHashSize;
 218                 boxInvSize[i] = 1.0f / boxSize;
 219                 boxHalfSize[i] = boxSize * 0.5f;
 220         }
 221 }
 222
 223 template< class type, int dimension >
 224 ID_INLINE void idVectorSubset<type,dimension>::Clear( void ) {
 225         idList<type>::Clear();
 226         hash.Clear();
 227 }
 228
 229 template< class type, int dimension >
 230 ID_INLINE int idVectorSubset<type,dimension>::FindVector( const type *vectorList, const int vectorNum, const float epsilon ) {
 231         int i, j, k, hashKey, partialHashKey[dimension];
 232         const type &v = vectorList[vectorNum];
 233
 234         for ( i = 0; i < dimension; i++ ) {
 235                 assert( epsilon <= boxHalfSize[i] );
 236                 partialHashKey[i] = (int) ( ( v[i] - mins[i] - boxHalfSize[i] ) * boxInvSize[i] );
 237         }
 238
 239         for ( i = 0; i < ( 1 << dimension ); i++ ) {
 240
 241                 hashKey = 0;
 242                 for ( j = 0; j < dimension; j++ ) {
 243                         hashKey *= boxHashSize;
 244                         hashKey += partialHashKey[j] + ( ( i >> j ) & 1 );
 245                 }
 246
 247                 for ( j = hash.First( hashKey ); j >= 0; j = hash.Next( j ) ) {
 248                         const type &lv = vectorList[j];
 249                         for ( k = 0; k < dimension; k++ ) {
 250                                 if ( idMath::Fabs( lv[k] - v[k] ) > epsilon ) {
 251                                         break;
 252                                 }
 253                         }
 254                         if ( k >= dimension ) {
 255                                 return j;
 256                         }
 257                 }
 258         }
 259
 260         hashKey = 0;
 261         for ( i = 0; i < dimension; i++ ) {
 262                 hashKey *= boxHashSize;
 263                 hashKey += (int) ( ( v[i] - mins[i] ) * boxInvSize[i] );
 264         }
 265
 266         hash.Add( hashKey, vectorNum );
 267         return vectorNum;
 268 }
 269
 270 #endif /* !__VECTORSET_H__ */