/* * Node.h * Jonathan Boldiga * 08/26/03 * * Description: A cyclic linked-list tree data structure. * */ #ifndef __NODE_H #define __NODE_H #ifndef NULL #define NULL 0L #endif // Node class class Node{ public: // data Node* parentNode; // parent node Node* childNode; // child node Node* previousNode; // previous node Node* nextNode; // next node // constructor Node(){ // setup node parentNode = childNode = NULL; previousNode = nextNode = this; } // constructor Node(Node* node){ parentNode = childNode = NULL; // setup and attach this node to node previousNode = nextNode = this; attachTo(node); } // destructor virtual ~Node(){ detach(); // detach from hierarchy //delete all the children while (childNode){ delete childNode; } } //does the node have a parent bool hasParent(){ return (parentNode != NULL); } //does the node have a child bool hasChild(){ return (childNode != NULL); } //is this node the first child? bool isFirstChild(){ if (parentNode) return (parentNode->childNode == this); else return false; } // is this node the last child? bool isLastChild(){ if (parentNode) return (parentNode->childNode->previousNode == this); else return false; } // attach this node to a parent node void attachTo(Node* newParent){ // if this node is already attached to another node, then detach if (parentNode) detach(); parentNode = newParent; if (parentNode->childNode){ previousNode = parentNode->childNode->previousNode; nextNode = parentNode->childNode; parentNode->childNode->previousNode->nextNode = this; parentNode->childNode->previousNode = this; } else{ parentNode->childNode = this; // this is the first child } } // attach a child to this node void attach(Node* newChild){ // if the child node is already attached, then detach it if (newChild->hasParent()) newChild->detach(); newChild->parentNode = this; if (childNode){ newChild->previousNode = childNode->previousNode; newChild->nextNode = childNode; childNode->previousNode->nextNode = newChild; childNode->previousNode = newChild; } else childNode = newChild; } // detach node from parent void detach(){ // if this node is the first child of the parent (first in list) // then the parent points to the next child in the list if (parentNode && parentNode->childNode == this){ if (nextNode != this) parentNode->childNode = nextNode; else parentNode->childNode = NULL; // no next child } // get rid of links previousNode->nextNode = nextNode; nextNode->previousNode = previousNode; // now this node is not in the list previousNode = this; nextNode = this; } // count the number of nodes int CountNodes(){ if (childNode) return childNode->CountNodes() + 1; else return 1; } }; #endif