sparse-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_SPARSE_TREE_H
#define TREE_SPARSE_TREE_H

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

using namespace std;

namespace libpmk {


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

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

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

  T* root() { return root_node_; }

  T* const root() const { return root_node_; }

  int size() const { return num_nodes_; }


  T* node(const LargeIndex& index);


  T* node(const LargeIndex& index, SparseTreeNode* finger);




  T* add_node(const T& new_node);


  T* add_node(const T& new_node, SparseTreeNode* parent);


  void ReadFromStream(istream& input_stream);


  void WriteToStream(ostream& output_stream) const;



  void remove_node(SparseTreeNode* 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(SparseTreeNode* 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:
    SparseTreeNode* 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<SparseTreeNode*> todo_;
  };


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

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

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

private:
  T* root_node_;
  void DeleteLeafNode(SparseTreeNode* 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 SparseTree<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  // TREE_SPARSE_TREE_H

---