#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;
	}
}

do
ri
mi
fa
sol
la
ti
do