00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef HashTable_H
00039 #define HashTable_H
00040
00041 #include "label.H"
00042 #include "word.H"
00043 #include "className.H"
00044
00045
00046
00047 namespace Foam
00048 {
00049
00050
00051
00052 template<class T>
00053 class List;
00054
00055 template<class T, class Key, class Hash> class HashTable;
00056
00057 template<class T, class Key, class Hash> Istream& operator>>
00058 (
00059 Istream&,
00060 HashTable<T, Key, Hash>&
00061 );
00062
00063 template<class T, class Key, class Hash> Ostream& operator<<
00064 (
00065 Ostream&,
00066 const HashTable<T, Key, Hash>&
00067 );
00068
00069
00070
00071
00072
00073
00074 TemplateName(HashTable);
00075
00076
00077
00078
00079
00080
00081 template<class T, class Key=word, class Hash=string::hash>
00082 class HashTable
00083 :
00084 public HashTableName
00085 {
00086
00087
00088 struct hashedEntry
00089 {
00090
00091 Key key_;
00092
00093
00094 hashedEntry* next_;
00095
00096
00097 T obj_;
00098
00099
00100
00101
00102 inline hashedEntry
00103 (
00104 const Key& key,
00105 hashedEntry* next,
00106 const T& newEntry
00107 );
00108
00109
00110 hashedEntry(const hashedEntry&);
00111 };
00112
00113
00114
00115
00116
00117 label tableSize_;
00118
00119
00120 hashedEntry** table_;
00121
00122
00123 label nElmts_;
00124
00125
00126 public:
00127
00128
00129 template<class T2, class Key2, class Hash2>
00130 friend class HashPtrTable;
00131
00132
00133
00134
00135 template<class TRef, class TableRef, class HashedEntryPtr>
00136 class Iterator;
00137
00138 typedef Iterator
00139 <
00140 T&,
00141 HashTable<T, Key, Hash>&,
00142 hashedEntry*
00143 > iterator;
00144
00145 typedef Iterator
00146 <
00147 const T&,
00148 const HashTable<T, Key, Hash>&,
00149 const hashedEntry*
00150 > const_iterator;
00151
00152
00153
00154
00155 friend class Iterator
00156 <
00157 T&,
00158 HashTable<T, Key, Hash>&,
00159 hashedEntry*
00160 >;
00161
00162 friend class Iterator
00163 <
00164 const T&,
00165 const HashTable<T, Key, Hash>&,
00166 const hashedEntry*
00167 >;
00168
00169
00170
00171
00172
00173 HashTable(const label size = 100);
00174
00175
00176 HashTable(Istream&, const label size = 100);
00177
00178
00179 HashTable(const HashTable<T, Key, Hash>&);
00180
00181
00182
00183
00184 ~HashTable();
00185
00186
00187
00188
00189
00190
00191
00192 inline label size() const;
00193
00194
00195 bool found(const Key& key) const;
00196
00197
00198
00199 iterator find(const Key& key);
00200
00201
00202
00203 const_iterator find(const Key& key) const;
00204
00205
00206 List<Key> toc() const;
00207
00208
00209
00210
00211
00212 bool insert(const Key& key, const T& newElmt);
00213
00214
00215 bool erase(const iterator& it);
00216
00217
00218 bool erase(const Key& key);
00219
00220
00221 void resize(const label newSize);
00222
00223
00224 void clear();
00225
00226
00227
00228 void transfer(HashTable<T, Key, Hash>&);
00229
00230
00231
00232
00233
00234 inline T& operator[](const Key& key);
00235
00236
00237 inline const T& operator[](const Key& key) const;
00238
00239
00240 void operator=(const HashTable<T, Key, Hash>&);
00241
00242
00243
00244
00245
00246 typedef T value_type;
00247
00248
00249
00250 typedef T& reference;
00251
00252
00253
00254
00255 typedef const T& const_reference;
00256
00257
00258 typedef label size_type;
00259
00260
00261
00262
00263 template<class TRef, class TableRef, class HashedEntryPtr>
00264 class Iterator
00265 {
00266 friend class HashTable;
00267
00268 # ifndef __INTEL_COMPILER
00269 template<class TRef2, class TableRef2, class HashedEntryPtr2>
00270 friend class Iterator;
00271 # endif
00272
00273
00274
00275
00276 TableRef curHashTable_;
00277
00278
00279 HashedEntryPtr elmtPtr_;
00280
00281
00282 HashedEntryPtr prevElmtPtr_;
00283
00284
00285 label hashIndex_;
00286
00287
00288 public:
00289
00290
00291
00292
00293 inline Iterator
00294 (
00295 TableRef curHashTable,
00296 HashedEntryPtr elmt,
00297 HashedEntryPtr prev,
00298 label hashIndex
00299 );
00300
00301
00302 inline Iterator(const iterator&);
00303
00304
00305
00306
00307 inline void operator=(const iterator& iter);
00308
00309 inline bool operator==(const iterator& iter) const;
00310 inline bool operator==(const const_iterator& iter) const;
00311
00312 inline bool operator!=(const iterator& iter) const;
00313 inline bool operator!=(const const_iterator& iter) const;
00314
00315 inline TRef operator*();
00316 inline TRef operator()();
00317
00318 inline Iterator& operator++();
00319 inline Iterator operator++(int);
00320
00321 inline const Key& key();
00322 };
00323
00324
00325
00326 inline iterator begin();
00327
00328
00329 inline const iterator& end();
00330
00331
00332 inline const_iterator begin() const;
00333
00334
00335 inline const const_iterator& end() const;
00336
00337
00338
00339
00340 friend Istream& operator>> <T, Key, Hash>
00341 (
00342 Istream&,
00343 HashTable<T, Key, Hash>&
00344 );
00345
00346 friend Ostream& operator<< <T, Key, Hash>
00347 (
00348 Ostream&,
00349 const HashTable<T, Key, Hash>&
00350 );
00351
00352
00353 private:
00354
00355
00356 iterator endIter_;
00357
00358
00359 const_iterator endConstIter_;
00360 };
00361
00362
00363
00364
00365 }
00366
00367
00368
00369 # include "HashTableI.H"
00370
00371
00372
00373 #ifndef NoHashTableC
00374 #ifdef NoRepository
00375 # include "HashTable.C"
00376 #endif
00377 #endif
00378
00379
00380
00381 #endif
00382
00383