/*
 *
 * bltTreeCmd.c --
 *
 * 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.
 */

/*
  tree create t0 t1 t2
  tree names
  t0 destroy
     -or-
  tree destroy t0
  tree copy tree@node tree@node -recurse -tags

  tree move node after|before|into t2@node

  $t apply -recurse $root command arg arg			

  $t attach treename				

  $t children $n
  t0 copy node1 node2 node3 node4 node5 destName 
  $t delete $n...				
  $t depth $n
  $t dump $root
  $t dup $t2		
  $t find $root -name pat -name pattern
  $t firstchild $n
  $t get $n $key
  $t index $n
  $t insert $parent $switches?
  $t isancestor $n1 $n2
  $t isbefore $n1 $n2
  $t isleaf $n
  $t lastchild $n
  $t move $n1 after|before|into $n2
  $t next $n
  $t nextsibling $n
  $t path $n1 $n2 $n3...
  $t parent $n
  $t previous $n
  $t prevsibling $n
  $t restore $root name data name data name data
  $t root ?$n?

  $t set $n $key $value ?$key $value?
  $t size $n
  $t slink $n $t2@$node				???
  $t sort -recurse $root		

  $t tag delete tag1 tag2 tag3...
  $t tag names
  $t tag nodes $tag
  $t tag set $n tag1 tag2 tag3...
  $t tag unset $n tag1 tag2 tag3...

  $t trace create $n $key how command		
  $t trace delete id1 id2 id3...
  $t trace names
  $t trace info $id

  $t unset $n key1 key2 key3...
  
  $t notify create -oncreate -ondelete -onmove command 
  $t notify create -oncreate -ondelete -onmove -onsort command arg arg arg 
  $t notify delete id1 id2 id3
  $t notify names
  $t notify info id

  for { set n [$t firstchild $node] } { $n >= 0 } { 
        set n [$t nextsibling $n] } {
  }
  foreach n [$t children $node] { 
	  
  }
  set n [$t next $node]
  set n [$t previous $node]

*/

#include <bltInt.h>

#ifndef NO_TREE

#include <bltChain.h>
#include <bltList.h>
#include <bltTree.h>
#include "bltSwitch.h"
#include <ctype.h>

#define TREE_THREAD_KEY "BLT Tree Command Data"
#define TREE_MAGIC ((unsigned int) 0x46170277)

enum TagTypes { TAG_TYPE_NONE, TAG_TYPE_ALL, TAG_TYPE_TAG };

typedef struct {
    Tcl_HashTable treeTable;	/* Hash table of trees keyed by address. */
    Tcl_Interp *interp;
} TreeCmdInterpData;

typedef struct {
    Blt_Uid tagUid;
    Tcl_HashEntry *hashPtr;
    Blt_ChainLink *linkPtr;
    Tcl_HashTable nodeTable;
} TagInfo;

typedef struct {
    Tcl_Interp *interp;
    Tcl_Command cmdToken;	/* Token for tree's Tcl command. */
    Blt_Tree tree;		/* Token holding internal tree. */

    Tcl_HashEntry *hashPtr;

    Tcl_HashTable tagsTable;
    Blt_Chain *tagChainPtr;	/* Chain of tags.  Same as hash table
				 * above but maintains the tag order
				 * and can delete entries in tag walks. */

    TreeCmdInterpData *dataPtr;	/*  */

    int traceCounter;		/* Used to generate trace id strings.  */
    Tcl_HashTable traceTable;	/* Table of active traces. Maps trace ids
				 * back to their TraceInfo records. */

    int notifyCounter;		/* Used to generate notify id strings. */
    Tcl_HashTable notifyTable;	/* Table of event handlers. Maps notify ids
				 * back to their NotifyInfo records. */
} TreeCmd;

typedef struct {
    TreeCmd *cmdPtr;
    Blt_Uid tagUid;		/* If non-NULL, the event or trace was
				 * specified with this tag. In this
				 * case, the standard handler will
				 * check if the particular node has
				 * this tag. */
    char *command;		/* Command prefix for the trace or notify
				 * Tcl callback.  Extra arguments will be
				 * appended to the end. */
    Blt_TreeNode node;
    Blt_TreeTrace traceToken;
    
} TraceInfo;

typedef struct {
    TreeCmd *cmdPtr;
    int mask;
    Tcl_Obj **objv;
    int objc;
    char *command;		/* Command prefix for the notify Tcl 
				 * callback.  Extra arguments will be
				 * appended to the end. */
    Blt_TreeNode node;		/* Node affected by event. */
    Blt_TreeTrace notifyToken;
    
} NotifyInfo;


typedef struct {
    int mask;
} NotifyData;

static Blt_SwitchSpec notifySwitches[] = 
{
    {BLT_SWITCH_FLAG, "-create", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_CREATE},
    {BLT_SWITCH_FLAG, "-delete", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_DELETE},
    {BLT_SWITCH_FLAG, "-move", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_MOVE},
    {BLT_SWITCH_FLAG, "-sort", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_SORT},
    {BLT_SWITCH_FLAG, "-relabel", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_RELABEL},
    {BLT_SWITCH_FLAG, "-allevents", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_ALL},
    {BLT_SWITCH_FLAG, "-whenidle", Blt_Offset(NotifyData, mask), 0, 0, 
	TREE_NOTIFY_WHENIDLE},
    {BLT_SWITCH_END, NULL, 0, 0}
};

typedef struct {
    char *label;
    int insertPos;
    char **tags;
    char **dataPairs;
} InsertData;

static Blt_SwitchSpec insertSwitches[] = 
{
    {BLT_SWITCH_INT_NONNEGATIVE, "-at", Blt_Offset(InsertData, insertPos), 0},
    {BLT_SWITCH_LIST, "-data", Blt_Offset(InsertData, dataPairs), 0},
    {BLT_SWITCH_STRING, "-label", Blt_Offset(InsertData, label), 0},
    {BLT_SWITCH_LIST, "-tags", Blt_Offset(InsertData, tags), 0},
    {BLT_SWITCH_END, NULL, 0, 0}
};

#define PATTERN_NONE		(0)
#define PATTERN_EXACT		(1)
#define PATTERN_GLOB		(2)
#define PATTERN_REGEXP		(3)
#define PATTERN_MASK		(0x3)
#define MATCH_INVERT		(1<<8)
#define MATCH_LEAFONLY		(1<<4)
#define MATCH_NOCASE		(1<<5)
#define MATCH_PATHNAME		(1<<6)

typedef struct {
    TreeCmd *cmdPtr;		/* Tree to examine. */
    Tcl_Obj *listObjPtr;	/* List to accumulate the indices of 
				 * matching nodes. */
    Tcl_Obj **objv;		/* Command converted into an array of 
				 * Tcl_Obj's. */
    int objc;			/* Number of Tcl_Objs in above array. */

    int nMatches;		/* Current number of matches. */

    int flags;			/* See flags definitions above. */

    /* Integer options. */
    int maxMatches;		/* If > 0, stop after this many matches. */
    int maxDepth;		/* If > 0, don't descend more than this
				 * many levels. */
    int order;			/* Order of search: Can be either
				 * TREE_PREORDER, TREE_POSTORDER,
				 * TREE_INORDER, TREE_BREADTHFIRST. */
    /* String options. */
    char *pattern;		/* If non-NULL, pattern to use when 
				 * comparing node names. */
    char *addTag;		/* If non-NULL, tag to add to selected nodes. */

    char **command;		/* Command split into a Tcl list. */

    char *key;			/*  */
    char *tag;			/* Search tag */
    char *tagUid;

} FindData;

static int StringToOrder _ANSI_ARGS_((ClientData clientData,
	Tcl_Interp *interp, char *string, char *record, int offset));

static Blt_CustomSwitch orderSwitch =
{
    StringToOrder, (ClientData)0,
};

static Blt_SwitchSpec findSwitches[] = 
{
    {BLT_SWITCH_STRING, "-addtag", Blt_Offset(FindData, addTag), 0},
    {BLT_SWITCH_INT_NONNEGATIVE, "-count", Blt_Offset(FindData, maxMatches), 0},
    {BLT_SWITCH_INT_NONNEGATIVE, "-depth", Blt_Offset(FindData, maxDepth), 0},
    {BLT_SWITCH_STRING, "-exact", Blt_Offset(FindData, pattern), 0},
    {BLT_SWITCH_LIST, "-exec", Blt_Offset(FindData, command), 0},
    {BLT_SWITCH_STRING, "-glob", Blt_Offset(FindData, pattern), 0},
    {BLT_SWITCH_FLAG, "-invert", Blt_Offset(FindData, flags), 0, 0, 
	MATCH_INVERT},
    {BLT_SWITCH_STRING, "-key", Blt_Offset(FindData, key), 0},
    {BLT_SWITCH_FLAG, "-leafonly", Blt_Offset(FindData, flags), 0, 0, 
	MATCH_LEAFONLY},
    {BLT_SWITCH_FLAG, "-nocase", Blt_Offset(FindData, flags), 0, 0, 
	MATCH_NOCASE},
    {BLT_SWITCH_CUSTOM, "-order", Blt_Offset(FindData, order), 0, &orderSwitch},
    {BLT_SWITCH_FLAG, "-path", Blt_Offset(FindData, flags), 0, 0, 
	MATCH_PATHNAME},
    {BLT_SWITCH_STRING, "-regexp", Blt_Offset(FindData, pattern), 0},
    {BLT_SWITCH_STRING, "-tag", Blt_Offset(FindData, tag), 0},
    {BLT_SWITCH_END, NULL, 0, 0}
};

static int StringToNode _ANSI_ARGS_((ClientData clientData,
	Tcl_Interp *interp, char *string, char *record, int offset));

static Blt_CustomSwitch nodeSwitch =
{
    StringToNode, (ClientData)0,
};

typedef struct {
    TreeCmd *cmdPtr;		/* Tree to move nodes. */
    Blt_TreeNode node;
    int insertPos;
} MoveData;

static Blt_SwitchSpec moveSwitches[] = 
{
    {BLT_SWITCH_CUSTOM, "-after", Blt_Offset(MoveData, node), 0, &nodeSwitch},
    {BLT_SWITCH_INT_NONNEGATIVE, "-at", Blt_Offset(MoveData, insertPos), 0},
    {BLT_SWITCH_CUSTOM, "-before", Blt_Offset(MoveData, node), 0, &nodeSwitch},
    {BLT_SWITCH_END, NULL, 0, 0}
};

typedef struct {
    Blt_TreeNode srcNode, destNode;
    Blt_Tree srcTree, destTree;
    TreeCmd *srcPtr, *destPtr;
    int flags;
} CopyData;

#define COPY_RECURSE	(1<<0)
#define COPY_TAGS	(1<<1)

static Blt_SwitchSpec copySwitches[] = 
{
    {BLT_SWITCH_FLAG, "-recurse", Blt_Offset(CopyData, flags), 0, 0, 
	COPY_RECURSE},
    {BLT_SWITCH_FLAG, "-tags", Blt_Offset(CopyData, flags), 0, 0, 
	COPY_TAGS},
    {BLT_SWITCH_END, NULL, 0, 0}
};


typedef struct {
    TreeCmd *cmdPtr;		/* Tree to examine. */
    Tcl_Obj **preObjv;		/* Command converted into an array of 
				 * Tcl_Obj's. */
    int preObjc;		/* Number of Tcl_Objs in above array. */

    Tcl_Obj **postObjv;		/* Command converted into an array of 
				 * Tcl_Obj's. */
    int postObjc;		/* Number of Tcl_Objs in above array. */

    int flags;			/* See flags definitions above. */

    int maxDepth;		/* If > 0, don't descend more than this
				 * many levels. */
    /* String options. */
    char *pattern;		/* If non-NULL, pattern to use when 
				 * comparing node names. */
    char **preCmd;		/* Pre-command split into a Tcl list. */
    char **postCmd;		/* Post-command split into a Tcl list. */

    char *key;			/*  */
    char *tag;			/* Search tag */
    char *tagUid;
} ApplyData;

static Blt_SwitchSpec applySwitches[] = 
{
    {BLT_SWITCH_LIST, "-precommand", Blt_Offset(ApplyData, preCmd), 0},
    {BLT_SWITCH_LIST, "-postcommand", Blt_Offset(ApplyData, postCmd), 0},
    {BLT_SWITCH_INT_NONNEGATIVE, "-depth", Blt_Offset(ApplyData, maxDepth), 0},
    {BLT_SWITCH_STRING, "-exact", Blt_Offset(ApplyData, pattern), 0},
    {BLT_SWITCH_STRING, "-glob", Blt_Offset(ApplyData, pattern), 0},
    {BLT_SWITCH_FLAG, "-invert", Blt_Offset(ApplyData, flags), 0, 0, 
	MATCH_INVERT},
    {BLT_SWITCH_STRING, "-key", Blt_Offset(ApplyData, key), 0},
    {BLT_SWITCH_FLAG, "-leafonly", Blt_Offset(ApplyData, flags), 0, 0, 
	MATCH_LEAFONLY},
    {BLT_SWITCH_FLAG, "-nocase", Blt_Offset(ApplyData, flags), 0, 0, 
	MATCH_NOCASE},
    {BLT_SWITCH_FLAG, "-path", Blt_Offset(ApplyData, flags), 0, 0, 
	MATCH_PATHNAME},
    {BLT_SWITCH_STRING, "-regexp", Blt_Offset(ApplyData, pattern), 0},
    {BLT_SWITCH_STRING, "-tag", Blt_Offset(ApplyData, tag), 0},
    {BLT_SWITCH_END, NULL, 0, 0}
};


static Tcl_InterpDeleteProc TreeInterpDeleteProc;
static Blt_TreeApplyProc MatchNodeProc, SortApplyProc;
static Blt_TreeApplyProc ApplyNodeProc;
static Blt_TreeTraceProc TreeTraceProc;
static Tcl_CmdDeleteProc TreeInstDeleteProc;
static Blt_TreeCompareNodesProc CompareNodes;

static int TreeEventProc _ANSI_ARGS_((ClientData clientData, 
	Blt_TreeNotifyEvent *eventPtr));
static int GetNode _ANSI_ARGS_((TreeCmd *cmdPtr, Tcl_Obj *objPtr, 
	Blt_TreeNode *nodePtr));

static Tk_Uid allUid, rootUid;


/*
 *----------------------------------------------------------------------
 *
 * StringToNode --
 *
 *	Convert a string represent a node number into its integer
 *	value.
 *
 * Results:
 *	The return value is a standard Tcl result.
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
static int
StringToNode(clientData, interp, string, record, offset)
    ClientData clientData;	/* Contains a pointer to the tabset containing
				 * this image. */
    Tcl_Interp *interp;		/* Interpreter to send results back to */
    char *string;		/* String representation */
    char *record;		/* Structure record */
    int offset;			/* Offset to field in structure */
{
    MoveData *dataPtr = (MoveData *)record;
    Blt_TreeNode node;
    Tcl_Obj *objPtr;
    TreeCmd *cmdPtr = dataPtr->cmdPtr;

    objPtr = Tcl_NewStringObj(string, -1);
    if (GetNode(cmdPtr, objPtr, &node) != TCL_OK) {
	return TCL_ERROR;
    }
    dataPtr->node = node;
    return TCL_OK;
}


/*
 *----------------------------------------------------------------------
 *
 * StringToNode --
 *
 *	Convert a string represent a node number into its integer
 *	value.
 *
 * Results:
 *	The return value is a standard Tcl result.
 *
 *----------------------------------------------------------------------
 */
/*ARGSUSED*/
static int
StringToOrder(clientData, interp, string, record, offset)
    ClientData clientData;	/* Contains a pointer to the tabset containing
				 * this image. */
    Tcl_Interp *interp;		/* Interpreter to send results back to */
    char *string;		/* String representation */
    char *record;		/* Structure record */
    int offset;			/* Offset to field in structure */
{
    int *orderPtr = (int *)(record + offset);
    char c;

    c = string[0];
    if ((c == 'b') && (strcmp(string, "breadthfirst") == 0)) {
	*orderPtr = TREE_BREADTHFIRST;
    } else if ((c == 'i') && (strcmp(string, "inorder") == 0)) {
	*orderPtr = TREE_INORDER;
    } else if ((c == 'p') && (strcmp(string, "preorder") == 0)) {
	*orderPtr = TREE_PREORDER;
    } else if ((c == 'p') && (strcmp(string, "postorder") == 0)) {
	*orderPtr = TREE_POSTORDER;
    } else {
	Tcl_AppendResult(interp, "bad order \"", string, 
		 "\": should be breadthfirst, inorder, preorder, or postorder",
		 (char *)NULL);
	return TCL_ERROR;
    }
    return TCL_OK;
}


static void
strtolower(s) 
    register char *s;
{
    while (*s != '\0') {
	*s = tolower(UCHAR(*s));
	s++;
    }
}
    
#if (TK_VERSION_NUMBER < _VERSION(8,1,0))

int 
Tcl_EvalObjv(interp, objc, objv, flags)
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
    int flags;
{
    Tcl_DString dString;
    register int i;
    int result, nBytes;
    char *string;

    Tcl_DStringInit(&dString);
    for (i = 0; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	Tcl_DStringAppendElement(&dString, string);
    }
    result = Tcl_Eval(interp, Tcl_DStringValue(&dString)); 
    Tcl_DStringFree(&dString);
    return result;
}

#endif

/*
 *----------------------------------------------------------------------
 *
 * GetTreeInterpData --
 *
 *---------------------------------------------------------------------- 
 */
static TreeCmdInterpData *
GetTreeInterpData(interp)
    Tcl_Interp *interp;
{
    TreeCmdInterpData *dataPtr;
    Tcl_InterpDeleteProc *proc;

    dataPtr = (TreeCmdInterpData *)
	Tcl_GetAssocData(interp, TREE_THREAD_KEY, &proc);
    if (dataPtr == NULL) {
	dataPtr = (TreeCmdInterpData *)malloc(sizeof(TreeCmdInterpData));
	assert(dataPtr);
	dataPtr->interp = interp;
	Tcl_SetAssocData(interp, TREE_THREAD_KEY, TreeInterpDeleteProc,
		 (ClientData)dataPtr);
	Tcl_InitHashTable(&(dataPtr->treeTable), TCL_ONE_WORD_KEYS);
    }
    return dataPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * GetTreeCmd --
 *
 *	Find the tree command associated with the Tcl command "string".
 *	
 *	We have to do multiple lookups to get this right.  
 *
 *	The first step is to generate a canonical command name.
 *	Unlike Tcl's view of namespaces, I want an unqualified command
 *	name (i.e.  no namespace) qualifier to designate the current
 *	namespace, not the global one.  If there is no namespace
 *	qualifier, we'll rebuild the command string, tacking on the
 *	the current namespace rather than the global one that
 *	Tcl_GetCommandInfo will give us.
 *
 *	Next, we check if the string is a) a Tcl command and b) really
 *	a command for a tree object.  Tcl_GetCommandInfo will get us
 *	the objClientData field that should be a cmdPtr.  We can
 *	verify that by searching our hashtable of cmdPtr addresses.
 *
 *---------------------------------------------------------------------- 
*/
static TreeCmd *
GetTreeCmd(dataPtr, interp, string)
    TreeCmdInterpData *dataPtr;
    Tcl_Interp *interp;
    char *string;
{
    char *name;
    Tcl_Namespace *nsPtr;
    Tcl_CmdInfo cmdInfo;
    Tcl_HashEntry *hPtr;
    Tcl_DString dString;
    char *treeName;
    int result;

    /* Put apart the tree name and put is back together in a standard
     * format. */
    if (Blt_ParseQualifiedName(interp, string, &nsPtr, &name) != TCL_OK) {
	return NULL;		/* No such parent namespace. */
    }
    if (nsPtr == NULL) {
	nsPtr = Tcl_GetCurrentNamespace(interp);
    }
    /* Rebuild the fully qualified name. */
    treeName = Blt_GetQualifiedName(nsPtr, name, &dString);

    result = Tcl_GetCommandInfo(interp, treeName, &cmdInfo);
    Tcl_DStringFree(&dString);

    if (!result) {
	return NULL;
    }
    hPtr = Tcl_FindHashEntry(&(dataPtr->treeTable), 
		     (char *)(cmdInfo.objClientData));
    if (hPtr == NULL) {
	return NULL;
    }
    return (TreeCmd *)Tcl_GetHashValue(hPtr);
}


/*
 *----------------------------------------------------------------------
 *
 * GetTagTable --
 *
 *---------------------------------------------------------------------- 
 */
static Tcl_HashTable *
GetTagTable(cmdPtr, tagUid)
    TreeCmd *cmdPtr;
    Blt_Uid tagUid;
{
    Tcl_HashEntry *hPtr;

    hPtr = Tcl_FindHashEntry(&(cmdPtr->tagsTable), tagUid);
    if (hPtr != NULL) {
	TagInfo *tagPtr;
	
	tagPtr = (TagInfo *)Tcl_GetHashValue(hPtr);
	return &(tagPtr->nodeTable);
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * DestroyTagInfo --
 *
 *---------------------------------------------------------------------- 
 */
static void
DestroyTagInfo(cmdPtr, tagPtr)
    TreeCmd *cmdPtr;
    TagInfo *tagPtr;
{
    Tcl_DeleteHashEntry(tagPtr->hashPtr);
    Tcl_DeleteHashTable(&(tagPtr->nodeTable));
    Blt_ChainDeleteLink(cmdPtr->tagChainPtr, tagPtr->linkPtr);
    Blt_FreeUid(tagPtr->tagUid);
    free((char *)tagPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * ForgetTag --
 *
 *---------------------------------------------------------------------- 
 */
static int
ForgetTag(cmdPtr, string)
    TreeCmd *cmdPtr;
    char *string;
{
    Tcl_HashEntry *hPtr;
    TagInfo *tagPtr;
    Blt_Uid tagUid;

    tagUid = Blt_FindUid(string);
    if (tagUid == NULL) {
	return TCL_ERROR;
    }
    if ((tagUid == allUid) || (tagUid == rootUid)) {
	return TCL_OK;
    }
    hPtr = Tcl_FindHashEntry(&(cmdPtr->tagsTable), tagUid);
    if (hPtr == NULL) {
	return TCL_ERROR;
    }
    tagPtr = (TagInfo *)Tcl_GetHashValue(hPtr);
    DestroyTagInfo(cmdPtr, tagPtr);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * AddTag --
 *
 *---------------------------------------------------------------------- 
 */
static int
AddTag(cmdPtr, node, string)
    TreeCmd *cmdPtr;
    Blt_TreeNode node;
    char *string;
{
    Tcl_HashEntry *hPtr;
    TagInfo *tagPtr;
    int isNew;
    Blt_Uid tagUid;

    tagUid = Blt_FindUid(string);
    if ((tagUid == allUid) || (tagUid == rootUid)) {
	Tcl_AppendResult(cmdPtr->interp, "can't add reserved tag \"",
			 string, "\"", (char *)NULL);
	return TCL_ERROR;
    }
    tagUid = Blt_GetUid(string);
    hPtr = Tcl_CreateHashEntry(&(cmdPtr->tagsTable), tagUid, &isNew);
    assert(hPtr);
    if (isNew) {
	tagPtr = (TagInfo *)malloc(sizeof(TagInfo));
	Tcl_InitHashTable(&(tagPtr->nodeTable), TCL_ONE_WORD_KEYS);
	Tcl_SetHashValue(hPtr, (ClientData)tagPtr);
	tagPtr->hashPtr = hPtr;
	tagPtr->tagUid = Blt_GetUid(string);
	tagPtr->linkPtr = Blt_ChainAppend(cmdPtr->tagChainPtr, 
		(ClientData)tagPtr);
    } else {
	tagPtr = (TagInfo *)Tcl_GetHashValue(hPtr);
    }
    hPtr = Tcl_CreateHashEntry(&(tagPtr->nodeTable), (char *)node, &isNew);
    assert(hPtr);
    if (isNew) {
	Tcl_SetHashValue(hPtr, (ClientData)node);
    }
    Blt_FreeUid(tagUid);
    return TCL_OK;
}
    
/*
 *----------------------------------------------------------------------
 *
 * HasTag --
 *
 *---------------------------------------------------------------------- 
 */
static int
HasTag(cmdPtr, node, tagUid)
    TreeCmd *cmdPtr;
    Blt_TreeNode node;
    Blt_Uid tagUid;
{
    Tcl_HashEntry *hPtr;
    TagInfo *tagPtr;

    if ((tagUid == rootUid) && (node == Blt_TreeRootNode(cmdPtr->tree))) {
	return TRUE;
    }
    if (tagUid == allUid) {
	return TRUE;
    }
    hPtr = Tcl_FindHashEntry(&(cmdPtr->tagsTable), tagUid);
    if (hPtr == NULL) {
	return FALSE;
    }
    tagPtr = (TagInfo *)Tcl_GetHashValue(hPtr);
    hPtr = Tcl_FindHashEntry(&(tagPtr->nodeTable), (char *)node);
    if (hPtr == NULL) {
	return FALSE;
    }
    return TRUE;
}

static void
ClearTags(cmdPtr, node)
    TreeCmd *cmdPtr;
    Blt_TreeNode node;
{
    Tcl_HashEntry *hPtr;
    TagInfo *tagPtr;
    Blt_ChainLink *linkPtr, *nextPtr;

    for (linkPtr = Blt_ChainFirstLink(cmdPtr->tagChainPtr); linkPtr != NULL;
	 linkPtr = nextPtr) {
	nextPtr = Blt_ChainNextLink(linkPtr);

	tagPtr = (TagInfo *)Blt_ChainGetValue(linkPtr);
	hPtr = Tcl_FindHashEntry(&(tagPtr->nodeTable), (char *)node);
	if (hPtr != NULL) {
	    Tcl_DeleteHashEntry(hPtr);
	}
	if (tagPtr->nodeTable.numEntries == 0) {
	    DestroyTagInfo(cmdPtr, tagPtr);
	}
    }
}

static Blt_TreeNode 
ParseModifiers(tree, node, modifiers)
     Blt_Tree tree;
     Blt_TreeNode node;
     char *modifiers;
{
    char *p, *np;
    Blt_TreeNode last;

    p = modifiers;
    do {
	last = node;
	p += 2;			/* Skip the initial "->" */
	np = strstr(p, "->");
	if (np != NULL) {
	    *np = '\0';
	}
	if ((*p == 'p') && (strcmp(p, "parent") == 0)) {
	    node = Blt_TreeNodeParent(node);
	} else if ((*p == 'f') && (strcmp(p, "firstchild") == 0)) {
	    node = Blt_TreeFirstChild(node);
	} else if ((*p == 'l') && (strcmp(p, "lastchild") == 0)) {
	    node = Blt_TreeLastChild(node);
	} else if ((*p == 'n') && (strcmp(p, "next") == 0)) {
	    node = Blt_TreeNextNode(Blt_TreeRootNode(tree), node);
	} else if ((*p == 'n') && (strcmp(p, "nextsibling") == 0)) {
	    node = Blt_TreeNextSibling(node);
	} else if ((*p == 'p') && (strcmp(p, "previous") == 0)) {
	    node = Blt_TreePrevNode(Blt_TreeRootNode(tree), node);
	} else if ((*p == 'p') && (strcmp(p, "prevsibling") == 0)) {
	    node = Blt_TreePrevSibling(node);
	} else {
	    goto error;
	}
	if (node == NULL) {
	    goto error;
	}
	if (np != NULL) {
	    *np = '-';		/* Repair the string */
	}
	p = np;
    } while (np != NULL);
    return node;
 error:
    if (np != NULL) {
	*np = '-';		/* Repair the string */
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * GetNode --
 *
 *---------------------------------------------------------------------- 
 */
static int 
GetForeignNode(interp, tree, objPtr, nodePtr)
    Tcl_Interp *interp;
    Blt_Tree tree;
    Tcl_Obj *objPtr;
    Blt_TreeNode *nodePtr;
{
    char c;
    Blt_TreeNode node;
    char *string;
    int nBytes;
    char *p;

    node = NULL;
    string = Tcl_GetStringFromObj(objPtr, &nBytes);
    c = string[0];

    /* 
     * Check if modifiers are present.
     */
    p = strstr(string, "->");
    if (isdigit(UCHAR(c))) {
	int inode;

	if (p != NULL) {
	    char save;
	    int result;

	    save = *p;
	    *p = '\0';
	    result = Tcl_GetInt(interp, string, &inode);
	    *p = save;
	    if (result != TCL_OK) {
		return TCL_ERROR;
	    }
	} else {
	    if (Tcl_GetIntFromObj(interp, objPtr, &inode) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
	node = Blt_TreeGetNode(tree, inode);
	if (p != NULL) {
	    node = ParseModifiers(tree, node, p);
	}
	if (node != NULL) {
	    *nodePtr = node;
	    return TCL_OK;
	}
    }
    Tcl_AppendResult(interp, "can't find node \"", string, "\" in ",
	 Blt_TreeName(tree), (char *)NULL);
    return TCL_ERROR;
}

/*
 *----------------------------------------------------------------------
 *
 * GetNode --
 *
 *---------------------------------------------------------------------- 
 */
static int 
GetNode(cmdPtr, objPtr, nodePtr)
    TreeCmd *cmdPtr;
    Tcl_Obj *objPtr;
    Blt_TreeNode *nodePtr;
{
    Tcl_Interp *interp = cmdPtr->interp;
    Blt_Tree tree = cmdPtr->tree;
    char c;
    Blt_TreeNode node;
    char *string;
    int nBytes;
    char *p;

    node = NULL;
    string = Tcl_GetStringFromObj(objPtr, &nBytes);
    c = string[0];

    /* 
     * Check if modifiers are present.
     */
    p = strstr(string, "->");
    if (isdigit(UCHAR(c))) {
	int inode;

	if (p != NULL) {
	    char save;
	    int result;

	    save = *p;
	    *p = '\0';
	    result = Tcl_GetInt(interp, string, &inode);
	    *p = save;
	    if (result != TCL_OK) {
		return TCL_ERROR;
	    }
	} else {
	    if (Tcl_GetIntFromObj(interp, objPtr, &inode) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
	node = Blt_TreeGetNode(tree, inode);
	if (p != NULL) {
	    node = ParseModifiers(tree, node, p);
	}
	if (node != NULL) {
	    *nodePtr = node;
	    return TCL_OK;
	}
    }  else if (cmdPtr != NULL) {
	Blt_Uid tagUid;
	
	if (p != NULL) {
	    char save;

	    save = *p;
	    *p = '\0';
	    tagUid = Blt_FindUid(string);
	    *p = save;
	} else {
	    tagUid = Blt_FindUid(string);
	}
	if (tagUid != NULL) {
	    if ((tagUid == allUid) && 
		(Blt_TreeSize(Blt_TreeRootNode(tree)) > 1)) {
		Tcl_AppendResult(interp, "more than one node tagged as \"", 
				     tagUid, "\"", (char *)NULL);
		return TCL_ERROR;
	    }
	    if (tagUid == rootUid) {
		node = Blt_TreeRootNode(tree);
	    } else {
		Tcl_HashTable *tablePtr;
		Tcl_HashSearch cursor;
		Tcl_HashEntry *hPtr;

		tablePtr = GetTagTable(cmdPtr, tagUid);
		if (tablePtr == NULL) {
		    Tcl_AppendResult(interp, "nothing tagged as \"", 
				 tagUid, "\"", (char *)NULL);
		    return TCL_ERROR;
		}
		if (tablePtr->numEntries > 1) {
		    Tcl_AppendResult(interp, 
				 "more than one node tagged as \"", 
				 tagUid, "\"", (char *)NULL);
		    return TCL_ERROR;
		}
		hPtr = Tcl_FirstHashEntry(tablePtr, &cursor);
		node = (Blt_TreeNode)Tcl_GetHashValue(hPtr);
	    }
	    if (p != NULL) {
		node = ParseModifiers(tree, node, p);
	    }
	    if (node != NULL) {
		*nodePtr = node;
		return TCL_OK;
	    }
	}
    }
    Tcl_AppendResult(interp, "can't find node \"", string, "\" in ",
		 Blt_TreeName(tree), (char *)NULL);
    return TCL_ERROR;
}

typedef struct {
    int tagType;
    Blt_TreeNode root;
    Tcl_HashSearch cursor;
} TagSearch;

static Blt_TreeNode
FirstTaggedNode(interp, cmdPtr, objPtr, cursorPtr)	
    Tcl_Interp *interp;
    TreeCmd *cmdPtr;
    Tcl_Obj *objPtr;
    TagSearch *cursorPtr;
{
    char *string;
    int nBytes;
    Blt_TreeNode node;
    Blt_Uid tagUid;
    Blt_TreeNode root;

    root = Blt_TreeRootNode(cmdPtr->tree);
    string = Tcl_GetStringFromObj(objPtr, &nBytes);
    cursorPtr->tagType = TAG_TYPE_NONE;
    cursorPtr->root = root;

    if (isdigit(UCHAR(*string))) {
	if (GetNode(cmdPtr, objPtr, &node) != TCL_OK) {
	    return NULL;
	}
	return node;
    } 
    tagUid = Blt_FindUid(string);
    if (tagUid != NULL) {
	if (tagUid == allUid) {
	    cursorPtr->tagType = TAG_TYPE_ALL;
	    return root;
	} else if (tagUid == rootUid)  {
	    return root;
	} else {
	    Tcl_HashTable *tablePtr;

	    tablePtr = GetTagTable(cmdPtr, tagUid);
	    if (tablePtr != NULL) {
		Tcl_HashEntry *hPtr;
		
		hPtr = Tcl_FirstHashEntry(tablePtr, &(cursorPtr->cursor)); 
		node = (Blt_TreeNode)Tcl_GetHashValue(hPtr);
		cursorPtr->tagType = TAG_TYPE_TAG;
		return node;
	    }
	}
    }
    Tcl_AppendResult(interp, "can't find tag or id \"", string, "\" in ", 
	Blt_TreeName(cmdPtr->tree), (char *)NULL);
    return NULL;
}

static Blt_TreeNode
NextTaggedNode(node, cursorPtr)	
    Blt_TreeNode node;
    TagSearch *cursorPtr;
{
    if (cursorPtr->tagType == TAG_TYPE_ALL) {
	return Blt_TreeNextNode(cursorPtr->root, node);
    }
    if (cursorPtr->tagType == TAG_TYPE_TAG) {
	Tcl_HashEntry *hPtr;

	hPtr = Tcl_NextHashEntry(&(cursorPtr->cursor));
	if (hPtr == NULL) {
	    return NULL;
	}
	return (Blt_TreeNode)Tcl_GetHashValue(hPtr);
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * DeleteNode --
 *
 *---------------------------------------------------------------------- 
 */
static void
DeleteNode(cmdPtr, node)
    TreeCmd *cmdPtr;
    Blt_TreeNode node;
{
    Blt_TreeNode root;

    ClearTags(cmdPtr, node);
    root = Blt_TreeRootNode(cmdPtr->tree);
    if (node == root) {
	Blt_TreeNode next;
	/* Don't delete the root node. Simply clean out the tree. */
	for (node = Blt_TreeFirstChild(node); node != NULL; node = next) {
	    next = Blt_TreeNextSibling(node);
	    Blt_TreeDeleteNode(cmdPtr->tree, node);
	}	    
    } else if (Blt_TreeIsAncestor(root, node)) {
	Blt_TreeDeleteNode(cmdPtr->tree, node);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * GetNodePath --
 *
 *---------------------------------------------------------------------- 
 */
static char *
GetNodePath(cmdPtr, root, node, dStrPtr)
    TreeCmd *cmdPtr;
    Blt_TreeNode root, node;
    Tcl_DString *dStrPtr;
{
    char **nameArr;		/* Used to stack the component names. */
    char *staticSpace[64];
    register int i;
    int nLevels;

    nLevels = Blt_TreeNodeDepth(cmdPtr->tree, node) -
	Blt_TreeNodeDepth(cmdPtr->tree, root);
    if (nLevels > 64) {
	nameArr = (char **)malloc(nLevels * sizeof(char *));
	assert(nameArr);
    } else {
	nameArr = staticSpace;
    }
    for (i = nLevels; i > 0; i--) {
	/* Save the name of each ancestor in the name array. 
	 * Note that we ignore the root. */
	nameArr[i - 1] = Blt_TreeNodeLabel(node);
	node = Blt_TreeNodeParent(node);
    }
    /* Append each the names in the array. */
    Tcl_DStringInit(dStrPtr);
    for (i = 0; i < nLevels; i++) {
	Tcl_DStringAppendElement(dStrPtr, nameArr[i]);
    }
    if (nameArr != staticSpace) {
	free((char *)nameArr);
    }
    return Tcl_DStringValue(dStrPtr);
}

static void
PrintNode(cmdPtr, root, node, dStrPtr)
    TreeCmd *cmdPtr;
    Blt_TreeNode root, node;
    Tcl_DString *dStrPtr;
{
    char *pathName;
    Tcl_DString dString;
    int nBytes;
    char *string;
    Blt_TreeCursor cursor;
    Tcl_Obj *valuePtr;
    register Blt_Uid keyUid;
    TagInfo *tagPtr;
    Blt_ChainLink *linkPtr;

    pathName = GetNodePath(cmdPtr, root, node, &dString);
    Tcl_DStringAppendElement(dStrPtr, pathName);
    Tcl_DStringStartSublist(dStrPtr);
    for (keyUid = Blt_TreeFirstKey(node, &cursor); keyUid != NULL;
	 keyUid = Blt_TreeNextKey(&cursor)) {
	/* 
	 * Don't call BltTreeGetValueByUid even though we already have
	 * a Uid. It will pick up even those fields that we don't want
	 * to publish. 
	 */
	if (Blt_TreeGetValue(cmdPtr->tree, node, keyUid, &valuePtr) == TCL_OK) {
	    string = Tcl_GetStringFromObj(valuePtr, &nBytes);
	    Tcl_DStringAppendElement(dStrPtr, keyUid);
	    Tcl_DStringAppendElement(dStrPtr, string);
	}
    }	    
    Tcl_DStringEndSublist(dStrPtr);
    Tcl_DStringStartSublist(dStrPtr);
    for (linkPtr = Blt_ChainFirstLink(cmdPtr->tagChainPtr); linkPtr != NULL;
	 linkPtr = Blt_ChainNextLink(linkPtr)) {
	tagPtr = (TagInfo *)Blt_ChainGetValue(linkPtr);
	if (Tcl_FindHashEntry(&(tagPtr->nodeTable), (char *)node) != NULL) {
	    Tcl_DStringAppendElement(dStrPtr, tagPtr->tagUid);
	}
    }
    Tcl_DStringEndSublist(dStrPtr);
    Tcl_DStringAppend(dStrPtr, "\n", -1);
    Tcl_DStringFree(&dString);
}

/*
 *----------------------------------------------------------------------
 *
 * PrintTraceFlags --
 *
 *---------------------------------------------------------------------- 
 */
static void
PrintTraceFlags(flags, string)
    int flags;
    char *string;
{
    register char *p;

    p = string;
    if (flags & TREE_TRACE_READ) {
	*p++ = 'r';
    } 
    if (flags & TREE_TRACE_WRITE) {
	*p++ = 'w';
    } 
    if (flags & TREE_TRACE_UNSET) {
	*p++ = 'u';
    } 
    if (flags & TREE_TRACE_CREATE) {
	*p++ = 'c';
    } 
    *p = '\0';
}

/*
 *----------------------------------------------------------------------
 *
 * GetTraceFlags --
 *
 *---------------------------------------------------------------------- 
 */
static int
GetTraceFlags(string)
    char *string;
{
    register char *p;
    int flags;

    flags = 0;
    for (p = string; *p != '\0'; p++) {
	switch (toupper(*p)) {
	case 'R':
	    flags |= TREE_TRACE_READ;
	    break;
	case 'W':
	    flags |= TREE_TRACE_WRITE;
	    break;
	case 'U':
	    flags |= TREE_TRACE_UNSET;
	    break;
	case 'C':
	    flags |= TREE_TRACE_CREATE;
	    break;
	default:
	    return -1;
	}
    }
    return flags;
}

/*
 *----------------------------------------------------------------------
 *
 * SetValues --
 *
 *---------------------------------------------------------------------- 
 */
static int
SetValues(cmdPtr, node, objc, objv)
    TreeCmd *cmdPtr;
    Blt_TreeNode node;
    int objc;
    Tcl_Obj **objv;
{
    register int i;
    char *string;
    int nBytes;

    for (i = 0; i < objc; i += 2) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	if ((i + 1) == objc) {
	    Tcl_AppendResult(cmdPtr->interp, "missing value for field \"", 
		string, "\"", (char *)NULL);
	    return TCL_ERROR;
	}
	if (Blt_TreeSetValue(cmdPtr->tree, node, string, 
			     objv[i + 1]) != TCL_OK) {
	    return TCL_ERROR;
	}
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * UnsetValues --
 *
 *---------------------------------------------------------------------- 
 */
static int
UnsetValues(cmdPtr, node, objc, objv)
    TreeCmd *cmdPtr;
    Blt_TreeNode node;
    int objc;
    Tcl_Obj **objv;
{
    if (objc == 0) {
	Blt_Uid keyUid;
	Blt_TreeCursor cursor;

	for (keyUid = Blt_TreeFirstKey(node, &cursor); keyUid != NULL;
	     keyUid = Blt_TreeNextKey(&cursor)) {
	    if (Blt_TreeUnsetValue(NULL, node, keyUid) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
    } else {
	register int i;
	char *string;
	int nBytes;

	for (i = 0; i < objc; i ++) {
	    string = Tcl_GetStringFromObj(objv[i], &nBytes);
	    if (Blt_TreeUnsetValue(NULL, node, string) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
    }
    return TCL_OK;
}

static int
MatchNodeProc(node, clientData, order)
    Blt_TreeNode node;
    ClientData clientData;
    int order;
{
    FindData *dataPtr = (FindData *)clientData;
    Tcl_DString dString;
    TreeCmd *cmdPtr = dataPtr->cmdPtr;
    Tcl_Interp *interp = dataPtr->cmdPtr->interp;
    int result, invert, pattern;
    char *string;
    int nBytes;

    if ((dataPtr->flags & MATCH_LEAFONLY) && (!Blt_TreeIsLeaf(node))) {
	return TCL_OK;
    }
    if ((dataPtr->maxDepth >= 0) &&
	(dataPtr->maxDepth < Blt_TreeNodeDepth(cmdPtr->tree, node))) {
	return TCL_OK;
    }
    result = TRUE;
    pattern = (dataPtr->flags & PATTERN_MASK);

    string = NULL;
    if (dataPtr->key != NULL) {
	Tcl_Obj *objPtr;
	
	if (Blt_TreeGetValue(cmdPtr->tree, node, dataPtr->key, 
			     &objPtr) != TCL_OK) {
	    result = FALSE;
	} else {
	    string = Tcl_GetStringFromObj(objPtr, &nBytes);
	}
    } else {	    
	if (dataPtr->flags & MATCH_PATHNAME) {
	    string = GetNodePath(cmdPtr, Blt_TreeRootNode(cmdPtr->tree),
			 node, &dString);
	} else {
	    string = Blt_TreeNodeLabel(node);
	}
    }
    if (pattern != PATTERN_NONE) {
	if (dataPtr->flags & MATCH_NOCASE) {
	    string = strdup(string);
	    strtolower(string);
	}
	switch (pattern) {
	case PATTERN_EXACT:
	    result = (strcmp(string, dataPtr->pattern) == 0);
	    break;
	    
	case PATTERN_GLOB:
	    result = Tcl_StringMatch(string, dataPtr->pattern);
	    break;
	    
	case PATTERN_REGEXP:
	    result = Tcl_RegExpMatch(interp, string, dataPtr->pattern); 
	    break;
	}
	if (dataPtr->flags & MATCH_NOCASE) {
	    free(string);
	}
    } 
    if ((dataPtr->tagUid != NULL) && (!HasTag(cmdPtr, node, dataPtr->tagUid))) {
	result = FALSE;
    }
    invert = (dataPtr->flags & MATCH_INVERT) ? TRUE : FALSE;
    if (result != invert) {
	Tcl_Obj *objPtr;

	if (dataPtr->addTag != NULL) {
	    if (AddTag(cmdPtr, node, dataPtr->addTag) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
	objPtr = Tcl_NewIntObj(Blt_TreeNodeId(node));
	Tcl_ListObjAppendElement(interp, dataPtr->listObjPtr, objPtr);
	if (dataPtr->objv != NULL) {
	    dataPtr->objv[dataPtr->objc - 1] = objPtr;
	    result = Tcl_EvalObjv(interp, dataPtr->objc, dataPtr->objv, 0);
	    if (result != TCL_OK) {
		return result;
	    }
	}
	dataPtr->nMatches++;
	if ((dataPtr->maxMatches > 0) && 
	    (dataPtr->nMatches >= dataPtr->maxMatches)) {
	    return TCL_BREAK;
	}
    }
    return TCL_OK;
}

static int
ApplyNodeProc(node, clientData, order)
    Blt_TreeNode node;
    ClientData clientData;
    int order;
{
    ApplyData *dataPtr = (ApplyData *)clientData;
    TreeCmd *cmdPtr = dataPtr->cmdPtr;
    Tcl_Interp *interp = cmdPtr->interp;
    int nBytes;
    char *string;
    int invert, result, pattern;
    Tcl_DString dString;
    
    if ((dataPtr->flags & MATCH_LEAFONLY) && (!Blt_TreeIsLeaf(node))) {
	return TCL_OK;
    }
    if ((dataPtr->maxDepth >= 0) &&
	(dataPtr->maxDepth < Blt_TreeNodeDepth(cmdPtr->tree, node))) {
	return TCL_OK;
    }
    result = TRUE;
    pattern = (dataPtr->flags & PATTERN_MASK);
    string = NULL;
    if (dataPtr->key != NULL) {
	Tcl_Obj *objPtr;

	if (Blt_TreeGetValue(cmdPtr->tree, node, dataPtr->key, &objPtr) 
	    != TCL_OK) {
	    result = FALSE;
	} else {
	    string = Tcl_GetStringFromObj(objPtr, &nBytes);
	}
    } else {	    
	if (dataPtr->flags & MATCH_PATHNAME) {
	    string = GetNodePath(cmdPtr, Blt_TreeRootNode(cmdPtr->tree),
			 node, &dString);
	} else {
	    string = Blt_TreeNodeLabel(node);
	}
    }
    if (pattern != PATTERN_NONE) {
	if (dataPtr->flags & MATCH_NOCASE) {
	    string = strdup(string);
	    strtolower(string);
	}
	switch (pattern) {
	case PATTERN_EXACT:
	    result = (strcmp(string, dataPtr->pattern) == 0);
	    break;
	    
	case PATTERN_GLOB:
	    result = Tcl_StringMatch(string, dataPtr->pattern);
	    break;
	    
	case PATTERN_REGEXP:
	    result = Tcl_RegExpMatch(interp, string, dataPtr->pattern); 
	    break;
	}
	if (dataPtr->flags & MATCH_NOCASE) {
	    free(string);
	}
    } 
    if ((dataPtr->tagUid != NULL) && (!HasTag(cmdPtr, node, dataPtr->tagUid))) {
	result = FALSE;
    }
    invert = (dataPtr->flags & MATCH_INVERT) ? 1 : 0;
    if (result != invert) {
	Tcl_Obj *objPtr;

	objPtr = Tcl_NewIntObj(Blt_TreeNodeId(node));
	if (order == TREE_PREORDER) {
	    dataPtr->preObjv[dataPtr->preObjc - 1] = objPtr;
	    return Tcl_EvalObjv(interp, dataPtr->preObjc, dataPtr->preObjv, 0);
	} else if (order == TREE_POSTORDER) {
	    dataPtr->postObjv[dataPtr->postObjc - 1] = objPtr;
	    return Tcl_EvalObjv(interp, dataPtr->postObjc, dataPtr->postObjv,0);
	}
    }
    return TCL_OK;
}

static void
ReleaseTreeObject(cmdPtr)
    TreeCmd *cmdPtr;
{
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;
    TraceInfo *tracePtr;
    NotifyInfo *notifyPtr;
    Blt_ChainLink *linkPtr, *nextPtr;
    TagInfo *tagPtr;
    int i;

    Blt_TreeReleaseToken(cmdPtr->tree);
    /* 
     * When the tree token is released, all the traces and
     * notification events are automatically removed.  But we still
     * need to clean up the bookkeeping kept for traces. Clear all
     * the tags and trace information.  
     */
    for (hPtr = Tcl_FirstHashEntry(&(cmdPtr->traceTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	tracePtr = (TraceInfo *)Tcl_GetHashValue(hPtr);
	free(tracePtr->command);
	free((char *)tracePtr);
    }
    for (hPtr = Tcl_FirstHashEntry(&(cmdPtr->notifyTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	notifyPtr = (NotifyInfo *)Tcl_GetHashValue(hPtr);
	for (i = 0; i < notifyPtr->objc - 2; i++) {
	    Tcl_DecrRefCount(notifyPtr->objv[i]);
	}
	free((char *)notifyPtr->objv);
	free((char *)notifyPtr);
    }
    /* Clear all tags. */
    for (linkPtr = Blt_ChainFirstLink(cmdPtr->tagChainPtr); linkPtr != NULL;
	 linkPtr = nextPtr) {
	nextPtr = Blt_ChainNextLink(linkPtr);
	tagPtr = (TagInfo *)Blt_ChainGetValue(linkPtr);
	DestroyTagInfo(cmdPtr, tagPtr);
    }
    cmdPtr->tree = NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeTraceProc --
 *
 *---------------------------------------------------------------------- 
 */
/*ARGSUSED*/
static int
TreeTraceProc(clientData, interp, node, keyUid, flags)
    ClientData clientData;
    Tcl_Interp *interp;
    Blt_TreeNode node;		/* Node that has just been updated. */
    Blt_Uid keyUid;		/* Field that's updated. */
    unsigned int flags;
{
    TraceInfo *tracePtr = (TraceInfo *)clientData; 
    Tcl_DString dString;
    char string[5];
    char *name;
    int result;

    /* 
     * If the trace was set on a tag, check that this node has the tag. 
     * There's a special check for the "all" tag.  We don't want to 
     * actually tag all nodes in the table, so we do a separate test.
     */
    if ((tracePtr->tagUid != NULL) &&
	(!HasTag(tracePtr->cmdPtr, node, tracePtr->tagUid))) {
	return TCL_OK;
    }
    Tcl_DStringInit(&dString);
    Tcl_DStringAppend(&dString, tracePtr->command, -1);
    name = Tcl_GetCommandName(interp, tracePtr->cmdPtr->cmdToken);
    Tcl_DStringAppendElement(&dString, name);
    if (node != NULL) {
	Tcl_DStringAppendElement(&dString, Blt_Itoa(Blt_TreeNodeId(node)));
    } else {
	Tcl_DStringAppendElement(&dString, "");
    }
    Tcl_DStringAppendElement(&dString, keyUid);
    PrintTraceFlags(flags, string);
    Tcl_DStringAppendElement(&dString, string);
    result = Tcl_Eval(interp, Tcl_DStringValue(&dString));
    Tcl_DStringFree(&dString);
    return result;
}

static int
TreeEventProc(clientData, eventPtr) 
    ClientData clientData;
    Blt_TreeNotifyEvent *eventPtr;
{
    TreeCmd *cmdPtr = (TreeCmd *)clientData; 
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;
    NotifyInfo *notifyPtr;
    Blt_TreeNode node;
    char *string;

    switch (eventPtr->type) {
    case TREE_NOTIFY_CREATE:
	string = "-create";
	break;

    case TREE_NOTIFY_DELETE:
	node = Blt_TreeGetNode(cmdPtr->tree, eventPtr->inode);
	if (node != NULL) {
	    ClearTags(cmdPtr, node);
	}
	string = "-delete";
	break;

    case TREE_NOTIFY_MOVE:
	string = "-move";
	break;

    case TREE_NOTIFY_SORT:
	string = "-sort";
	break;

    case TREE_NOTIFY_RELABEL:
	string = "-relabel";
	break;

    default:
	/* empty */
	string = "???";
	break;
    }	

    for (hPtr = Tcl_FirstHashEntry(&(cmdPtr->notifyTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	notifyPtr = (NotifyInfo *)Tcl_GetHashValue(hPtr);
	if (notifyPtr->mask & eventPtr->type) {
	    int result;
	    Tcl_Obj *flagObjPtr, *nodeObjPtr;

	    flagObjPtr = Tcl_NewStringObj(string, -1);
	    nodeObjPtr = Tcl_NewIntObj(eventPtr->inode);
	    Tcl_IncrRefCount(flagObjPtr);
	    notifyPtr->objv[notifyPtr->objc - 2] = flagObjPtr;
	    notifyPtr->objv[notifyPtr->objc - 1] = nodeObjPtr;
	    Tcl_IncrRefCount(nodeObjPtr);
	    result = Tcl_EvalObjv(cmdPtr->interp, notifyPtr->objc, 
		notifyPtr->objv, 0);
	    Tcl_DecrRefCount(nodeObjPtr);
	    Tcl_DecrRefCount(flagObjPtr);
	    if (result != TCL_OK) {
		Tcl_BackgroundError(cmdPtr->interp);
		return TCL_ERROR;
	    }
	    Tcl_ResetResult(cmdPtr->interp);
	}
    }
    return TCL_OK;
}


/* Tree command operations. */

/*
 *----------------------------------------------------------------------
 *
 * ApplyOp --
 *
 * t0 apply root -precommand {command} -postcommand {command}
 *
 *---------------------------------------------------------------------- 
 */
static int
ApplyOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int result;
    Blt_TreeNode node;
    int i;
    Tcl_Obj **objArr;
    int count;
    ApplyData data;
    int order;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    memset(&data, 0, sizeof(data));
    data.maxDepth = -1;
    data.cmdPtr = cmdPtr;

    /* Process switches  */
    if (Blt_ProcessObjSwitches(interp, applySwitches, objc - 3, objv + 3, 
	     (char *)&data, 0) != TCL_OK) {
	return TCL_ERROR;
    }
    order = 0;
    if (data.preCmd != NULL) {
	char **p;

	count = 0;
	for (p = data.preCmd; *p != NULL; p++) {
	    count++;
	}
	objArr = (Tcl_Obj **)malloc((count + 1) * sizeof(Tcl_Obj *));
	for (i = 0; i < count; i++) {
	    objArr[i] = Tcl_NewStringObj(data.preCmd[i], -1);
	    Tcl_IncrRefCount(objArr[i]);
	}
	data.preObjv = objArr;
	data.preObjc = count + 1;
	order |= TREE_PREORDER;
    }
    if (data.postCmd != NULL) {
	char **p;

	count = 0;
	for (p = data.postCmd; *p != NULL; p++) {
	    count++;
	}
	objArr = (Tcl_Obj **)malloc((count + 1) * sizeof(Tcl_Obj *));
	for (i = 0; i < count; i++) {
	    objArr[i] = Tcl_NewStringObj(data.postCmd[i], -1);
	    Tcl_IncrRefCount(objArr[i]);
	}
	data.postObjv = objArr;
	data.postObjc = count + 1;
	order |= TREE_POSTORDER;
    }
    if (data.tag != NULL) {
	data.tagUid = Blt_GetUid(data.tag);
    }
    result = Blt_TreeApplyDFS(node, ApplyNodeProc, (ClientData)&data, order);
    if (data.preObjv != NULL) {
	for (i = 0; i < (data.preObjc - 1); i++) {
	    Tcl_DecrRefCount(data.preObjv[i]);
	}
	free((char *)data.preObjv);
    }
    if (data.postObjv != NULL) {
	for (i = 0; i < (data.postObjc - 1); i++) {
	    Tcl_DecrRefCount(data.postObjv[i]);
	}
	free((char *)data.postObjv);
    }
    Blt_FreeSwitches(applySwitches, (char *)&data, 0);
    if (data.tagUid != NULL) {
	Blt_FreeUid(data.tagUid);
    }
    if (result == TCL_ERROR) {
	return TCL_ERROR;
    }
    return TCL_OK;
}


static int
AncestorOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int d1, d2, minDepth;
    register int i;
    Blt_TreeNode ancestor, node1, node2;

    if ((GetNode(cmdPtr, objv[2], &node1) != TCL_OK) ||
	(GetNode(cmdPtr, objv[3], &node2) != TCL_OK)) {
	return TCL_ERROR;
    }
    if (node1 == node2) {
	ancestor = node1;
	goto done;
    }
    d1 = Blt_TreeNodeDepth(cmdPtr->tree, node1);
    d2 = Blt_TreeNodeDepth(cmdPtr->tree, node2);
    minDepth = MIN(d1, d2);
    if (minDepth == 0) {	/* One of the nodes is root. */
	ancestor = Blt_TreeRootNode(cmdPtr->tree);
	goto done;
    }
    /* 
     * Traverse back from the deepest node, until the both nodes are
     * at the same depth.  Check if the ancestor node found is the
     * other node.  
     */
    for (i = d1; i > minDepth; i--) {
	node1 = Blt_TreeNodeParent(node1);
    }
    if (node1 == node2) {
	ancestor = node2;
	goto done;
    }
    for (i = d2; i > minDepth; i--) {
	node2 = Blt_TreeNodeParent(node2);
    }
    if (node2 == node1) {
	ancestor = node1;
	goto done;
    }

    /* 
     * First find the mutual ancestor of both nodes.  Look at each
     * preceding ancestor level-by-level for both nodes.  Eventually
     * we'll find a node that's the parent of both ancestors.  Then
     * find the first ancestor in the parent's list of subnodes.  
     */
    for (i = minDepth; i > 0; i--) {
	node1 = Blt_TreeNodeParent(node1);
	node2 = Blt_TreeNodeParent(node2);
	if (node1 == node2) {
	    ancestor = node2;
	    goto done;
	}
    }
    Tcl_AppendResult(interp, "unknown ancestor", (char *)NULL);
    return TCL_ERROR;
 done:
    Tcl_SetIntObj(Tcl_GetObjResult(interp), Blt_TreeNodeId(ancestor));
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * AttachOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
AttachOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    if (objc == 3) {
	char *treeName;
	int nBytes;
	char *name;
	Blt_Tree token;
	Tcl_Namespace *nsPtr;
	Tcl_DString dString;
	
	treeName = Tcl_GetStringFromObj(objv[2], &nBytes);
	if (Blt_ParseQualifiedName(interp, treeName, &nsPtr, &name) != TCL_OK) {
	    Tcl_AppendResult(interp, "can't find namespace in \"", treeName, 
			     "\"", (char *)NULL);
	    return TCL_ERROR;
	}
	if (nsPtr == NULL) {
	    nsPtr = Tcl_GetCurrentNamespace(interp);
	}
	treeName = Blt_GetQualifiedName(nsPtr, name, &dString);
	if (!Blt_TreeExists(interp, treeName)) {
	    Tcl_AppendResult(interp, "can't find tree object \"", treeName, 
			     "\"", (char *)NULL);
	    return TCL_ERROR;
	}
	if (Blt_TreeGetToken(interp, treeName, &token) != TCL_OK) {
	    return TCL_ERROR;
	}
	ReleaseTreeObject(cmdPtr);
	cmdPtr->tree = token;
    }
    Tcl_SetObjResult(interp, Tcl_NewStringObj(Blt_TreeName(cmdPtr->tree), -1));
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * ChildrenOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
ChildrenOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    
    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    if (objc == 3) {
	Tcl_Obj *objPtr, *listObjPtr;

	listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
	for (node = Blt_TreeFirstChild(node); node != NULL;
	     node = Blt_TreeNextSibling(node)) {
	    objPtr = Tcl_NewIntObj(Blt_TreeNodeId(node));
	    Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
	}
	Tcl_SetObjResult(interp, listObjPtr);
    } else if (objc == 4) {
	int childPos;
	int inode, count;
	
	/* Get the node at  */
	if (Tcl_GetIntFromObj(interp, objv[3], &childPos) != TCL_OK) {
		return TCL_ERROR;
	}
	count = 0;
	inode = -1;
	for (node = Blt_TreeFirstChild(node); node != NULL;
	     node = Blt_TreeNextSibling(node)) {
	    if (count == childPos) {
		inode = Blt_TreeNodeId(node);
		break;
	    }
	    count++;
	}
	Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
	return TCL_OK;
    } else if (objc == 5) {
	int firstPos, lastPos, count;
	Tcl_Obj *objPtr, *listObjPtr;
	char *string;
	int nBytes;

	firstPos = lastPos = Blt_TreeNodeDegree(node) - 1;
	string = Tcl_GetStringFromObj(objv[3], &nBytes);
	if ((strcmp(string, "end") != 0) &&
	    (Tcl_GetIntFromObj(interp, objv[3], &firstPos) != TCL_OK)) {
	    return TCL_ERROR;
	}
	string = Tcl_GetStringFromObj(objv[4], &nBytes);
	if ((strcmp(string, "end") != 0) &&
	    (Tcl_GetIntFromObj(interp, objv[4], &lastPos) != TCL_OK)) {
	    return TCL_ERROR;
	}

	count = 0;
	listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
	for (node = Blt_TreeFirstChild(node); node != NULL;
	     node = Blt_TreeNextSibling(node)) {
	    if ((count >= firstPos) && (count <= lastPos)) {
		objPtr = Tcl_NewIntObj(Blt_TreeNodeId(node));
		Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
	    }
	    count++;
	}
	Tcl_SetObjResult(interp, listObjPtr);
    }
    return TCL_OK;
}


static int
CopyNodes(dataPtr, srcNode, destNode)
    CopyData *dataPtr;
    Blt_TreeNode srcNode, destNode;
{
    char *label;
    Blt_TreeNode srcChild, destChild;

    label = Blt_TreeNodeLabel(srcNode);

    destChild = Blt_TreeFindChild(destNode, label);
    if (destChild == NULL) {
	/* Create node in destination. */
	destChild = Blt_TreeCreateNode(dataPtr->destTree, destNode, label, -1);
    }
    /* Copy the data fields. */
    {
	Blt_Uid keyUid;
	Tcl_Obj *objPtr;
	Blt_TreeCursor cursor;

	for (keyUid = Blt_TreeFirstKey(srcNode, &cursor); keyUid != NULL;
	     keyUid = Blt_TreeNextKey(&cursor)) {
	    Blt_TreeGetValue(dataPtr->srcTree, srcNode, keyUid, &objPtr);
	    Blt_TreeSetValue(dataPtr->destTree, destChild, keyUid, objPtr);
	}	    
    }

    /* Add tags to destination tree command. */
    if ((dataPtr->destPtr != NULL) && (dataPtr->flags & COPY_TAGS)) {
	TagInfo *tagPtr;
	Blt_ChainLink *linkPtr;
	Tcl_HashEntry *hPtr;

	for (linkPtr = Blt_ChainFirstLink(dataPtr->srcPtr->tagChainPtr); 
	     linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
	    tagPtr = (TagInfo *)Blt_ChainGetValue(linkPtr);
	    hPtr = Tcl_FindHashEntry(&(tagPtr->nodeTable), (char *)srcNode);
	    if (hPtr != NULL) {
		AddTag(dataPtr->destPtr, destChild, tagPtr->tagUid);
	    }
	}
    }
    if (dataPtr->flags & COPY_RECURSE) {
	for (srcChild = Blt_TreeFirstChild(srcNode); srcChild != NULL;
	     srcChild = Blt_TreeNextSibling(srcChild)) {
	    if (CopyNodes(dataPtr, srcChild, destChild) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * CopyOp --
 * 
 *	t0 copy node tree node 
 *
 *---------------------------------------------------------------------- 
 */
/*ARGSUSED*/
static int
CopyOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    TreeCmd *srcPtr, *destPtr;
    Blt_Tree srcTree, destTree;
    Blt_TreeNode srcNode, destNode;
    CopyData data;
    int nArgs, nSwitches;
    char *string;
    int nBytes, result;
    register int i;

    if (GetNode(cmdPtr, objv[2], &srcNode) != TCL_OK) {
	return TCL_ERROR;
    }
    srcTree = cmdPtr->tree;
    srcPtr = cmdPtr;
    for(i = 3; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	if (string[0] == '-') {
	    break;
	}
    }
    nArgs = i - 2;
    nSwitches = objc - i;
    if (nArgs < 2) {
	string = Tcl_GetStringFromObj(objv[0], &nBytes);
	Tcl_AppendResult(interp, "must specify source and destination nodes: ",
			 "should be \"", string, 
			 " copy srcNode ?destTree? destNode ?switches?", 
			 (char *)NULL);
	return TCL_ERROR;
	
    }
    if (nArgs == 3) {
	/* 
	 * The tree name is either the name of a tree command (first choice)
	 * or an internal tree object.  
	 */
	string = Tcl_GetStringFromObj(objv[3], &nBytes);
	destPtr = GetTreeCmd(cmdPtr->dataPtr, interp, string);
	if (destPtr != NULL) {
	    destTree = destPtr->tree;
	} else {
	    /* Try to get the tree as an internal tree data object. */
	    if (Blt_TreeGetToken(interp, string, &destTree) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
	objv++, objc--;
    } else {
	destPtr = cmdPtr;
	destTree = destPtr->tree;
    }

    result = TCL_ERROR;
    if (destPtr == NULL) {
	if (GetForeignNode(interp, destTree, objv[3], &destNode) != TCL_OK) {
	    goto error;
	}
    } else {
	if (GetNode(destPtr, objv[3], &destNode) != TCL_OK) {
	    goto error;
	}
    }
    if (srcNode == destNode) {
	Tcl_AppendResult(interp, "source and destination nodes are the same",
		 (char *)NULL);	     
	goto error;
    }
    memset((char *)&data, 0, sizeof(data));
    /* Process switches  */
    if (Blt_ProcessObjSwitches(interp, copySwitches, nSwitches, objv + 4, 
	     (char *)&data, 0) != TCL_OK) {
	goto error;
    }
    data.destPtr = destPtr;
    data.destTree = destTree;
    data.srcPtr = srcPtr;
    data.srcTree = srcTree;

    if ((srcTree == destTree) && (data.flags & COPY_RECURSE) &&
	(Blt_TreeIsAncestor(srcNode, destNode))) {    
	Tcl_AppendResult(interp, "can't make cyclic copy: ",
			 "source node is an ancestor of the destination",
			 (char *)NULL);	     
	goto error;
    }

    /* Copy nodes to destination. */
    result = CopyNodes(&data, srcNode, destNode);
    
 error:
    if (destPtr == NULL) {
	Blt_TreeReleaseToken(destTree);
    }
    return result;

}

/*
 *----------------------------------------------------------------------
 *
 * DepthOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
DegreeOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int degree;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    degree = Blt_TreeNodeDegree(node);
    Tcl_SetIntObj(Tcl_GetObjResult(interp), degree);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * DeleteOp --
 *
 *	Deletes one or more nodes from the tree.  Nodes may be
 *	specified by their id (a number) or a tag.
 *	
 *	Tags have to be handled carefully here.  We can't use the
 *	normal GetTaggedNode, NextTaggedNode, etc. routines because
 *	they walk hashtables while we're deleting nodes.  Also,
 *	remember that deleting a node recursively deletes all its
 *	children. If a parent and its children have the same tag, its
 *	possible that the tag list may contain nodes than no longer
 *	exist. So save the node indices in a list and then delete 
 *	then in a second pass.
 *
 *---------------------------------------------------------------------- 
 */
static int
DeleteOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int i;
    char *string;
    int nBytes;

    for (i = 2; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	if (isdigit(UCHAR(string[0]))) {
	    if (GetNode(cmdPtr, objv[i], &node) != TCL_OK) {
		return TCL_ERROR;
	    }
	    DeleteNode(cmdPtr, node);
	} else {
	    Blt_Uid tagUid;
	    Tcl_HashEntry *hPtr;
	    TagInfo *tagPtr;
	    Tcl_HashSearch cursor;
	    Blt_Chain *chainPtr;
	    Blt_ChainLink *linkPtr, *nextPtr;
	    int inode;

	    tagUid = Blt_FindUid(string);
	    if (tagUid == NULL) {
		goto error;
	    }
	    if ((tagUid == allUid) || (tagUid == rootUid)) {
		node = Blt_TreeRootNode(cmdPtr->tree);
		DeleteNode(cmdPtr, node);
		continue;
	    }
	    hPtr = Tcl_FindHashEntry(&(cmdPtr->tagsTable), tagUid);
	    if (hPtr == NULL) {
		goto error;
	    }
	    tagPtr = (TagInfo *)Tcl_GetHashValue(hPtr);

	    /* 
	     * Generate a list of tagged nodes. Save the inode instead
	     * of the node itself since a pruned branch may contain
	     * more tagged nodes.  
	     */
	    chainPtr = Blt_ChainCreate();
	    for (hPtr = Tcl_FirstHashEntry(&(tagPtr->nodeTable), &cursor); 
		hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
		node = (Blt_TreeNode)Tcl_GetHashValue(hPtr);
		Blt_ChainAppend(chainPtr, (ClientData)Blt_TreeNodeId(node));
	    }   
	    /*  
	     * Iterate through this list to delete the nodes.  By
	     * side-effect the tag table is deleted and Uids are
	     * released.  
	     */
	    for (linkPtr = Blt_ChainFirstLink(chainPtr); linkPtr != NULL;
		 linkPtr = nextPtr) {
		nextPtr = Blt_ChainNextLink(linkPtr);
		inode = (int)Blt_ChainGetValue(linkPtr);
		node = Blt_TreeGetNode(cmdPtr->tree, inode);
		if (node != NULL) {
		    DeleteNode(cmdPtr, node);
		}
	    }
	    Blt_ChainDestroy(chainPtr);
	}
    }
    return TCL_OK;
 error:
    Tcl_AppendResult(interp, "can't find tag or id \"", string, "\" in ", 
		     Blt_TreeName(cmdPtr->tree), (char *)NULL);
    return TCL_ERROR;
}

/*
 *----------------------------------------------------------------------
 *
 * DepthOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
DepthOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int depth;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    depth = Blt_TreeNodeDepth(cmdPtr->tree, node);
    Tcl_SetIntObj(Tcl_GetObjResult(interp), depth);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * DumpOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
DumpOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    register Blt_TreeNode node;
    Blt_TreeNode top;
    Tcl_DString dString;

    if (GetNode(cmdPtr, objv[2], &top) != TCL_OK) {
	return TCL_ERROR;
    }
    Tcl_DStringInit(&dString);
    for (node = top; node != NULL; node = Blt_TreeNextNode(top, node)) {
	PrintNode(cmdPtr, top, node, &dString);
    }
    Tcl_DStringResult(interp, &dString);
    Tcl_DStringFree(&dString);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * FindOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
FindOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    FindData data;
    int count, result;
    register int i;
    Tcl_Obj **objArr;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    memset(&data, 0, sizeof(data));
    data.maxDepth = -1;
    data.order = TREE_POSTORDER;
    data.flags = 0;
    objArr = NULL;
    /* Process switches  */
    if (Blt_ProcessObjSwitches(interp, findSwitches, objc - 3, objv + 3, 
		     (char *)&data, 0) != TCL_OK) {
	return TCL_ERROR;
    }
    count = 0;
    if (Blt_SwitchChanged(findSwitches, "-glob", (char *)NULL)) {
	count++;
	data.flags &= ~PATTERN_MASK;
	data.flags |= PATTERN_GLOB;
    } 
    if (Blt_SwitchChanged(findSwitches, "-regexp", (char *)NULL)) {
	count++;
	data.flags &= ~PATTERN_MASK;
	data.flags |= PATTERN_REGEXP;
    }
    if (Blt_SwitchChanged(findSwitches, "-exact", (char *)NULL)) {
	count++;
	data.flags &= ~PATTERN_MASK;
	data.flags |= PATTERN_EXACT;
    }
    if ((data.flags & MATCH_NOCASE) && (data.pattern != NULL)) {
	strtolower(data.pattern);
    }
    if (data.maxDepth >= 0) {
	data.maxDepth += Blt_TreeNodeDepth(cmdPtr->tree, node);
    }
    if (count > 1) {
	/* Two many patterns supplied. */
    }
    if (data.command != NULL) {
	char **p;

	count = 0;
	for (p = data.command; *p != NULL; p++) {
	    count++;
	}
	objArr = (Tcl_Obj **)malloc((count + 1) * sizeof(Tcl_Obj *));
	for (i = 0; i < count; i++) {
	    objArr[i] = Tcl_NewStringObj(data.command[i], -1);
	    Tcl_IncrRefCount(objArr[i]);
	}
	data.objv = objArr;
	data.objc = count + 1;
    }
    if (data.tag != NULL) {
	data.tagUid = Blt_GetUid(data.tag);
    }
    data.listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
    data.cmdPtr = cmdPtr;
    if (data.order == TREE_BREADTHFIRST) {
	result = Blt_TreeApplyBFS(node, MatchNodeProc, (ClientData)&data);
    } else {
	result = Blt_TreeApplyDFS(node, MatchNodeProc, (ClientData)&data,
		  data.order);
    }
    if (data.command != NULL) {
	for (i = 0; i < count; i++) {
	    Tcl_DecrRefCount(objArr[i]);
	}
	free((char *)objArr);
    }
    Blt_FreeSwitches(findSwitches, (char *)&data, 0);
    if (data.tagUid != NULL) {
	Blt_FreeUid(data.tagUid);
    }
    if (result == TCL_ERROR) {
	return TCL_ERROR;
    }
    Tcl_SetObjResult(interp, data.listObjPtr);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * FirstChildOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
FirstChildOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreeFirstChild(node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * GetOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
GetOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    if (objc == 3) {
	Blt_Uid keyUid;
	Tcl_Obj *valuePtr, *listObjPtr;
	Blt_TreeCursor cursor;
	
	listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
	for (keyUid = Blt_TreeFirstKey(node, &cursor); keyUid != NULL;
	     keyUid = Blt_TreeNextKey(&cursor)) {
	    
	    if (Blt_TreeGetValue(cmdPtr->tree, node, keyUid, 
			 &valuePtr) == TCL_OK) {
		Tcl_Obj *objPtr;

		objPtr = Tcl_NewStringObj(keyUid, -1);
		Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
		Tcl_ListObjAppendElement(interp, listObjPtr, valuePtr);
	    }
	}	    
	Tcl_SetObjResult(interp, listObjPtr);
	return TCL_OK;
    } else {
	Tcl_Obj *objPtr;
	int nBytes;
	char *string;
	
	string = Tcl_GetStringFromObj(objv[3], &nBytes);
	if (Blt_TreeGetValue(cmdPtr->tree, node, string, &objPtr) != TCL_OK) {
	    Tcl_ResetResult(interp);
	    if (objc == 4) {
		Tcl_AppendResult(interp, "can't find field \"", string, 
		     "\"  in node \"", Blt_Itoa(Blt_TreeNodeId(node)),
			 (char *)NULL);
		return TCL_ERROR;
	    } 
	    objPtr = objv[4];
	} 
	Tcl_SetObjResult(interp, objPtr);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * IndexOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
IndexOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    inode = -1;
    if (GetNode(cmdPtr, objv[2], &node) == TCL_OK) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * InsertOp --
 *
 *---------------------------------------------------------------------- 
 */

static int
InsertOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode parent, node;
    InsertData data;

    node = NULL;
    if (GetNode(cmdPtr, objv[2], &parent) != TCL_OK) {
	return TCL_ERROR;
    }
    /* Initialize switch flags */
    memset(&data, 0, sizeof(data));
    data.insertPos = -1;	/* Default to append node. */

    /* Process  */
    if (Blt_ProcessObjSwitches(interp, insertSwitches, objc - 3, objv + 3, 
	     (char *)&data, 0) != TCL_OK) {
	goto error;
    }
    node = Blt_TreeCreateNode(cmdPtr->tree, parent, data.label, data.insertPos);
    if (node == NULL) {
	goto error;
    }
    if (data.tags != NULL) {
	register char **p;

	for (p = data.tags; *p != NULL; p++) {
	    if (AddTag(cmdPtr, node, *p) != TCL_OK) {
		goto error;
	    }
	}
    }
    if (data.dataPairs != NULL) {
	register char **p;
	char *key;
	Tcl_Obj *objPtr;

	for (p = data.dataPairs; *p != NULL; p++) {
	    key = *p;
	    p++;
	    if (*p == NULL) {
		Tcl_AppendResult(interp, "missing value for \"", key, "\"",
				 (char *)NULL);
		goto error;
	    }
	    objPtr = Tcl_NewStringObj(*p, -1);
	    if (Blt_TreeSetValue(cmdPtr->tree, node, key, objPtr) != TCL_OK) {
		goto error;
	    }
	}
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), Blt_TreeNodeId(node));
    Blt_FreeSwitches(insertSwitches, (char *)&data, 0);
    return TCL_OK;

 error:
    if (node != NULL) {
	Blt_TreeDeleteNode(cmdPtr->tree, node);
    }
    Blt_FreeSwitches(insertSwitches, (char *)&data, 0);
    return TCL_ERROR;
}

/*
 *----------------------------------------------------------------------
 *
 * IsAncestorOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
IsAncestorOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node1, node2;
    int bool;

    if ((GetNode(cmdPtr, objv[3], &node1) != TCL_OK) ||
	(GetNode(cmdPtr, objv[4], &node2) != TCL_OK)) {
	return TCL_ERROR;
    }
    bool = Blt_TreeIsAncestor(node1, node2);
    Tcl_SetIntObj(Tcl_GetObjResult(interp), bool);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * IsBeforeOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
IsBeforeOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node1, node2;
    int bool;

    if ((GetNode(cmdPtr, objv[3], &node1) != TCL_OK) ||
	(GetNode(cmdPtr, objv[4], &node2) != TCL_OK)) {
	return TCL_ERROR;
    }
    bool = Blt_TreeIsBefore(node1, node2);
    Tcl_SetIntObj(Tcl_GetObjResult(interp), bool);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * IsLeafOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
IsLeafOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;

    if (GetNode(cmdPtr, objv[3], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), Blt_TreeIsLeaf(node));
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * IsRootOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
IsRootOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int bool;

    if (GetNode(cmdPtr, objv[3], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    bool = (node == Blt_TreeRootNode(cmdPtr->tree));
    Tcl_SetIntObj(Tcl_GetObjResult(interp), bool);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * IsOp --
 *
 *---------------------------------------------------------------------- 
 */
static Blt_OpSpec isOps[] =
{
    {"ancestor", 1, (Blt_OpProc)IsAncestorOp, 5, 5, "node1 node2",},
    {"before", 1, (Blt_OpProc)IsBeforeOp, 5, 5, "node1 node2",},
    {"leaf", 1, (Blt_OpProc)IsLeafOp, 4, 4, "node",},
    {"root", 1, (Blt_OpProc)IsRootOp, 4, 4, "node",},
};

static int nIsOps = sizeof(isOps) / sizeof(Blt_OpSpec);

static int
IsOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_OpProc opProc;
    int result;

    opProc = Blt_GetOperationObj(interp, nIsOps, isOps, BLT_OPER_ARG2, 
	objc, objv, 0);
    if (opProc == NULL) {
	return TCL_ERROR;
    }
    result = (*opProc) (cmdPtr, interp, objc, objv);
    return result;
}


/*
 *----------------------------------------------------------------------
 *
 * LabelOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
LabelOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    if (objc == 4) {
	char *string;
	int nBytes;

	string = Tcl_GetStringFromObj(objv[3], &nBytes);
	Blt_TreeRelabelNode(cmdPtr->tree, node, string);
    }
    Tcl_SetStringObj(Tcl_GetObjResult(interp), Blt_TreeNodeLabel(node), -1);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * LastChildOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
LastChildOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreeLastChild(node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * MoveOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
MoveOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode root, parent, node;
    int nBytes;
    MoveData data;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    if (GetNode(cmdPtr, objv[3], &parent) != TCL_OK) {
	return TCL_ERROR;
    }
    data.node = NULL;
    data.cmdPtr = cmdPtr;
    data.insertPos = -1;
    /* Process switches  */
    if (Blt_ProcessObjSwitches(interp, moveSwitches, objc - 4, objv + 4, 
		     (char *)&data, 0) != TCL_OK) {
	return TCL_ERROR;
    }
    root = Blt_TreeRootNode(cmdPtr->tree);
    if (node == root) {
	Tcl_AppendResult(interp, "can't move root node", (char *)NULL);
	return TCL_ERROR;
    }
    /* Verify they aren't ancestors. */
    if (Blt_TreeIsAncestor(node, parent)) {
	Tcl_AppendResult(interp, "can't move node: \"", 
		 Tcl_GetStringFromObj(objv[2], &nBytes), (char *)NULL);
	Tcl_AppendResult(interp, "\" is an ancestor of \"", 
		 Tcl_GetStringFromObj(objv[3], &nBytes), "\"", (char *)NULL);
	return TCL_ERROR;
    }
    if (data.node != NULL) {
	if (Blt_TreeNodeParent(data.node) != parent) {
	    Tcl_AppendResult(interp, Tcl_GetStringFromObj(objv[2], &nBytes), 
		     " isn't the parent of ", Blt_TreeNodeLabel(data.node),
		     (char *)NULL);
	    return TCL_ERROR;
	}
	if (Blt_SwitchChanged(moveSwitches, "-before", (char *)NULL)) {
	    Blt_TreeMoveNode(cmdPtr->tree, node, parent, data.node);
	} else {
	    Blt_TreeMoveNode(cmdPtr->tree, node, parent,
			     Blt_TreeNextSibling(data.node));
	}
    } else {
	Blt_TreeNode before;

	before = NULL;
	if ((data.insertPos >= 0) && 
	    (data.insertPos < Blt_TreeNodeDegree(parent))) {
	    int count;
	    Blt_TreeNode child;

	    count = 0;
	    for(child = Blt_TreeFirstChild(parent); child != NULL; 
		node = Blt_TreeNextSibling(node)) {
		if (count == data.insertPos) {
		    before = child;
		    break;
		}
	    }
	}
	Blt_TreeMoveNode(cmdPtr->tree, node, parent, before);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NextOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
NextOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreeNextNode(Blt_TreeRootNode(cmdPtr->tree), node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NextSiblingOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
NextSiblingOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreeNextSibling(node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyCreateOp --
 *
 *	tree0 notify create ?flags? command arg
 *---------------------------------------------------------------------- 
 */
static int
NotifyCreateOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    NotifyInfo *notifyPtr;
    NotifyData data;
    char *string;
    char idString[200];
    int nBytes, isNew, nArgs;
    Tcl_HashEntry *hPtr;
    int count;
    register int i;

    count = 0;
    for (i = 3; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	if (string[0] != '-') {
	    break;
	}
	count++;
    }
    data.mask = 0;
    /* Process switches  */
    if (Blt_ProcessObjSwitches(interp, notifySwitches, count, objv + 3, 
	     (char *)&data, 0) != TCL_OK) {
	return TCL_ERROR;
    }
    notifyPtr = (NotifyInfo *)malloc(sizeof(NotifyInfo));

    nArgs = objc - i;

    /* Stash away the command in structure and pass that to the notifier. */
    notifyPtr->objv = (Tcl_Obj **)malloc((nArgs + 2) * sizeof(Tcl_Obj *));
    for (count = 0; i < objc; i++, count++) {
	Tcl_IncrRefCount(objv[i]);
	notifyPtr->objv[count] = objv[i];
    }
    notifyPtr->objc = nArgs + 2;
    notifyPtr->cmdPtr = cmdPtr;
    if (data.mask == 0) {
	data.mask = TREE_NOTIFY_ALL;
    }
    notifyPtr->mask = data.mask;

    sprintf(idString, "notify%d", cmdPtr->notifyCounter++);
    hPtr = Tcl_CreateHashEntry(&(cmdPtr->notifyTable), idString, &isNew);
    Tcl_SetHashValue(hPtr, notifyPtr);

    Tcl_SetStringObj(Tcl_GetObjResult(interp), idString, -1);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyDeleteOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
NotifyDeleteOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int nBytes;
    NotifyInfo *notifyPtr;
    Tcl_HashEntry *hPtr;
    register int i, j;
    char *string;

    for (i = 3; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	hPtr = Tcl_FindHashEntry(&(cmdPtr->notifyTable), string);
	if (hPtr == NULL) {
	    Tcl_AppendResult(interp, "unknown notify name \"", string, "\"", 
			     (char *)NULL);
	    return TCL_ERROR;
	}
	notifyPtr = (NotifyInfo *)Tcl_GetHashValue(hPtr);
	Tcl_DeleteHashEntry(hPtr);
	for (j = 0; j < (notifyPtr->objc - 2); j++) {
	    Tcl_DecrRefCount(notifyPtr->objv[j]);
	}
	free((char *)notifyPtr->objv);
	free((char *)notifyPtr);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyInfoOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
NotifyInfoOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int nBytes;
    NotifyInfo *notifyPtr;
    Tcl_HashEntry *hPtr;
    Tcl_DString dString;
    char *string;
    int i;

    string = Tcl_GetStringFromObj(objv[3], &nBytes);
    hPtr = Tcl_FindHashEntry(&(cmdPtr->notifyTable), string);
    if (hPtr == NULL) {
	Tcl_AppendResult(interp, "unknown notify name \"", string, "\"", 
			 (char *)NULL);
	return TCL_ERROR;
    }
    notifyPtr = (NotifyInfo *)Tcl_GetHashValue(hPtr);

    Tcl_DStringInit(&dString);
    Tcl_DStringAppendElement(&dString, string);	/* Copy notify Id */
    Tcl_DStringStartSublist(&dString);
    if (notifyPtr->mask & TREE_NOTIFY_CREATE) {
	Tcl_DStringAppendElement(&dString, "-create");
    }
    if (notifyPtr->mask & TREE_NOTIFY_DELETE) {
	Tcl_DStringAppendElement(&dString, "-delete");
    }
    if (notifyPtr->mask & TREE_NOTIFY_MOVE) {
	Tcl_DStringAppendElement(&dString, "-move");
    }
    if (notifyPtr->mask & TREE_NOTIFY_SORT) {
	Tcl_DStringAppendElement(&dString, "-sort");
    }
    if (notifyPtr->mask & TREE_NOTIFY_RELABEL) {
	Tcl_DStringAppendElement(&dString, "-relabel");
    }
    if (notifyPtr->mask & TREE_NOTIFY_WHENIDLE) {
	Tcl_DStringAppendElement(&dString, "-whenidle");
    }
    Tcl_DStringEndSublist(&dString);
    Tcl_DStringStartSublist(&dString);
    for (i = 0; i < (notifyPtr->objc - 2); i++) {
	string = Tcl_GetStringFromObj(notifyPtr->objv[i], &nBytes);
	Tcl_DStringAppendElement(&dString, string);	
    }
    Tcl_DStringEndSublist(&dString);
    Tcl_DStringResult(interp, &dString);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyNamesOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
NotifyNamesOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;
    Tcl_Obj *objPtr, *listObjPtr;
    char *notifyId;

    listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
    for (hPtr = Tcl_FirstHashEntry(&(cmdPtr->notifyTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	notifyId = Tcl_GetHashKey(&(cmdPtr->notifyTable), hPtr);
	objPtr = objPtr = Tcl_NewStringObj(notifyId, -1);
	Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
    }
    Tcl_SetObjResult(interp, listObjPtr);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * NotifyOp --
 *
 *---------------------------------------------------------------------- 
 */
static Blt_OpSpec notifyOps[] =
{
    {"create", 1, (Blt_OpProc)NotifyCreateOp, 4, 0, "?flags? command",},
    {"delete", 1, (Blt_OpProc)NotifyDeleteOp, 3, 0, "notifyId...",},
    {"info", 1, (Blt_OpProc)NotifyInfoOp, 4, 4, "notifyId",},
    {"names", 1, (Blt_OpProc)NotifyNamesOp, 3, 3, "",},
};

static int nNotifyOps = sizeof(notifyOps) / sizeof(Blt_OpSpec);

static int
NotifyOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_OpProc opProc;
    int result;

    opProc = Blt_GetOperationObj(interp, nNotifyOps, notifyOps, BLT_OPER_ARG2, 
	objc, objv, 0);
    if (opProc == NULL) {
	return TCL_ERROR;
    }
    result = (*opProc) (cmdPtr, interp, objc, objv);
    return result;
}


static int
ParentOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreeNodeParent(node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * PathOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
PathOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    Tcl_DString dString;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    GetNodePath(cmdPtr, Blt_TreeRootNode(cmdPtr->tree), node, &dString);
    Tcl_DStringResult(interp, &dString);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * PreviousOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
PreviousOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreePrevNode(Blt_TreeRootNode(cmdPtr->tree), node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

static int
PrevSiblingOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    int inode;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    inode = -1;
    node = Blt_TreePrevSibling(node);
    if (node != NULL) {
	inode = Blt_TreeNodeId(node);
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), inode);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * RestoreOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
RestoreOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    register Blt_TreeNode node;
    Blt_TreeNode parent, root;
    char *string;
    int nBytes;
    register int i, j;
    Tcl_Obj *valuePtr;
    int nElem, nObjs;
    Tcl_Obj **objArr;
    Tcl_Obj **listObjArr;

    if (GetNode(cmdPtr, objv[2], &root) != TCL_OK) {
	return TCL_ERROR;
    }
    if (Tcl_ListObjGetElements(interp, objv[3], &nObjs, &objArr) != TCL_OK) {
	return TCL_ERROR;
    }
    if ((nObjs % 3) != 0) {
	string = Tcl_GetStringFromObj(objv[3], &nBytes);
	Tcl_AppendResult(interp, "wrong # of values in restoration list \"",
			 string, "\"", (char *)NULL);
	return TCL_ERROR;
    }
    for (i = 0; i < nObjs; i += 3) {
	/* Parse the path name. */
	if (Tcl_ListObjGetElements(interp, objArr[i], &nElem, &listObjArr) 
	    != TCL_OK) {
	    return TCL_ERROR;
	}
	node = parent = root;
	/* Automatically create nodes as needed. */
	for (j = 0; j < nElem; j++) {
	    string = Tcl_GetStringFromObj(listObjArr[j], &nBytes);
	    node = Blt_TreeFindChild(parent, string);
	    if (node == NULL) {
		node = 
		    Blt_TreeCreateNode(cmdPtr->tree, parent, string, -1);
	    }
	    parent = node;
	}
	/* Parse the key-value list. */
	if (Tcl_ListObjGetElements(interp, objArr[i + 1], &nElem, 
		   &listObjArr) != TCL_OK) {
	    return TCL_ERROR;
	}
	for (j = 0; j < nElem; j += 2) {
	    string = Tcl_GetStringFromObj(listObjArr[j], &nBytes);
	    valuePtr = listObjArr[j + 1];
	    if (Blt_TreeSetValue(cmdPtr->tree, node, string, valuePtr) 
		!= TCL_OK) {
		return TCL_ERROR;
	    }
	}
	if (Tcl_ListObjGetElements(interp, objArr[i + 2], &nElem, 
		   &listObjArr) != TCL_OK) {
	    return TCL_ERROR;
	}
	for (j = 0; j < nElem; j++) {
	    string = Tcl_GetStringFromObj(listObjArr[j], &nBytes);
	    AddTag(cmdPtr, node, string);
	}
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * RootOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
RootOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode root;

    if (objc == 3) {
	Blt_TreeNode node;

	if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	    return TCL_ERROR;
	}
	Blt_TreeChangeRoot(cmdPtr->tree, node);
    }
    root = Blt_TreeRootNode(cmdPtr->tree);
    Tcl_SetIntObj(Tcl_GetObjResult(interp), Blt_TreeNodeId(root));
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * SetOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
SetOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    char *string;
    int nBytes;
    TagSearch cursor;
	
    string = Tcl_GetStringFromObj(objv[2], &nBytes);
    if (isdigit(UCHAR(*string))) {
	if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	    return TCL_ERROR;
	}
	if (SetValues(cmdPtr, node, objc - 3, objv + 3) != TCL_OK) {
	    return TCL_ERROR;
	}
    } else {
	node = FirstTaggedNode(interp, cmdPtr, objv[2], &cursor);
	if (node == NULL) {
	    return TCL_ERROR;
	}
	for (/* empty */; node != NULL; node = NextTaggedNode(node, &cursor)) {
	    if (SetValues(cmdPtr, node, objc - 3, objv + 3) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * SizeOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
SizeOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;

    if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	return TCL_ERROR;
    }
    Tcl_SetIntObj(Tcl_GetObjResult(interp), Blt_TreeSize(node));
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TagForgetOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TagForgetOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    char *string;
    int nBytes;
    register int i;

    for (i = 3; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	ForgetTag(cmdPtr, string);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TagNamesOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TagNamesOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_ChainLink *linkPtr;
    Blt_Uid tagUid;
    TagInfo *tagPtr;
    Tcl_Obj *listObjPtr, *objPtr;
    Tcl_HashSearch cursor;
    Tcl_HashEntry *hPtr;
    Tcl_HashTable nameTable;
    int isNew;

    Tcl_InitHashTable(&nameTable, TCL_ONE_WORD_KEYS);
    Tcl_CreateHashEntry(&nameTable, allUid, &isNew);
    if (objc == 3) {
	Tcl_CreateHashEntry(&nameTable, rootUid, &isNew);
	for (linkPtr = Blt_ChainFirstLink(cmdPtr->tagChainPtr); linkPtr != NULL;
	     linkPtr = Blt_ChainNextLink(linkPtr)) {
	    tagPtr = (TagInfo *)Blt_ChainGetValue(linkPtr);
	    Tcl_CreateHashEntry(&nameTable, tagPtr->tagUid, &isNew);
	}
    } else {
	register int i;
	Blt_TreeNode node;

	for (i = 3; i < objc; i++) {
	    if (GetNode(cmdPtr, objv[i], &node) != TCL_OK) {
		goto error;
	    }
	    if (node == Blt_TreeRootNode(cmdPtr->tree)) {
		Tcl_CreateHashEntry(&nameTable, rootUid, &isNew);
	    }
	    for (linkPtr = Blt_ChainFirstLink(cmdPtr->tagChainPtr); 
		linkPtr != NULL; linkPtr = Blt_ChainNextLink(linkPtr)) {
		tagPtr = (TagInfo *)Blt_ChainGetValue(linkPtr);
		hPtr = Tcl_FindHashEntry(&(tagPtr->nodeTable), (char *)node);
		if (hPtr != NULL) {
		    Tcl_CreateHashEntry(&nameTable, tagPtr->tagUid, &isNew);
		}
	    }
	}
    }
    listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
    for (hPtr = Tcl_FirstHashEntry(&nameTable, &cursor); hPtr != NULL; 
	 hPtr = Tcl_NextHashEntry(&cursor)) {
	tagUid = Tcl_GetHashKey(&nameTable, hPtr);
	objPtr = Tcl_NewStringObj(tagUid, -1);
	Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
    }
    Tcl_SetObjResult(interp, listObjPtr);
    Tcl_DeleteHashTable(&nameTable);
    return TCL_OK;
 error:
    Tcl_DeleteHashTable(&nameTable);
    return TCL_ERROR;
}

/*
 *----------------------------------------------------------------------
 *
 * TagNodesOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TagNodesOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Tcl_Obj *listObjPtr;
    Blt_Uid tagUid;
    char *string;
    int nBytes, isNew;
    Tcl_HashTable nodeTable;
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;
    Tcl_Obj *objPtr;
    register int i;
    Blt_TreeNode node;
	
    Tcl_InitHashTable(&nodeTable, TCL_ONE_WORD_KEYS);
    for (i = 3; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	tagUid = Blt_FindUid(string);
	if (tagUid == allUid) {
	    
	    break;
	} else if (tagUid == rootUid) {
	    Tcl_CreateHashEntry(&nodeTable, 
		(char *)Blt_TreeRootNode(cmdPtr->tree), &isNew);
	    continue;
	} else if (tagUid != NULL) {
	    Tcl_HashTable *tablePtr;
	    
	    tablePtr = GetTagTable(cmdPtr, tagUid);
	    if (tablePtr != NULL) {
		for (hPtr = Tcl_FirstHashEntry(tablePtr, &cursor); 
		     hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
		    node = (Blt_TreeNode)Tcl_GetHashValue(hPtr);
		    Tcl_CreateHashEntry(&nodeTable, (char *)node, &isNew);
		}
		continue;
	    }
	}
	Tcl_AppendResult(interp, "can't find a tag \"", string, "\"",
			 (char *)NULL);
	goto error;
    }
    listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
    for (hPtr = Tcl_FirstHashEntry(&nodeTable, &cursor); hPtr != NULL; 
	 hPtr = Tcl_NextHashEntry(&cursor)) {
	node = (Blt_TreeNode)Tcl_GetHashKey(&nodeTable, hPtr);
	objPtr = Tcl_NewIntObj(Blt_TreeNodeId(node));
	Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
    }
    Tcl_SetObjResult(interp, listObjPtr);
    Tcl_DeleteHashTable(&nodeTable);
    return TCL_OK;

 error:
    Tcl_DeleteHashTable(&nodeTable);
    return TCL_ERROR;
}

/*
 *----------------------------------------------------------------------
 *
 * TagAddOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TagAddOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    register int i;
    char *string;
    int nBytes;
    Blt_Uid tagUid;
    TagSearch cursor;

    string = Tcl_GetStringFromObj(objv[3], &nBytes);
    if (isdigit(UCHAR(string[0]))) {
	Tcl_AppendResult(interp, "bad tag \"", string, 
		 "\": can't start with a digit", (char *)NULL);
	return TCL_ERROR;
    }
    tagUid = Blt_FindUid(string);
    if ((tagUid == allUid) || (tagUid == rootUid)) {
	Tcl_AppendResult(cmdPtr->interp, "can't add reserved tag \"",
			 string, "\"", (char *)NULL);
	return TCL_ERROR;
    }
    for (i = 4; i < objc; i++) {
	node = FirstTaggedNode(interp, cmdPtr, objv[i], &cursor);
	if (node == NULL) {
	    return TCL_ERROR;
	}
	for (/* empty */; node != NULL; node = NextTaggedNode(node, &cursor)) {
	    if (AddTag(cmdPtr, node, string) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
    }
    return TCL_OK;
}


/*
 *----------------------------------------------------------------------
 *
 * TagDeleteOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TagDeleteOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    char *string;
    int nBytes;
    Blt_Uid tagUid;
    Tcl_HashTable *tablePtr;

    string = Tcl_GetStringFromObj(objv[3], &nBytes);
    tagUid = Blt_FindUid(string);
    if ((tagUid == allUid) || (tagUid == rootUid)) {
	Tcl_AppendResult(interp, "can't delete reserved tag \"", string, "\"", 
			 (char *)NULL);
        return TCL_ERROR;
    }
    if (tagUid == NULL) {
	return TCL_OK;
    }
    tablePtr = GetTagTable(cmdPtr, tagUid);
    if (tablePtr != NULL) {
        register int i;
        Blt_TreeNode node;
        TagSearch cursor;
        Tcl_HashEntry *hPtr;
      
        for (i = 4; i < objc; i++) {
	    node = FirstTaggedNode(interp, cmdPtr, objv[i], &cursor);
	    if (node == NULL) {
	        return TCL_ERROR;
	    }
	    for (/* empty */; node != NULL; 	
		node = NextTaggedNode(node, &cursor)) {
	        hPtr = Tcl_FindHashEntry(tablePtr, (char *)node);
	        if (hPtr != NULL) {
		    Tcl_DeleteHashEntry(hPtr);
	        }
	   }
       }
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TagDumpOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TagDumpOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    register Blt_TreeNode root, node;
    Tcl_DString dString;
    TagSearch cursor;
    register int i;

    Tcl_DStringInit(&dString);
    root = Blt_TreeRootNode(cmdPtr->tree);
    for (i = 3; i < objc; i++) {
	node = FirstTaggedNode(interp, cmdPtr, objv[i], &cursor);
	if (node == NULL) {
	    return TCL_ERROR;
	}
	for (/* empty */; node != NULL; node = NextTaggedNode(node, &cursor)) {
	    PrintNode(cmdPtr, root, node, &dString);
	}
    }
    Tcl_DStringResult(interp, &dString);
    Tcl_DStringFree(&dString);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TagOp --
 *
 *---------------------------------------------------------------------- 
 */
static Blt_OpSpec tagOps[] = {
    {"add", 1, (Blt_OpProc)TagAddOp, 5, 0, "tag node...",},
    {"delete", 2, (Blt_OpProc)TagDeleteOp, 5, 0, "tag node...",},
    {"dump", 2, (Blt_OpProc)TagDumpOp, 4, 0, "tag...",},
    {"forget", 1, (Blt_OpProc)TagForgetOp, 4, 0, "tag...",},
    {"names", 2, (Blt_OpProc)TagNamesOp, 3, 0, "?node...?",},
    {"nodes", 2, (Blt_OpProc)TagNodesOp, 4, 0, "tag ?tag...?",},
};

static int nTagOps = sizeof(tagOps) / sizeof(Blt_OpSpec);

static int
TagOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_OpProc opProc;
    int result;

    opProc = Blt_GetOperationObj(interp, nTagOps, tagOps, BLT_OPER_ARG2, 
	objc, objv, 0);
    if (opProc == NULL) {
	return TCL_ERROR;
    }
    result = (*opProc) (cmdPtr, interp, objc, objv);
    return result;
}

/*
 *----------------------------------------------------------------------
 *
 * TraceCreateOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TraceCreateOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    TraceInfo *tracePtr;
    char *string, *key, *command;
    char idString[200];
    int nBytes, flags, isNew;
    Tcl_HashEntry *hPtr;
    Blt_Uid tagUid;

    string = Tcl_GetStringFromObj(objv[3], &nBytes);
    if (isdigit(UCHAR(*string))) {
	if (GetNode(cmdPtr, objv[3], &node) != TCL_OK) {
	    return TCL_ERROR;
	}
	tagUid = NULL;
    } else {
	tagUid = Blt_GetUid(string);
	node = NULL;
    }
    key = Tcl_GetStringFromObj(objv[4], &nBytes);
    string = Tcl_GetStringFromObj(objv[5], &nBytes);
    flags = GetTraceFlags(string);
    if (flags < 0) {
	Tcl_AppendResult(interp, "unknown flag in \"", string, "\"", 
		     (char *)NULL);
	return TCL_ERROR;
    }
    command = Tcl_GetStringFromObj(objv[6], &nBytes);
    /* Stash away the command in structure and pass that to the trace. */
    tracePtr = (TraceInfo *)malloc(sizeof(TraceInfo));
    tracePtr->command = strdup(command);
    tracePtr->cmdPtr = cmdPtr;
    tracePtr->tagUid = tagUid;
    tracePtr->node = node;
    tracePtr->traceToken = Blt_TreeCreateTrace(cmdPtr->tree, node, key, 
	flags, TreeTraceProc, (ClientData)tracePtr);

    sprintf(idString, "trace%d", cmdPtr->traceCounter++);
    hPtr = Tcl_CreateHashEntry(&(cmdPtr->traceTable), idString, &isNew);
    Tcl_SetHashValue(hPtr, tracePtr);

    Tcl_SetStringObj(Tcl_GetObjResult(interp), idString, -1);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TraceDeleteOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TraceDeleteOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int nBytes;
    TraceInfo *tracePtr;
    Tcl_HashEntry *hPtr;
    register int i;
    char *key;

    for (i = 3; i < objc; i++) {
	key = Tcl_GetStringFromObj(objv[i], &nBytes);
	hPtr = Tcl_FindHashEntry(&(cmdPtr->traceTable), key);
	if (hPtr == NULL) {
	    Tcl_AppendResult(interp, "unknown trace \"", key, "\"", 
			     (char *)NULL);
	    return TCL_ERROR;
	}
	tracePtr = (TraceInfo *)Tcl_GetHashValue(hPtr);
	Blt_TreeDeleteTrace(tracePtr->traceToken);
	free(tracePtr->command);
	if (tracePtr->tagUid != NULL) {
	    Blt_FreeUid(tracePtr->tagUid);
	}
	free((char *)tracePtr);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TraceNamesOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TraceNamesOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;

    for (hPtr = Tcl_FirstHashEntry(&(cmdPtr->traceTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	Tcl_AppendElement(interp, Tcl_GetHashKey(&(cmdPtr->traceTable), hPtr));
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TraceInfoOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
TraceInfoOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int nBytes;
    TraceInfo *tracePtr;
    struct Blt_TreeTraceRec *tokenPtr;
    Tcl_HashEntry *hPtr;
    Tcl_DString dString;
    char string[5];
    char *key;

    key = Tcl_GetStringFromObj(objv[3], &nBytes);
    hPtr = Tcl_FindHashEntry(&(cmdPtr->traceTable), key);
    if (hPtr == NULL) {
	Tcl_AppendResult(interp, "unknown trace \"", key, "\"", 
			 (char *)NULL);
	return TCL_ERROR;
    }
    Tcl_DStringInit(&dString);
    tracePtr = (TraceInfo *)Tcl_GetHashValue(hPtr);
    if (tracePtr->tagUid != NULL) {
	Tcl_DStringAppendElement(&dString, tracePtr->tagUid);
    } else {
	int inode;

	inode = Blt_TreeNodeId(tracePtr->node);
	Tcl_DStringAppendElement(&dString, Blt_Itoa(inode));
    }
    tokenPtr = (struct Blt_TreeTraceRec *)tracePtr->traceToken;
    Tcl_DStringAppendElement(&dString, tokenPtr->keyUid);
    PrintTraceFlags(tokenPtr->mask, string);
    Tcl_DStringAppendElement(&dString, string);
    Tcl_DStringAppendElement(&dString, tracePtr->command);
    Tcl_DStringResult(interp, &dString);
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TraceOp --
 *
 *---------------------------------------------------------------------- 
 */
static Blt_OpSpec traceOps[] =
{
    {"create", 1, (Blt_OpProc)TraceCreateOp, 7, 7, "node key how command",},
    {"delete", 1, (Blt_OpProc)TraceDeleteOp, 3, 0, "id...",},
    {"info", 1, (Blt_OpProc)TraceInfoOp, 4, 4, "id",},
    {"names", 1, (Blt_OpProc)TraceNamesOp, 3, 3, "",},
};

static int nTraceOps = sizeof(traceOps) / sizeof(Blt_OpSpec);

static int
TraceOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_OpProc opProc;
    int result;

    opProc = Blt_GetOperationObj(interp, nTraceOps, traceOps, BLT_OPER_ARG2, 
	objc, objv, 0);
    if (opProc == NULL) {
	return TCL_ERROR;
    }
    result = (*opProc) (cmdPtr, interp, objc, objv);
    return result;
}

/*
 *----------------------------------------------------------------------
 *
 * UnsetOp --
 *
 *---------------------------------------------------------------------- 
 */
static int
UnsetOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode node;
    char *string;
    int nBytes;
	
    string = Tcl_GetStringFromObj(objv[2], &nBytes);
    if (isdigit(UCHAR(*string))) {
	if (GetNode(cmdPtr, objv[2], &node) != TCL_OK) {
	    return TCL_ERROR;
	}
	if (UnsetValues(cmdPtr, node, objc - 3, objv + 3) != TCL_OK) {
	    return TCL_ERROR;
	}
    } else {
	TagSearch cursor;

	node = FirstTaggedNode(interp, cmdPtr, objv[2], &cursor);
	if (node == NULL) {
	    return TCL_ERROR;
	}
	for (/* empty */; node != NULL; node = NextTaggedNode(node, &cursor)) {
	    if (UnsetValues(cmdPtr, node, objc - 3, objv + 3) != TCL_OK) {
		return TCL_ERROR;
	    }
	}
    }
    return TCL_OK;
}


typedef struct {
    TreeCmd *cmdPtr;
    int flags;
    int type;
    int mode;
    char *key;
    char *command;
} SortData;

#define SORT_RECURSE		(1<<2)
#define SORT_DECREASING		(1<<3)
#define SORT_PATHNAME		(1<<4)

enum SortTypes { SORT_DICTIONARY, SORT_REAL, SORT_INTEGER, SORT_ASCII, 
	SORT_COMMAND };

enum SortModes { SORT_FLAT, SORT_REORDER };

static Blt_SwitchSpec sortSwitches[] = 
{
    {BLT_SWITCH_VALUE, "-ascii", Blt_Offset(SortData, type), 0, 0, 
	SORT_ASCII},
    {BLT_SWITCH_STRING, "-command", Blt_Offset(SortData, command), 0},
    {BLT_SWITCH_FLAG, "-decreasing", Blt_Offset(SortData, flags), 0, 0, 
	SORT_DECREASING},
    {BLT_SWITCH_VALUE, "-dictionary", Blt_Offset(SortData, type), 0, 0, 
	SORT_DICTIONARY},
    {BLT_SWITCH_VALUE, "-integer", Blt_Offset(SortData, type), 0, 0, 
	SORT_INTEGER},
    {BLT_SWITCH_STRING, "-key", Blt_Offset(SortData, key), 0},
    {BLT_SWITCH_FLAG, "-path", Blt_Offset(SortData, flags), 0, 0, 
	SORT_PATHNAME},
    {BLT_SWITCH_VALUE, "-real", Blt_Offset(SortData, type), 0, 0, 
	SORT_REAL},
    {BLT_SWITCH_VALUE, "-recurse", Blt_Offset(SortData, flags), 0, 0, 
	SORT_RECURSE},
    {BLT_SWITCH_VALUE, "-reorder", Blt_Offset(SortData, mode), 0, 0, 
	SORT_REORDER},
    {BLT_SWITCH_END, NULL, 0, 0}
};

static SortData sortData;

static int
CompareNodes(n1Ptr, n2Ptr)
    Blt_TreeNode *n1Ptr, *n2Ptr;
{
    TreeCmd *cmdPtr = sortData.cmdPtr;
    char *s1, *s2;
    int result;
    Tcl_DString dString1, dString2;

    s1 = s2 = "";
    result = 0;

    if (sortData.flags & SORT_PATHNAME) {
	Tcl_DStringInit(&dString1);
	Tcl_DStringInit(&dString2);
    }
    if (sortData.key != NULL) {
	Tcl_Obj *objPtr;
	int nBytes;

	if (Blt_TreeGetValue(cmdPtr->tree, *n1Ptr, sortData.key, &objPtr)
	    == TCL_OK) {
	    s1 = Tcl_GetStringFromObj(objPtr, &nBytes);
	}
	if (Blt_TreeGetValue(cmdPtr->tree, *n2Ptr, sortData.key, &objPtr)
	    == TCL_OK) {
	    s2 = Tcl_GetStringFromObj(objPtr, &nBytes);
	}
    } else if (sortData.flags & SORT_PATHNAME)  {
	Blt_TreeNode root;
	
	root = Blt_TreeRootNode(cmdPtr->tree);
	s1 = GetNodePath(cmdPtr, root, *n1Ptr, &dString1);
	s2 = GetNodePath(cmdPtr, root, *n2Ptr, &dString2);
    } else {
	s1 = Blt_TreeNodeLabel(*n1Ptr);
	s2 = Blt_TreeNodeLabel(*n2Ptr);
    }
    switch (sortData.type) {
    case SORT_ASCII:
	result = strcmp(s1, s2);
	break;

    case SORT_COMMAND:
	if (sortData.command == NULL) {
	    result = Blt_DictionaryCompare(s1, s2);
	} else {
	    Tcl_DString dString;
	    
	    result = 0;	/* Hopefully this will be Ok even if the
			 * Tcl command fails to return the correct
			 * result. */
	    Tcl_DStringInit(&dString);
	    Tcl_DStringAppend(&dString, sortData.command, -1);
	    Tcl_DStringAppendElement(&dString, 
		     Tcl_GetCommandName(cmdPtr->interp, cmdPtr->cmdToken));
	    Tcl_DStringAppendElement(&dString, 
			Blt_Itoa(Blt_TreeNodeId(*n1Ptr)));
	    Tcl_DStringAppendElement(&dString, 
			Blt_Itoa(Blt_TreeNodeId(*n2Ptr)));
	    Tcl_DStringAppendElement(&dString, s1);
	    Tcl_DStringAppendElement(&dString, s2);
	    result = Tcl_GlobalEval(cmdPtr->interp, 
		Tcl_DStringValue(&dString));
	    Tcl_DStringFree(&dString);
	    
	    if ((result != TCL_OK) ||
		(Tcl_GetInt(cmdPtr->interp, 
		    Tcl_GetStringResult(cmdPtr->interp), &result) != TCL_OK)) {
		Tcl_BackgroundError(cmdPtr->interp);
	    }
	    Tcl_ResetResult(cmdPtr->interp);
	}
	break;

    case SORT_DICTIONARY:
	result = Blt_DictionaryCompare(s1, s2);
	break;

    case SORT_INTEGER:
	{
	    int i1, i2;

	    if (Tcl_GetInt(NULL, s1, &i1) == TCL_OK) {
		if (Tcl_GetInt(NULL, s2, &i2) == TCL_OK) {
		    result = i1 - i2;
		} else {
		    result = -1;
		} 
	    } else if (Tcl_GetInt(NULL, s2, &i2) == TCL_OK) {
		result = 1;
	    } else {
		result = Blt_DictionaryCompare(s1, s2);
	    }
	}
	break;

    case SORT_REAL:
	{
	    double r1, r2;

	    if (Tcl_GetDouble(NULL, s1, &r1) == TCL_OK) {
		if (Tcl_GetDouble(NULL, s2, &r2) == TCL_OK) {
		    result = (r1 < r2) ? -1 : (r1 > r2) ? 1 : 0;
		} else {
		    result = -1;
		} 
	    } else if (Tcl_GetDouble(NULL, s2, &r2) == TCL_OK) {
		result = 1;
	    } else {
		result = Blt_DictionaryCompare(s1, s2);
	    }
	}
	break;
    }
    if (sortData.flags & SORT_DECREASING) {
	result = -result;
    } 
    if (sortData.flags & SORT_PATHNAME) {
	Tcl_DStringFree(&dString1);
	Tcl_DStringFree(&dString2);
    }
    return result;
}

/*
 *----------------------------------------------------------------------
 *
 * SortApplyProc --
 *
 *	Sorts the subnodes at a given node.
 *
 * Results:
 *	Always returns TCL_OK.
 *
 *----------------------------------------------------------------------
 */
static int
SortApplyProc(node, clientData, order)
    Blt_TreeNode node;
    ClientData clientData;
    int order;			/* Not used. */
{
    TreeCmd *cmdPtr = (TreeCmd *)clientData;

    if (Blt_TreeNodeDegree(node) > 1) {
	Blt_TreeSortNode(cmdPtr->tree, node, CompareNodes);
    }
    return TCL_OK;
}


/*
 *----------------------------------------------------------------------
 *
 * SortOp --
 *  
 *---------------------------------------------------------------------- 
 */
static int
SortOp(cmdPtr, interp, objc, objv)
    TreeCmd *cmdPtr;
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_TreeNode top;
    SortData data;
    int result;

    if (GetNode(cmdPtr, objv[2], &top) != TCL_OK) {
	return TCL_ERROR;
    }
    result = TCL_ERROR;
    /* Process switches  */
    memset(&data, 0, sizeof(data));
    data.cmdPtr = cmdPtr;
    if (Blt_ProcessObjSwitches(interp, sortSwitches, objc - 3, objv + 3, 
	     (char *)&data, 0) != TCL_OK) {
	return TCL_ERROR;
    }
    if (data.command != NULL) {
	data.type = SORT_COMMAND;
    }
    data.cmdPtr = cmdPtr;
    sortData = data;
    if (data.mode == SORT_FLAT) {
	Blt_TreeNode *p, *nodeArr, node;
	int nNodes;
	Tcl_Obj *objPtr, *listObjPtr;
	int i;

	if (data.flags & SORT_RECURSE) {
	    nNodes = Blt_TreeSize(top);
	} else {
	    nNodes = Blt_TreeNodeDegree(top);
	}
	nodeArr = (Blt_TreeNode *)malloc(nNodes * sizeof(Blt_TreeNode));
	assert(nodeArr);
	p = nodeArr;
	if (data.flags & SORT_RECURSE) {
	    for(node = top; node != NULL; node = Blt_TreeNextNode(top, node)) {
		*p++ = node;
	    }
	} else {
	    for (node = Blt_TreeFirstChild(top); node != NULL;
		 node = Blt_TreeNextSibling(node)) {
		*p++ = node;
	    }
	}
	qsort((char *)nodeArr, nNodes, sizeof(Blt_TreeNode),
	      (QSortCompareProc *)CompareNodes);
	listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
	for (p = nodeArr, i = 0; i < nNodes; i++, p++) {
	    objPtr = Tcl_NewIntObj(Blt_TreeNodeId(*p));
	    Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
	}
	Tcl_SetObjResult(interp, listObjPtr);
	free((char *)nodeArr);
	result = TCL_OK;
    } else {
	if (data.flags & SORT_RECURSE) {
	    result = Blt_TreeApply(top, SortApplyProc, (ClientData)cmdPtr);
	} else {
	    result = SortApplyProc(top, (ClientData)cmdPtr, TREE_PREORDER);
	}
    }
    Blt_FreeSwitches(sortSwitches, (char *)&data, 0);
    return result;
}

/*
 * --------------------------------------------------------------
 *
 * TreeInstObjCmd --
 *
 * 	This procedure is invoked to process commands on behalf of
 *	the tree object.
 *
 * Results:
 *	A standard Tcl result.
 *
 * Side effects:
 *	See the user documentation.
 *
 * --------------------------------------------------------------
 */
static Blt_OpSpec treeOps[] =
{
    {"ancestor", 2, (Blt_OpProc)AncestorOp, 4, 4, "node1 node2",},
    {"apply", 1, (Blt_OpProc)ApplyOp, 3, 0, "node ?switches?",},
    {"attach", 2, (Blt_OpProc)AttachOp, 2, 3, "?tree?",},
    {"children", 2, (Blt_OpProc)ChildrenOp, 3, 5, "node ?first? ?last?",},
    {"copy", 2, (Blt_OpProc)CopyOp, 4, 0, 
	"srcNode ?destTree? destNode ?switches?",},
    {"degree", 2, (Blt_OpProc)DegreeOp, 3, 0, "node",},
    {"delete", 2, (Blt_OpProc)DeleteOp, 3, 0, "node ?node...?",},
    {"depth", 3, (Blt_OpProc)DepthOp, 3, 3, "node",},
    {"dump", 3, (Blt_OpProc)DumpOp, 3, 3, "node",},
#ifdef notdef
    {"dup", 2, (Blt_OpProc)DupOp, 2, 0, "node dest",},
#endif
    {"find", 3, (Blt_OpProc)FindOp, 3, 0, "node ?switches?",},
    {"firstchild", 3, (Blt_OpProc)FirstChildOp, 3, 3, "node",},
    {"get", 1, (Blt_OpProc)GetOp, 3, 5, "node ?key? ?defaultValue?",},
    {"index", 3, (Blt_OpProc)IndexOp, 3, 3, "name",},
    {"insert", 3, (Blt_OpProc)InsertOp, 3, 0, "parent ?switches?",},
    {"is", 2, (Blt_OpProc)IsOp, 2, 0, "oper args...",},
    {"label", 3, (Blt_OpProc)LabelOp, 3, 4, "node ?newLabel?",},
    {"lastchild", 3, (Blt_OpProc)LastChildOp, 3, 3, "node",},
    {"move", 1, (Blt_OpProc)MoveOp, 4, 0, "node newParent ?switches?",},
    {"next", 4, (Blt_OpProc)NextOp, 3, 3, "node",},
    {"nextsibling", 5, (Blt_OpProc)NextSiblingOp, 3, 3, "node",},
    {"notify", 2, (Blt_OpProc)NotifyOp, 2, 0, "args...",},
    {"parent", 3, (Blt_OpProc)ParentOp, 3, 3, "node",},
    {"path", 3, (Blt_OpProc)PathOp, 3, 3, "node",},
    {"previous", 5, (Blt_OpProc)PreviousOp, 3, 3, "node",},
    {"prevsibling", 5, (Blt_OpProc)PrevSiblingOp, 3, 3, "node",},
    {"restore", 2, (Blt_OpProc)RestoreOp, 4, 4, "node dataString",},
    {"root", 2, (Blt_OpProc)RootOp, 2, 3, "?node?",},
    {"set", 3, (Blt_OpProc)SetOp, 3, 0, "node ?key value...?",},
    {"size", 2, (Blt_OpProc)SizeOp, 3, 3, "node",},
    {"sort", 2, (Blt_OpProc)SortOp, 3, 0, "node ?flags...?",},
    {"tag", 2, (Blt_OpProc)TagOp, 3, 0, "args...",},
    {"trace", 2, (Blt_OpProc)TraceOp, 2, 0, "args...",},
    {"unset", 3, (Blt_OpProc)UnsetOp, 3, 0, "node ?key...?",},
};

static int nTreeOps = sizeof(treeOps) / sizeof(Blt_OpSpec);

static int
TreeInstObjCmd(clientData, interp, objc, objv)
    ClientData clientData;	/* Information about the widget. */
    Tcl_Interp *interp;		/* Interpreter to report errors back to. */
    int objc;			/* Number of arguments. */
    Tcl_Obj **objv;		/* Vector of argument strings. */
{
    Blt_OpProc opProc;
    TreeCmd *cmdPtr = (TreeCmd *)clientData;
    int result;

    opProc = Blt_GetOperationObj(interp, nTreeOps, treeOps, BLT_OPER_ARG1, 
	objc, objv, BLT_LINEAR_SEARCH);
    if (opProc == NULL) {
	return TCL_ERROR;
    }
    Tcl_Preserve((ClientData)cmdPtr);
    result = (*opProc) (cmdPtr, interp, objc, objv);
    Tcl_Release((ClientData)cmdPtr);
    return result;
}

/*
 * ----------------------------------------------------------------------
 *
 * TreeInstDeleteProc --
 *
 *	Deletes the command associated with the tree.  This is
 *	called only when the command associated with the tree is
 *	destroyed.
 *
 * Results:
 *	None.
 *
 * ----------------------------------------------------------------------
 */
static void
TreeInstDeleteProc(clientData)
    ClientData clientData;
{
    TreeCmd *cmdPtr = (TreeCmd *)clientData;

    ReleaseTreeObject(cmdPtr);
    if (cmdPtr->hashPtr != NULL) {
	Tcl_DeleteHashEntry(cmdPtr->hashPtr);
    }
    Tcl_DeleteHashTable(&(cmdPtr->traceTable));
    Tcl_DeleteHashTable(&(cmdPtr->tagsTable));
    Blt_ChainDestroy(cmdPtr->tagChainPtr);
    free((char *)cmdPtr);
}

static char *
GenerateName(interp, prefix, suffix, dStrPtr)
    Tcl_Interp *interp;
    char *prefix, *suffix;
    Tcl_DString *dStrPtr;
{
    /* Automatically generate a command name. */
    int n;
    Tcl_Namespace *nsPtr;
    char string[200];
    Tcl_CmdInfo cmdInfo;
    Tcl_DString dString;
    char *treeName, *name;

    /* 
     * Parse the command and put back so that it's in a consistent
     * format.  
     *
     *	t1         <current namespace>::t1
     *	n1::t1     <current namespace>::n1::t1
     *	::t1	   ::t1
     *  ::n1::t1   ::n1::t1
     */
    for (n = 0; n < INT_MAX; n++) {
	Tcl_DStringInit(&dString);
	Tcl_DStringAppend(&dString, prefix, -1);
	sprintf(string, "tree%d", n);
	Tcl_DStringAppend(&dString, string, -1);
	Tcl_DStringAppend(&dString, suffix, -1);
	treeName = Tcl_DStringValue(&dString);
	if (Blt_ParseQualifiedName(interp, treeName, &nsPtr, &name) != TCL_OK) {
	    Tcl_AppendResult(interp, "can't find namespace in \"", 
			     treeName, "\"", (char *)NULL);
	    return NULL;
	}
	if (nsPtr == NULL) {
	    nsPtr = Tcl_GetCurrentNamespace(interp);
	}
	treeName = Blt_GetQualifiedName(nsPtr, name, dStrPtr);
	/* 
	 * Check if the command already exists. 
	 */
	if (Tcl_GetCommandInfo(interp, treeName, &cmdInfo)) {
	    continue;
	}
	if (!Blt_TreeExists(interp, treeName)) {
	    /* 
	     * Synchronize the name of the tree command and the underlying 
	     * tree object. That is, don't create a new command
	     * by the same name of an existing tree object.
	     */
	    break;
	}
    }
    return treeName;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeCreateOp --
 *
 *---------------------------------------------------------------------- 
 */
/*ARGSUSED*/
static int
TreeCreateOp(clientData, interp, objc, objv)
    ClientData clientData;	/* Interpreter-specific data. */
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    TreeCmdInterpData *dataPtr = (TreeCmdInterpData *)clientData;
    char *treeName;
    Tcl_DString dString;
    Blt_Tree token;

    treeName = NULL;
    if (objc == 3) {
	int nBytes;

	treeName = Tcl_GetStringFromObj(objv[2], &nBytes);
    }
    Tcl_DStringInit(&dString);
    if (treeName == NULL) {
	treeName = GenerateName(interp, "", "", &dString);
    } else {
	char *p;

	p = strstr(treeName, "#auto");
	if (p != NULL) {
	    *p = '\0';
	    treeName = GenerateName(interp, treeName, p + 5, &dString);
	    *p = '#';
	} else {
	    char *name;
	    Tcl_CmdInfo cmdInfo;
	    Tcl_Namespace *nsPtr;

	    nsPtr = NULL;
	    /* 
	     * Parse the command and put back so that it's in a consistent
	     * format.  
	     *
	     *	t1         <current namespace>::t1
	     *	n1::t1     <current namespace>::n1::t1
	     *	::t1	   ::t1
	     *  ::n1::t1   ::n1::t1
	     */
	    if (Blt_ParseQualifiedName(interp, treeName, &nsPtr, &name) 
		!= TCL_OK) {
		Tcl_AppendResult(interp, "can't find namespace in \"", treeName,
			 "\"", (char *)NULL);
		return TCL_ERROR;
	    }
	    if (nsPtr == NULL) {
		nsPtr = Tcl_GetCurrentNamespace(interp);
	    }
	    treeName = Blt_GetQualifiedName(nsPtr, name, &dString);
	    /* 
	     * Check if the command already exists. 
	     */
	    if (Tcl_GetCommandInfo(interp, treeName, &cmdInfo)) {
		Tcl_AppendResult(interp, "a command \"", treeName,
				 "\" already exists", (char *)NULL);
		goto error;
	    }
	    if (Blt_TreeExists(interp, treeName)) {
		Tcl_AppendResult(interp, "a tree \"", treeName, 
			"\" already exists", (char *)NULL);
		goto error;
	    }
	} 
    } 
    if (treeName == NULL) {
	goto error;
    }
    if (Blt_TreeCreate(interp, treeName) != TCL_OK) {
	goto error;
    }
    if (Blt_TreeGetToken(interp, treeName, &token) == TCL_OK) {
	int isNew;
	TreeCmd *cmdPtr;

	cmdPtr = (TreeCmd *)calloc(1, sizeof(TreeCmd));
	assert(cmdPtr);
	cmdPtr->tree = token;
	cmdPtr->interp = interp;
	Tcl_InitHashTable(&(cmdPtr->traceTable), TCL_STRING_KEYS);
	Tcl_InitHashTable(&(cmdPtr->notifyTable), TCL_STRING_KEYS);
	Tcl_InitHashTable(&(cmdPtr->tagsTable), TCL_ONE_WORD_KEYS);
	cmdPtr->tagChainPtr = Blt_ChainCreate();
	cmdPtr->cmdToken = Tcl_CreateObjCommand(interp, treeName, 
		(Tcl_ObjCmdProc *)TreeInstObjCmd, (ClientData)cmdPtr, 
		TreeInstDeleteProc);
	cmdPtr->hashPtr = Tcl_CreateHashEntry(&(dataPtr->treeTable), 
	       (char *)cmdPtr, &isNew);
	Tcl_SetHashValue(cmdPtr->hashPtr, (ClientData)cmdPtr);
	Tcl_SetResult(interp, treeName, TCL_VOLATILE);
	Tcl_DStringFree(&dString);
	Blt_TreeCreateEventHandler(cmdPtr->tree, TREE_NOTIFY_ALL, 
	     TreeEventProc, (ClientData)cmdPtr);
	return TCL_OK;
    }
 error:
    Tcl_DStringFree(&dString);
    return TCL_ERROR;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeDestroyOp --
 *
 *---------------------------------------------------------------------- 
 */
/*ARGSUSED*/
static int
TreeDestroyOp(clientData, interp, objc, objv)
    ClientData clientData;	/* Interpreter-specific data. */
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    TreeCmdInterpData *dataPtr = (TreeCmdInterpData *)clientData;
    TreeCmd *cmdPtr;
    char *string;
    int nBytes;
    register int i;

    for (i = 2; i < objc; i++) {
	string = Tcl_GetStringFromObj(objv[i], &nBytes);
	cmdPtr = GetTreeCmd(dataPtr, interp, string);
	if (cmdPtr == NULL) {
	    Tcl_AppendResult(interp, "can't find a tree named \"", string,
			     "\"", (char *)NULL);
	    return TCL_ERROR;
	}
	Tcl_DeleteCommandFromToken(interp, cmdPtr->cmdToken);
    }
    return TCL_OK;
}

/*
 *----------------------------------------------------------------------
 *
 * TreeNamesOp --
 *
 *---------------------------------------------------------------------- 
 */
/*ARGSUSED*/
static int
TreeNamesOp(clientData, interp, objc, objv)
    ClientData clientData;	/* Interpreter-specific data. */
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    TreeCmdInterpData *dataPtr = (TreeCmdInterpData *)clientData;
    TreeCmd *cmdPtr;
    Tcl_HashEntry *hPtr;
    Tcl_HashSearch cursor;
    Tcl_Obj *objPtr, *listObjPtr;
    char *name;

    listObjPtr = Tcl_NewListObj(0, (Tcl_Obj **) NULL);
    for (hPtr = Tcl_FirstHashEntry(&(dataPtr->treeTable), &cursor);
	 hPtr != NULL; hPtr = Tcl_NextHashEntry(&cursor)) {
	cmdPtr = (TreeCmd *)Tcl_GetHashValue(hPtr);
	name = Tcl_GetCommandName(interp, cmdPtr->cmdToken);
	if (objc == 3) {
	    char *pattern;
	    int nBytes;

	    pattern = Tcl_GetStringFromObj(objv[2], &nBytes);
	    if (!Tcl_StringMatch(name, pattern)) {
		continue;
	    }
	}
	objPtr = Tcl_NewStringObj(name, -1);
	Tcl_ListObjAppendElement(interp, listObjPtr, objPtr);
    }
    Tcl_SetObjResult(interp, listObjPtr);
    return TCL_OK;
}



/*
 *----------------------------------------------------------------------
 *
 * TreeObjCmd --
 *
 *---------------------------------------------------------------------- 
 */
static Blt_OpSpec treeCmdOps[] =
{
    {"create", 1, (Blt_OpProc)TreeCreateOp, 2, 3, "?name?",},
    {"destroy", 1, (Blt_OpProc)TreeDestroyOp, 3, 0, "name...",},
    {"names", 1, (Blt_OpProc)TreeNamesOp, 2, 3, "?pattern?...",},
};

static int nCmdOps = sizeof(treeCmdOps) / sizeof(Blt_OpSpec);

/*ARGSUSED*/
static int
TreeObjCmd(clientData, interp, objc, objv)
    ClientData clientData;	/* Interpreter-specific data. */
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    Blt_OpProc opProc;

    opProc = Blt_GetOperationObj(interp, nCmdOps, treeCmdOps, BLT_OPER_ARG1,
		      objc, objv, 0);
    if (opProc == NULL) {
	return TCL_ERROR;
    }
    return (*opProc) (clientData, interp, objc, objv);
}

/*
 * -----------------------------------------------------------------------
 *
 * TreeInterpDeleteProc --
 *
 *	This is called when the interpreter hosting the "tree" command
 *	is deleted.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Removes the hash table managing all tree names.
 *
 * ------------------------------------------------------------------------
 */
/* ARGSUSED */
static void
TreeInterpDeleteProc(clientData, interp)
    ClientData clientData;	/* Interpreter-specific data. */
    Tcl_Interp *interp;
{
    TreeCmdInterpData *dataPtr = (TreeCmdInterpData *)clientData;

    /* All tree instances should already have been destroyed when
     * their respective Tcl commands were deleted. */
    Tcl_DeleteHashTable(&(dataPtr->treeTable));
    Tcl_DeleteAssocData(interp, TREE_THREAD_KEY);
    free((char *)dataPtr);
}

/*ARGSUSED*/
static int
CompareDictionaryCmd(clientData, interp, objc, objv)
    ClientData clientData;	/* Not used. */
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int result, nBytes;
    char *s1, *s2;

    s1 = Tcl_GetStringFromObj(objv[1], &nBytes);
    s2 = Tcl_GetStringFromObj(objv[2], &nBytes);
    result = Blt_DictionaryCompare(s1, s2);
    result = (result > 0) ? -1 : (result < 0) ? 1 : 0;
    Tcl_SetIntObj(Tcl_GetObjResult(interp), result);
    return TCL_OK;
}

/*ARGSUSED*/
static int
ExitCmd(clientData, interp, objc, objv)
    ClientData clientData;	/* Not used. */
    Tcl_Interp *interp;
    int objc;
    Tcl_Obj **objv;
{
    int code;

    if (Tcl_GetIntFromObj(interp, objv[1], &code) != TCL_OK) {
	return TCL_ERROR;
    }
#ifdef TCL_THREADS
    Tcl_Exit(code);
#else 
    exit(code);
#endif
    /*NOTREACHED*/
    return TCL_OK;
}

/*
 * -----------------------------------------------------------------------
 *
 * Blt_TreeInit --
 *
 *	This procedure is invoked to initialize the "tree" command.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Creates the new command and adds a new entry into a global Tcl
 *	associative array.
 *
 * ------------------------------------------------------------------------
 */
int
Blt_TreeInit(interp)
    Tcl_Interp *interp;
{
    TreeCmdInterpData *dataPtr;	/* Interpreter-specific data. */
    static Blt_CmdSpec cmdSpec = { 
	"tree", (Tcl_CmdProc *)TreeObjCmd, 
    };
    static Blt_CmdSpec compareSpec = { 
	"compare", (Tcl_CmdProc *)CompareDictionaryCmd, 
    };
    static Blt_CmdSpec exitSpec = { 
	"exit", (Tcl_CmdProc *)ExitCmd, 
    };

    if (Blt_InitObjCmd(interp, "blt::util", &compareSpec) == NULL) {
	return TCL_ERROR;
    }
    if (Blt_InitObjCmd(interp, "blt::util", &exitSpec) == NULL) {
	return TCL_ERROR;
    }

    dataPtr = GetTreeInterpData(interp);
    cmdSpec.clientData = (ClientData)dataPtr;
    allUid = Blt_GetUid("all");
    rootUid = Blt_GetUid("root");
    if (Blt_InitObjCmd(interp, "blt", &cmdSpec) == NULL) {
	return TCL_ERROR;
    }
    return TCL_OK;
}

#endif /* NO_TREE */
