liboce-foundation-dev 0.18.2-2build1 / usr / include / oce / 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)
    Standard_DomainError::Raise("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)
        Standard_DomainError::Raise("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();
  }
  Standard_OutOfRange::Raise("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();
  }
  Standard_OutOfRange::Raise("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();
  }
  Standard_OutOfRange::Raise("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();
  }
  Standard_OutOfRange::Raise("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();
  }
  Standard_OutOfRange::Raise("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;
}