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   //! Empty constructor.
  62   NCollection_List() : NCollection_BaseList(Handle(NCollection_BaseAllocator)()) {}
  63
  64   //! Constructor
  65   explicit NCollection_List(const Handle(NCollection_BaseAllocator)& theAllocator) : NCollection_BaseList(theAllocator) {}
  66
  67   //! Copy constructor
  68   NCollection_List (const NCollection_List& theOther) :
  69     NCollection_BaseList(theOther.myAllocator)
  70   {
  71     Assign (theOther);
  72   }
  73
  74   //! Size - Number of items
  75   Standard_Integer Size (void) const
  76   { return Extent(); }
  77
  78   //! Replace this list by the items of another list (theOther parameter).
  79   //! This method does not change the internal allocator.
  80   NCollection_List& Assign (const NCollection_List& theOther)
  81   {
  82     if (this != &theOther) {
  83       Clear();
  84       appendList(theOther.PFirst());
  85     }
  86     return *this;
  87   }
  88
  89   //! Replacement operator
  90   NCollection_List& operator= (const NCollection_List& theOther)
  91   {
  92     return Assign (theOther);
  93   }
  94
  95   //! Clear this list
  96   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
  97   {
  98     PClear (ListNode::delNode);
  99     if (!theAllocator.IsNull())
 100       this->myAllocator = theAllocator;
 101   }
 102
 103   //! First item
 104   const TheItemType& First (void) const
 105   {
 106     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
 107     return ((const ListNode *) PFirst())->Value();
 108   }
 109
 110   //! First item (non-const)
 111   TheItemType& First (void)
 112   {
 113     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
 114     return ((ListNode *) PFirst())->ChangeValue();
 115   }
 116
 117   //! Last item
 118   const TheItemType& Last (void) const
 119   {
 120     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
 121     return ((const ListNode *) PLast())->Value();
 122   }
 123
 124   //! Last item (non-const)
 125   TheItemType& Last (void)
 126   {
 127     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
 128     return ((ListNode *) PLast())->ChangeValue();
 129   }
 130
 131   //! Append one item at the end
 132   TheItemType& Append (const TheItemType& theItem)
 133   {
 134     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 135     PAppend(pNew);
 136     return ((ListNode *) PLast())->ChangeValue();
 137   }
 138
 139   //! Append one item at the end and output iterator
 140   //!   pointing at the appended item
 141   void Append (const TheItemType& theItem, Iterator& theIter)
 142   {
 143     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 144     PAppend(pNew, theIter);
 145   }
 146
 147   //! Append another list at the end
 148   void Append (NCollection_List& theOther)
 149   {
 150     if (this == &theOther || theOther.Extent()<1)
 151       return;
 152     if (this->myAllocator == theOther.myAllocator)
 153     {
 154       // Then we take the list and glue it to our end -
 155       // deallocation will bring no problem
 156       PAppend(theOther);
 157     }
 158     else
 159     {
 160       // No - this list has different memory scope
 161       appendList(theOther.myFirst);
 162       theOther.Clear();
 163     }
 164   }
 165
 166   //! Prepend one item at the beginning
 167   TheItemType& Prepend (const TheItemType& theItem)
 168   {
 169     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 170     PPrepend(pNew);
 171     return ((ListNode *) PFirst())->ChangeValue();
 172   }
 173
 174   //! Prepend another list at the beginning
 175   void Prepend (NCollection_List& theOther)
 176   {
 177     if (this == &theOther || theOther.Extent()<1)
 178       return;
 179     if (this->myAllocator == theOther.myAllocator)
 180     {
 181       // Then we take the list and glue it to our head -
 182       // deallocation will bring no problem
 183       PPrepend(theOther);
 184     }
 185     else
 186     {
 187       // No - this list has different memory scope
 188       Iterator it(*this);
 189       prependList(theOther.PFirst(), it);
 190       theOther.Clear();
 191     }
 192   }
 193
 194   //! RemoveFirst item
 195   void RemoveFirst (void)
 196   { PRemoveFirst (ListNode::delNode); }
 197
 198   //! Remove item pointed by iterator theIter;
 199   //! theIter is then set to the next item
 200   void Remove (Iterator& theIter)
 201   {
 202     PRemove (theIter, ListNode::delNode);
 203   }
 204
 205   //! Remove the first occurrence of the object.
 206   template<typename TheValueType> // instantiate this method on first call only for types defining equality operator
 207   Standard_Boolean Remove (const TheValueType& theObject)
 208   {
 209     for (Iterator anIter (*this); anIter.More(); anIter.Next())
 210     {
 211       if (anIter.Value() == theObject)
 212       {
 213         Remove (anIter);
 214         return Standard_True;
 215       }
 216     }
 217     return Standard_False;
 218   }
 219
 220   //! InsertBefore
 221   TheItemType& InsertBefore (const TheItemType& theItem,
 222                              Iterator& theIter)
 223   {
 224     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 225     PInsertBefore (pNew, theIter);
 226     return pNew -> ChangeValue();
 227   }
 228
 229   //! InsertBefore
 230   void InsertBefore (NCollection_List& theOther,
 231                      Iterator& theIter)
 232   {
 233     if (this == &theOther)
 234       return;
 235
 236     if (this->myAllocator == theOther.myAllocator)
 237     {
 238       // Then we take the list and glue it to our head -
 239       // deallocation will bring no problem
 240       PInsertBefore (theOther, theIter);
 241     }
 242     else
 243     {
 244       // No - this list has different memory scope
 245       prependList(theOther.myFirst, theIter);
 246       theOther.Clear();
 247     }
 248   }
 249
 250   //! InsertAfter
 251   TheItemType& InsertAfter (const TheItemType& theItem,
 252                             Iterator& theIter)
 253   {
 254     ListNode * pNew = new (this->myAllocator) ListNode(theItem);
 255     PInsertAfter (pNew, theIter);
 256     return pNew -> ChangeValue();
 257   }
 258
 259   //! InsertAfter
 260   void InsertAfter (NCollection_List& theOther,
 261                     Iterator& theIter)
 262   {
 263     if (!theIter.More())
 264     {
 265       Append(theOther);
 266       return;
 267     }
 268     if (this->myAllocator == theOther.myAllocator)
 269     {
 270       // Then we take the list and glue it to our head -
 271       // deallocation will bring no problem
 272       PInsertAfter (theOther, theIter);
 273     }
 274     else
 275     {
 276       // No - this list has different memory scope
 277       Standard_NoSuchObject_Raise_if (!theIter.More(), "NCollection_List::InsertAfter");
 278
 279       Iterator anIter;
 280       anIter.myPrevious = theIter.myCurrent;
 281       anIter.myCurrent = theIter.myCurrent->Next();
 282       prependList(theOther.PFirst(), anIter);
 283       theOther.Clear();
 284     }
 285   }
 286
 287   //! Reverse the list
 288   void Reverse ()
 289   { PReverse(); }
 290
 291   //! Return true if object is stored in the list.
 292   template<typename TheValueType> // instantiate this method on first call only for types defining equality operator
 293   Standard_Boolean Contains (const TheValueType& theObject) const
 294   {
 295     for (Iterator anIter (*this); anIter.More(); anIter.Next())
 296     {
 297       if (anIter.Value() == theObject)
 298       {
 299         return Standard_True;
 300       }
 301     }
 302     return Standard_False;
 303   }
 304
 305   //! Destructor - clears the List
 306   virtual ~NCollection_List (void)
 307   { Clear(); }
 308
 309  private:
 310   // ----------- PRIVATE METHODS -----------
 311
 312   //! append the list headed by the given ListNode
 313   void appendList(const NCollection_ListNode * pCur) {
 314     while (pCur) {
 315       NCollection_ListNode * pNew =
 316         new (this->myAllocator) ListNode(((const ListNode *)(pCur))->Value());
 317       PAppend(pNew);
 318       pCur = pCur->Next();
 319     }
 320   }
 321
 322   //! insert the list headed by the given ListNode before the given iterator
 323   void prependList(const NCollection_ListNode * pCur, Iterator& theIter) {
 324     while (pCur) {
 325       NCollection_ListNode * pNew =
 326         new (this->myAllocator) ListNode (((const ListNode *)(pCur))->Value());
 327       PInsertBefore(pNew, theIter);
 328       pCur = pCur->Next();
 329     }
 330   }
 331 };
 332
 333 #endif