Class Tree

Class Tree#

Defined in File Tree.h

Inheritance Relationships#

Derived Type#

public DomTree (Class DomTree)

Class Documentation#

class Tree#

Tree is the base class of a general tree where each node can have a variable number of child nodes.

All algorithms that operate on abstract trees should use this base class for maximum portability.

Nodes and edges must be unique, meaning, a node or object cannot be added to the tree more than once. The root node cannot be deleted if there are other nodes or edges remaining in the tree. Finally, no node can have more than one incoming (parent) edge. Edges and nodes are identified by their pointer values (Tree::Edge* and Tree::Node*). An node is allowed to point to an empty edge since this comes handy in many situations where the order of outgoing edges matters. Such an edge must be inserted using add_empty_edge method.

Following exceptions are thrown by the class (all are subclasses of Exception):

Tree::EmptyEdge — attempt to add, or remove, an empty edge (null pointer)
Tree::DuplicateEdge — attempt to add an edge more than once
Tree::NonexistentEdge — attempt to remove an edge that does not belong to the tree
Tree::EdgeInUse — attempt to add an edge that is already a part of another tree
Tree::SecondParent — attempt to add a second incoming edge to a node
Tree::EmptyNode — attempt to add, or remove, an empty node (null pointer)
Tree::DuplicateNode — attempt to add a node more than once
Tree::NonexistentNode — attempt to remove a node that does not belong to the tree
Tree::NodeInUse — attempt to add a node that is already a part of another tree
Tree::DeletingRootOfNonSingletonTree — attempt to delete the root node when tree has more nodes & edges

NOTE ON friend CLASSES: Many classes (especially Tree::Node and Tree::Edge) have many friend classes. This is not* a kludge. It is simulating “package” visiblity in Java. We want a limited public interface to Node and Edge and yet give more permissions to methods within the Graph class.

Subclassed by DomTree

Public Functions

inline Tree()#

inline Tree(Node *root)#

inline virtual ~Tree()#

inline Node *getRoot()#

void add(Edge*)#

void add(Node*)#

void add_empty_edge(Node*)#

void remove(Edge*)#

void remove(Node*)#

Node *clone(Node*)#

Protected Attributes

Node *root_node#

std::set<Node*> node_set#

std::set<Edge*> edge_set#

bool preorder_needed#

bool postorder_needed#

bool rpostorder_needed#

Friends

friend class NodesIterator

friend class EdgesIterator

friend class PreOrderIterator

friend class PostOrderIterator

friend class ReversePostOrderIterator

class ChildNodesIterator : private Tree::OutEdgesIterator #

ChildNodesIterator iterates over all the child nodes of a node.

Thus, it skips the null edges.

Public Functions

inline ChildNodesIterator(Node *n)#

inline ~ChildNodesIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

inline operator Node*()#

class DeletingRootOfNonSingletonTree : public Exception #

DeletingRootOfNonSingletonTree is thrown when an attempt is made to remove the root of a tree that has other nodes and edges.

Public Functions

inline DeletingRootOfNonSingletonTree(Tree::Node *n)#

inline ~DeletingRootOfNonSingletonTree()#

inline void report(std::ostream &o) const#

class DuplicateEdge : public Exception #

DuplicateEdge exception is thrown if an edge being added is already a part of the tree.

Public Functions

inline DuplicateEdge(Tree::Edge *e)#

inline ~DuplicateEdge()#

inline void report(std::ostream &o) const#

class DuplicateNode : public Exception #

DuplicateNode exception is thrown if a node being added is already a part of the tree.

Public Functions

inline DuplicateNode(Tree::Node *n)#

inline ~DuplicateNode()#

inline void report(std::ostream &o) const#

class Edge#

A tree edge has pointers to the nodes it links (parent and child).

Public Functions

inline Edge(Node *_source, Node *_sink)#

inline virtual Edge *new_copy(Node *_src, Node *_snk)#

inline virtual ~Edge()#

inline Node *parent() const#

inline Node *source() const#

inline Node *tail() const#

inline Node *child() const#

inline Node *sink() const#

inline Node *head() const#

inline virtual void dump(std::ostream &os)#

Protected Functions

inline void copy(Edge *e)#

Protected Attributes

Node *parent_node#

Node *child_node#

bool in_use#

Friends

friend class Tree

friend class Tree::Node

class EdgeInUse : public Exception #

EdgeInUse exception is thrown if an edge being added is already a part of another tree.

Public Functions

inline EdgeInUse(Tree::Edge *e)#

inline ~EdgeInUse()#

inline void report(std::ostream &o) const#

class EdgesIterator : public Iterator #

The edge iterator iterates over all the edges in the tree in no particular order.

Public Functions

inline EdgesIterator(Tree &t)#

inline ~EdgesIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

Protected Attributes

std::set<Edge*>::iterator iter#

Tree *tr#

class EmptyEdge : public Exception #

EmptyEdge exception is thrown if an edge being added is null (0)

Public Functions

inline EmptyEdge()#

inline ~EmptyEdge()#

inline void report(std::ostream &o) const#

class EmptyEndPoint : public Exception #

EmptyEndPoint exception is thrown if the one, or both, of the end points of an edge being added is null.

Public Functions

inline EmptyEndPoint(Tree::Edge *e)#

inline ~EmptyEndPoint()#

inline void report(std::ostream &o) const#

class EmptyNode : public Exception #

EmptyNode exception is thrown if a node being added is null (0)

Public Functions

inline EmptyNode()#

inline ~EmptyNode()#

inline void report(std::ostream &o) const#

class Node#

A tree node has a pointer for the incoming (parent) node, a list of outgoing (children) nodes and links for different traversal orders.

Subclassed by DomTree::Node

Public Functions

inline Node()#

inline virtual Node *new_copy()#

inline virtual ~Node()#

inline Node *parent() const#

inline Node *child(int i) const#

inline Edge *in_edge() const#

inline Edge *out_edge(int i) const#

inline int num_children() const#

inline virtual void dump(std::ostream &os)#

Protected Functions

inline void copy(Node *n)#

Protected Attributes

Edge *incoming#

std::deque<Edge*> outgoing#

Node *next_preorder#

Node *next_postorder#

Node *prev_postorder#

bool in_use#

Friends

friend class Tree

friend class Tree::PreOrderIterator

friend class Tree::PostOrderIterator

friend class Tree::ReversePostOrderIterator

friend class Tree::OutEdgesIterator

friend class Tree::ChildNodesIterator

class NodeInUse : public Exception #

NodeInUse exception is thrown if a node being added is already a part of another tree.

Public Functions

inline NodeInUse(Tree::Node *n)#

inline ~NodeInUse()#

inline void report(std::ostream &o) const#

class NodesIterator : public Iterator #

The node iterator iterates over all the nodes in the tree in no particular order.

Public Functions

inline NodesIterator(Tree &t)#

inline ~NodesIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

inline operator Node*()#

inline Node *operator->()#

Protected Attributes

std::set<Node*>::iterator iter#

Tree *tr#

class NonexistentEdge : public Exception #

NonexistentEdge exception is thrown if an edge being deleted is not a part of the tree.

Public Functions

inline NonexistentEdge(Tree::Edge *e)#

inline ~NonexistentEdge()#

inline void report(std::ostream &o) const#

class NonexistentNode : public Exception #

NonexistentNode exception is thrown if a node being deleted is not a part of the tree.

Public Functions

inline NonexistentNode(Tree::Node *n)#

inline ~NonexistentNode()#

inline void report(std::ostream &o) const#

class OutEdgesIterator : public Iterator #

OutEdgesIterator iterates over all the non-null outgoing nodes of a node.

Subclassed by Tree::ChildNodesIterator

Public Functions

OutEdgesIterator(Node *n)#

inline virtual ~OutEdgesIterator()#

virtual void operator++()#

inline virtual operator bool()#

inline operator Edge*()#

class PostOrderIterator : public Iterator #

Post-order iterator enumerates the nodes in post-order (a node’s sub-trees are visited before the node).

Public Functions

PostOrderIterator(Tree &t)#

inline virtual ~PostOrderIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

inline operator Node*()#

inline Node *operator->()#

class PreOrderIterator : public Iterator #

Pre-order iterator enumerates the nodes in pre-order (a node is visited before all its sub-trees).

Public Functions

PreOrderIterator(Tree &t)#

inline virtual ~PreOrderIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

inline operator Node*()#

inline Node *operator->()#

class ReversePostOrderIterator : public Iterator #

Reverse post-order iterator, as the name suggests, enumerates the nodes in the order that is reverse of post-order.

Public Functions

ReversePostOrderIterator(Tree &t)#

inline virtual ~ReversePostOrderIterator()#

inline virtual void operator++()#

inline virtual operator bool()#

inline operator Node*()#

inline Node *operator->()#

class SecondParent : public Exception #

SecondParent exception is thrown if the sink (child) of the edge being added is already present in the tree, meaning that it already has a parent.

Public Functions

inline SecondParent(Tree::Edge *e)#

inline ~SecondParent()#

inline void report(std::ostream &o) const#

Class Tree

Contents

Class Tree#

Nested Relationships#

Nested Types#

Inheritance Relationships#

Derived Type#

Class Documentation#