1 // Created on: 2002-04-17
2 // Created by: Alexander Kartomin (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_List_HeaderFile
17 #define NCollection_List_HeaderFile
19 #include <NCollection_TListIterator.hxx>
20 #include <NCollection_StlIterator.hxx>
22 #include <Standard_NoSuchObject.hxx>
25 * Purpose: Simple list to link items together keeping the first
27 * Inherits BaseList, adding the data item to each node.
29 template <class TheItemType>
30 class NCollection_List : public NCollection_BaseList
33 //! STL-compliant typedef for value type
34 typedef TheItemType value_type;
37 typedef NCollection_TListNode<TheItemType> ListNode;
38 typedef NCollection_TListIterator<TheItemType> Iterator;
40 //! Shorthand for a regular iterator type.
41 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
43 //! Shorthand for a constant iterator type.
44 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
46 //! Returns an iterator pointing to the first element in the list.
47 iterator begin() const { return Iterator (*this); }
49 //! Returns an iterator referring to the past-the-end element in the list.
50 iterator end() const { return Iterator(); }
52 //! Returns a const iterator pointing to the first element in the list.
53 const_iterator cbegin() const { return Iterator (*this); }
55 //! Returns a const iterator referring to the past-the-end element in the list.
56 const_iterator cend() const { return Iterator(); }
59 // ---------- PUBLIC METHODS ------------
62 NCollection_List(const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
63 NCollection_BaseList(theAllocator) {}
66 NCollection_List (const NCollection_List& theOther) :
67 NCollection_BaseList(theOther.myAllocator)
72 //! Size - Number of items
73 Standard_Integer Size (void) const
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)
80 if (this != &theOther) {
82 appendList(theOther.PFirst());
87 //! Replacement operator
88 NCollection_List& operator= (const NCollection_List& theOther)
90 return Assign (theOther);
94 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
96 PClear (ListNode::delNode);
97 if (!theAllocator.IsNull())
98 this->myAllocator = theAllocator;
102 const TheItemType& First (void) const
104 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
105 return ((const ListNode *) PFirst())->Value();
108 //! First item (non-const)
109 TheItemType& First (void)
111 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
112 return ((ListNode *) PFirst())->ChangeValue();
116 const TheItemType& Last (void) const
118 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
119 return ((const ListNode *) PLast())->Value();
122 //! Last item (non-const)
123 TheItemType& Last (void)
125 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
126 return ((ListNode *) PLast())->ChangeValue();
129 //! Append one item at the end
130 TheItemType& Append (const TheItemType& theItem)
132 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
134 return ((ListNode *) PLast())->ChangeValue();
137 //! Append one item at the end and output iterator
138 //! pointing at the appended item
139 void Append (const TheItemType& theItem, Iterator& theIter)
141 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
142 PAppend(pNew, theIter);
145 //! Append another list at the end
146 void Append (NCollection_List& theOther)
148 if (this == &theOther || theOther.Extent()<1)
150 if (this->myAllocator == theOther.myAllocator)
152 // Then we take the list and glue it to our end -
153 // deallocation will bring no problem
158 // No - this list has different memory scope
159 appendList(theOther.myFirst);
164 //! Prepend one item at the beginning
165 TheItemType& Prepend (const TheItemType& theItem)
167 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
169 return ((ListNode *) PFirst())->ChangeValue();
172 //! Prepend another list at the beginning
173 void Prepend (NCollection_List& theOther)
175 if (this == &theOther || theOther.Extent()<1)
177 if (this->myAllocator == theOther.myAllocator)
179 // Then we take the list and glue it to our head -
180 // deallocation will bring no problem
185 // No - this list has different memory scope
187 prependList(theOther.PFirst(), it);
193 void RemoveFirst (void)
194 { PRemoveFirst (ListNode::delNode); }
197 void Remove (Iterator& theIter)
199 PRemove (theIter, ListNode::delNode);
202 //! Remove the first occurrence of the object.
203 template<typename TheValueType> // instantiate this method on first call only for types defining equality operator
204 Standard_Boolean Remove (const TheValueType& theObject)
206 for (Iterator anIter (*this); anIter.More(); anIter.Next())
208 if (anIter.Value() == theObject)
211 return Standard_True;
214 return Standard_False;
218 TheItemType& InsertBefore (const TheItemType& theItem,
221 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
222 PInsertBefore (pNew, theIter);
223 return pNew -> ChangeValue();
227 void InsertBefore (NCollection_List& theOther,
230 if (this == &theOther)
233 if (this->myAllocator == theOther.myAllocator)
235 // Then we take the list and glue it to our head -
236 // deallocation will bring no problem
237 PInsertBefore (theOther, theIter);
241 // No - this list has different memory scope
242 prependList(theOther.myFirst, theIter);
248 TheItemType& InsertAfter (const TheItemType& theItem,
251 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
252 PInsertAfter (pNew, theIter);
253 return pNew -> ChangeValue();
257 void InsertAfter (NCollection_List& theOther,
265 if (this->myAllocator == theOther.myAllocator)
267 // Then we take the list and glue it to our head -
268 // deallocation will bring no problem
269 PInsertAfter (theOther, theIter);
273 // No - this list has different memory scope
274 Standard_NoSuchObject_Raise_if (!theIter.More(), "NCollection_List::InsertAfter");
277 anIter.myPrevious = theIter.myCurrent;
278 anIter.myCurrent = theIter.myCurrent->Next();
279 prependList(theOther.PFirst(), anIter);
288 //! Return true if object is stored in the list.
289 template<typename TheValueType> // instantiate this method on first call only for types defining equality operator
290 Standard_Boolean Contains (const TheValueType& theObject) const
292 for (Iterator anIter (*this); anIter.More(); anIter.Next())
294 if (anIter.Value() == theObject)
296 return Standard_True;
299 return Standard_False;
302 //! Destructor - clears the List
303 virtual ~NCollection_List (void)
307 // ----------- PRIVATE METHODS -----------
309 //! append the list headed by the given ListNode
310 void appendList(const NCollection_ListNode * pCur) {
312 NCollection_ListNode * pNew =
313 new (this->myAllocator) ListNode(((const ListNode *)(pCur))->Value());
319 //! insert the list headed by the given ListNode before the given iterator
320 void prependList(const NCollection_ListNode * pCur, Iterator& theIter) {
322 NCollection_ListNode * pNew =
323 new (this->myAllocator) ListNode (((const ListNode *)(pCur))->Value());
324 PInsertBefore(pNew, theIter);