1 //===- BinTree.h ----------------------------------------------------------===// 2 // 3 // The MCLinker Project 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 #ifndef MCLD_ADT_BINTREE_H_ 10 #define MCLD_ADT_BINTREE_H_ 11 12 #include "mcld/ADT/TreeAllocator.h" 13 #include "mcld/ADT/TreeBase.h" 14 #include "mcld/Support/Compiler.h" 15 16 #include <cstddef> 17 #include <iterator> 18 #include <memory> 19 #include <queue> 20 #include <stack> 21 22 namespace mcld { 23 24 template <class DataType> 25 class BinaryTree; 26 27 class DFSIterator : public TreeIteratorBase { 28 public: DFSIterator()29 DFSIterator() : TreeIteratorBase() {} 30 DFSIterator(NodeBase * X)31 explicit DFSIterator(NodeBase* X) : TreeIteratorBase(X) { 32 if (hasRightChild()) 33 m_Stack.push(m_pNode->right); 34 if (hasLeftChild()) 35 m_Stack.push(m_pNode->left); 36 } 37 ~DFSIterator()38 virtual ~DFSIterator() {} 39 advance()40 void advance() { 41 if (m_Stack.empty()) { // reach the end 42 m_pNode = m_pNode->right; // should be root 43 return; 44 } 45 m_pNode = m_Stack.top(); 46 m_Stack.pop(); 47 if (hasRightChild()) 48 m_Stack.push(m_pNode->right); 49 if (hasLeftChild()) 50 m_Stack.push(m_pNode->left); 51 } 52 53 private: 54 std::stack<NodeBase*> m_Stack; 55 }; 56 57 class BFSIterator : public TreeIteratorBase { 58 public: BFSIterator()59 BFSIterator() : TreeIteratorBase() {} 60 BFSIterator(NodeBase * X)61 explicit BFSIterator(NodeBase* X) : TreeIteratorBase(X) { 62 if (hasRightChild()) 63 m_Queue.push(m_pNode->right); 64 if (hasLeftChild()) 65 m_Queue.push(m_pNode->left); 66 } 67 ~BFSIterator()68 virtual ~BFSIterator() {} 69 advance()70 void advance() { 71 if (m_Queue.empty()) { // reach the end 72 m_pNode = m_pNode->right; // should be root 73 return; 74 } 75 m_pNode = m_Queue.front(); 76 m_Queue.pop(); 77 if (hasRightChild()) 78 m_Queue.push(m_pNode->right); 79 if (hasLeftChild()) 80 m_Queue.push(m_pNode->left); 81 } 82 83 private: 84 std::queue<NodeBase*> m_Queue; 85 }; 86 87 template <class DataType, class Traits, class IteratorType> 88 class PolicyIteratorBase : public IteratorType { 89 public: 90 typedef DataType value_type; 91 typedef Traits traits; 92 typedef typename traits::pointer pointer; 93 typedef typename traits::reference reference; 94 95 typedef PolicyIteratorBase<value_type, Traits, IteratorType> Self; 96 typedef Node<value_type> node_type; 97 98 typedef typename traits::nonconst_traits nonconst_traits; 99 typedef typename traits::const_traits const_traits; 100 101 typedef PolicyIteratorBase<value_type, nonconst_traits, IteratorType> 102 iterator; 103 typedef PolicyIteratorBase<value_type, const_traits, IteratorType> 104 const_iterator; 105 106 typedef std::forward_iterator_tag iterator_category; 107 typedef size_t size_type; 108 typedef ptrdiff_t difference_type; 109 110 public: PolicyIteratorBase()111 PolicyIteratorBase() : IteratorType() {} 112 PolicyIteratorBase(const iterator & X)113 PolicyIteratorBase(const iterator& X) : IteratorType(X.m_pNode) {} 114 PolicyIteratorBase(NodeBase * X)115 explicit PolicyIteratorBase(NodeBase* X) : IteratorType(X) {} 116 ~PolicyIteratorBase()117 virtual ~PolicyIteratorBase() {} 118 119 // ----- operators ----- // 120 pointer operator*() const { 121 return static_cast<node_type*>(IteratorType::m_pNode)->data; 122 } 123 124 reference operator->() const { 125 return *static_cast<node_type*>(IteratorType::m_pNode)->data; 126 } 127 hasData()128 bool hasData() const { 129 return (!IteratorType::isRoot() && 130 (0 != static_cast<node_type*>(IteratorType::m_pNode)->data)); 131 } 132 }; 133 134 template <class DataType, class Traits, class IteratorType> 135 class PolicyIterator 136 : public PolicyIteratorBase<DataType, Traits, IteratorType> { 137 public: 138 typedef PolicyIterator<DataType, Traits, IteratorType> Self; 139 typedef PolicyIteratorBase<DataType, Traits, IteratorType> Base; 140 typedef PolicyIterator<DataType, 141 typename Traits::nonconst_traits, 142 IteratorType> iterator; 143 typedef PolicyIterator<DataType, typename Traits::const_traits, IteratorType> 144 const_iterator; 145 146 public: PolicyIterator()147 PolicyIterator() : Base() {} 148 PolicyIterator(const iterator & X)149 PolicyIterator(const iterator& X) : Base(X.m_pNode) {} 150 PolicyIterator(NodeBase * X)151 explicit PolicyIterator(NodeBase* X) : Base(X) {} 152 ~PolicyIterator()153 virtual ~PolicyIterator() {} 154 155 Self& operator++() { 156 IteratorType::advance(); 157 return *this; 158 } 159 160 Self operator++(int) { 161 Self tmp = *this; 162 IteratorType::advance(); 163 return tmp; 164 } 165 }; 166 167 template <class DataType> 168 class BinaryTree; 169 170 /** \class TreeIterator 171 * \brief TreeIterator provides full functions of binary tree's iterator. 172 * 173 * TreeIterator is designed to compatible with STL iterators. 174 * TreeIterator is bi-directional. Incremental direction means to move 175 * rightward, and decremental direction is leftward. 176 * 177 * @see TreeIteratorBase 178 */ 179 template <class DataType, class Traits> 180 struct TreeIterator : public TreeIteratorBase { 181 public: 182 typedef DataType value_type; 183 typedef Traits traits; 184 typedef typename traits::pointer pointer; 185 typedef typename traits::reference reference; 186 187 typedef TreeIterator<value_type, Traits> Self; 188 typedef Node<value_type> node_type; 189 190 typedef typename traits::nonconst_traits nonconst_traits; 191 typedef TreeIterator<value_type, nonconst_traits> iterator; 192 typedef typename traits::const_traits const_traits; 193 typedef TreeIterator<value_type, const_traits> const_iterator; 194 typedef std::bidirectional_iterator_tag iterator_category; 195 typedef size_t size_type; 196 typedef ptrdiff_t difference_type; 197 198 public: TreeIteratorTreeIterator199 TreeIterator() : TreeIteratorBase() {} 200 TreeIteratorTreeIterator201 TreeIterator(const iterator& X) : TreeIteratorBase(X.m_pNode) {} 202 ~TreeIteratorTreeIterator203 ~TreeIterator() {} 204 205 // ----- operators ----- // 206 pointer operator*() const { return static_cast<node_type*>(m_pNode)->data; } 207 208 reference operator->() const { 209 return *static_cast<node_type*>(m_pNode)->data; 210 } 211 isRootTreeIterator212 bool isRoot() const { return (m_pNode->right == m_pNode); } 213 hasDataTreeIterator214 bool hasData() const { 215 return (!isRoot() && (0 != static_cast<node_type*>(m_pNode)->data)); 216 } 217 218 Self& operator++() { 219 this->move<TreeIteratorBase::Rightward>(); 220 return *this; 221 } 222 223 Self operator++(int) { 224 Self tmp = *this; 225 this->move<TreeIteratorBase::Rightward>(); 226 return tmp; 227 } 228 229 Self& operator--() { 230 this->move<TreeIteratorBase::Leftward>(); 231 return *this; 232 } 233 234 Self operator--(int) { 235 Self tmp = *this; 236 this->move<TreeIteratorBase::Leftward>(); 237 return tmp; 238 } 239 TreeIteratorTreeIterator240 explicit TreeIterator(NodeBase* X) : TreeIteratorBase(X) {} 241 }; 242 243 /** \class BinaryTreeBase 244 * \brief BinaryTreeBase gives root node and memory management. 245 * 246 * The memory management of nodes in is hidden by BinaryTreeBase. 247 * BinaryTreeBase also provides the basic functions for merging a tree and 248 * inserton of a node. 249 * 250 * @see BinaryTree 251 */ 252 template <class DataType> 253 class BinaryTreeBase { 254 public: 255 typedef Node<DataType> NodeType; 256 257 protected: 258 /// TreeImpl - TreeImpl records the root node and the number of nodes 259 // 260 // +---> Root(end) <---+ 261 // | |left | 262 // | begin | 263 // | / \ | 264 // | Left Right | 265 // +---/ \-----+ 266 // 267 class TreeImpl : public NodeFactory<DataType> { 268 typedef typename NodeFactory<DataType>::iterator iterator; 269 typedef typename NodeFactory<DataType>::const_iterator const_iterator; 270 271 public: 272 NodeBase node; 273 274 public: TreeImpl()275 TreeImpl() : NodeFactory<DataType>() { node.left = node.right = &node; } 276 ~TreeImpl()277 ~TreeImpl() {} 278 279 /// summon - change the final edges of pClient to our root summon(TreeImpl & pClient)280 void summon(TreeImpl& pClient) { 281 if (this == &pClient) 282 return; 283 284 iterator data; 285 iterator dEnd = pClient.end(); 286 for (data = pClient.begin(); data != dEnd; ++data) { 287 if ((*data).left == &pClient.node) 288 (*data).left = &node; 289 if ((*data).right == &pClient.node) 290 (*data).right = &node; 291 } 292 } 293 }; // TreeImpl 294 295 protected: 296 /// m_Root is a special object who responses: 297 // - the pointer of root 298 // - the simple factory of nodes. 299 TreeImpl m_Root; 300 301 protected: createNode()302 NodeType* createNode() { 303 NodeType* result = m_Root.produce(); 304 result->left = result->right = &m_Root.node; 305 return result; 306 } 307 destroyNode(NodeType * pNode)308 void destroyNode(NodeType* pNode) { 309 pNode->left = pNode->right = 0; 310 pNode->data = 0; 311 m_Root.deallocate(pNode); 312 } 313 314 public: BinaryTreeBase()315 BinaryTreeBase() : m_Root() {} 316 ~BinaryTreeBase()317 virtual ~BinaryTreeBase() {} 318 size()319 size_t size() const { return m_Root.size(); } 320 empty()321 bool empty() const { return m_Root.empty(); } 322 323 protected: clear()324 void clear() { m_Root.clear(); } 325 326 private: 327 DISALLOW_COPY_AND_ASSIGN(BinaryTreeBase); 328 }; 329 330 /** \class BinaryTree 331 * \brief An abstract data type of binary tree. 332 * 333 * @see mcld::InputTree 334 */ 335 template <class DataType> 336 class BinaryTree : public BinaryTreeBase<DataType> { 337 public: 338 typedef size_t size_type; 339 typedef ptrdiff_t difference_type; 340 typedef DataType value_type; 341 typedef value_type* pointer; 342 typedef value_type& reference; 343 typedef const value_type* const_pointer; 344 typedef const value_type& const_reference; 345 346 typedef BinaryTree<DataType> Self; 347 typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator; 348 typedef TreeIterator<value_type, ConstTraits<value_type> > const_iterator; 349 350 typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> 351 dfs_iterator; 352 typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator> 353 const_dfs_iterator; 354 355 typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> 356 bfs_iterator; 357 typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator> 358 const_bfs_iterator; 359 360 protected: 361 typedef Node<value_type> node_type; 362 363 public: 364 // ----- constructors and destructor ----- // BinaryTree()365 BinaryTree() : BinaryTreeBase<DataType>() {} 366 ~BinaryTree()367 ~BinaryTree() {} 368 369 // ----- iterators ----- // bfs_begin()370 bfs_iterator bfs_begin() { 371 return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); 372 } 373 bfs_end()374 bfs_iterator bfs_end() { 375 return bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); 376 } 377 bfs_begin()378 const_bfs_iterator bfs_begin() const { 379 return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); 380 } 381 bfs_end()382 const_bfs_iterator bfs_end() const { 383 return const_bfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); 384 } 385 dfs_begin()386 dfs_iterator dfs_begin() { 387 return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); 388 } 389 dfs_end()390 dfs_iterator dfs_end() { 391 return dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); 392 } 393 dfs_begin()394 const_dfs_iterator dfs_begin() const { 395 return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.left); 396 } 397 dfs_end()398 const_dfs_iterator dfs_end() const { 399 return const_dfs_iterator(BinaryTreeBase<DataType>::m_Root.node.right); 400 } 401 root()402 iterator root() { return iterator(&(BinaryTreeBase<DataType>::m_Root.node)); } 403 root()404 const_iterator root() const { 405 return const_iterator(&(BinaryTreeBase<DataType>::m_Root.node)); 406 } 407 begin()408 iterator begin() { 409 return iterator(BinaryTreeBase<DataType>::m_Root.node.left); 410 } 411 end()412 iterator end() { 413 return iterator(BinaryTreeBase<DataType>::m_Root.node.right); 414 } 415 begin()416 const_iterator begin() const { 417 return const_iterator(BinaryTreeBase<DataType>::m_Root.node.left); 418 } 419 end()420 const_iterator end() const { 421 return const_iterator(BinaryTreeBase<DataType>::m_Root.node.right); 422 } 423 424 // ----- modifiers ----- // 425 /// join - create a leaf node and merge it in the tree. 426 // This version of join determines the direction on compilation time. 427 // @param DIRECT the direction of the connecting edge of the parent node. 428 // @param position the parent node 429 // @param value the value being pushed. 430 template <size_t DIRECT> join(TreeIteratorBase & pPosition,const DataType & pValue)431 BinaryTree& join(TreeIteratorBase& pPosition, const DataType& pValue) { 432 node_type* node = BinaryTreeBase<DataType>::createNode(); 433 node->data = const_cast<DataType*>(&pValue); 434 435 if (pPosition.isRoot()) 436 pPosition.hook<TreeIteratorBase::Leftward>(node); 437 else 438 pPosition.hook<DIRECT>(node); 439 440 return *this; 441 } 442 443 /// merge - merge the tree 444 // @param DIRECT the direction of the connecting edge of the parent node. 445 // @param position the parent node 446 // @param the tree being joined. 447 // @return the joined tree 448 template <size_t DIRECT> merge(TreeIteratorBase & pPosition,BinaryTree & pTree)449 BinaryTree& merge(TreeIteratorBase& pPosition, BinaryTree& pTree) { 450 if (this == &pTree) 451 return *this; 452 453 if (!pTree.empty()) { 454 pPosition.hook<DIRECT>(pTree.m_Root.node.left); 455 BinaryTreeBase<DataType>::m_Root.summon( 456 pTree.BinaryTreeBase<DataType>::m_Root); 457 BinaryTreeBase<DataType>::m_Root.delegate(pTree.m_Root); 458 pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node; 459 } 460 return *this; 461 } 462 }; 463 464 } // namespace mcld 465 466 #endif // MCLD_ADT_BINTREE_H_ 467