[occt.git] / src / TCollection / TCollection_IndexedDataMap.gxx

// Created on: 1993-01-08
// Created by: Remi LEQUETTE
// Copyright (c) 1993-1999 Matra Datavision
// Copyright (c) 1999-2014 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#include <Standard_DomainError.hxx>
#include <Standard_MultiplyDefined.hxx>
#include <Standard_NoSuchObject.hxx>
#include <Standard_OutOfRange.hxx>
#include <TCollection_BasicMapIterator.hxx>

//=======================================================================
//function : TCollection_IndexedDataMap
//purpose  : 
//=======================================================================

TCollection_IndexedDataMap::TCollection_IndexedDataMap
  (const Standard_Integer NbBuckets):
  TCollection_BasicMap(NbBuckets,Standard_False)
{
}

//=======================================================================
//function : TCollection_IndexedDataMap
//purpose  : 
//=======================================================================

TCollection_IndexedDataMap::TCollection_IndexedDataMap
  (const TCollection_IndexedDataMap& Other) :
  TCollection_BasicMap(Other.NbBuckets(),Standard_False)
{
  if (Other.Extent() != 0)
    throw Standard_DomainError("TCollection:Copy of non empty IndexedDataMap");
}

//=======================================================================
//function : Assign
//purpose  : 
//=======================================================================

TCollection_IndexedDataMap& TCollection_IndexedDataMap::Assign
  (const TCollection_IndexedDataMap& Other)
{
  // very simple implementation
  // not optimal (recompute the hashcode values)

  if (this == &Other) return *this;
  Clear();
//  ReSize(Other.NbBuckets());
  if  (!Other.IsEmpty()) { 
    ReSize(Other.Extent());
    for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
      Add(Other.FindKey(i),Other(i));
    }
  }
  return *this;
}


//=======================================================================
//function : ReSize
//purpose  : 
//=======================================================================

void TCollection_IndexedDataMap::ReSize(const Standard_Integer N)
{
  Standard_Integer newBuck;
  Standard_Address newData1=NULL, newData2=NULL;
  if (BeginResize(N,newBuck,newData1,newData2)) {
    if (myData1) {
      TCollection_IndexedDataMapNode** newdata1 = (TCollection_IndexedDataMapNode**)newData1;
      TCollection_IndexedDataMapNode** newdata2 = (TCollection_IndexedDataMapNode**)newData2;
      TCollection_IndexedDataMapNode** olddata1 = (TCollection_IndexedDataMapNode**) myData1;
      TCollection_IndexedDataMapNode *p, *q;
      Standard_Integer i,k1,k2;
      for (i = 0; i <= NbBuckets(); i++) {
	if (olddata1[i]) {
	  p = olddata1[i];
	  while (p) {
	    k1 = Hasher::HashCode(p->Key1(),newBuck);
	    k2 = ::HashCode(p->Key2(),newBuck);
	    q = (TCollection_IndexedDataMapNode*)p->Next();
	    p->Next() = newdata1[k1];
	    p->Next2() = newdata2[k2];
	    newdata1[k1] = p;
	    newdata2[k2] = p;
	    p = q;
	  }
	}
      }
    }
    EndResize(N,newBuck,newData1,newData2);
  }
}

//=======================================================================
//function : Clear
//purpose  : 
//=======================================================================

void TCollection_IndexedDataMap::Clear()
{
  if (!IsEmpty()) {
    Standard_Integer i;
    TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**) myData1;
    TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**) myData2;
    TCollection_IndexedDataMapNode *p,*q;
    for (i = 0; i <= NbBuckets(); i++) {
      p = data1[i];
      while (p) {
	q = (TCollection_IndexedDataMapNode*) p->Next();
	delete p;
	p = q;
      }
      data1[i] = data2[i] = NULL;
    }
  }
  TCollection_BasicMap::Destroy();
}

//=======================================================================
//function : Add
//purpose  : 
//=======================================================================

Standard_Integer TCollection_IndexedDataMap::Add(const TheKey& K1, const TheItem& I)
{
  if (Resizable())  ReSize(Extent());
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  TCollection_IndexedDataMapNode* p;
  p = data1[k1];
  while (p) {
    if (Hasher::IsEqual(p->Key1(),K1)) 
      return p->Key2();
    p = (TCollection_IndexedDataMapNode*) p->Next();
  }
  Increment();
  TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
  Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
  p = new TCollection_IndexedDataMapNode(K1,Extent(),I,data1[k1],data2[k2]);
  data1[k1] = p;
  data2[k2] = p;
  return Extent();
}


//=======================================================================
//function : Substitute
//purpose  : 
//=======================================================================

void TCollection_IndexedDataMap::Substitute(const Standard_Integer I,
                                            const TheKey& K1,
                                            const TheItem& T)
{
  Standard_OutOfRange_Raise_if(I < 1 || I > Extent(), "IndexedDataMap::Substitute : "
                                                      "Index is out of range");
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  TCollection_IndexedDataMapNode* p;

  // check if K1 is not already in the map
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  p = data1[k1];
  while (p) {
    if (Hasher::IsEqual(p->Key1(),K1)) {
      if (p->Key2() != I)
        throw Standard_DomainError("IndexedDataMap::Substitute : "
                                   "Attempt to substitute existing key");
      p->Key1() = K1;
      p->Value() = T;
      return;
    }
    p = (TCollection_IndexedDataMapNode*) p->Next();
  }

  // Find the node for the index I
  TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
  Standard_Integer k2 = ::HashCode(I,NbBuckets());
  p = data2[k2];
  while (p) {
    if (p->Key2() == I)
      break;
    p = (TCollection_IndexedDataMapNode*) p->Next2();
  }

  // remove the old key
  Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
  TCollection_IndexedDataMapNode* q = data1[k];
  if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
  else {
    while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
    q->Next() = p->Next();
  }

  // update the node
  p->Key1() = K1;
  p->Value() = T;
  p->Next() = data1[k1];
  data1[k1] = p;
}

//=======================================================================
//function : RemoveLast
//purpose  : 
//=======================================================================

void TCollection_IndexedDataMap::RemoveLast()
{
  Standard_OutOfRange_Raise_if(Extent() == 0,
			       "IndexedMap::RemoveLast");
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  TCollection_IndexedDataMapNode* p;
  TCollection_IndexedDataMapNode* q;

  // Find the node for the last index and remove it
  TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
  Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
  p = data2[k2];
  q = NULL;
  while (p) {
    if (p->Key2() == Extent())
      break;
    q = p;
    p = (TCollection_IndexedDataMapNode*) p->Next2();
  }
  if (q == NULL) 
    data2[k2] = (TCollection_IndexedDataMapNode*)p->Next2();
  else 
    q->Next2() = p->Next2();

  // remove the key
  Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
  q = data1[k];
  if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
  else {
    while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
    q->Next() = p->Next();
  }

  Decrement();
  delete p;
}


//=======================================================================
//function : FindKey
//purpose  : 
//=======================================================================

const TheKey& TCollection_IndexedDataMap::FindKey(const Standard_Integer K2) const
{
  Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
  TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
  Standard_Integer k2 = ::HashCode(K2,NbBuckets());
  TCollection_IndexedDataMapNode *p2;
  p2 = data2[k2];
  while (p2) {
    if (p2->Key2() == K2) return p2->Key1();
    p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
  }
  throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
  return p2->Key1();
}

//=======================================================================
//function : FindFromIndex
//purpose  : 
//=======================================================================

const TheItem& TCollection_IndexedDataMap::FindFromIndex
  (const Standard_Integer K2) const
{
  Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
  TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
  Standard_Integer k2 = ::HashCode(K2,NbBuckets());
  TCollection_IndexedDataMapNode *p2;
  p2 = data2[k2];
  while (p2) {
    if (p2->Key2() == K2) return p2->Value();
    p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
  }
  throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
  return p2->Value();
}

//=======================================================================
//function : ChangeFromIndex
//purpose  : 
//=======================================================================

TheItem& TCollection_IndexedDataMap::ChangeFromIndex(const Standard_Integer K2)
{
  Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
  TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
  Standard_Integer k2 = ::HashCode(K2,NbBuckets());
  TCollection_IndexedDataMapNode *p2;
  p2 = data2[k2];
  while (p2) {
    if (p2->Key2() == K2) return p2->Value();
    p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
  }
  throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
  return p2->Value();
}

//=======================================================================
//function : FindIndex
//purpose  : 
//=======================================================================

Standard_Integer TCollection_IndexedDataMap::FindIndex(const TheKey& K1) const
{
  if (IsEmpty()) return 0;
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  TCollection_IndexedDataMapNode *p1;
  p1 = data1[k1];
  while (p1) {
    if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
    p1 = (TCollection_IndexedDataMapNode*)p1->Next();
  }
  return 0;
}
//=======================================================================
//function : Contains
//purpose  : 
//=======================================================================
Standard_Boolean TCollection_IndexedDataMap::Contains(const TheKey& K1) const
{
  if (IsEmpty()) return Standard_False;
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  TCollection_IndexedDataMapNode *p1;
  p1 = data1[k1];
  while (p1) {
    if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
    p1 = (TCollection_IndexedDataMapNode*) p1->Next();
  }
  return Standard_False;
}
//=======================================================================
//function : FindFromKey
//purpose  : 
//=======================================================================
const TheItem& TCollection_IndexedDataMap::FindFromKey(const TheKey& K1) const
{
  Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::FindFromKey");  
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  TCollection_IndexedDataMapNode *p1;
  p1 = data1[k1];
  while (p1) {
    if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
    p1 = (TCollection_IndexedDataMapNode*) p1->Next();
  }
  throw Standard_OutOfRange("TCollection_IndexedDataMap::FindFromKey");
  return p1->Value();
}
//=======================================================================
//function : ChangeFromKey
//purpose  : 
//=======================================================================
TheItem& TCollection_IndexedDataMap::ChangeFromKey(const TheKey& K1)
{
  Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::ChangeFromKey");  
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  TCollection_IndexedDataMapNode *p1;
  p1 = data1[k1];
  while (p1) {
    if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
    p1 = (TCollection_IndexedDataMapNode*)p1->Next();
  }
  throw Standard_OutOfRange("TCollection_IndexedDataMap::ChangeFromKey");
  return p1->Value();
}
//modified by NIZNHY-PKV Tue Jul 05 08:37:03 2011f
//=======================================================================
//function : FindFromKey1
//purpose  : 
//=======================================================================
Standard_Address TCollection_IndexedDataMap::FindFromKey1(const TheKey& K1) const
{
  TCollection_IndexedDataMap *pMap=(TCollection_IndexedDataMap *)this;
  return pMap->ChangeFromKey1(K1);
}
//=======================================================================
//function : ChangeFromKey1
//purpose  : 
//=======================================================================
Standard_Address TCollection_IndexedDataMap::ChangeFromKey1(const TheKey& K1)
{
  if (IsEmpty()) {
    return NULL;
  }
  TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
  Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
  TCollection_IndexedDataMapNode *p1;
  p1 = data1[k1];
  while (p1) {
    if (Hasher::IsEqual(p1->Key1(),K1)) {
      return (Standard_Address)&p1->Value();
    }
    p1 = (TCollection_IndexedDataMapNode*) p1->Next();
  }
  return NULL;
}
Commit	Line	Data
b311480e	1	// Created on: 1993-01-08
	2	// Created by: Remi LEQUETTE
	3	// Copyright (c) 1993-1999 Matra Datavision
973c2be1	4	// Copyright (c) 1999-2014 OPEN CASCADE SAS
b311480e	5	//
973c2be1	6	// This file is part of Open CASCADE Technology software library.
b311480e	7	//
d5f74e42	8	// This library is free software; you can redistribute it and/or modify it under
d5f74e42	9	// the terms of the GNU Lesser General Public License version 2.1 as published
973c2be1	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.
b311480e	13	//
973c2be1	14	// Alternatively, this file may be used under the terms of Open CASCADE
973c2be1	15	// commercial license or contractual agreement.
7fd59977	16
	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>
	22
	23	//=======================================================================
	24	//function : TCollection_IndexedDataMap
	25	//purpose :
	26	//=======================================================================
	27
	28	TCollection_IndexedDataMap::TCollection_IndexedDataMap
	29	(const Standard_Integer NbBuckets):
	30	TCollection_BasicMap(NbBuckets,Standard_False)
	31	{
	32	}
	33
	34	//=======================================================================
	35	//function : TCollection_IndexedDataMap
	36	//purpose :
	37	//=======================================================================
	38
	39	TCollection_IndexedDataMap::TCollection_IndexedDataMap
	40	(const TCollection_IndexedDataMap& Other) :
	41	TCollection_BasicMap(Other.NbBuckets(),Standard_False)
	42	{
	43	if (Other.Extent() != 0)
9775fa61	44	throw Standard_DomainError("TCollection:Copy of non empty IndexedDataMap");
7fd59977	45	}
	46
	47	//=======================================================================
	48	//function : Assign
	49	//purpose :
	50	//=======================================================================
	51
	52	TCollection_IndexedDataMap& TCollection_IndexedDataMap::Assign
	53	(const TCollection_IndexedDataMap& Other)
	54	{
	55	// very simple implementation
	56	// not optimal (recompute the hashcode values)
	57
	58	if (this == &Other) return *this;
	59	Clear();
	60	// ReSize(Other.NbBuckets());
	61	if (!Other.IsEmpty()) {
	62	ReSize(Other.Extent());
	63	for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
	64	Add(Other.FindKey(i),Other(i));
	65	}
	66	}
	67	return *this;
	68	}
	69
	70
	71
	72	//=======================================================================
	73	//function : ReSize
	74	//purpose :
	75	//=======================================================================
	76
	77	void TCollection_IndexedDataMap::ReSize(const Standard_Integer N)
	78	{
	79	Standard_Integer newBuck;
	80	Standard_Address newData1=NULL, newData2=NULL;
	81	if (BeginResize(N,newBuck,newData1,newData2)) {
	82	if (myData1) {
	83	TCollection_IndexedDataMapNode newdata1 = (TCollection_IndexedDataMapNode)newData1;
	84	TCollection_IndexedDataMapNode newdata2 = (TCollection_IndexedDataMapNode)newData2;
	85	TCollection_IndexedDataMapNode olddata1 = (TCollection_IndexedDataMapNode) myData1;
	86	TCollection_IndexedDataMapNode p, q;
	87	Standard_Integer i,k1,k2;
	88	for (i = 0; i <= NbBuckets(); i++) {
	89	if (olddata1[i]) {
	90	p = olddata1[i];
	91	while (p) {
	92	k1 = Hasher::HashCode(p->Key1(),newBuck);
	93	k2 = ::HashCode(p->Key2(),newBuck);
	94	q = (TCollection_IndexedDataMapNode*)p->Next();
	95	p->Next() = newdata1[k1];
	96	p->Next2() = newdata2[k2];
	97	newdata1[k1] = p;
	98	newdata2[k2] = p;
	99	p = q;
	100	}
	101	}
	102	}
	103	}
	104	EndResize(N,newBuck,newData1,newData2);
	105	}
	106	}
	107
	108	//=======================================================================
109	//function : Clear
110	//purpose :
111	//=======================================================================
112
113	void TCollection_IndexedDataMap::Clear()
114	{
115	if (!IsEmpty()) {
116	Standard_Integer i;
117	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode) myData1;
118	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode) myData2;
119	TCollection_IndexedDataMapNode p,q;
120	for (i = 0; i <= NbBuckets(); i++) {
121	p = data1[i];
122	while (p) {
123	q = (TCollection_IndexedDataMapNode*) p->Next();
124	delete p;
125	p = q;
126	}
127	data1[i] = data2[i] = NULL;
128	}
129	}
130	TCollection_BasicMap::Destroy();
131	}
132
133	//=======================================================================
134	//function : Add
135	//purpose :
136	//=======================================================================
137
138	Standard_Integer TCollection_IndexedDataMap::Add(const TheKey& K1, const TheItem& I)
139	{
140	if (Resizable()) ReSize(Extent());
141	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
142	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
143	TCollection_IndexedDataMapNode* p;
144	p = data1[k1];
145	while (p) {
146	if (Hasher::IsEqual(p->Key1(),K1))
147	return p->Key2();
148	p = (TCollection_IndexedDataMapNode*) p->Next();
149	}
150	Increment();
151	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode)myData2;
152	Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
153	p = new TCollection_IndexedDataMapNode(K1,Extent(),I,data1[k1],data2[k2]);
154	data1[k1] = p;
155	data2[k2] = p;
156	return Extent();
157	}
158
159
160	//=======================================================================
161	//function : Substitute
162	//purpose :
163	//=======================================================================
164
165	void TCollection_IndexedDataMap::Substitute(const Standard_Integer I,
985aed12	166	const TheKey& K1,
985aed12	167	const TheItem& T)
7fd59977	168	{
985aed12	169	Standard_OutOfRange_Raise_if(I < 1 \|\| I > Extent(), "IndexedDataMap::Substitute : "
985aed12	170	"Index is out of range");
7fd59977	171	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	172	TCollection_IndexedDataMapNode* p;
	173
	174	// check if K1 is not already in the map
	175	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
	176	p = data1[k1];
	177	while (p) {
985aed12	178	if (Hasher::IsEqual(p->Key1(),K1)) {
985aed12	179	if (p->Key2() != I)
9775fa61	180	throw Standard_DomainError("IndexedDataMap::Substitute : "
9775fa61	181	"Attempt to substitute existing key");
985aed12	182	p->Key1() = K1;
	183	p->Value() = T;
	184	return;
	185	}
7fd59977	186	p = (TCollection_IndexedDataMapNode*) p->Next();
	187	}
	188
	189	// Find the node for the index I
	190	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode)myData2;
	191	Standard_Integer k2 = ::HashCode(I,NbBuckets());
	192	p = data2[k2];
	193	while (p) {
	194	if (p->Key2() == I)
	195	break;
	196	p = (TCollection_IndexedDataMapNode*) p->Next2();
	197	}
	198
	199	// remove the old key
	200	Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
	201	TCollection_IndexedDataMapNode* q = data1[k];
	202	if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
	203	else {
	204	while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
	205	q->Next() = p->Next();
	206	}
	207
	208	// update the node
	209	p->Key1() = K1;
	210	p->Value() = T;
	211	p->Next() = data1[k1];
	212	data1[k1] = p;
	213	}
	214
	215	//=======================================================================
	216	//function : RemoveLast
	217	//purpose :
	218	//=======================================================================
	219
	220	void TCollection_IndexedDataMap::RemoveLast()
	221	{
	222	Standard_OutOfRange_Raise_if(Extent() == 0,
	223	"IndexedMap::RemoveLast");
	224	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	225	TCollection_IndexedDataMapNode* p;
	226	TCollection_IndexedDataMapNode* q;
	227
	228	// Find the node for the last index and remove it
	229	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode)myData2;
	230	Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
	231	p = data2[k2];
	232	q = NULL;
	233	while (p) {
	234	if (p->Key2() == Extent())
	235	break;
	236	q = p;
	237	p = (TCollection_IndexedDataMapNode*) p->Next2();
	238	}
	239	if (q == NULL)
	240	data2[k2] = (TCollection_IndexedDataMapNode*)p->Next2();
	241	else
	242	q->Next2() = p->Next2();
	243
	244	// remove the key
	245	Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
	246	q = data1[k];
	247	if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
	248	else {
	249	while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
250	q->Next() = p->Next();
251	}
252
253	Decrement();
254	delete p;
255	}
256
7fd59977	257
	258	//=======================================================================
	259	//function : FindKey
	260	//purpose :
	261	//=======================================================================
	262
	263	const TheKey& TCollection_IndexedDataMap::FindKey(const Standard_Integer K2) const
	264	{
	265	Standard_OutOfRange_Raise_if(K2 < 1 \|\| K2 > Extent(), "IndexedDataMap");
	266	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode)myData2;
	267	Standard_Integer k2 = ::HashCode(K2,NbBuckets());
	268	TCollection_IndexedDataMapNode *p2;
	269	p2 = data2[k2];
	270	while (p2) {
	271	if (p2->Key2() == K2) return p2->Key1();
	272	p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
	273	}
9775fa61	274	throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
7fd59977	275	return p2->Key1();
	276	}
	277
	278	//=======================================================================
	279	//function : FindFromIndex
	280	//purpose :
	281	//=======================================================================
	282
	283	const TheItem& TCollection_IndexedDataMap::FindFromIndex
	284	(const Standard_Integer K2) const
	285	{
	286	Standard_OutOfRange_Raise_if(K2 < 1 \|\| K2 > Extent(), "IndexedDataMap");
	287	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode)myData2;
	288	Standard_Integer k2 = ::HashCode(K2,NbBuckets());
	289	TCollection_IndexedDataMapNode *p2;
	290	p2 = data2[k2];
	291	while (p2) {
	292	if (p2->Key2() == K2) return p2->Value();
	293	p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
	294	}
9775fa61	295	throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
7fd59977	296	return p2->Value();
	297	}
	298
	299	//=======================================================================
	300	//function : ChangeFromIndex
	301	//purpose :
	302	//=======================================================================
	303
	304	TheItem& TCollection_IndexedDataMap::ChangeFromIndex(const Standard_Integer K2)
	305	{
	306	Standard_OutOfRange_Raise_if(K2 < 1 \|\| K2 > Extent(), "IndexedDataMap");
	307	TCollection_IndexedDataMapNode data2 = (TCollection_IndexedDataMapNode)myData2;
	308	Standard_Integer k2 = ::HashCode(K2,NbBuckets());
	309	TCollection_IndexedDataMapNode *p2;
	310	p2 = data2[k2];
	311	while (p2) {
	312	if (p2->Key2() == K2) return p2->Value();
	313	p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
	314	}
9775fa61	315	throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
7fd59977	316	return p2->Value();
	317	}
	318
	319	//=======================================================================
	320	//function : FindIndex
	321	//purpose :
	322	//=======================================================================
	323
	324	Standard_Integer TCollection_IndexedDataMap::FindIndex(const TheKey& K1) const
	325	{
	326	if (IsEmpty()) return 0;
	327	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	328	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
	329	TCollection_IndexedDataMapNode *p1;
	330	p1 = data1[k1];
	331	while (p1) {
	332	if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
	333	p1 = (TCollection_IndexedDataMapNode*)p1->Next();
	334	}
	335	return 0;
	336	}
cf8e963a	337	//=======================================================================
	338	//function : Contains
	339	//purpose :
	340	//=======================================================================
	341	Standard_Boolean TCollection_IndexedDataMap::Contains(const TheKey& K1) const
	342	{
	343	if (IsEmpty()) return Standard_False;
	344	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	345	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
	346	TCollection_IndexedDataMapNode *p1;
	347	p1 = data1[k1];
	348	while (p1) {
	349	if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
	350	p1 = (TCollection_IndexedDataMapNode*) p1->Next();
	351	}
	352	return Standard_False;
	353	}
7fd59977	354	//=======================================================================
	355	//function : FindFromKey
	356	//purpose :
	357	//=======================================================================
7fd59977	358	const TheItem& TCollection_IndexedDataMap::FindFromKey(const TheKey& K1) const
	359	{
	360	Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::FindFromKey");
	361	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	362	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
	363	TCollection_IndexedDataMapNode *p1;
	364	p1 = data1[k1];
	365	while (p1) {
	366	if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
	367	p1 = (TCollection_IndexedDataMapNode*) p1->Next();
	368	}
9775fa61	369	throw Standard_OutOfRange("TCollection_IndexedDataMap::FindFromKey");
7fd59977	370	return p1->Value();
7fd59977	371	}
7fd59977	372	//=======================================================================
	373	//function : ChangeFromKey
	374	//purpose :
	375	//=======================================================================
7fd59977	376	TheItem& TCollection_IndexedDataMap::ChangeFromKey(const TheKey& K1)
	377	{
	378	Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::ChangeFromKey");
	379	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	380	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
	381	TCollection_IndexedDataMapNode *p1;
	382	p1 = data1[k1];
	383	while (p1) {
	384	if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
	385	p1 = (TCollection_IndexedDataMapNode*)p1->Next();
	386	}
9775fa61	387	throw Standard_OutOfRange("TCollection_IndexedDataMap::ChangeFromKey");
7fd59977	388	return p1->Value();
7fd59977	389	}
cf8e963a	390	//modified by NIZNHY-PKV Tue Jul 05 08:37:03 2011f
	391	//=======================================================================
	392	//function : FindFromKey1
	393	//purpose :
	394	//=======================================================================
	395	Standard_Address TCollection_IndexedDataMap::FindFromKey1(const TheKey& K1) const
	396	{
	397	TCollection_IndexedDataMap pMap=(TCollection_IndexedDataMap )this;
	398	return pMap->ChangeFromKey1(K1);
	399	}
	400	//=======================================================================
	401	//function : ChangeFromKey1
	402	//purpose :
	403	//=======================================================================
	404	Standard_Address TCollection_IndexedDataMap::ChangeFromKey1(const TheKey& K1)
	405	{
	406	if (IsEmpty()) {
	407	return NULL;
	408	}
	409	TCollection_IndexedDataMapNode data1 = (TCollection_IndexedDataMapNode)myData1;
	410	Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
	411	TCollection_IndexedDataMapNode *p1;
	412	p1 = data1[k1];
	413	while (p1) {
	414	if (Hasher::IsEqual(p1->Key1(),K1)) {
	415	return (Standard_Address)&p1->Value();
	416	}
	417	p1 = (TCollection_IndexedDataMapNode*) p1->Next();
	418	}
	419	return NULL;
	420	}