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 ------------
61 //! Empty constructor.
62 NCollection_List() : NCollection_BaseList(Handle(NCollection_BaseAllocator)()) {}
65 explicit NCollection_List(const Handle(NCollection_BaseAllocator)& theAllocator) : NCollection_BaseList(theAllocator) {}
68 NCollection_List (const NCollection_List& theOther) :
69 NCollection_BaseList(theOther.myAllocator)
74 //! Size - Number of items
75 Standard_Integer Size (void) const
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)
82 if (this != &theOther) {
84 appendList(theOther.PFirst());
89 //! Replacement operator
90 NCollection_List& operator= (const NCollection_List& theOther)
92 return Assign (theOther);
96 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator=0L)
98 PClear (ListNode::delNode);
99 if (!theAllocator.IsNull())
100 this->myAllocator = theAllocator;
104 const TheItemType& First (void) const
106 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
107 return ((const ListNode *) PFirst())->Value();
110 //! First item (non-const)
111 TheItemType& First (void)
113 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::First");
114 return ((ListNode *) PFirst())->ChangeValue();
118 const TheItemType& Last (void) const
120 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
121 return ((const ListNode *) PLast())->Value();
124 //! Last item (non-const)
125 TheItemType& Last (void)
127 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_List::Last");
128 return ((ListNode *) PLast())->ChangeValue();
131 //! Append one item at the end
132 TheItemType& Append (const TheItemType& theItem)
134 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
136 return ((ListNode *) PLast())->ChangeValue();
139 //! Append one item at the end and output iterator
140 //! pointing at the appended item
141 void Append (const TheItemType& theItem, Iterator& theIter)
143 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
144 PAppend(pNew, theIter);
147 //! Append another list at the end
148 void Append (NCollection_List& theOther)
150 if (this == &theOther || theOther.Extent()<1)
152 if (this->myAllocator == theOther.myAllocator)
154 // Then we take the list and glue it to our end -
155 // deallocation will bring no problem
160 // No - this list has different memory scope
161 appendList(theOther.myFirst);
166 //! Prepend one item at the beginning
167 TheItemType& Prepend (const TheItemType& theItem)
169 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
171 return ((ListNode *) PFirst())->ChangeValue();
174 //! Prepend another list at the beginning
175 void Prepend (NCollection_List& theOther)
177 if (this == &theOther || theOther.Extent()<1)
179 if (this->myAllocator == theOther.myAllocator)
181 // Then we take the list and glue it to our head -
182 // deallocation will bring no problem
187 // No - this list has different memory scope
189 prependList(theOther.PFirst(), it);
195 void RemoveFirst (void)
196 { PRemoveFirst (ListNode::delNode); }
198 //! Remove item pointed by iterator theIter;
199 //! theIter is then set to the next item
200 void Remove (Iterator& theIter)
202 PRemove (theIter, ListNode::delNode);
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)
209 for (Iterator anIter (*this); anIter.More(); anIter.Next())
211 if (anIter.Value() == theObject)
214 return Standard_True;
217 return Standard_False;
221 TheItemType& InsertBefore (const TheItemType& theItem,
224 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
225 PInsertBefore (pNew, theIter);
226 return pNew -> ChangeValue();
230 void InsertBefore (NCollection_List& theOther,
233 if (this == &theOther)
236 if (this->myAllocator == theOther.myAllocator)
238 // Then we take the list and glue it to our head -
239 // deallocation will bring no problem
240 PInsertBefore (theOther, theIter);
244 // No - this list has different memory scope
245 prependList(theOther.myFirst, theIter);
251 TheItemType& InsertAfter (const TheItemType& theItem,
254 ListNode * pNew = new (this->myAllocator) ListNode(theItem);
255 PInsertAfter (pNew, theIter);
256 return pNew -> ChangeValue();
260 void InsertAfter (NCollection_List& theOther,
268 if (this->myAllocator == theOther.myAllocator)
270 // Then we take the list and glue it to our head -
271 // deallocation will bring no problem
272 PInsertAfter (theOther, theIter);
276 // No - this list has different memory scope
277 Standard_NoSuchObject_Raise_if (!theIter.More(), "NCollection_List::InsertAfter");
280 anIter.myPrevious = theIter.myCurrent;
281 anIter.myCurrent = theIter.myCurrent->Next();
282 prependList(theOther.PFirst(), anIter);
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
295 for (Iterator anIter (*this); anIter.More(); anIter.Next())
297 if (anIter.Value() == theObject)
299 return Standard_True;
302 return Standard_False;
305 //! Destructor - clears the List
306 virtual ~NCollection_List (void)
310 // ----------- PRIVATE METHODS -----------
312 //! append the list headed by the given ListNode
313 void appendList(const NCollection_ListNode * pCur) {
315 NCollection_ListNode * pNew =
316 new (this->myAllocator) ListNode(((const ListNode *)(pCur))->Value());
322 //! insert the list headed by the given ListNode before the given iterator
323 void prependList(const NCollection_ListNode * pCur, Iterator& theIter) {
325 NCollection_ListNode * pNew =
326 new (this->myAllocator) ListNode (((const ListNode *)(pCur))->Value());
327 PInsertBefore(pNew, theIter);