Program Trees

Program trees are built from nodes; trees are referenced by their root node. The Node class itself is a virtual base class; its definition follows:

// base class for the 4 types of nodes
class Node {
  protected:
    Node *parent;               // the parent node
    int n_children;             // number of child nodes
    int n_valid;                // validity flag for above

  public:
    Node(void);                 // constructor
    ~Node(void);                // destructor will reset the parent's 
                                // pointer to this node

    int type;                   // indicates the type of node
    void invalidate_count(void); // called when the number of children
                                 // of this node has changed
    virtual Val value(void) = 0; // this is the function that takes care
                                 // of everything needed to assign a
                                 // value to this node
    virtual int count(void) = 0; // returns the number of children
    virtual Node *find(int) = 0; // used to return a particular node
    virtual char *print(void) = 0; // prints the subtree's expression to a 
                                   // string
    // resets the parent node
    void set_parent(Node *n) {parent = n;};
    // accesses the parent node
    Node *get_parent(void) {return parent;};
};

*parent

This is a pointer to the parent node of this node. If this is the root of the tree, the pointer is set to NULL.

n_children, n_valid

Since the number of children in a subtree is used often, it is cached here. n_valid is a flag that indicates when this value needs to be recomputed. Neither of these can be accessed directly.

type

Indicates the type of node; these will be discussed later.

invalidate_count()

This function is called when the number of children of a node has changed (usually due to crossover or another reproductive function). It sets the n_valid flag to 0, then calls the parent's invalidate_count() function to recursively notify all nodes above.

value()

This function evaluates the node by calling its function on the operands (children). Calling the root node's value() function will evaluate the entire tree.

find()

This is used to find a particular child of a node.

print()

This is used to recursively print the subtree in human-readable form. The node's operator sign is used along with the strings produced by each child.