OpenFOAM logo
Open Source CFD Toolkit

StaticHashTable.H

Go to the documentation of this file.
00001 /*---------------------------------------------------------------------------*\
00002   =========                 |
00003   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
00004    \\    /   O peration     |
00005     \\  /    A nd           | Copyright (C) 1991-2005 OpenCFD Ltd.
00006      \\/     M anipulation  |
00007 -------------------------------------------------------------------------------
00008 License
00009     This file is part of OpenFOAM.
00010 
00011     OpenFOAM is free software; you can redistribute it and/or modify it
00012     under the terms of the GNU General Public License as published by the
00013     Free Software Foundation; either version 2 of the License, or (at your
00014     option) any later version.
00015 
00016     OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
00017     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00018     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
00019     for more details.
00020 
00021     You should have received a copy of the GNU General Public License
00022     along with OpenFOAM; if not, write to the Free Software Foundation,
00023     Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
00024 
00025 Class
00026     StaticHashTable
00027 
00028 Description
00029     STL conforming hash table. Uses straight lists as underlying type.
00030     Is slower to insert but should be more memory efficient and faster to
00031     access.
00032     Explicitly does not have default size.
00033 
00034 SourceFiles
00035     StaticHashTableI.H
00036     StaticHashTable.C
00037     StaticHashTableIO.C
00038 
00039 \*---------------------------------------------------------------------------*/
00040 
00041 #ifndef StaticHashTable_H
00042 #define StaticHashTable_H
00043 
00044 #include "label.H"
00045 #include "word.H"
00046 #include "className.H"
00047 
00048 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00049 
00050 namespace Foam
00051 {
00052 
00053 // * * * * * * Forward declaration of template friend fuctions * * * * * * * //
00054 
00055 template<class T>
00056 class List;
00057 
00058 template<class T, class Key, class Hash> class StaticHashTable;
00059 
00060 template<class T, class Key, class Hash> Istream& operator>>
00061 (
00062     Istream&,
00063     StaticHashTable<T, Key, Hash>&
00064 );
00065 
00066 template<class T, class Key, class Hash> Ostream& operator<<
00067 (
00068     Ostream&,
00069     const StaticHashTable<T, Key, Hash>&
00070 );
00071 
00072 
00073 /*---------------------------------------------------------------------------*\
00074                         Class StaticHashTableName Declaration
00075 \*---------------------------------------------------------------------------*/
00076 
00077 TemplateName(StaticHashTable);
00078 
00079 
00080 /*---------------------------------------------------------------------------*\
00081                           Class StaticHashTable Declaration
00082 \*---------------------------------------------------------------------------*/
00083 
00084 template<class T, class Key=word, class Hash=string::hash>
00085 class StaticHashTable
00086 :
00087     public StaticHashTableName
00088 {
00089     // Private data type for table entries
00090 
00091         //- The lookup keys, ordered per hash value
00092         List<List<Key> > keys_;
00093 
00094         //- For each key the corresponding object.
00095         List<List<T> > objects_;
00096 
00097         //- The current number of elements in table
00098         label nElmts_;
00099 
00100 public:
00101 
00102 
00103     // Forward declaration of STL iterators
00104 
00105         template<class TRef, class TableRef>
00106         class Iterator;
00107 
00108         typedef Iterator
00109         <
00110             T&,
00111             StaticHashTable<T, Key, Hash>&
00112         > iterator;
00113 
00114         typedef Iterator
00115         <
00116             const T&,
00117             const StaticHashTable<T, Key, Hash>&
00118         > const_iterator;
00119 
00120 
00121     // Declare friendship with the iterators
00122 
00123         friend class Iterator
00124         <
00125             T&,
00126             StaticHashTable<T, Key, Hash>&
00127         >;
00128 
00129         friend class Iterator
00130         <
00131             const T&,
00132             const StaticHashTable<T, Key, Hash>&
00133         >;
00134 
00135 
00136     // Constructors
00137 
00138         //- Construct given initial table size
00139         StaticHashTable(const label size);
00140 
00141         //- Construct from Istream
00142         StaticHashTable(Istream&, const label size);
00143 
00144         //- Construct as copy
00145         StaticHashTable(const StaticHashTable<T, Key, Hash>&);
00146 
00147 
00148     // Destructor
00149 
00150         ~StaticHashTable();
00151 
00152 
00153     // Member Functions
00154 
00155         // Access
00156 
00157             //- Return number of elements in table.
00158             inline label size() const;
00159 
00160             //- Return true if hashedEntry is found in table
00161             bool found(const Key& key) const;
00162 
00163             //- Find and return an iterator set at the hashedEntry
00164             //  If not found iterator = end()
00165             iterator find(const Key& key);
00166 
00167             //- Find and return an const_iterator set at the hashedEntry
00168             //  If not found iterator = end()
00169             const_iterator find(const Key& key) const;
00170 
00171             //- Return the table of contents
00172             List<Key> toc() const;
00173 
00174 
00175         // Edit
00176 
00177             //- Insert a new hashedEntry
00178             bool insert(const Key& key, const T& newElmt);
00179 
00180             //- Erase an hashedEntry specified by given iterator
00181             bool erase(const iterator& it);
00182 
00183             //- Erase an hashedEntry specified by given key if in table
00184             bool erase(const Key& key);
00185 
00186             //- Resize the hash table for efficiency
00187             void resize(const label newSize);
00188 
00189             //- Clear all entries from table
00190             void clear();
00191 
00192             //- Transfer the contents of the argument table into this table
00193             //  and annull the argument table.
00194             void transfer(StaticHashTable<T, Key, Hash>&);
00195 
00196 
00197     // Member Operators
00198 
00199         //- Find and return an hashedEntry
00200         inline T& operator[](const Key& key);
00201 
00202         //- Find and return an hashedEntry
00203         inline const T& operator[](const Key& key) const;
00204 
00205         //- Assignment
00206         void operator=(const StaticHashTable<T, Key, Hash>&);
00207 
00208 
00209     // STL type definitions
00210 
00211         //- Type of values the StaticHashTable contains.
00212         typedef T value_type;
00213 
00214         //- Type that can be used for storing into StaticHashTable::value_type
00215         //  objects.  This type is usually List::value_type&.
00216         typedef T& reference;
00217 
00218         //- Type that can be used for storing into constant
00219         //  StaticHashTable::value_type objects.  This type is usually const
00220         //  StaticHashTable::value_type&.
00221         typedef const T& const_reference;
00222 
00223         //- The type that can represent the size of a StaticHashTable.
00224         typedef label size_type;
00225 
00226 
00227     // STL iterator
00228 
00229         template<class TRef, class TableRef>
00230         class Iterator
00231         {
00232             friend class StaticHashTable;
00233 
00234 #           ifndef __INTEL_COMPILER
00235             template<class TRef2, class TableRef2>
00236             friend class Iterator;
00237 #           endif
00238 
00239             // Private data
00240 
00241                 //- Reference to the StaticHashTable this is an iterator for
00242                 TableRef curStaticHashTable_;
00243 
00244                 //- Current hash index
00245                 label hashIndex_;
00246 
00247                 //- Index of current element at hashIndex
00248                 label elementIndex_;
00249 
00250         public:
00251 
00252             // Constructors
00253 
00254                 //- Construct from hash table, element and hash index
00255                 inline Iterator
00256                 (
00257                     TableRef curStaticHashTable,
00258                     label hashIndex_,
00259                     label elementIndex_
00260                 );
00261 
00262                 //- Construct from the non-const iterator
00263                 inline Iterator(const iterator&);
00264 
00265 
00266             // Member operators
00267 
00268                 inline void operator=(const iterator& iter);
00269 
00270                 inline bool operator==(const iterator& iter) const;
00271                 inline bool operator==(const const_iterator& iter) const;
00272 
00273                 inline bool operator!=(const iterator& iter) const;
00274                 inline bool operator!=(const const_iterator& iter) const;
00275 
00276                 inline TRef operator*();
00277                 inline TRef operator()();
00278 
00279                 inline Iterator& operator++();
00280                 inline Iterator operator++(int);
00281 
00282                 inline const Key& key();
00283         };
00284 
00285 
00286         //- iterator set to the begining of the StaticHashTable
00287         inline iterator begin();
00288 
00289         //- iterator set to beyond the end of the StaticHashTable
00290         inline const iterator& end();
00291 
00292         //- const_iterator set to the begining of the StaticHashTable
00293         inline const_iterator begin() const;
00294 
00295         //- const_iterator set to beyond the end of the StaticHashTable
00296         inline const const_iterator& end() const;
00297 
00298 
00299     // IOstream Operator
00300 
00301         friend Istream& operator>> <T, Key, Hash>
00302         (
00303             Istream&,
00304             StaticHashTable<T, Key, Hash>&
00305         );
00306 
00307         friend Ostream& operator<< <T, Key, Hash>
00308         (
00309             Ostream&,
00310             const StaticHashTable<T, Key, Hash>&
00311         );
00312 
00313 
00314 private:
00315 
00316         //- iterator returned by end()
00317         iterator endIter_;
00318 
00319         //- const_iterator returned by end()
00320         const_iterator endConstIter_;
00321 };
00322 
00323 
00324 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00325 
00326 } // End namespace Foam
00327 
00328 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00329 
00330 #   include "StaticHashTableI.H"
00331 
00332 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00333 
00334 #ifndef NoStaticHashTableC
00335 #ifdef NoRepository
00336 #   include "StaticHashTable.C"
00337 #endif
00338 #endif
00339 
00340 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
00341 
00342 #endif
00343 
00344 // ************************************************************************* //
For further information go to www.openfoam.org