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