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