tree.h

Go to the documentation of this file.

// Copyright 2007, Massachusetts Institute of Technology.
// The use of this code is permitted for research only. There is
// absolutely no warranty for this software.
//
// Author: John Lee (jjl@mit.edu)
//

#ifndef UTIL_TREE_H
#define UTIL_TREE_H

#include <list>
#include <stack>
#include "util/tree-node.h"

using namespace std;

namespace libpmk {


template <class T>
class Tree {
 public:
   Tree();
   ~Tree();

   Tree(const Tree<T>& other);
   Tree(const Tree<T>& one, const Tree<T>& two);

   class Iterator;
   class PreorderIterator;
   class PostorderIterator;
   class BreadthFirstIterator;

   T* const GetRootNode() const;

   int GetNumNodes() const;

   T* GetNode(const LargeIndex& index);


   T* GetNode(const LargeIndex& index, TreeNode* finger);


   T* GetRootNode();


   T* AddNode(const T& new_node);


   T* AddNode(const T& new_node, TreeNode* parent);
   

   void ReadFromStream(istream& input_stream);


   void WriteToStream(ostream& output_stream) const;



   void DeleteNode(TreeNode* node);

   PreorderIterator BeginPreorder() const;

   static const PreorderIterator& EndPreorder();

   PostorderIterator BeginPostorder() const;

   static const PostorderIterator& EndPostorder();

   BreadthFirstIterator BeginBreadthFirst() const;

   static const BreadthFirstIterator& EndBreadthFirst();

   class Iterator {
    public:
      Iterator(TreeNode* node) : node_(node) {}
      virtual ~Iterator() {}

      Iterator& operator=(const Iterator& other) {
         node_ = other.node_;
         return *this;
      }

      bool operator==(const Iterator& other) {
         return node_ == other.node_;
      }
      
      bool operator!=(const Iterator& other) {
         return node_ != other.node_;
      }

      T* operator->() {
         return static_cast<T*>(node_);
      }

      T* get() {
         return static_cast<T*>(node_);
      }
      virtual Iterator& operator++() = 0;

    protected:
      TreeNode* node_;
   };


   // Internally, we let <node_> be the current position. <todo_>
   // contains all remaining nodes, but the nodes in <todo_> may
   // have yet to be expanded.
   class PreorderIterator : public Iterator {
    public:
      PreorderIterator(T* node) : Iterator(node) {}
      virtual ~PreorderIterator() {}
      virtual Iterator& operator++();

    private:
      list<TreeNode*> todo_;
   };


   class PostorderIterator : public Iterator {
    public:
      PostorderIterator(T* node);
      virtual ~PostorderIterator() {}
      virtual Iterator& operator++();

    private:
      stack<TreeNode*> todo_;
      stack<bool> visited_;
   };

   class BreadthFirstIterator : public Iterator {
    public:
      BreadthFirstIterator(T* node) : Iterator(node) {}
      virtual ~BreadthFirstIterator() {}
      virtual Iterator& operator++();
    private:
      list<TreeNode*> todo_;
   };

 private:
   T* root_node_;
   void DeleteLeafNode(TreeNode* node);
   void FreeAllNodes();

   // Assumes my_node has no children (will not free any memory).
   // Makes my_node's children into a deep copy of other_node (copies
   // children and link structure as well). This will increment the
   // node count for each new bin added as well. It will NOT modify
   // my_node however.
   void CopySubtree(T** my_node, T* other_node);
   int num_nodes_;

   // Block the copy assignment operator
   void operator=(const Tree<T>&);

   // Static variable hacks so we don't have to always create end-iterators.
   static PreorderIterator end_preorder_;
   static PostorderIterator end_postorder_;
   static BreadthFirstIterator end_breadth_first_;
};
}  // namespace libpmk
#endif  // UTIL_TREE_H

---