sequential_tree.h

C++ STL 中没有树形容器是最大的遗憾！ 还好高手总是能及时出现

	const_pre_order_node_iterator pre_order_node_begin() const { const_node_iterator it = node_begin(); return const_pre_order_node_iterator(it, this); }
	const_pre_order_node_iterator pre_order_node_end() const { const_node_iterator it = node_end(); return const_pre_order_node_iterator(it, this); }
	post_order_node_iterator post_order_node_begin() { post_order_node_iterator it(this); return it; }
	post_order_node_iterator post_order_node_end() { node_iterator it = node_end(); return post_order_node_iterator(it, this); }
	const_post_order_node_iterator post_order_node_begin() const { const_post_order_node_iterator it(this); return it; }
	const_post_order_node_iterator post_order_node_end() const { const_node_iterator it = node_end(); return const_post_order_node_iterator(it, this); }
	level_order_node_iterator level_order_node_begin() { node_iterator it = node_begin(); return level_order_node_iterator(it, this); }
	level_order_node_iterator level_order_node_end() { node_iterator it = node_end(); return level_order_node_iterator(it, this); }
	const_level_order_node_iterator level_order_node_begin() const { const_node_iterator it = node_begin(); return const_level_order_node_iterator(it, this); }
	const_level_order_node_iterator level_order_node_end() const { const_node_iterator it = node_end(); return const_level_order_node_iterator(it, this); }
	

	// public interface
	size_type capacity() const { return basic_tree_type::children.capacity(); }
	void reserve(size_type sz) { basic_tree_type::children.reserve(sz); }
	tree_type& front() { return *basic_tree_type::children.front(); }
	tree_type& back() { return *basic_tree_type::children.back(); }
	const tree_type& front() const { return *basic_tree_type::children.front(); }
	const tree_type& back() const { return *basic_tree_type::children.back(); }
	void push_back(const stored_type& value);
	void pop_back() { iterator it = end(); erase(--it); }

	iterator insert(const stored_type& value);
	iterator insert(const tree_type& tree_obj );
	iterator insert(const_iterator pos, const stored_type& value);
	iterator insert(const_iterator pos, const tree_type& tree_obj);
	void insert(const_iterator pos, size_type num, const stored_type& value);
	#if !defined(_MSC_VER) || _MSC_VER >= 1300 // insert range not available for VC6
	template<typename iterator_type> void insert(const_iterator pos, iterator_type it_beg, iterator_type it_end) 
	{ while (it_beg != it_end) { pos = insert(pos, *it_beg++); ++pos; } }
	#endif
	void set(const stored_type& value) { basic_tree_type::set(value); }
	void set(const tree_type& tree_obj);
	void swap(tree_type& rhs);
	iterator erase(iterator it);
	iterator erase(iterator beg_it, iterator end_it);
	void clear();

	// subscript operators
	tree_type& operator [](size_type index);
	const tree_type& operator [](size_type index) const; 

	// overloaded operations
	bool operator == (const tree_type& rhs) const;
	bool operator < (const tree_type& rhs) const;
	bool operator != (const tree_type& rhs) const { return !(*this == rhs); }
	bool operator > (const tree_type& rhs) const { return rhs < *this; }
	bool operator <= (const tree_type& rhs) const { return !(rhs < *this); }
	bool operator >= (const tree_type& rhs) const { return !(*this < rhs); }

	// children sort operations
	template<typename T> void sort(const T& comparer) { std::sort(basic_tree_type::children.begin(), basic_tree_type::children.end(), sort_functor_deref<T>(comparer)); }
	void sort() { std::sort(basic_tree_type::children.begin(), basic_tree_type::children.end(), sort_deref()); }

	// descendant sort operations
	template<typename T> void sort_descendants(const T& comparer)
	{
		sort(comparer);
		post_order_iterator it = post_order_begin(), it_end = post_order_end();
		for ( ; it != it_end; ++it )
		{
			it.node()->sort(comparer);
		}
	}
	void sort_descendants(); 

	// overloaded iterator arithmetic operators
	friend const_iterator operator +(const const_iterator& lhs, size_type n) 
	{ const_iterator temp(lhs); temp += n; return temp; }

	friend const_iterator operator +(size_type n, const const_iterator& rhs)
	{ const_iterator temp(rhs); temp += n; return temp; }

	friend const_iterator operator -(const const_iterator& lhs, size_type n)
	{ const_iterator temp(lhs); temp -= n; return temp; }

	friend iterator operator +(const iterator& lhs, size_type n)
	{ iterator temp(lhs); temp += n; return temp; }

	friend iterator operator +(size_type n, const iterator& rhs)
	{ iterator temp(rhs); temp += n; return temp; }

	friend iterator operator -(const iterator& lhs, size_type n)
	{ iterator temp(lhs); temp -= n; return temp; }

	// overloaded node iterator arithmetic operators
	friend const_node_iterator operator +(const const_node_iterator& lhs, size_type n) 
	{ const_node_iterator temp(lhs); temp += n; return temp; }

	friend const_node_iterator operator +(size_type n, const const_node_iterator& rhs)
	{ const_node_iterator temp(rhs); temp += n; return temp; }

	friend const_node_iterator operator -(const const_node_iterator& lhs, size_type n)
	{ const_node_iterator temp(lhs); temp -= n; return temp; }

	friend node_iterator operator +(const node_iterator& lhs, size_type n)
	{ node_iterator temp(lhs); temp += n; return temp; }

	friend node_iterator operator +(size_type n, const node_iterator& rhs)
	{ node_iterator temp(rhs); temp += n; return temp; }

	friend node_iterator operator -(const node_iterator& lhs, size_type n)
	{ node_iterator temp(lhs); temp -= n; return temp; }


private:
	// sort() dereference functor
	struct sort_deref
	{
		bool operator() (const tree_type* lhs, const tree_type* rhs)
		{
			return *lhs->get() < *rhs->get();
		}
	};

	// sort<T>() dereference functor
	template<typename T>
	struct sort_functor_deref 
	{
		explicit sort_functor_deref(const T& sort_functor_) : sort_functor(sort_functor_) {}
		bool operator() (const tree_type* lhs, const tree_type* rhs) const
		{
			return sort_functor(*lhs->get(), *rhs->get());
		}
		sort_functor_deref& operator = (const sort_functor_deref& rhs) { sort_functor = rhs->sort_functor; return *this; }
		const T& sort_functor;
	};
};




#include "sequential_tree.inl"