Program Listing for File Tree.h

↰ Return to documentation for file (src/midend/programAnalysis/OpenAnalysis/Utils/Tree.h)

// $Id: Tree.h,v 1.1 2004/07/07 10:26:35 dquinlan Exp $
// -*-C++-*-
// * BeginRiceCopyright *****************************************************
//
// Copyright ((c)) 2002, Rice University
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright
//   notice, this list of conditions and the following disclaimer.
//
// * Redistributions in binary form must reproduce the above copyright
//   notice, this list of conditions and the following disclaimer in the
//   documentation and/or other materials provided with the distribution.
//
// * Neither the name of Rice University (RICE) nor the names of its
//   contributors may be used to endorse or promote products derived from
//   this software without specific prior written permission.
//
// This software is provided by RICE and contributors "as is" and any
// express or implied warranties, including, but not limited to, the
// implied warranties of merchantability and fitness for a particular
// purpose are disclaimed. In no event shall RICE or contributors be
// liable for any direct, indirect, incidental, special, exemplary, or
// consequential damages (including, but not limited to, procurement of
// substitute goods or services; loss of use, data, or profits; or
// business interruption) however caused and on any theory of liability,
// whether in contract, strict liability, or tort (including negligence
// or otherwise) arising in any way out of the use of this software, even
// if advised of the possibility of such damage.
//
// ******************************************************* EndRiceCopyright *

// Best seen in 120-column wide window (or print in landscape mode).
//--------------------------------------------------------------------------------------------------------------------
// This file is part of Mint.
// Arun Chauhan (achauhan@cs.rice.edu), Dept of Computer Science, Rice University, 2001.
//--------------------------------------------------------------------------------------------------------------------

#ifndef Tree_H
#define Tree_H

// STL headers
#include <deque>
#include <set>

// Mint headers
#include "Iterator.h"
#include "Exception.h"


//--------------------------------------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------------------------------------
class Tree {
 public:
  class Node;
  class Edge;
  class NodesIterator;
  class EdgesIterator;
  class PreOrderIterator;
  class PostOrderIterator;
  class ReversePostOrderIterator;
  class OutEdgesIterator;
  class ChildNodesIterator;
  friend class NodesIterator;
  friend class EdgesIterator;
  friend class PreOrderIterator;
  friend class PostOrderIterator;
  friend class ReversePostOrderIterator;
  //------------------------------------------------------------------------------------------------------------------
  class EmptyEdge : public Exception {
  public:
    EmptyEdge () {}
    ~EmptyEdge () {}
    void report (std::ostream& o) const { o << "E!  Adding a null edge to a tree." << std::endl; }
  };
  //------------------------------------------------------------------------------------------------------------------
  class DuplicateEdge : public Exception {
  public:
    DuplicateEdge (Tree::Edge* e) { offending_edge = e; }
    ~DuplicateEdge () {}
    void report (std::ostream& o) const { o << "E!  Adding a duplicate edge to a tree." << std::endl; }
  private:
    Tree::Edge* offending_edge;
  };
  //------------------------------------------------------------------------------------------------------------------
  class NonexistentEdge : public Exception {
  public:
    NonexistentEdge (Tree::Edge* e) { offending_edge = e; }
    ~NonexistentEdge () {}
    void report (std::ostream& o) const { o << "E!  Removing a non-existent edge from a tree." << std::endl; }
  private:
    Tree::Edge* offending_edge;
  };
  //------------------------------------------------------------------------------------------------------------------
  class EdgeInUse : public Exception {
  public:
    EdgeInUse (Tree::Edge* e) { offending_edge = e; }
    ~EdgeInUse () {}
    void report (std::ostream& o) const { o << "E!  Adding an edge that is already a part of another tree." << std::endl; }
  private:
    Tree::Edge* offending_edge;
  };
  //------------------------------------------------------------------------------------------------------------------
  class SecondParent : public Exception {
  public:
    SecondParent (Tree::Edge* e) { offending_edge = e; }
    ~SecondParent () {}
    void report (std::ostream& o) const { o << "E!  Adding an edge that points to an existing node in the tree." << std::endl; }
  private:
    Tree::Edge* offending_edge;
  };
  //------------------------------------------------------------------------------------------------------------------
  class EmptyEndPoint : public Exception {
  public:
    EmptyEndPoint (Tree::Edge* e) { offending_edge = e; }
    ~EmptyEndPoint () {}
    void report (std::ostream& o) const { o << "E!  Adding an edge that points to an empty node." << std::endl; }
  private:
    Tree::Edge* offending_edge;
  };
  //------------------------------------------------------------------------------------------------------------------
  class EmptyNode : public Exception {
  public:
    EmptyNode () {}
    ~EmptyNode () {}
    void report (std::ostream& o) const { o << "E!  Adding a null node to a tree." << std::endl; }
  };
  //------------------------------------------------------------------------------------------------------------------
  class DuplicateNode : public Exception {
  public:
    DuplicateNode (Tree::Node* n) { offending_node = n; }
    ~DuplicateNode () {}
    void report (std::ostream& o) const { o << "E!  Adding a duplicate node to a tree." << std::endl; }
  private:
    Tree::Node* offending_node;
  };
  //------------------------------------------------------------------------------------------------------------------
  class NonexistentNode : public Exception {
  public:
    NonexistentNode (Tree::Node* n) { offending_node = n; }
    ~NonexistentNode () {}
    void report (std::ostream& o) const { o << "E!  Removing a non-existent node from the tree." << std::endl; }
  private:
    Tree::Node* offending_node;
  };
  //------------------------------------------------------------------------------------------------------------------
  class NodeInUse : public Exception {
  public:
    NodeInUse (Tree::Node* n) { offending_node = n; }
    ~NodeInUse () {}
    void report (std::ostream& o) const { o << "E!  Adding a node that is already a part of another tree." << std::endl; }
  private:
    Tree::Node* offending_node;
  };
  //------------------------------------------------------------------------------------------------------------------
  class DeletingRootOfNonSingletonTree : public Exception {
  public:
    DeletingRootOfNonSingletonTree (Tree::Node* n) { offending_node = n; }
    ~DeletingRootOfNonSingletonTree () {}
    void report (std::ostream& o) const { o << "E!  Deleting the root node of a non-singleton tree." << std::endl; }
  private:
    Tree::Node* offending_node;
  };
  //------------------------------------------------------------------------------------------------------------------
  class Node {
  public:
    Node () { in_use = false; next_preorder = next_postorder = prev_postorder = 0;  incoming = 0; }
    virtual Node* new_copy () { Node* n = new Node(); copy(n); return n; }
    virtual ~Node () {}
    Node* parent () const { if (incoming != 0) return incoming->source(); else return 0; }
    Node* child (int i) const { if (outgoing[i] != 0) return outgoing[i]->child(); else return 0; }
    Edge* in_edge () const { return incoming; }
    Edge* out_edge (int i) const { return outgoing[i]; }
    int num_children () const { return outgoing.size(); }
    virtual void dump (std::ostream& os) { os << this; }
  protected:
    void copy (Node* n) {}
    Edge* incoming;
    std::deque<Edge*> outgoing;
    Node* next_preorder;
    Node* next_postorder;
    Node* prev_postorder;
    bool in_use;
    friend class Tree;
    friend class Tree::PreOrderIterator;
    friend class Tree::PostOrderIterator;
    friend class Tree::ReversePostOrderIterator;
    friend class Tree::OutEdgesIterator;
    friend class Tree::ChildNodesIterator;
  };
  //------------------------------------------------------------------------------------------------------------------
  class Edge {
  public:
    Edge (Node* _source, Node* _sink) { in_use = false; parent_node = _source; child_node = _sink; }
    virtual Edge* new_copy (Node* _src, Node* _snk) { Edge* e = new Edge(_src, _snk); copy(e); return e; }
    virtual ~Edge () {}
    Node* parent () const { return parent_node; }
    Node* source () const { return parent(); }
    Node* tail () const { return parent(); }
    Node* child () const { return child_node; }
    Node* sink () const { return child(); }
    Node* head () const { return child(); }
    virtual void dump (std::ostream& os) { os << this; }
  protected:
    void copy (Edge* e) {}
    Node* parent_node;
    Node* child_node;
    bool in_use;
    friend class Tree;
    friend class Tree::Node;
  };
  //------------------------------------------------------------------------------------------------------------------
  class NodesIterator : public Iterator {
  public:
    NodesIterator (Tree& t) { tr = &t;  iter = tr->node_set.begin(); }
    ~NodesIterator () {}
    void operator++ () { ++iter; }
    operator bool () { return (iter != tr->node_set.end()); }
    operator Node* () { return *iter; }
    Node* operator -> () { return *iter; }
  protected:
    std::set<Node*>::iterator iter;
    Tree* tr;
  };
  //------------------------------------------------------------------------------------------------------------------
  class EdgesIterator : public Iterator {
  public:
    EdgesIterator (Tree& t) { tr = &t;  iter = tr->edge_set.begin(); }
    ~EdgesIterator () {}
    void operator++ () { ++iter; }
    operator bool () { return (iter != tr->edge_set.end()); }
  protected:
    std::set<Edge*>::iterator iter;
    Tree* tr;
  };
  //------------------------------------------------------------------------------------------------------------------
  class OutEdgesIterator : public Iterator {
  public:
    OutEdgesIterator (Node* n);
    virtual ~OutEdgesIterator () {}
    void operator++ ();
    operator bool () { return (iter != center->outgoing.end()); }
    operator Edge* () { return *iter; }
  private:
    Node* center;
    std::deque<Edge*>::iterator iter;
  };
  //------------------------------------------------------------------------------------------------------------------
  class ChildNodesIterator : private OutEdgesIterator {
  public:
    ChildNodesIterator (Node* n) : OutEdgesIterator(n) {}
    ~ChildNodesIterator () {}
    void operator++ () { OutEdgesIterator::operator++(); }
    operator bool () { return OutEdgesIterator::operator bool(); }
    operator Node* () { Edge* e = (Edge*)(*this);  return e->sink(); }
  };
  //------------------------------------------------------------------------------------------------------------------
  class PreOrderIterator : public Iterator {
  public:
    PreOrderIterator (Tree& t);
    virtual ~PreOrderIterator () {}
    void operator++ () { if (p != 0) p = p->next_preorder; }
    operator bool () { return (p != 0); }
    operator Node* () { return p; }
    Node* operator -> () { return p; }
  private:
    Node* p; // pointer to the last visited node
  };
  //------------------------------------------------------------------------------------------------------------------
  class PostOrderIterator : public Iterator {
  public:
    PostOrderIterator (Tree& t);
    virtual ~PostOrderIterator () {}
    void operator++ () { if (p != 0) p = p->next_postorder; }
    operator bool () { return (p != 0); }
    operator Node* () { return p; }
    Node* operator -> () { return p; }
  private:
    Node* p; // pointer to the last visited node
  };
  //------------------------------------------------------------------------------------------------------------------
  class ReversePostOrderIterator : public Iterator {
  public:
    ReversePostOrderIterator (Tree& t);
    virtual ~ReversePostOrderIterator () {}
    void operator++ () { if (p != 0) p = p->prev_postorder; }
    operator bool() { return (p != 0); }
    operator Node* () { return p; }
    Node* operator -> () { return p; }
  private:
    Node* p; // pointer to the last visited node
  };
  //------------------------------------------------------------------------------------------------------------------
  Tree () { root_node = 0; }
  Tree (Node* root) { root_node = 0; add(root); }
  virtual ~Tree () {}

  Node* getRoot () { return root_node; }

  void add (Edge*) throw (DuplicateEdge, EdgeInUse, EmptyEdge, SecondParent, EmptyEndPoint);
  void add (Node*) throw (DuplicateNode, NodeInUse, EmptyNode);
  void add_empty_edge (Node*) throw (EmptyNode);
  void remove (Edge*) throw (NonexistentEdge, EmptyEdge);
  void remove (Node*) throw (NonexistentNode, DeletingRootOfNonSingletonTree, EmptyNode);
  Node* clone (Node*);

protected:
  Node* root_node;
  std::set<Node*> node_set;
  std::set<Edge*> edge_set;
  bool preorder_needed;
  bool postorder_needed;
  bool rpostorder_needed;

private:
  Node* create_preorder_links (Node*);
  Node* create_postorder_links (Node*);
  Node* create_rpostrder_links (Node*);
};
//--------------------------------------------------------------------------------------------------------------------

#endif