#ifndef __Tree_H__
#define __Tree_H__
#include <memory>
#include <iterator>
#include <cassert>
namespace Blaze
{
template <class T, class Alloc = std::allocator<T>>
class tree
{
public:
typedef tree<T, Alloc> TreeT;
typedef TreeT value_type;
typedef TreeT* pointer;
typedef const TreeT* const_pointer;
typedef TreeT& reference;
typedef const TreeT& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// provide special handling for non-standard VC6 allocators
#if _MSC_VER < 1300
typedef Alloc allocator_type;
#else
typedef typename Alloc::template rebind<TreeT>::other allocator_type;
#endif
class iterator;
class const_iterator;
class child_iterator;
class const_child_iterator;
tree() { init(); }
tree(const T& t) : value(t) { init(); }
tree(const TreeT& copy) : value(copy.value)
{
init();
copy_children(copy);
}
~tree() { clear(); }
const tree& operator=(const TreeT& rhs)
{
TreeT temp(rhs);
swap(temp);
return *this;
}
class iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void>
{
public:
TreeT* _ptr;
TreeT* _root;
iterator(TreeT* ptr, TreeT* root) : _ptr(ptr), _root(root) {}
friend class tree<T, Alloc>;
friend class const_iterator;
friend class child_iterator;
friend class const_child_iterator;
public:
iterator() : _ptr(0), _root(0) {}
TreeT& operator*() const {return *_ptr;}
TreeT* operator->() const {return _ptr;}
bool operator==(const iterator& rhs) const {return _ptr == rhs._ptr;}
bool operator!=(const iterator& rhs) const {return _ptr != rhs._ptr;}
iterator& operator++() {_ptr = _ptr->_next; return *this;}
iterator& operator--() {_ptr = (_ptr ? _ptr->prev() : _root->_last_descendant); return *this;}
iterator operator++(int i) { iterator temp = *this; ++*this; return temp; }
iterator operator--(int i) { iterator temp = *this; --*this; return temp; }
friend void skip(iterator& it) { it._ptr = it._ptr->next_sibling(); }
};
class const_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void>
{
protected:
const TreeT* _ptr;
const TreeT* _root;
const_iterator(const TreeT* ptr, const TreeT* root) : _ptr(ptr), _root(root) {}
friend class tree<T, Alloc>;
friend class const_child_iterator;
public:
const_iterator() : _ptr(0), _root(0) {}
const const_iterator& operator=(const const_iterator& it) {_ptr = it._ptr;_root = it._root; return *this;}
const const_iterator& operator=(const iterator& it) {_ptr = it._ptr;_root = it._root; return *this;}
const const_iterator& operator=(iterator& it) {_ptr = it._ptr;_root = it._root; return *this;}
const TreeT& operator*() const {return *_ptr;}
const TreeT* operator->() const {return _ptr;}
bool operator==(const const_iterator& rhs) const {return _ptr == rhs._ptr;}
bool operator!=(const const_iterator& rhs) const {return _ptr != rhs._ptr;}
const_iterator& operator++() {_ptr = _ptr->_next; return *this;}
const_iterator& operator--() {_ptr = (_ptr ? _ptr->prev() : _root->_last_descendant); return *this;}
const_iterator operator++(int i) { const_iterator temp = *this; ++*this; return temp; }
const_iterator operator--(int i) { const_iterator temp = *this; --*this; return temp; }
};
class child_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void>
{
public:
TreeT* _ptr;
TreeT* _root;
child_iterator(TreeT* ptr, TreeT* root) : _ptr(ptr), _root(root) {}
friend class tree<T, Alloc>;
friend class const_child_iterator;
public:
child_iterator() : _ptr(0), _root(0) {}
const child_iterator& operator=(const iterator& it){_ptr = it._ptr;_root = it._root;return *this;}
operator iterator() const { return iterator(_ptr, _root); }
TreeT& operator*() const {return *_ptr;}
TreeT* operator->() const {return _ptr;}
bool operator==(const child_iterator& rhs) const {return _ptr == rhs._ptr;}
bool operator!=(const child_iterator& rhs) const {return _ptr != rhs._ptr;}
child_iterator& operator++() {_ptr = _ptr->next_sibling(); return *this;}
child_iterator& operator--() {_ptr = (_ptr ? _ptr->prev_sibling() : _root->last_child()); return *this;}
child_iterator operator++(int i) { child_iterator temp = *this; ++*this; return temp; }
child_iterator operator--(int i) { child_iterator temp = *this; --*this; return temp; }
};
class const_child_iterator : public std::iterator<std::bidirectional_iterator_tag, value_type, void>
{
protected:
const TreeT* _ptr;
const TreeT* _root;
const_child_iterator(const TreeT* ptr, const TreeT* root) : _ptr(ptr), _root(root) {}
friend class tree<T, Alloc>;
public:
const_child_iterator() : _ptr(0), _root(0) {}
const_child_iterator(const child_iterator& it) : _ptr(it._ptr), _root(it._root) {}
const_child_iterator(const iterator& it) : _ptr(it._ptr), _root(it._root) {}
const_child_iterator(const const_iterator& it) : _ptr(it._ptr), _root(it._root) {}
operator const_iterator() const { return iterator(_ptr, _root); }
const TreeT& operator*() const {return *_ptr;}
const TreeT* operator->() const {return _ptr;}
bool operator==(const const_child_iterator& rhs) const {return _ptr == rhs._ptr;}
bool operator!=(const const_child_iterator& rhs) const {return _ptr != rhs._ptr;}
const_child_iterator& operator++() {_ptr = _ptr->next_sibling(); return *this;}
const_child_iterator& operator--() {_ptr = (_ptr ? _ptr->prev_sibling() : _root->last_child()); return *this;}
const_child_iterator operator++(int i) { const_child_iterator temp = *this; ++*this; return temp; }
const_child_iterator operator--(int i) { const_child_iterator temp = *this; --*this; return temp; }
};
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef std::reverse_iterator<child_iterator> reverse_child_iterator;
typedef std::reverse_iterator<const_child_iterator> const_reverse_child_iterator;
const_iterator begin() const {return const_iterator(this, this);}
const_iterator end() const {return const_iterator(0, this);}
iterator begin() {return iterator(this, this);}
iterator end() {return iterator(0, this);}
const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
reverse_iterator rbegin() {return reverse_iterator(end());}
reverse_iterator rend() {return reverse_iterator(begin());}
const_child_iterator begin_child() const {return const_child_iterator(first_child(), this);}
const_child_iterator end_child() const {return const_child_iterator(0, this);}
child_iterator begin_child() {return child_iterator(first_child(), this);}
child_iterator end_child() {return child_iterator(0, this);}
const_reverse_child_iterator rbegin_child() const {return const_reverse_child_iterator(end_child());}
const_reverse_child_iterator rend_child() const {return const_reverse_child_iterator(begin_child());}
reverse_child_iterator rbegin_child() {return reverse_child_iterator(end_child());}
reverse_child_iterator rend_child() {return reverse_child_iterator(begin_child());}
void push_back(const TreeT& subtree)
{
TreeT* child = create_subtree(subtree);
insert_subtree(*child, 0);
}
void push_front(const TreeT& subtree)
{
TreeT* child = create_subtree(subtree);
TreeT* next = first_child();
insert_subtree(*child, next);
}
void pop_back()
{
TreeT* last = last_child();
assert(last);
erase(iterator(last, this));
}
void pop_front()
{
TreeT* first = first_child();
assert(first);
erase
- 1
- 2
- 3
- 4
- 5
- 6
前往页