
/*
 * bltTree.h --
 *
 * Copyright 1998-1999 Lucent Technologies, Inc.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that the copyright notice and warranty
 * disclaimer appear in supporting documentation, and that the names
 * of Lucent Technologies or any of their entities not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.
 *
 * Lucent Technologies disclaims all warranties with regard to this
 * software, including all implied warranties of merchantability and
 * fitness.  In no event shall Lucent Technologies be liable for any
 * special, indirect or consequential damages or any damages
 * whatsoever resulting from loss of use, data or profits, whether in
 * an action of contract, negligence or other tortuous action, arising
 * out of or in connection with the use or performance of this
 * software.
 *
 *	The "tree" data object was created by George A. Howlett.
 */

#ifndef _BLT_TREE_H
#define _BLT_TREE_H

typedef struct Blt_TreeNodeRec *Blt_TreeNode;
typedef struct Blt_TreeObjectRec *Blt_TreeObject;
typedef struct Blt_TreeTokenRec *Blt_Tree;
typedef struct Blt_TreeTraceRec *Blt_TreeTrace;
typedef struct Blt_TreeCursorRec *Blt_TreeCursor;

#define TREE_PREORDER		(1<<0)
#define TREE_POSTORDER		(1<<1)
#define TREE_INORDER		(1<<2)
#define TREE_BREADTHFIRST	(1<<3)

#define TREE_TRACE_UNSET	(1<<3)
#define TREE_TRACE_WRITE	(1<<4)
#define TREE_TRACE_READ		(1<<5)
#define TREE_TRACE_CREATE	(1<<6)
#define TREE_TRACE_ALL		\
    (TREE_TRACE_UNSET | TREE_TRACE_WRITE | TREE_TRACE_READ | TREE_TRACE_CREATE)
#define TREE_TRACE_MASK		(TREE_TRACE_ALL)

#define TREE_TRACE_FOREIGN_ONLY	(1<<8)
#define TREE_TRACE_ACTIVE	(1<<9)

#define TREE_NOTIFY_CREATE	(1<<0)
#define TREE_NOTIFY_DELETE	(1<<1)
#define TREE_NOTIFY_MOVE	(1<<2)
#define TREE_NOTIFY_SORT	(1<<3)
#define TREE_NOTIFY_RELABEL	(1<<4)
#define TREE_NOTIFY_ALL		\
    (TREE_NOTIFY_CREATE | TREE_NOTIFY_DELETE | TREE_NOTIFY_MOVE | \
	TREE_NOTIFY_SORT | TREE_NOTIFY_RELABEL)
#define TREE_NOTIFY_MASK	(TREE_NOTIFY_ALL)

#define TREE_NOTIFY_WHENIDLE	 (1<<8)
#define TREE_NOTIFY_FOREIGN_ONLY (1<<9)
#define TREE_NOTIFY_ACTIVE	 (1<<10)

typedef struct {
    int type;
    Blt_Tree tree;
    int inode;			/* Node of event */
} Blt_TreeNotifyEvent;

/*
 * Blt_TreeObject --
 *
 *	Structure providing the internal representation of the tree
 *	object.	A tree is uniquely identified by a combination of 
 *	its name and originating namespace.  Two trees in the same 
 *	interpreter can have the same names but reside in different 
 *	namespaces.
 *
 *	The tree object represents a general-ordered tree of node.
 *	Each node may contain a heterogeneous collection of data.  
 *	Nodes do not need to contain the same data fields.  Each 
 *	piece of data is identified by a field name.  Data field
 *	names are saved as reference counted strings and can be 
 *	shared among nodes.
 *
 *	The tree is threaded.  A node contains both a pointer to 
 *	back its parents and another to its siblings.  Therefore
 *	the tree maybe traversed non-recursively.
 * 
 *	A tree object can be shared by several clients.  When a
 *	client wants to use a tree object, it is given a token
 *	that represents the tree.  The tree object uses the tokens
 *	to keep track of its clients.  When all clients have 
 *	released their tokens the tree is automatically destroyed.
 */
struct Blt_TreeObjectRec {

    Tcl_Interp *interp;		/* Interpreter associated with this tree. */

    char *name;

    Tcl_Namespace *nsPtr;

    Tcl_HashEntry *hashPtr;	/* Pointer to this tree object in tree
				 * object hash table. */

    Blt_TreeNode root;		/* Root of the entire tree. */

    int nNodes;			/* Always counts root node. */

    int depth;			/* Maximum depth of the tree. */

    unsigned int flags;		/* Internal flags. See definitions
				 * below. */
    unsigned int notifyFlags;	/* Notification flags. See definitions
				 * below. */

    Tcl_HashTable nodeTable;	/* Table of node identifiers. Used to
				 * search for a node pointer given an inode.*/
    unsigned int nextNode;

    char *sortNodesCmd;		/* Tcl command to invoke to sort entries */

    Blt_Chain *chainPtr;	/* List of clients using this tree */

};

/*
 * Blt_TreeNode_ --
 *
 *	Structure representing a node in a general ordered tree.
 *	Nodes are identified by their index, or inode.  Nodes also
 *	have names, but nodes names are not unique and can be 
 *	changed.  Inodes are valid even if the node is moved.
 *
 *	Each node can contain a list of data fields.  Fields are
 *	name-value pairs.  The values are represented by Tcl_Objs.
 *	
 */
struct Blt_TreeNodeRec {
    Blt_Uid labelUid;		/* Node label (doesn't have to be unique */

    unsigned int inode;		/* Unique identifier for node. */

    Blt_TreeObject treePtr;

    Blt_TreeNode parent;	/* Pointer to the parent node. If
				 * NULL, this is the root node. */

    short int depth;		/* The depth of this node in the tree. */

    unsigned short flags;
    
    Blt_Chain *chainPtr;	/* Pointer to a chain of subnodes. The
				 * chain isn't allocated until the
				 * node has children. */

    Blt_ChainLink *linkPtr;	/* Pointer to this node in the
				 * parent's chain of children nodes.
				 * Used to remove the node from its
				 * parent when destroying the node. */

    Blt_Chain *dataPtr;		/* A chain of Tcl_Obj's. Hold the
				 * various fields of the node.  Can be
				 * NULL, if no data is currently held.
				 */
};

/*
 * Blt_TokenToken --
 *
 *	A tree can be shared by several clients.  Each client allocates
 *	this structure which acts as a key for using the tree.  Clients
 *	can designate notifier routines that are automatically invoked
 *	by the tree object whenever the tree is changed is specific
 *	ways by other clients.
 */

struct Blt_TreeTokenRec {
    unsigned int magic;		/* Magic value designating whether this
				 * really is a tree token or not */
    Blt_ChainLink *linkPtr;
    Blt_TreeObject tree;	/* Pointer to the structure containing
				 * the master information about the
				 * tree used by the client.  If NULL,
				 * this indicates that the tree has
				 * been destroyed (but as of yet, this
				 * client hasn't recognized it). */

    Blt_Chain *chainPtr;	/* Chain of node event handlers. */
    Blt_Chain *tracePtr;	/* Chain of data field callbacks. */
    Blt_TreeNode root;		/* Designated root for this client */
};

typedef int (Blt_TreeNotifyEventProc) _ANSI_ARGS_((ClientData clientData, 
	Blt_TreeNotifyEvent *eventPtr));

typedef int (Blt_TreeTraceProc) _ANSI_ARGS_((ClientData clientData, 
	Tcl_Interp *interp, Blt_TreeNode node, Blt_Uid keyUid, 
	unsigned int flags));

typedef int (Blt_TreeEnumProc) _ANSI_ARGS_((Blt_TreeNode node, Blt_Uid keyUid,
	Tcl_Obj *valuePtr));

typedef int (Blt_TreeCompareNodesProc) _ANSI_ARGS_((Blt_TreeNode *n1Ptr, 
	Blt_TreeNode *n2Ptr));

typedef int (Blt_TreeApplyProc) _ANSI_ARGS_((Blt_TreeNode node, 
	ClientData clientData, int order));

struct Blt_TreeTraceRec {
    ClientData clientData;
    Blt_Uid keyUid;
    Blt_TreeNode node;
    unsigned int mask;
    Blt_TreeTraceProc *proc;
};

EXTERN Blt_TreeNode Blt_TreeCreateNode _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode parent, char *name, int position)); 

EXTERN int Blt_TreeDeleteNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node));

EXTERN int Blt_TreeMoveNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	Blt_TreeNode parent, Blt_TreeNode before));

EXTERN Blt_TreeNode Blt_TreeGetNode _ANSI_ARGS_((Blt_Tree tree, 
	unsigned int inode));

EXTERN Blt_TreeNode Blt_TreeFindChild _ANSI_ARGS_((Blt_TreeNode parent, 
	char *name));

EXTERN Blt_TreeNode Blt_TreeFirstChild _ANSI_ARGS_((Blt_TreeNode parent));

EXTERN Blt_TreeNode Blt_TreeNextSibling _ANSI_ARGS_((Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeLastChild _ANSI_ARGS_((Blt_TreeNode parent));

EXTERN Blt_TreeNode Blt_TreePrevSibling _ANSI_ARGS_((Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeNextNode _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreePrevNode _ANSI_ARGS_((Blt_TreeNode root,
	Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeChangeRoot _ANSI_ARGS_((Blt_Tree tree,
	Blt_TreeNode node));

EXTERN Blt_TreeNode Blt_TreeEndNode _ANSI_ARGS_((Blt_TreeNode node,
	unsigned int nodeFlags));

EXTERN int Blt_TreeIsBefore _ANSI_ARGS_((Blt_TreeNode node1, 
	Blt_TreeNode node2));

EXTERN int Blt_TreeIsAncestor _ANSI_ARGS_((Blt_TreeNode node1, 
	Blt_TreeNode node2));

EXTERN int Blt_TreeGetValue _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	char *key, Tcl_Obj **valuePtr));

EXTERN int Blt_TreeSetValue _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	char *key, Tcl_Obj *valuePtr));

EXTERN int Blt_TreeUnsetValue _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	char *key));

EXTERN int Blt_TreeGetValueByUid _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	Blt_Uid keyUid, Tcl_Obj **valuePtr));

EXTERN int Blt_TreeSetValueByUid _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	Blt_Uid keyUid, Tcl_Obj *valuePtr));

EXTERN int Blt_TreeUnsetValueByUid _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode node, Blt_Uid keyUid));

EXTERN Blt_Uid Blt_TreeFirstKey _ANSI_ARGS_((Blt_TreeNode node,
    Blt_TreeCursor *cursorPtr));

EXTERN Blt_Uid Blt_TreeNextKey _ANSI_ARGS_((Blt_TreeCursor *cursorPtr));

EXTERN int Blt_TreeEnumKeys _ANSI_ARGS_((Blt_TreeNode node, 
	Blt_TreeEnumProc *proc));

EXTERN int Blt_TreeApply _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeApplyProc *proc, ClientData clientData));

EXTERN int Blt_TreeApplyDFS _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeApplyProc *proc, ClientData clientData, int order));

EXTERN int Blt_TreeApplyBFS _ANSI_ARGS_((Blt_TreeNode root, 
	Blt_TreeApplyProc *proc, ClientData clientData));

EXTERN int Blt_TreeSortNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	Blt_TreeCompareNodesProc *proc));

EXTERN int Blt_TreeCreate _ANSI_ARGS_((Tcl_Interp *interp, char *name));

EXTERN int Blt_TreeExists _ANSI_ARGS_((Tcl_Interp *interp, char *name));

EXTERN int Blt_TreeGetToken _ANSI_ARGS_((Tcl_Interp *interp, char *name, 
	Blt_Tree *treePtr));

EXTERN void Blt_TreeReleaseToken _ANSI_ARGS_((Blt_Tree tree));

EXTERN int Blt_TreeSize _ANSI_ARGS_((Blt_TreeNode node));

EXTERN Blt_TreeTrace Blt_TreeCreateTrace _ANSI_ARGS_((Blt_Tree tree, 
	Blt_TreeNode node, char *pattern, unsigned int mask, 
	Blt_TreeTraceProc *proc, ClientData clientData));

EXTERN void Blt_TreeDeleteTrace _ANSI_ARGS_((Blt_TreeTrace token));

EXTERN void Blt_TreeCreateEventHandler _ANSI_ARGS_((Blt_Tree tree, 
	unsigned int mask, Blt_TreeNotifyEventProc *proc, 
	ClientData clientData));

EXTERN void Blt_TreeDeleteEventHandler _ANSI_ARGS_((Blt_Tree tree, 
	unsigned int mask, Blt_TreeNotifyEventProc *proc, 
	ClientData clientData));

EXTERN void Blt_TreeRelabelNode _ANSI_ARGS_((Blt_Tree tree, Blt_TreeNode node, 
	char *string));

#define Blt_TreeName(token)	((token)->tree->name)
#define Blt_TreeRootNode(token)	((token)->root)
#define Blt_TreeChangeRoot(token, node) ((token)->root = (node))

#define Blt_TreeNodeDepth(token, node)	((node)->depth - (token)->root->depth)
#define Blt_TreeNodeLabel(node)	((node)->labelUid)
#define Blt_TreeNodeId(node)	((node)->inode)
#define Blt_TreeNodeParent(node) ((node)->parent)
#define Blt_TreeNodeDegree(node) \
	(((node)->chainPtr == NULL) ? 0 : Blt_ChainGetLength((node)->chainPtr))

#define Blt_TreeIsLeaf(node) \
    (((node)->chainPtr == NULL) || (Blt_ChainGetLength((node)->chainPtr) == 0))

#endif /* _BLT_TREE_H */

