/* node.h --- the data structure representing phylogenetic trees Jim Blandy --- July 1994 */ #ifndef NODE_H #define NODE_H #include "lenstring.h" /* data structures */ struct node { /* The name of this node, used in protocol requests. */ struct lenstring name; /* The description of this node, displayed after the name. */ struct lenstring description; /* The depth of this node in the tree; the root is at depth zero, and the children of a node at depth N are at depth N+1. */ int depth; /* The number of children this node has. */ size_t num_children; /* The children of this node --- an array of pointers. Let P be the least power of two >= num_children; this array has at least P elements allocated to it. */ struct node **children; /* If NODE points to this node and NODE->parent != 0, then node->parent->children[node->child_index] == node. */ int child_index; /* The parent of this node. */ struct node *parent; /* Marks on this node --- open, selected, etcetera. */ unsigned long marks; /* Marks that were on this node as of the last redisplay. */ unsigned long prev_marks; /* The next node in the usual traversal order, considering all nodes open. */ struct node *next; }; /* Bits to set in a node's MARKS field. I've got both numbers and masks, with distinctive names, because I figured otherwise I would always be thinking a mask was a number and vice versa. This actually happened once before I changed it. */ enum mark_numbers { OPEN_N = 1, VISIBLE_N, SELECTED_N, CHILDREN_SELECTED_N, IN_FILE_N, }; enum mark_masks { OPEN_M = (1 << OPEN_N), VISIBLE_M = (1 << VISIBLE_N), SELECTED_M = (1 << SELECTED_N), CHILDREN_SELECTED_M = (1 << CHILDREN_SELECTED_N), IN_FILE_M = (1 << IN_FILE_N), }; /* tree construction */ /* Allocate and return a new node. NAME and NAME_LEN are the node's name. DESCRIPTION and DESCRIPTION_LEN are the node's description. The node is created with no children, and no parent, at depth zero. */ extern struct node *new_node (char *NAME, size_t NAME_LEN, char *DESCRIPTION, size_t DESCRIPTION_LEN); /* Make CHILD a child-node of PARENT; set child's depth to one more than the depth of PARENT. */ extern void add_child (struct node *PARENT, struct node *CHILD); /* naming nodes and marks */ /* Build and return a string hash table mapping TREE's node names onto nodes. If two nodes have the same name, rename them to be unique. Set the special node name "!root" to the root of the tree. */ struct string_hash *hash_node_names (struct node *TREE); /* Casting versions of the hashing functions. */ #define LOOKUP_NODE(table, string, string_len) \ ((struct node **) lookup_hash_table ((table), (string), (string_len))) #define LOOKUP_NODE_SOFT(table, string, string_len) \ ((struct node **) lookup_hash_table_soft ((table), (string), (string_len))) /* Given the name of a mark as a lenstring, return the number of that mark. This also deals with numbered marks. If NAME is not a valid mark name, then return 0. */ extern int mark_by_name (struct lenstring *NAME); /* tree-like traversal */ /* The type for functions to be passed to the traversor functions. */ typedef void (*node_function_t) (struct node *NODE); /* Post-order traverse the tree rooted at NODE, applying FUNC as we go. */ extern void traverse_post (struct node *NODE, node_function_t FUNC); /* linear traversal */ /* Return t iff NODE1 appears strictly before NODE2 in the usual pre-order presentation of TREE. */ extern int node_before_p (struct node *NODE1, struct node *NODE2); /* Initialize the `next' pointers in TREE. Assume NEXT is the successor of the last node in tree. Return the first node in TREE. */ extern struct node *thread_tree (struct node *TREE, struct node *NEXT); /* Return the node immediately following NODE, walking only visible nodes. Return 0 iff NODE is the last node in the tree. */ extern struct node *next_visible_node (struct node *NODE); /* Return non-zero iff NODE is visible. */ extern int node_visible_p (struct node *node); #endif /* NODE_H */