1 // Created on: 1993-01-08
2 // Created by: Remi LEQUETTE
3 // Copyright (c) 1993-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 #include <Standard_DomainError.hxx>
18 #include <Standard_MultiplyDefined.hxx>
19 #include <Standard_NoSuchObject.hxx>
20 #include <Standard_OutOfRange.hxx>
21 #include <TCollection_BasicMapIterator.hxx>
24 //=======================================================================
25 //function : TCollection_IndexedMap
27 //=======================================================================
29 TCollection_IndexedMap::TCollection_IndexedMap
30 (const Standard_Integer NbBuckets):
31 TCollection_BasicMap(NbBuckets,Standard_False)
35 //=======================================================================
36 //function : TCollection_IndexedMap
38 //=======================================================================
40 TCollection_IndexedMap::TCollection_IndexedMap
41 (const TCollection_IndexedMap& Other) :
42 TCollection_BasicMap(Other.NbBuckets(),Standard_False)
44 if (!Other.IsEmpty()) {
45 ReSize(Other.Extent());
46 for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
52 //=======================================================================
55 //=======================================================================
57 TCollection_IndexedMap& TCollection_IndexedMap::Assign
58 (const TCollection_IndexedMap& Other)
60 // very simple implementation
61 // not optimal (recompute the hashcode values)
63 if (this == &Other) return *this;
65 // ReSize(Other.NbBuckets());
66 if (!Other.IsEmpty()) {
67 ReSize(Other.Extent());
68 for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
75 //=======================================================================
78 //=======================================================================
80 void TCollection_IndexedMap::ReSize(const Standard_Integer N)
82 Standard_Integer newBuck;
83 Standard_Address newData1, newData2;
84 if (BeginResize(N,newBuck,newData1,newData2)) {
86 TCollection_IndexedMapNode** newdata1 = (TCollection_IndexedMapNode**)newData1;
87 TCollection_IndexedMapNode** newdata2 = (TCollection_IndexedMapNode**)newData2;
88 TCollection_IndexedMapNode** olddata1 = (TCollection_IndexedMapNode**) myData1;
89 TCollection_IndexedMapNode *p, *q;
90 Standard_Integer i,k1,k2;
91 for (i = 0; i <= NbBuckets(); i++) {
95 k1 = Hasher::HashCode(p->Key1(),newBuck);
96 q = (TCollection_IndexedMapNode*) p->Next();
97 p->Next() = newdata1[k1];
100 k2 = ::HashCode(p->Key2(),newBuck);
101 p->Next2() = newdata2[k2];
109 EndResize(N,newBuck,newData1,newData2);
113 //=======================================================================
116 //=======================================================================
118 void TCollection_IndexedMap::Clear()
122 TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**) myData1;
123 // TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**) myData2;
124 TCollection_IndexedMapNode *p,*q;
125 for (i = 0; i <= NbBuckets(); i++) {
128 q = (TCollection_IndexedMapNode*) p->Next();
134 TCollection_BasicMap::Destroy();
137 //=======================================================================
140 //=======================================================================
142 Standard_Integer TCollection_IndexedMap::Add(const TheKey& K1)
144 if (Resizable()) ReSize(Extent());
145 TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
146 Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
147 TCollection_IndexedMapNode* p;
150 if (Hasher::IsEqual(p->Key1(),K1))
152 p = (TCollection_IndexedMapNode*) p->Next();
155 TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
156 Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
157 p = new TCollection_IndexedMapNode(K1,Extent(),data1[k1],data2[k2]);
163 //=======================================================================
164 //function : Substitute
166 //=======================================================================
168 void TCollection_IndexedMap::Substitute(const Standard_Integer I,
171 Standard_OutOfRange_Raise_if(I < 1 || I > Extent(), "IndexedMap::Substitute : "
172 "Index is out of range");
173 TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
174 TCollection_IndexedMapNode* p;
176 // check if K1 is not already in the map
177 Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
180 if (Hasher::IsEqual(p->Key1(),K1)) {
182 throw Standard_DomainError("IndexedMap::Substitute : "
183 "Attempt to substitute existing key");
187 p = (TCollection_IndexedMapNode*) p->Next();
190 // Find the node for the index I
191 TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
192 Standard_Integer k2 = ::HashCode(I,NbBuckets());
197 p = (TCollection_IndexedMapNode*) p->Next2();
200 // remove the old key
201 Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
202 TCollection_IndexedMapNode* q = data1[k];
203 if (q == p) data1[k] = (TCollection_IndexedMapNode*) p->Next();
205 while(q->Next() != p) q = (TCollection_IndexedMapNode*) q->Next();
206 q->Next() = p->Next();
211 p->Next() = data1[k1];
215 //=======================================================================
216 //function : RemoveLast
218 //=======================================================================
220 void TCollection_IndexedMap::RemoveLast()
222 Standard_OutOfRange_Raise_if(Extent() == 0,
223 "IndexedMap::RemoveLast");
224 TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
225 TCollection_IndexedMapNode* p;
226 TCollection_IndexedMapNode* q;
228 // Find the node for the last index and remove it
229 TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
230 Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
234 if (p->Key2() == Extent())
237 p = (TCollection_IndexedMapNode*) p->Next2();
240 data2[k2] = (TCollection_IndexedMapNode*)p->Next2();
242 q->Next2() = p->Next2();
245 Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
247 if (q == p) data1[k] = (TCollection_IndexedMapNode*) p->Next();
249 while(q->Next() != p) q = (TCollection_IndexedMapNode*) q->Next();
250 q->Next() = p->Next();
257 //=======================================================================
258 //function : Contains
260 //=======================================================================
262 Standard_Boolean TCollection_IndexedMap::Contains(const TheKey& K1) const
264 if (IsEmpty()) return Standard_False;
265 TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
266 Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
267 TCollection_IndexedMapNode *p1;
270 if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
271 p1 = (TCollection_IndexedMapNode*) p1->Next();
273 return Standard_False;
276 //=======================================================================
279 //=======================================================================
281 const TheKey& TCollection_IndexedMap::FindKey(const Standard_Integer K2) const
283 Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedMap");
284 TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
285 Standard_Integer k2 = ::HashCode(K2,NbBuckets());
286 TCollection_IndexedMapNode *p2;
289 if (p2->Key2() == K2) return p2->Key1();
290 p2 = (TCollection_IndexedMapNode*)p2->Next2();
292 throw Standard_OutOfRange("IndexedMap : missing index !!!");
296 //=======================================================================
297 //function : FindIndex
299 //=======================================================================
301 Standard_Integer TCollection_IndexedMap::FindIndex(const TheKey& K1) const
303 if (IsEmpty()) return 0;
304 TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
305 Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
306 TCollection_IndexedMapNode *p1;
309 if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
310 p1 = (TCollection_IndexedMapNode*) p1->Next();