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 TREE_TREE_H
#define TREE_TREE_H

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

using namespace std;
using namespace __gnu_cxx;

namespace libpmk {

// TODO: clarify behavior when tree is empty.
// Tree always has a root with ID 0.


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

  Tree(const Tree<T>& other);

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

  void clear();

  T* root() { return tree_[0]; }
  const T* root() const { return node(0); }

  int size() const { return tree_.size(); }


  T* node(int id);
  const T* node(int id) const;


  T* add_node(const T& new_node);


  T* add_node();



  void ReadFromStream(istream& input_stream);


  void WriteToStream(ostream& output_stream) const;


  void DeleteNode(int node_id);

  PreorderIterator BeginPreorder() const;

  const PreorderIterator& EndPreorder() const;

  PostorderIterator BeginPostorder() const;

  const PostorderIterator& EndPostorder() const;

  BreadthFirstIterator BeginBreadthFirst() const;

  const BreadthFirstIterator& EndBreadthFirst() const;

  class Iterator {
  public:
    Iterator(int node_id, const Tree<T>* source_tree) :
      node_id_(node_id), source_tree_(source_tree) { }

    virtual ~Iterator() { }

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

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

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

    int operator*() {
      return node_id_;
    }

    int id() {
      return node_id_;
    }

    virtual Iterator& operator++() = 0;

  protected:
    int node_id_;
    const Tree<T>* source_tree_;
  };


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

  private:
    list<int> todo_;
  };

  class PostorderIterator : public Iterator {
  public:
    PostorderIterator(int node_id, const Tree<T>* tree);
    virtual ~PostorderIterator() {}
    virtual Iterator& operator++();

  private:
    stack<int> todo_;
    stack<bool> visited_;
  };

  class BreadthFirstIterator : public Iterator {
  public:
    BreadthFirstIterator(int node_id, const Tree<T>* tree) :
      Iterator(node_id, tree) {}
    virtual ~BreadthFirstIterator() {}
    virtual Iterator& operator++();
  private:
    list<int> todo_;
  };

private:
  hash_map<int, T*> tree_;
  int last_used_id_;

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

  // Pre-create some end-iterators so we don't have to always create
  // them. This is useful for loops like:
  //   while (iter != tree.EndPreorder())
  // because calling this iterators generally involves instantiating
  // an STL stack, vector, or list.
  const PreorderIterator end_preorder_;
  const PostorderIterator end_postorder_;
  const BreadthFirstIterator end_breadth_first_;
};
}  // namespace libpmk

#endif  // TREE_TREE_H

---