blob: f015ac82568ce7df968d30a75d398589248853dd [file] [log] [blame]
//===- BinTree.h ----------------------------------------------------------===//
//
// The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef MCLD_BINARY_TREE_H
#define MCLD_BINARY_TREE_H
#ifdef ENABLE_UNITTEST
#include <gtest.h>
#endif
#include "mcld/ADT/Uncopyable.h"
#include "mcld/ADT/TreeAllocator.h"
#include <cstddef>
#include <iterator>
#include <memory>
#include <queue>
#include <stack>
namespace mcld
{
template<class DataType>
class BinaryTree;
class DFSIterator : public TreeIteratorBase
{
public:
DFSIterator()
: TreeIteratorBase()
{ }
DFSIterator(NodeBase *X)
: TreeIteratorBase(X) {
if (hasRightChild())
m_Stack.push(m_pNode->right);
if (hasLeftChild())
m_Stack.push(m_pNode->left);
}
virtual ~DFSIterator()
{ }
void advance() {
if (m_Stack.empty()) { // reach the end
m_pNode = m_pNode->right; // should be root
return;
}
m_pNode = m_Stack.top();
m_Stack.pop();
if (hasRightChild())
m_Stack.push(m_pNode->right);
if (hasLeftChild())
m_Stack.push(m_pNode->left);
}
private:
std::stack<NodeBase *> m_Stack;
};
class BFSIterator : public TreeIteratorBase
{
public:
BFSIterator()
: TreeIteratorBase()
{ }
BFSIterator(NodeBase *X)
: TreeIteratorBase(X) {
if (hasRightChild())
m_Queue.push(m_pNode->right);
if (hasLeftChild())
m_Queue.push(m_pNode->left);
}
virtual ~BFSIterator()
{ }
void advance() {
if (m_Queue.empty()) { // reach the end
m_pNode = m_pNode->right; // should be root
return;
}
m_pNode = m_Queue.front();
m_Queue.pop();
if (hasRightChild())
m_Queue.push(m_pNode->right);
if (hasLeftChild())
m_Queue.push(m_pNode->left);
}
private:
std::queue<NodeBase *> m_Queue;
};
template<class DataType, class Traits, class IteratorType>
class PolicyIteratorBase : public IteratorType
{
public:
typedef DataType value_type;
typedef Traits traits;
typedef typename traits::pointer pointer;
typedef typename traits::reference reference;
typedef PolicyIteratorBase<value_type, Traits, IteratorType> Self;
typedef Node<value_type> node_type;
typedef typename traits::nonconst_traits nonconst_traits;
typedef PolicyIteratorBase<value_type, nonconst_traits, IteratorType> iterator;
typedef typename traits::const_traits const_traits;
typedef PolicyIteratorBase<value_type, const_traits, IteratorType> const_iterator;
typedef std::forward_iterator_tag iterator_category;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public:
PolicyIteratorBase()
: IteratorType() {}
PolicyIteratorBase(const iterator &X)
: IteratorType(X.m_pNode) {}
explicit PolicyIteratorBase(NodeBase* X)
: IteratorType(X) {}
virtual ~PolicyIteratorBase() {}
// ----- operators ----- //
pointer operator*() const
{ return static_cast<node_type*>(IteratorType::m_pNode)->data; }
reference operator->() const
{ return *static_cast<node_type*>(IteratorType::m_pNode)->data; }
bool hasData() const
{ return (!IteratorType::isRoot() && (0 != static_cast<node_type*>(IteratorType::m_pNode)->data)); }
};
template<class DataType, class Traits, class IteratorType>
class PolicyIterator : public PolicyIteratorBase<DataType, Traits, IteratorType>
{
public:
typedef PolicyIterator<DataType, Traits, IteratorType> Self;
typedef PolicyIteratorBase<DataType, Traits, IteratorType> Base;
typedef PolicyIterator<DataType, typename Traits::nonconst_traits, IteratorType> iterator;
typedef PolicyIterator<DataType, typename Traits::const_traits, IteratorType> const_iterator;
public:
PolicyIterator()
: Base() {}
PolicyIterator(const iterator &X)
: Base(X.m_pNode) {}
explicit PolicyIterator(NodeBase* X)
: Base(X) {}
virtual ~PolicyIterator() {}
Self& operator++() {
IteratorType::advance();
return *this;
}
Self operator++(int) {
Self tmp = *this;
IteratorType::advance();
return tmp;
}
};
template<class DataType>
class BinaryTree;
/** \class TreeIterator
* \brief TreeIterator provides full functions of binary tree's iterator.
*
* TreeIterator is designed to compatible with STL iterators.
* TreeIterator is bi-directional. Incremental direction means to move
* rightward, and decremental direction is leftward.
*
* @see TreeIteratorBase
*/
template<class DataType, class Traits>
struct TreeIterator : public TreeIteratorBase
{
public:
typedef DataType value_type;
typedef Traits traits;
typedef typename traits::pointer pointer;
typedef typename traits::reference reference;
typedef TreeIterator<value_type, Traits> Self;
typedef Node<value_type> node_type;
typedef typename traits::nonconst_traits nonconst_traits;
typedef TreeIterator<value_type, nonconst_traits> iterator;
typedef typename traits::const_traits const_traits;
typedef TreeIterator<value_type, const_traits> const_iterator;
typedef std::bidirectional_iterator_tag iterator_category;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public:
TreeIterator()
: TreeIteratorBase() {}
TreeIterator(const iterator &X)
: TreeIteratorBase(X.m_pNode) {}
~TreeIterator() {}
// ----- operators ----- //
pointer operator*() const
{ return static_cast<node_type*>(m_pNode)->data; }
reference operator->() const
{ return *static_cast<node_type*>(m_pNode)->data; }
bool isRoot() const
{ return (m_pNode->right == m_pNode); }
bool hasData() const
{ return (!isRoot() && (0 != static_cast<node_type*>(m_pNode)->data)); }
Self& operator++() {
this->move<TreeIteratorBase::Rightward>();
return *this;
}
Self operator++(int) {
Self tmp = *this;
this->move<TreeIteratorBase::Rightward>();
return tmp;
}
Self& operator--() {
this->move<TreeIteratorBase::Leftward>();
return *this;
}
Self operator--(int) {
Self tmp = *this;
this->move<TreeIteratorBase::Leftward>();
return tmp;
}
explicit TreeIterator(NodeBase* X)
: TreeIteratorBase(X) {}
};
/** \class BinaryTreeBase
* \brief BinaryTreeBase gives root node and memory management.
*
* The memory management of nodes in is hidden by BinaryTreeBase.
* BinaryTreeBase also provides the basic functions for merging a tree and
* inserton of a node.
*
* @see BinaryTree
*/
template<class DataType>
class BinaryTreeBase : private Uncopyable
{
public:
typedef Node<DataType> NodeType;
protected:
/// TreeImpl - TreeImpl records the root node and the number of nodes
//
// +---> Root(end) <---+
// | |left |
// | begin |
// | / \ |
// | Left Right |
// +---/ \-----+
//
class TreeImpl : public NodeFactory<DataType>
{
typedef typename NodeFactory<DataType>::iterator iterator;
typedef typename NodeFactory<DataType>::const_iterator const_iterator;
public:
NodeBase node;
public:
TreeImpl()
: NodeFactory<DataType>() {
node.left = node.right = &node;
}
~TreeImpl()
{ }
/// summon - change the final edges of pClient to our root
void summon(TreeImpl& pClient) {
if (this == &pClient)
return;
iterator data;
iterator dEnd = pClient.end();
for (data = pClient.begin(); data!=dEnd; ++data ) {
if ((*data).left == &pClient.node)
(*data).left = &node;
if ((*data).right == &pClient.node)
(*data).right = &node;
}
}
}; // TreeImpl
protected:
/// m_Root is a special object who responses:
// - the pointer of root
// - the simple factory of nodes.
TreeImpl m_Root;
protected:
NodeType *createNode() {
NodeType *result = m_Root.produce();
result->left = result->right = &m_Root.node;
return result;
}
void destroyNode(NodeType *pNode) {
pNode->left = pNode->right = 0;
pNode->data = 0;
m_Root.deallocate(pNode);
}
public:
BinaryTreeBase()
: m_Root()
{ }
virtual ~BinaryTreeBase()
{ }
size_t size() const {
return m_Root.size();
}
bool empty() const {
return m_Root.empty();
}
protected:
void clear() {
m_Root.clear();
}
};
/** \class BinaryTree
* \brief An abstract data type of binary tree.
*
* @see mcld::InputTree
*/
template<class DataType>
class BinaryTree : public BinaryTreeBase<DataType>
{
public:
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef DataType value_type;
typedef value_type* pointer;
typedef value_type& reference;
typedef const value_type* const_pointer;
typedef const value_type& const_reference;
typedef BinaryTree<DataType> Self;
typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator;
typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator;
typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> dfs_iterator;
typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator> const_dfs_iterator;
typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> bfs_iterator;
typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator> const_bfs_iterator;
protected:
typedef Node<value_type> node_type;
public:
// ----- constructors and destructor ----- //
BinaryTree()
: BinaryTreeBase<DataType>()
{ }
~BinaryTree() {
}
// ----- iterators ----- //
bfs_iterator bfs_begin()
{ return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
bfs_iterator bfs_end()
{ return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
const_bfs_iterator bfs_begin() const
{ return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
const_bfs_iterator bfs_end() const
{ return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
dfs_iterator dfs_begin()
{ return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
dfs_iterator dfs_end()
{ return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
const_dfs_iterator dfs_begin() const
{ return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
const_dfs_iterator dfs_end() const
{ return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
iterator root()
{ return iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
const_iterator root() const
{ return const_iterator(&(BinaryTreeBase<DataType>::m_Root.node)); }
iterator begin()
{ return iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
iterator end()
{ return iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
const_iterator begin() const
{ return const_iterator(BinaryTreeBase<DataType>::m_Root.node.left); }
const_iterator end() const
{ return const_iterator(BinaryTreeBase<DataType>::m_Root.node.right); }
// ----- modifiers ----- //
/// join - create a leaf node and merge it in the tree.
// This version of join determines the direction on compilation time.
// @param DIRECT the direction of the connecting edge of the parent node.
// @param position the parent node
// @param value the value being pushed.
template<size_t DIRECT, class Pos>
BinaryTree& join(Pos position, const DataType& value) {
node_type *node = BinaryTreeBase<DataType>::createNode();
node->data = const_cast<DataType*>(&value);
if (position.isRoot())
proxy::hook<TreeIteratorBase::Leftward>(position.m_pNode,
const_cast<const node_type*>(node));
else
proxy::hook<DIRECT>(position.m_pNode,
const_cast<const node_type*>(node));
return *this;
}
/// merge - merge the tree
// @param DIRECT the direction of the connecting edge of the parent node.
// @param position the parent node
// @param the tree being joined.
// @return the joined tree
template<size_t DIRECT, class Pos>
BinaryTree& merge(Pos position, BinaryTree& pTree) {
if (this == &pTree)
return *this;
if (!pTree.empty()) {
proxy::hook<DIRECT>(position.m_pNode,
const_cast<const NodeBase*>(pTree.m_Root.node.left));
BinaryTreeBase<DataType>::m_Root.summon(
pTree.BinaryTreeBase<DataType>::m_Root);
BinaryTreeBase<DataType>::m_Root.delegate(pTree.m_Root);
pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node;
}
return *this;
}
};
} // namespace of mcld
#endif