src/NCollection/NCollection_List.hxx

   1 // Created on: 2002-04-17
   2 // Created by: Alexander Kartomin (akm)
   3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 #ifndef NCollection_List_HeaderFile
  17 #define NCollection_List_HeaderFile
  18
  19 #include <NCollection_TListIterator.hxx>
  20 #include <NCollection_StlIterator.hxx>
  21
  22 #include <Standard_NoSuchObject.hxx>
  23
  24 /**
  25  * Purpose:      Simple list to link  items together keeping the first
  26  *               and the last one.
  27  *               Inherits BaseList, adding the data item to each node.
  28  */
  29 template <class TheItemType>
  30 class NCollection_List : public NCollection_BaseList
  31 {
  32 public:
  33   //! STL-compliant typedef for value type
  34   typedef TheItemType value_type;
  35
  36 public:
  37   typedef NCollection_TListNode<TheItemType>     ListNode;
  38   typedef NCollection_TListIterator<TheItemType> Iterator;
  39
  40   //! Shorthand for a regular iterator type.
  41   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
  42
  43   //! Shorthand for a constant iterator type.
  44   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
  45
  46   //! Returns an iterator pointing to the first element in the list.
  47   iterator begin() const { return Iterator (*this); }
  48
  49   //! Returns an iterator referring to the past-the-end element in the list.
  50   iterator end() const { return Iterator(); }
  51
  52   //! Returns a const iterator pointing to the first element in the list.
  53   const_iterator cbegin() const { return Iterator (*this); }
  54
  55   //! Returns a const iterator referring to the past-the-end element in the list.
  56   const_iterator cend() const { return Iterator(); }
  57
  58  public:
  59   // ---------- PUBLIC METHODS ------------
  60
  61   //! Constructor
  62   NCollection_List(const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
  63     NCollection_BaseList(theAllocator) {}
  64
  65   //! Copy constructor
  66   NCollection_List (const NCollection_List& theOther) :
  67     NCollection_BaseList(theOther.myAllocator)
  68   {
  69     Assign (theOther);
  70   }
  71
  72   //! Size - Number of items
  73   Standard_Integer Size (void) const
  74   { return Extent(); }
  75
  76   //! Replace this list by the items of another list (theOther parameter).
  77   //! This method does not change the internal allocator.
  78   NCollection_List& Assign (const NCollection_List& theOther)
  79   {
  80     if (this != &theOther) {
  81       Clear();
  82       appendList(theOther.PFirst());
  83     }
  84     return *this;
  85   }
  86
  87   //! Replacement operator
  88   NCollection_List& operator= (const NCollection_List& theOther)
  89   {
  90     return Assign (theOther);
  91   }
  92
  93   //! Clear this list
  94   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
  95   {
  96     PClear (ListNode::delNode);
  97     if (!theAllocator.IsNull())
  98       this->myAllocator = theAllocator;
  99   }
 100
 101   //! First item
 102   const TheItemType& First (void) const
 103   {
 104     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
 105     return ((const ListNode *) PFirst())->Value();
 106   }
 107
 108   //! First item (non-const)
 109   TheItemType& First (void)
 110   {
 111     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
 112     return ((ListNode *) PFirst())->ChangeValue();
 113   }
 114
 115   //! Last item
 116   const TheItemType& Last (void) const
 117   {
 118     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
 119     return ((const ListNode *) PLast())->Value();
 120   }
 121
 122   //! Last item (non-const)
 123   TheItemType& Last (void)
 124   {
 125     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
 126     return ((ListNode *) PLast())->ChangeValue();
 127   }
 128
 129   //! Append one item at the end
 130   TheItemType& Append (const TheItemType& theItem)
 131   {
 132     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 133     PAppend(pNew);
 134     return ((ListNode *) PLast())->ChangeValue();
 135   }
 136
 137   //! Append one item at the end and output iterator
 138   //!   pointing at the appended item
 139   void Append (const TheItemType& theItem, Iterator& theIter)
 140   {
 141     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 142     PAppend(pNew, theIter);
 143   }
 144
 145   //! Append another list at the end
 146   void Append (NCollection_List& theOther)
 147   {
 148     if (this == &theOther || theOther.Extent()<1)
 149       return;
 150     if (this->myAllocator == theOther.myAllocator)
 151     {
 152       // Then we take the list and glue it to our end -
 153       // deallocation will bring no problem
 154       PAppend(theOther);
 155     }
 156     else
 157     {
 158       // No - this list has different memory scope
 159       appendList(theOther.myFirst);
 160       theOther.Clear();
 161     }
 162   }
 163
 164   //! Prepend one item at the beginning
 165   TheItemType& Prepend (const TheItemType& theItem)
 166   {
 167     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 168     PPrepend(pNew);
 169     return ((ListNode *) PFirst())->ChangeValue();
 170   }
 171
 172   //! Prepend another list at the beginning
 173   void Prepend (NCollection_List& theOther)
 174   {
 175     if (this == &theOther || theOther.Extent()<1)
 176       return;
 177     if (this->myAllocator == theOther.myAllocator)
 178     {
 179       // Then we take the list and glue it to our head -
 180       // deallocation will bring no problem
 181       PPrepend(theOther);
 182     }
 183     else
 184     {
 185       // No - this list has different memory scope
 186       Iterator it(*this);
 187       prependList(theOther.PFirst(), it);
 188       theOther.Clear();
 189     }
 190   }
 191
 192   //! RemoveFirst item
 193   void RemoveFirst (void)
 194   { PRemoveFirst (ListNode::delNode); }
 195
 196   //! Remove item pointed by iterator theIter;
 197   //! theIter is then set to the next item
 198   void Remove (Iterator& theIter)
 199   {
 200     PRemove (theIter, ListNode::delNode);
 201   }
 202
 203   //! Remove the first occurrence of the object.
 204   template<typename TheValueType> // instantiate this method on first call only for types defining equality operator
 205   Standard_Boolean Remove (const TheValueType& theObject)
 206   {
 207     for (Iterator anIter (*this); anIter.More(); anIter.Next())
 208     {
 209       if (anIter.Value() == theObject)
 210       {
 211         Remove (anIter);
 212         return Standard_True;
 213       }
 214     }
 215     return Standard_False;
 216   }
 217
 218   //! InsertBefore
 219   TheItemType& InsertBefore (const TheItemType& theItem,
 220                              Iterator& theIter)
 221   {
 222     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 223     PInsertBefore (pNew, theIter);
 224     return pNew -> ChangeValue();
 225   }
 226
 227   //! InsertBefore
 228   void InsertBefore (NCollection_List& theOther,
 229                      Iterator& theIter)
 230   {
 231     if (this == &theOther)
 232       return;
 233
 234     if (this->myAllocator == theOther.myAllocator)
 235     {
 236       // Then we take the list and glue it to our head -
 237       // deallocation will bring no problem
 238       PInsertBefore (theOther, theIter);
 239     }
 240     else
 241     {
 242       // No - this list has different memory scope
 243       prependList(theOther.myFirst, theIter);
 244       theOther.Clear();
 245     }
 246   }
 247
 248   //! InsertAfter
 249   TheItemType& InsertAfter (const TheItemType& theItem,
 250                             Iterator& theIter)
 251   {
 252     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 253     PInsertAfter (pNew, theIter);
 254     return pNew -> ChangeValue();
 255   }
 256
 257   //! InsertAfter
 258   void InsertAfter (NCollection_List& theOther,
 259                     Iterator& theIter)
 260   {
 261     if (!theIter.More())
 262     {
 263       Append(theOther);
 264       return;
 265     }
 266     if (this->myAllocator == theOther.myAllocator)
 267     {
 268       // Then we take the list and glue it to our head -
 269       // deallocation will bring no problem
 270       PInsertAfter (theOther, theIter);
 271     }
 272     else
 273     {
 274       // No - this list has different memory scope
 275       Standard_NoSuchObject_Raise_if (!theIter.More(), "NCollection_List::InsertAfter");
 276
 277       Iterator anIter;
 278       anIter.myPrevious = theIter.myCurrent;
 279       anIter.myCurrent = theIter.myCurrent->Next();
 280       prependList(theOther.PFirst(), anIter);
 281       theOther.Clear();
 282     }
 283   }
 284
 285   //! Reverse the list
 286   void Reverse ()
 287   { PReverse(); }
 288
 289   //! Return true if object is stored in the list.
 290   template<typename TheValueType> // instantiate this method on first call only for types defining equality operator
 291   Standard_Boolean Contains (const TheValueType& theObject) const
 292   {
 293     for (Iterator anIter (*this); anIter.More(); anIter.Next())
 294     {
 295       if (anIter.Value() == theObject)
 296       {
 297         return Standard_True;
 298       }
 299     }
 300     return Standard_False;
 301   }
 302
 303   //! Destructor - clears the List
 304   virtual ~NCollection_List (void)
 305   { Clear(); }
 306
 307  private:
 308   // ----------- PRIVATE METHODS -----------
 309
 310   //! append the list headed by the given ListNode
 311   void appendList(const NCollection_ListNode * pCur) {
 312     while (pCur) {
 313       NCollection_ListNode * pNew =
 314         new (this->myAllocator) ListNode(((const ListNode *)(pCur))->Value());
 315       PAppend(pNew);
 316       pCur = pCur->Next();
 317     }
 318   }
 319
 320   //! insert the list headed by the given ListNode before the given iterator
 321   void prependList(const NCollection_ListNode * pCur, Iterator& theIter) {
 322     while (pCur) {
 323       NCollection_ListNode * pNew =
 324         new (this->myAllocator) ListNode (((const ListNode *)(pCur))->Value());
 325       PInsertBefore(pNew, theIter);
 326       pCur = pCur->Next();
 327     }
 328   }
 329 };
 330
 331 #endif