// Created on: 2002-04-24
// Created by: Alexander KARTOMIN (akm)
-// Copyright (c) 2002-2012 OPEN CASCADE SAS
+// Copyright (c) 2002-2014 OPEN CASCADE SAS
//
-// The content of this file is subject to the Open CASCADE Technology Public
-// License Version 6.5 (the "License"). You may not use the content of this file
-// except in compliance with the License. Please obtain a copy of the License
-// at http://www.opencascade.org and read it completely before using this file.
+// This file is part of Open CASCADE Technology software library.
//
-// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
-// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
+// 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.
//
-// The Original Code and all software distributed under the License is
-// distributed on an "AS IS" basis, without warranty of any kind, and the
-// Initial Developer hereby disclaims all such warranties, including without
-// limitation, any warranties of merchantability, fitness for a particular
-// purpose or non-infringement. Please see the License for the specific terms
-// and conditions governing the rights and limitations under the License.
-
+// Alternatively, this file may be used under the terms of Open CASCADE
+// commercial license or contractual agreement.
#ifndef NCollection_DataMap_HeaderFile
#define NCollection_DataMap_HeaderFile
-#include <NCollection_BaseCollection.hxx>
#include <NCollection_BaseMap.hxx>
#include <NCollection_TListNode.hxx>
-
+#include <NCollection_StlIterator.hxx>
#include <NCollection_DefaultHasher.hxx>
#include <Standard_TypeMismatch.hxx>
template < class TheKeyType,
class TheItemType,
- class Hasher = NCollection_DefaultHasher<TheKeyType> > class NCollection_DataMap
-
- : public NCollection_BaseCollection<TheItemType>,
- public NCollection_BaseMap
+ class Hasher = NCollection_DefaultHasher<TheKeyType> >
+class NCollection_DataMap : public NCollection_BaseMap
{
+public:
+ //! STL-compliant typedef for key type
+ typedef TheKeyType key_type;
+ //! STL-compliant typedef for value type
+ typedef TheItemType value_type;
+
+public:
// **************** Adaptation of the TListNode to the DATAmap
- public:
class DataMapNode : public NCollection_TListNode<TheItemType>
{
public:
DataMapNode (const TheKeyType& theKey,
const TheItemType& theItem,
NCollection_ListNode* theNext) :
- NCollection_TListNode<TheItemType> (theItem, theNext)
- { myKey = theKey; }
+ NCollection_TListNode<TheItemType> (theItem, theNext),
+ myKey(theKey)
+ {}
+
//! Key
const TheKeyType& Key (void) const
{ return myKey; }
- //! Static deleter to be passed to BaseList
+ //! Static deleter to be passed to BaseMap
static void delNode (NCollection_ListNode * theNode,
Handle(NCollection_BaseAllocator)& theAl)
{
public:
// **************** Implementation of the Iterator interface.
- class Iterator
- : public NCollection_BaseCollection<TheItemType>::Iterator,
- public NCollection_BaseMap::Iterator
+ class Iterator : public NCollection_BaseMap::Iterator
{
public:
//! Empty constructor
Iterator (const NCollection_DataMap& theMap) :
NCollection_BaseMap::Iterator(theMap) {}
//! Query if the end of collection is reached by iterator
- virtual Standard_Boolean More(void) const
+ Standard_Boolean More(void) const
{ return PMore(); }
//! Make a step along the collection
- virtual void Next(void)
+ void Next(void)
{ PNext(); }
//! Value inquiry
- virtual const TheItemType& Value(void) const
+ const TheItemType& Value(void) const
{
-#if !defined No_Exception && !defined No_Standard_NoSuchObject
- if (!More())
- Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value");
-#endif
+ Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Value");
return ((DataMapNode *) myNode)->Value();
}
//! Value change access
- virtual TheItemType& ChangeValue(void) const
+ TheItemType& ChangeValue(void) const
{
-#if !defined No_Exception && !defined No_Standard_NoSuchObject
- if (!More())
- Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue");
-#endif
+ Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::ChangeValue");
return ((DataMapNode *) myNode)->ChangeValue();
}
//! Key
const TheKeyType& Key (void) const
{
-#if !defined No_Exception && !defined No_Standard_NoSuchObject
- if (!More())
- Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key");
-#endif
+ Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Key");
return ((DataMapNode *) myNode)->Key();
}
};
+
+ //! Shorthand for a regular iterator type.
+ typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
+
+ //! Shorthand for a constant iterator type.
+ typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
+
+ //! Returns an iterator pointing to the first element in the map.
+ iterator begin() const { return Iterator (*this); }
+
+ //! Returns an iterator referring to the past-the-end element in the map.
+ iterator end() const { return Iterator(); }
+
+ //! Returns a const iterator pointing to the first element in the map.
+ const_iterator cbegin() const { return Iterator (*this); }
+
+ //! Returns a const iterator referring to the past-the-end element in the map.
+ const_iterator cend() const { return Iterator(); }
public:
// ---------- PUBLIC METHODS ------------
+ //! Empty Constructor.
+ NCollection_DataMap() : NCollection_BaseMap (1, Standard_True, Handle(NCollection_BaseAllocator)()) {}
+
//! Constructor
- NCollection_DataMap (const Standard_Integer NbBuckets=1,
- const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
- : NCollection_BaseCollection<TheItemType>(theAllocator),
- NCollection_BaseMap (NbBuckets, Standard_True) {}
+ explicit NCollection_DataMap (const Standard_Integer theNbBuckets,
+ const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
+ : NCollection_BaseMap (theNbBuckets, Standard_True, theAllocator) {}
//! Copy constructor
NCollection_DataMap (const NCollection_DataMap& theOther)
- : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
- NCollection_BaseMap (theOther.NbBuckets(), Standard_True)
+ : NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator)
{ *this = theOther; }
- //! Assign another collection
- virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
- {
- if (this == &theOther)
- return;
- Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible");
+ //! Exchange the content of two maps without re-allocations.
+ //! Notice that allocators will be swapped as well!
+ void Exchange (NCollection_DataMap& theOther)
+ {
+ this->exchangeMapsData (theOther);
}
- //! = another map
- NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
+ //! Assignment.
+ //! This method does not change the internal allocator.
+ NCollection_DataMap& Assign (const NCollection_DataMap& theOther)
{
if (this == &theOther)
return *this;
- Clear(theOther.myAllocator);
+ Clear();
ReSize (theOther.Extent()-1);
Iterator anIter(theOther);
for (; anIter.More(); anIter.Next())
return *this;
}
+ //! Assignment operator
+ NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
+ {
+ return Assign (theOther);
+ }
+
//! ReSize
void ReSize (const Standard_Integer N)
{
- DataMapNode** newdata = NULL;
- DataMapNode** dummy = NULL;
+ NCollection_ListNode** newdata = NULL;
+ NCollection_ListNode** dummy = NULL;
Standard_Integer newBuck;
- if (BeginResize (N, newBuck,
- (NCollection_ListNode**&)newdata,
- (NCollection_ListNode**&)dummy,
- this->myAllocator))
+ if (BeginResize (N, newBuck, newdata, dummy))
{
if (myData1)
{
}
}
}
- EndResize(N,newBuck,
- (NCollection_ListNode**&)newdata,
- (NCollection_ListNode**&)dummy,
- this->myAllocator);
+ EndResize (N, newBuck, newdata, dummy);
}
}
- //! Bind
+ //! Bind binds Item to Key in map.
+ //! @param theKey key to add/update
+ //! @param theItem new item; overrides value previously bound to the key, if any
+ //! @return Standard_True if Key was not bound already
Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
{
if (Resizable())
return Standard_True;
}
- //! IsBound
- Standard_Boolean IsBound(const TheKeyType& K) const
+ //! Bound binds Item to Key in map. Returns modifiable Item
+ TheItemType* Bound (const TheKeyType& theKey, const TheItemType& theItem)
{
- if (IsEmpty())
- return Standard_False;
- DataMapNode** data = (DataMapNode**) myData1;
- DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
- while (p)
+ if (Resizable())
+ ReSize(Extent());
+ DataMapNode** data = (DataMapNode**)myData1;
+ Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
+ DataMapNode* p = data[k];
+ while (p)
{
- if (Hasher::IsEqual(p->Key(),K))
- return Standard_True;
- p = (DataMapNode *) p->Next();
+ if (Hasher::IsEqual(p->Key(), theKey))
+ {
+ p->ChangeValue() = theItem;
+ return &p->ChangeValue();
+ }
+ p = (DataMapNode*)p->Next();
}
- return Standard_False;
+ data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
+ Increment();
+ return &data[k]->ChangeValue();
+ }
+
+ //! IsBound
+ Standard_Boolean IsBound(const TheKeyType& theKey) const
+ {
+ DataMapNode* p;
+ return lookup(theKey, p);
}
- //! UnBind
- Standard_Boolean UnBind(const TheKeyType& K)
+ //! UnBind removes Item Key pair from map
+ Standard_Boolean UnBind(const TheKeyType& theKey)
{
if (IsEmpty())
return Standard_False;
DataMapNode** data = (DataMapNode**) myData1;
- Standard_Integer k = Hasher::HashCode(K,NbBuckets());
+ Standard_Integer k = Hasher::HashCode(theKey,NbBuckets());
DataMapNode* p = data[k];
DataMapNode* q = NULL;
while (p)
{
- if (Hasher::IsEqual(p->Key(),K))
+ if (Hasher::IsEqual(p->Key(), theKey))
{
Decrement();
if (q)
return Standard_False;
}
- //! Find
+ //! Seek returns pointer to Item by Key. Returns
+ //! NULL is Key was not bound.
+ const TheItemType* Seek(const TheKeyType& theKey) const
+ {
+ DataMapNode* p = 0;
+ if (!lookup(theKey, p))
+ return 0L;
+ return &p->Value();
+ }
+
+ //! Find returns the Item for Key. Raises if Key was not bound
const TheItemType& Find(const TheKeyType& theKey) const
{
-#if !defined No_Exception && !defined No_Standard_NoSuchObject
- if (IsEmpty())
- Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
-#endif
- DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
- while (p)
- {
- if (Hasher::IsEqual(p->Key(),theKey))
- return p->Value();
- p = (DataMapNode*) p->Next();
- }
- Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
- return p->Value(); // This for compiler
+ DataMapNode* p = 0;
+ if (!lookup(theKey, p))
+ throw Standard_NoSuchObject("NCollection_DataMap::Find");
+ return p->Value();
+ }
+
+ //! Find Item for key with copying.
+ //! @return true if key was found
+ Standard_Boolean Find (const TheKeyType& theKey,
+ TheItemType& theValue) const
+ {
+ DataMapNode* p = 0;
+ if (!lookup(theKey, p))
+ return Standard_False;
+
+ theValue = p->Value();
+ return Standard_True;
}
//! operator ()
const TheItemType& operator() (const TheKeyType& theKey) const
{ return Find(theKey); }
- //! ChangeFind
+ //! ChangeSeek returns modifiable pointer to Item by Key. Returns
+ //! NULL is Key was not bound.
+ TheItemType* ChangeSeek(const TheKeyType& theKey)
+ {
+ DataMapNode* p = 0;
+ if (!lookup(theKey, p))
+ return 0L;
+ return &p->ChangeValue();
+ }
+
+ //! ChangeFind returns mofifiable Item by Key. Raises if Key was not bound
TheItemType& ChangeFind (const TheKeyType& theKey)
{
-#if !defined No_Exception && !defined No_Standard_NoSuchObject
- if (IsEmpty())
- Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
-#endif
- DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
- while (p)
- {
- if (Hasher::IsEqual(p->Key(),theKey))
- return p->ChangeValue();
- p = (DataMapNode*) p->Next();
- }
- Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
- return p->ChangeValue(); // This for compiler
+ DataMapNode* p = 0;
+ if (!lookup(theKey, p))
+ throw Standard_NoSuchObject("NCollection_DataMap::Find");
+ return p->ChangeValue();
}
//! operator ()
//! Clear data. If doReleaseMemory is false then the table of
//! buckets is not released and will be reused.
void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
- { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); }
+ { Destroy (DataMapNode::delNode, doReleaseMemory); }
//! Clear data and reset allocator
void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
}
//! Destructor
- ~NCollection_DataMap (void)
+ virtual ~NCollection_DataMap (void)
{ Clear(); }
//! Size
- virtual Standard_Integer Size(void) const
+ Standard_Integer Size(void) const
{ return Extent(); }
- private:
- // ----------- PRIVATE METHODS -----------
-
- //! Creates Iterator for use on BaseCollection
- virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
- CreateIterator(void) const
- { return *(new (this->IterAllocator()) Iterator(*this)); }
+
+ protected:
+ // ---------- PROTECTED METHODS ----------
+ //! Lookup for particular key in map. Returns true if key is found and
+ //! thepNode points to binded node. Returns false if key is not found,
+ //! thehNode value is this case is not usable.
+ Standard_Boolean lookup(const TheKeyType& theKey,DataMapNode*& thepNode) const
+ {
+ if (IsEmpty())
+ return Standard_False; // Not found
+ for (thepNode = (DataMapNode*)myData1[Hasher::HashCode(theKey, NbBuckets())];
+ thepNode; thepNode = (DataMapNode*)thepNode->Next())
+ {
+ if (Hasher::IsEqual(thepNode->Key(), theKey))
+ return Standard_True;
+ }
+ return Standard_False; // Not found
+ }
};