codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#define nullptr 0 #define EVER ;; #define IMPLEMENTS : #define INITIALIZER_LIST : //#pragma warning(disable : 4290) template <typename T> class shrub { // Types. private: class Wood { friend class shrub<T>; // Types. private: enum ChildType { ROOT, LEFTCHILD, RIGHTCHILD }; enum WoodType { FIRSTLEAF, LASTLEAF, FORK, MIDDLELEAF }; union TypeOrData { WoodType Type; T* Data; }; union LeafOrChild { Wood* Child; Wood* Leaf; }; // Private members. private: // For everyone. Wood* Parent; ChildType TypeOfChild; TypeOrData TheWood; LeafOrChild Left; LeafOrChild Right; // For forks. unsigned int NumberOfLeavesToTheLeft; unsigned int NumberOfLeavesToTheRight; // Constructor, copy constructor, assignment operator, destructor. private: Wood() { } ~Wood() { if(TheWood.Type >= MIDDLELEAF) { delete TheWood.Data; } } // Private methods. private: void Burn() { if(TheWood.Type == FORK) { Right.Child->Burn(); Left.Child->Burn(); } delete this; } }; typedef size_t size_type; public: class const_iterator IMPLEMENTS public std::iterator<std::bidirectional_iterator_tag, T> { friend class shrub<T>; // Private members. private: Wood* CurrentLeaf; // The public constructor. public: const_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: const_iterator(Wood* Leaf) { CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: T& operator*() { return *CurrentLeaf->TheWood.Data; } const_iterator& operator++() { CurrentLeaf = CurrentLeaf->Right.Leaf; return *this; } const_iterator& operator--() { CurrentLeaf = CurrentLeaf->Left.Leaf; return *this; } bool operator==(const const_iterator& rhs) { return CurrentLeaf == rhs.CurrentLeaf; } bool operator!=(const const_iterator& rhs) { return CurrentLeaf != rhs.CurrentLeaf; } }; class const_checked_iterator IMPLEMENTS virtual public const_iterator { friend class shrub<T>; // Constructor, copy constructor, assignment operator, destructor. public: const_checked_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: const_checked_iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: const T& operator*() { if(const_iterator::CurrentLeaf->TheWood.Type >= Wood::MIDDLELEAF) { return *const_iterator::CurrentLeaf->TheWood.Data; } else { throw iterator_exception(*this, "Attempt to dereference a past-the-end iterator."); } } const_checked_iterator& operator++() { if(const_iterator::CurrentLeaf->TheWood.Type != Wood::LASTLEAF) { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; return *this; } else { throw iterator_exception(*this, "Attempt to increment an iterator past end()."); } } const_checked_iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; if(const_iterator::CurrentLeaf->TheWood.Type != Wood::FIRSTLEAF) { return *this; } else { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; throw iterator_exception(*this, "Attempt to decrement an iterator past begin()."); } } }; class iterator IMPLEMENTS virtual public const_iterator { friend class shrub<T>; // The public constructor. public: iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: T& operator*() { return *const_iterator::CurrentLeaf->TheWood.Data; } iterator& operator++() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; return *this; } iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; return *this; } }; class const_reverse_iterator IMPLEMENTS virtual public const_iterator { friend class shrub<T>; // The public constructor. public: const_reverse_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: const_reverse_iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: const T& operator*() { return *const_iterator::CurrentLeaf->TheWood.Data; } const_reverse_iterator& operator++() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; return *this; } const_reverse_iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; return *this; } }; class const_checked_reverse_iterator IMPLEMENTS public const_checked_iterator, public const_reverse_iterator { friend class shrub<T>; // The public constructor. public: const_checked_reverse_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: const_checked_reverse_iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: const T& operator*() { if(const_iterator::CurrentLeaf->TheWood.Type >= Wood::MIDDLELEAF) { return *const_iterator::CurrentLeaf->TheWood.Data; } else { throw iterator_exception(*this, "Attempt to dereference a past-the-end iterator."); } } const_checked_reverse_iterator& operator++() { if(const_iterator::CurrentLeaf->TheWood.Type != Wood::FIRSTLEAF) { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; return *this; } else { throw iterator_exception(*this, "Attempt to increment an iterator past rend()."); } } const_checked_reverse_iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; if(const_iterator::CurrentLeaf->TheWood.Type != Wood::LASTLEAF) { return *this; } else { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; throw iterator_exception(*this, "Attempt to decrement an iterator past rbegin()."); } } }; class checked_iterator IMPLEMENTS virtual public iterator, virtual public const_checked_iterator { friend class shrub<T>; // The public constructor. public: checked_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: checked_iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: T& operator*() { if(const_iterator::CurrentLeaf->TheWood.Type >= Wood::MIDDLELEAF) { return *const_iterator::CurrentLeaf->TheWood.Data; } else { throw iterator_exception(*this, "Attempt to dereference a past-the-end iterator."); } } checked_iterator& operator++() { if(const_iterator::CurrentLeaf->TheWood.Type != Wood::LASTLEAF) { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; return *this; } else { throw iterator_exception(*this, "Attempt to increment an iterator past end()."); } } checked_iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; if(const_iterator::CurrentLeaf->TheWood.Type != Wood::FIRSTLEAF) { return *this; } else { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; throw iterator_exception(*this, "Attempt to decrement an iterator past begin()."); } } }; class reverse_iterator IMPLEMENTS virtual public iterator, virtual public const_reverse_iterator { friend class shrub<T>; // The public constructor. public: reverse_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: reverse_iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: T& operator*() { return *const_iterator::CurrentLeaf->TheWood.Data; } reverse_iterator& operator++() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; return *this; } reverse_iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; return *this; } }; class checked_reverse_iterator IMPLEMENTS public checked_iterator, public reverse_iterator { friend class shrub<T>; // The public constructor. public: checked_reverse_iterator() { } // Only methods of shrub, which is a friend of iterator, should call this. private: checked_reverse_iterator(Wood* Leaf) { const_iterator::CurrentLeaf = Leaf; } // The public methods of a bidirectional iterator. public: T& operator*() { if(const_iterator::CurrentLeaf->TheWood.Type >= Wood::MIDDLELEAF) { return *const_iterator::CurrentLeaf->TheWood.Data; } else { throw iterator_exception(*this, "Attempt to dereference a past-the-end iterator."); } } checked_reverse_iterator& operator++() { if(const_iterator::CurrentLeaf->TheWood.Type != Wood::FIRSTLEAF) { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; return *this; } else { throw iterator_exception(*this, "Attempt to increment an iterator past rend()."); } } checked_reverse_iterator& operator--() { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Right.Leaf; if(const_iterator::CurrentLeaf->TheWood.Type != Wood::LASTLEAF) { return *this; } else { const_iterator::CurrentLeaf = const_iterator::CurrentLeaf->Left.Leaf; throw iterator_exception(*this, "Attempt to decrement an iterator past rbegin()."); } } }; class iterator_exception { const_checked_iterator ThrownIterator; const char* Message; // Constructor, copy constructor, assignment operator, destructor. public: iterator_exception(const const_checked_iterator& PassedIterator, const char* PassedMessage) INITIALIZER_LIST ThrownIterator(PassedIterator), Message(PassedMessage) { } }; // Private members. private: Wood* Root; Wood* FirstLeaf; Wood* LastLeaf; size_type ShrubSize; // Constructor, copy constructor, assignment operator, destructor. public: shrub() throw() { Construct(); } shrub(const shrub<T>& ShrubToCopyFrom) throw() { Construct(); iterator Iter = ShrubToCopyFrom.begin(); while(Iter != ShrubToCopyFrom.end()) { push_back(*Iter); ++Iter; } } void operator=(const shrub<T>& ShrubToCopyFrom) throw() { clear(); iterator Iter = ShrubToCopyFrom.begin(); while(Iter != ShrubToCopyFrom.end()) { push_back(*Iter); ++Iter; } } ~shrub() throw() { Root->Burn(); } // Private methods. private: void Construct() { Root = new Wood; FirstLeaf = new Wood; LastLeaf = new Wood; Root->Parent = nullptr; Root->TypeOfChild = Wood::ROOT; Root->TheWood.Type = Wood::FORK; Root->Left.Child = FirstLeaf; Root->Right.Child = LastLeaf; Root->NumberOfLeavesToTheRight = 1; Root->NumberOfLeavesToTheLeft = 1; FirstLeaf->Parent = Root; FirstLeaf->TypeOfChild = Wood::LEFTCHILD; FirstLeaf->TheWood.Type = Wood::FIRSTLEAF; FirstLeaf->Left.Leaf = nullptr; FirstLeaf->Right.Leaf = LastLeaf; LastLeaf->Parent = Root; LastLeaf->TypeOfChild = Wood::RIGHTCHILD; LastLeaf->TheWood.Type = Wood::LASTLEAF; LastLeaf->Left.Leaf = FirstLeaf; LastLeaf->Right.Leaf = nullptr; ShrubSize = 0; } void UpdateShrub(Wood* Crawler) { for(EVER) { if(Crawler->TypeOfChild == Wood::LEFTCHILD) { Crawler = Crawler->Parent; Crawler->NumberOfLeavesToTheLeft = Crawler->Left.Child->NumberOfLeavesToTheLeft + Crawler->Left.Child->NumberOfLeavesToTheRight; } else if (Crawler->TypeOfChild == Wood::RIGHTCHILD) { Crawler = Crawler->Parent; Crawler->NumberOfLeavesToTheRight = Crawler->Right.Child->NumberOfLeavesToTheLeft + Crawler->Right.Child->NumberOfLeavesToTheRight; } else { break; } if(Crawler->NumberOfLeavesToTheLeft > Crawler->NumberOfLeavesToTheRight) { RotateRight(Crawler); Crawler = Crawler->Parent; } else if(Crawler->NumberOfLeavesToTheRight > Crawler->NumberOfLeavesToTheLeft) { RotateLeft(Crawler); Crawler = Crawler->Parent; } else { continue; } } } void RotateLeft(Wood* ForkToMoveLeft) { Wood* ForkToMoveUp = ForkToMoveLeft->Right.Child; // Step #1: Update the leaf counts. ForkToMoveLeft->NumberOfLeavesToTheRight -= ForkToMoveUp->NumberOfLeavesToTheRight; ForkToMoveUp->NumberOfLeavesToTheLeft += ForkToMoveLeft->NumberOfLeavesToTheLeft; // Step #2: Update TypeOfChild for all the items that are being moved. ForkToMoveUp->TypeOfChild = ForkToMoveLeft->TypeOfChild; ForkToMoveLeft->TypeOfChild = Wood::LEFTCHILD; ForkToMoveUp->Left.Child->TypeOfChild = Wood::RIGHTCHILD; // Step #3: Move ForkToMoveUp up. ForkToMoveUp->Parent = ForkToMoveLeft->Parent; if(ForkToMoveUp->TypeOfChild == Wood::LEFTCHILD) { ForkToMoveLeft->Parent->Left.Child = ForkToMoveUp; } else if(ForkToMoveUp->TypeOfChild == Wood::RIGHTCHILD) { ForkToMoveLeft->Parent->Right.Child = ForkToMoveUp; } else { Root = ForkToMoveUp; } // Step #4: Have ForkToMoveLeft take ForkToMoveUp's left child. ForkToMoveLeft->Right.Child = ForkToMoveUp->Left.Child; ForkToMoveLeft->Right.Child->Parent = ForkToMoveLeft; // Step #5: Make ForkToMoveUp's new left child be ForkToMoveLeft. ForkToMoveUp->Left.Child = ForkToMoveLeft; ForkToMoveUp->Left.Child->Parent = ForkToMoveUp; } void RotateRight(Wood* ForkToMoveRight) { Wood* ForkToMoveUp = ForkToMoveRight->Left.Child; // Step #1: Update the leaf counts. ForkToMoveRight->NumberOfLeavesToTheLeft -= ForkToMoveUp->NumberOfLeavesToTheLeft; ForkToMoveUp->NumberOfLeavesToTheRight += ForkToMoveRight->NumberOfLeavesToTheRight; // Step #2: Update TypeOfChild for all the items that are being moved. ForkToMoveUp->TypeOfChild = ForkToMoveRight->TypeOfChild; ForkToMoveRight->TypeOfChild = Wood::RIGHTCHILD; ForkToMoveUp->Right.Child->TypeOfChild = Wood::LEFTCHILD; // Step #3: Move ForkToMoveUp up. ForkToMoveUp->Parent = ForkToMoveRight->Parent; if(ForkToMoveUp->TypeOfChild == Wood::RIGHTCHILD) { ForkToMoveRight->Parent->Right.Child = ForkToMoveUp; } else if(ForkToMoveUp->TypeOfChild == Wood::LEFTCHILD) { ForkToMoveRight->Parent->Left.Child = ForkToMoveUp; } else { Root = ForkToMoveUp; } // Step #4: Have ForkToMoveRight take ForkToMoveUp's right child. ForkToMoveRight->Left.Child = ForkToMoveUp->Right.Child; ForkToMoveRight->Left.Child->Parent = ForkToMoveRight; // Step #5: Make ForkToMoveUp's new right child be ForkToMoveRight. ForkToMoveUp->Right.Child = ForkToMoveRight; ForkToMoveUp->Right.Child->Parent = ForkToMoveUp; } // Public methods. public: size_type size() const throw() { return ShrubSize; } bool empty() const throw() { if(ShrubSize == 0) { return true; } else { return false; } } const_checked_iterator position(size_type Index) const throw(iterator_exception) { // Will return end() if the index is out of bounds. Wood* Crawler = Root; // To compensate for the dummy nodes. ++Index; while(Crawler->TheWood.Type == Wood::FORK) { if(Crawler->NumberOfLeavesToTheLeft > Index) { Crawler = Crawler->Left.Child; } else { Index -= Crawler->NumberOfLeavesToTheLeft; Crawler = Crawler->Right.Child; } } return checked_iterator(Crawler); } const_checked_iterator begin() const throw(iterator_exception) { return checked_iterator(FirstLeaf->Right.Leaf); } const_checked_iterator end() const throw(iterator_exception) { return checked_iterator(LastLeaf); } checked_iterator position(size_type Index) throw(iterator_exception) { // Will return end() if the index is out of bounds. Wood* Crawler = Root; // To compensate for the dummy nodes. ++Index; while(Crawler->TheWood.Type == Wood::FORK) { if(Crawler->NumberOfLeavesToTheLeft > Index) { Crawler = Crawler->Left.Child; } else { Index -= Crawler->NumberOfLeavesToTheLeft; Crawler = Crawler->Right.Child; } } return checked_iterator(Crawler); } checked_iterator begin() throw(iterator_exception) { return checked_iterator(FirstLeaf->Right.Leaf); } checked_iterator end() throw(iterator_exception) { return checked_iterator(LastLeaf); } const_checked_reverse_iterator rposition(size_type Index) const throw(iterator_exception) { // Will return rend() if the index is out of bounds. Wood* Crawler = Root; // To compensate for the dummy nodes. ++Index; while(Crawler->TheWood.Type == Wood::FORK) { if(Crawler->NumberOfLeavesToTheRight > Index) { Crawler = Crawler->Right.Child; } else { Index -= Crawler->NumberOfLeavesToTheRight; Crawler = Crawler->Left.Child; } } return checked_reverse_iterator(Crawler); } const_checked_reverse_iterator rbegin() const throw(iterator_exception) { return checked_reverse_iterator(LastLeaf->Left.Leaf); } const_checked_reverse_iterator rend() const throw(iterator_exception) { return checked_reverse_iterator(FirstLeaf); } checked_reverse_iterator rposition(size_type Index) throw(iterator_exception) { // Will return rend() if the index is out of bounds. Wood* Crawler = Root; // To compensate for the dummy nodes. ++Index; while(Crawler->TheWood.Type == Wood::FORK) { if(Crawler->NumberOfLeavesToTheRight > Index) { Crawler = Crawler->Right.Child; } else { Index -= Crawler->NumberOfLeavesToTheRight; Crawler = Crawler->Left.Child; } } return checked_reverse_iterator(Crawler); } checked_reverse_iterator rbegin() throw(iterator_exception) { return checked_reverse_iterator(LastLeaf->Left.Leaf); } checked_reverse_iterator rend() throw(iterator_exception) { return checked_reverse_iterator(FirstLeaf); } T& at(size_type Index) throw(iterator_exception) { return *position(Index); } const T& at(size_type Index) const throw(iterator_exception) { return *position(Index); } T& front() throw(iterator_exception) { return *checked_iterator(FirstLeaf->Right.Leaf); } const T& front() const throw(iterator_exception) { return *const_checked_iterator(FirstLeaf->Right.Leaf); } T& back() throw(iterator_exception) { return *checked_iterator(LastLeaf->Left.Leaf); } const T& back() const throw(iterator_exception) { return *const_checked_iterator(LastLeaf->Left.Leaf); } iterator insert(iterator Position, const T& DataToInsert) throw(iterator_exception) { Wood* LeafToInsert = new Wood; Wood* ForkToInsert = new Wood; // Step #1: Fill LeafToInsert with data. LeafToInsert->Parent = ForkToInsert; LeafToInsert->TypeOfChild = Wood::LEFTCHILD; LeafToInsert->TheWood.Data = new T(DataToInsert); LeafToInsert->Right.Leaf = Position.CurrentLeaf; LeafToInsert->Left.Leaf = Position.CurrentLeaf->Left.Leaf; // Step #2: Make LeafToInsert's neighbors point back to LeafToInsert. LeafToInsert->Right.Leaf->Left.Leaf = LeafToInsert; LeafToInsert->Left.Leaf->Right.Leaf = LeafToInsert; // Step #3: Place ForkToInsert where LeafToInsert's sibling used to be. if(LeafToInsert->Right.Leaf->TypeOfChild == Wood::LEFTCHILD) { LeafToInsert->Right.Leaf->Parent->Left.Child = ForkToInsert; } else if(LeafToInsert->Right.Leaf->TypeOfChild == Wood::RIGHTCHILD) { LeafToInsert->Right.Leaf->Parent->Right.Child = ForkToInsert; } else { Root = ForkToInsert; } // Step #4: Fill ForkToInsert with data. ForkToInsert->Parent = LeafToInsert->Right.Leaf->Parent; ForkToInsert->TypeOfChild = LeafToInsert->Right.Leaf->TypeOfChild; ForkToInsert->TheWood.Type = Wood::FORK; ForkToInsert->Left.Child = LeafToInsert; ForkToInsert->Right.Child = LeafToInsert->Right.Leaf; ForkToInsert->NumberOfLeavesToTheLeft = 1; ForkToInsert->NumberOfLeavesToTheRight = 1; // Step #5: Update LeafToInsert's sibling. Position.CurrentLeaf->Parent = ForkToInsert; Position.CurrentLeaf->TypeOfChild = Wood::RIGHTCHILD; // Step #6: Ensure that the shrub stays balanced. UpdateShrub(ForkToInsert); // Step #7: Update Size. ++ShrubSize; return iterator(LeafToInsert); } void push_front(const T& DataToInsert) throw(iterator_exception) { insert(iterator(FirstLeaf->Right.Leaf), DataToInsert); } void push_back(const T& DataToInsert) throw(iterator_exception) { insert(iterator(LastLeaf), DataToInsert); } iterator erase(iterator Position) throw(iterator_exception) { Wood* LeafToDelete = Position.CurrentLeaf; Wood* MoveMeUp; iterator ReturnValue = iterator(LeafToDelete->Right.Leaf); // Step #1: Update the leaves pointing to LeafToDelete. LeafToDelete->Right.Leaf->Left.Leaf = LeafToDelete->Left.Leaf; LeafToDelete->Left.Leaf->Right.Leaf = LeafToDelete->Right.Leaf; // Step #2: The piece of wood we want to move up is LeafToDelete's sibling. if(LeafToDelete->TypeOfChild == Wood::LEFTCHILD) { MoveMeUp = LeafToDelete->Parent->Right.Child; } else if(LeafToDelete->TypeOfChild == Wood::RIGHTCHILD) { MoveMeUp = LeafToDelete->Parent->Left.Child; } else { // Will never be reached, because a leaf with data can never be the root. return ReturnValue; } // Step #3: Make MoveMeUp's TypeOfChild the TypeOfChild of the fork it's replacing. MoveMeUp->TypeOfChild = MoveMeUp->Parent->TypeOfChild; // Step #4: Make MoveMeUp's parent the parent of the fork it's replacing. MoveMeUp->Parent = MoveMeUp->Parent->Parent; // Step #5: MoveMeUp up and update its parent's NumberOfLeavesToThe(Left/Right). if(MoveMeUp->TypeOfChild == Wood::LEFTCHILD) { MoveMeUp->Parent->Left.Child = MoveMeUp; if(MoveMeUp->TheWood.Type != Wood::FORK) { MoveMeUp->Parent->NumberOfLeavesToTheLeft = 1; } else { MoveMeUp->Parent->NumberOfLeavesToTheLeft = MoveMeUp->NumberOfLeavesToTheLeft + MoveMeUp->NumberOfLeavesToTheRight; } } else if(LeafToDelete->Parent->TypeOfChild == Wood::RIGHTCHILD) { MoveMeUp->Parent->Right.Child = MoveMeUp; if(MoveMeUp->TheWood.Type != Wood::FORK) { MoveMeUp->Parent->NumberOfLeavesToTheRight = 1; } else { MoveMeUp->Parent->NumberOfLeavesToTheRight = MoveMeUp->NumberOfLeavesToTheLeft + MoveMeUp->NumberOfLeavesToTheRight; } } else { Root = MoveMeUp; } // Step #6: Delete LeafToDelete and its parent. delete LeafToDelete->Parent; delete LeafToDelete; // Step #7: Ensure that the shrub stays balanced. if(MoveMeUp->TypeOfChild != Wood::ROOT) { UpdateShrub(MoveMeUp->Parent); } // Step #8: Update Size. --ShrubSize; return ReturnValue; } void pop_front() throw(iterator_exception) { erase(iterator(FirstLeaf->Right.Leaf)); } void pop_back() throw(iterator_exception) { erase(iterator(LastLeaf->Left.Leaf)); } void clear() throw() { Root->Burn(); Construct(); } void swap(shrub<T>& ShrubToSwapWith) throw() { union WoodOrSize { Wood* Pointer; size_type Size; }; WoodOrSize Temp; Temp.Pointer = Root; Root = ShrubToSwapWith.Root; ShrubToSwapWith.Root = Temp.Pointer; Temp.Pointer = FirstLeaf; FirstLeaf = ShrubToSwapWith.FirstLeaf; ShrubToSwapWith.FirstLeaf = Temp.Pointer; Temp.Pointer = LastLeaf; LastLeaf = ShrubToSwapWith.LastLeaf; ShrubToSwapWith.LastLeaf = Temp.Pointer; Temp.Size = ShrubSize; ShrubSize = ShrubToSwapWith.ShrubSize; ShrubToSwapWith.ShrubSize = Temp.Size; } }; int main() { shrub<std::string> TestShrub; TestShrub.push_back("do"); TestShrub.push_back("ri"); TestShrub.push_back("mi"); TestShrub.push_back("fa"); TestShrub.push_back("sol"); TestShrub.push_back("la"); TestShrub.push_back("ti"); TestShrub.push_back("do"); shrub<std::string>::iterator Iter = TestShrub.begin(); while(Iter != TestShrub.end()) { std::cout << *Iter << std::endl; ++Iter; } }
Private
[
?
]
Run code
Submit