42cf5bc1 |
1 | // Created on: 1993-02-26 |
2 | // Created by: Remi LEQUETTE |
3 | // Copyright (c) 1993-1999 Matra Datavision |
4 | // Copyright (c) 1999-2014 OPEN CASCADE SAS |
5 | // |
6 | // This file is part of Open CASCADE Technology software library. |
7 | // |
8 | // This library is free software; you can redistribute it and/or modify it under |
9 | // the terms of the GNU Lesser General Public License version 2.1 as published |
10 | // by the Free Software Foundation, with special exception defined in the file |
11 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
12 | // distribution for complete text of the license and disclaimer of any warranty. |
13 | // |
14 | // Alternatively, this file may be used under the terms of Open CASCADE |
15 | // commercial license or contractual agreement. |
16 | |
17 | #ifndef _TCollection_BasicMap_HeaderFile |
18 | #define _TCollection_BasicMap_HeaderFile |
19 | |
20 | #include <Standard.hxx> |
21 | #include <Standard_DefineAlloc.hxx> |
22 | #include <Standard_Handle.hxx> |
23 | |
24 | #include <Standard_Boolean.hxx> |
25 | #include <Standard_Integer.hxx> |
26 | #include <Standard_Address.hxx> |
27 | #include <Standard_OStream.hxx> |
28 | class TCollection_BasicMapIterator; |
29 | |
30 | |
31 | //! Root class of all the maps, provides utilitites |
32 | //! for managing the buckets. |
33 | //! Maps are dynamically extended data structures where |
34 | //! data is quickly accessed with a key. |
35 | //! General properties of maps |
36 | //! - Map items may be (complex) non-unitary data; they |
37 | //! may be difficult to manage with an array. Moreover, the |
38 | //! map allows a data structure to be indexed by complex data. |
39 | //! - The size of a map is dynamically extended. So a map |
40 | //! may be first dimensioned for a little number of items. |
41 | //! Maps avoid the use of large and quasi-empty arrays. |
42 | //! - The access to a map item is much faster than the one |
43 | //! to a sequence, a list, a queue or a stack item. |
44 | //! - The access time to a map item may be compared with |
45 | //! the one to an array item. First of all, it depends on the |
46 | //! size of the map. It also depends on the quality of a user |
47 | //! redefinable function (the hashing function) to find |
48 | //! quickly where the item is. |
49 | //! - The exploration of a map may be of better performance |
50 | //! than the exploration of an array because the size of the |
51 | //! map is adapted to the number of inserted items. |
52 | //! These properties explain why maps are commonly used as |
53 | //! internal data structures for algorithms. |
54 | //! Definitions |
55 | //! - A map is a data structure for which data is addressed by keys. |
56 | //! - Once inserted in the map, a map item is referenced as an entry of the map. |
57 | //! - Each entry of the map is addressed by a key. Two |
58 | //! different keys address two different entries of the map. |
59 | //! - The position of an entry in the map is called a bucket. |
60 | //! - A map is dimensioned by its number of buckets, i.e. the |
61 | //! maximum number of entries in the map. The |
62 | //! performance of a map is conditioned by the number of buckets. |
63 | //! - The hashing function transforms a key into a bucket |
64 | //! index. The number of values that can be computed by |
65 | //! the hashing function is equal to the number of buckets of the map. |
66 | //! - Both the hashing function and the equality test |
67 | //! between two keys are provided by a hasher object. |
68 | //! - A map may be explored by a map iterator. This |
69 | //! exploration provides only inserted entries in the map |
70 | //! (i.e. non empty buckets). |
71 | //! Collections' generic maps |
72 | //! The Collections component provides numerous generic derived maps. |
73 | //! - These maps include automatic management of the |
74 | //! number of buckets: they are automatically resized when |
75 | //! the number of keys exceeds the number of buckets. If |
76 | //! you have a fair idea of the number of items in your map, |
77 | //! you can save on automatic resizing by specifying a |
78 | //! number of buckets at the time of construction, or by using |
79 | //! a resizing function. This may be considered for crucial optimization issues. |
80 | //! - Keys, items and hashers are parameters of these generic derived maps. |
81 | //! - TCollection_MapHasher class describes the |
82 | //! functions required by any hasher which is to be used |
83 | //! with a map instantiated from the Collections component. |
84 | //! - An iterator class is automatically instantiated at the |
85 | //! time of instantiation of a map provided by the |
86 | //! Collections component if this map is to be explored |
87 | //! with an iterator. Note that some provided generic maps |
88 | //! are not to be explored with an iterator but with indexes (indexed maps). |
89 | class TCollection_BasicMap |
90 | { |
91 | public: |
92 | |
93 | DEFINE_STANDARD_ALLOC |
94 | |
95 | |
96 | //! Returns the number of buckets in <me>. |
97 | Standard_Integer NbBuckets() const; |
98 | |
99 | //! Returns the number of keys already stored in <me>. |
100 | Standard_Integer Extent() const; |
101 | |
102 | //! Returns True when the map contains no keys. |
103 | //! This is exactly Extent() == 0. |
104 | Standard_Boolean IsEmpty() const; |
105 | |
106 | //! Prints on <S> usefull statistics about the map |
107 | //! <me>. It can be used to test the quality of the hashcoding. |
108 | Standard_EXPORT void Statistics (Standard_OStream& S) const; |
109 | |
110 | |
111 | friend class TCollection_BasicMapIterator; |
112 | |
113 | |
114 | protected: |
115 | |
116 | |
117 | //! Initialize the map. Single is True when the map |
118 | //! uses only one table of buckets. |
119 | //! |
120 | //! One table : Map, DataMap |
121 | //! Two tables : DoubleMap, IndexedMap, IndexedDataMap |
122 | Standard_EXPORT TCollection_BasicMap(const Standard_Integer NbBuckets, const Standard_Boolean single); |
123 | |
124 | //! Tries to resize the Map with NbBuckets. Returns |
125 | //! True if possible, NewBuckts is the new nuber of |
126 | //! buckets. data1 and data2 are the new tables of |
127 | //! buckets where the data must be copied. |
128 | Standard_EXPORT Standard_Boolean BeginResize (const Standard_Integer NbBuckets, Standard_Integer& NewBuckets, Standard_Address& data1, Standard_Address& data2) const; |
129 | |
130 | //! If BeginResize was succesfull after copying the |
131 | //! data to data1 and data2 this methods update the |
132 | //! tables and destroys the old ones. |
133 | Standard_EXPORT void EndResize (const Standard_Integer NbBuckets, const Standard_Integer NewBuckets, const Standard_Address data1, const Standard_Address data2); |
134 | |
135 | //! Returns True if resizing the map should be |
136 | //! considered. |
137 | Standard_Boolean Resizable() const; |
138 | |
139 | //! Decrement the extent of the map. |
140 | void Increment(); |
141 | |
142 | //! Decrement the extent of the map. |
143 | void Decrement(); |
144 | |
145 | //! Destroys the buckets. |
146 | Standard_EXPORT void Destroy(); |
147 | |
148 | |
149 | Standard_Address myData1; |
150 | Standard_Address myData2; |
151 | |
152 | |
153 | private: |
154 | |
155 | |
156 | |
157 | Standard_Boolean isDouble; |
158 | Standard_Boolean mySaturated; |
159 | Standard_Integer myNbBuckets; |
160 | Standard_Integer mySize; |
161 | |
162 | |
163 | }; |
164 | |
165 | |
166 | #include <TCollection_BasicMap.lxx> |
167 | |
168 | |
169 | |
170 | |
171 | |
172 | #endif // _TCollection_BasicMap_HeaderFile |