/*
 *	$Source: /u1/Xr/src/Xrlib/Intrinsic/RCS/tree.c,v $
 *	$Header: tree.c,v 1.1 86/12/17 09:09:33 swick Exp $
 */

#ifndef lint
static char *rcsid_tree_c = "$Header: tree.c,v 1.1 86/12/17 09:09:33 swick Exp $";
#endif	lint

#include <Xr/xr-copyright.h>

/* $Header: tree.c,v 1.1 86/12/17 09:09:33 swick Exp $ */
/* Copyright 1986, Hewlett-Packard Company */
/* Copyright 1986, Massachussetts Institute of Technology */

static char rcsid[] = "$Header: tree.c,v 1.1 86/12/17 09:09:33 swick Exp $";
/*************************************<+>*************************************
 *****************************************************************************
 **
 **   File:        tree.c
 **
 **   Project:     X-ray Toolbox
 **
 **   Description: The resource manager tree handling routines.
 **
 **
 **   ------------------------ MODIFICATION RECORD   ------------------------
 *
 * $Log:	tree.c,v $
 * Revision 1.1  86/12/17  09:09:33  swick
 * Initial revision
 * 
 * Revision 7.0  86/11/13  08:21:59  08:21:59  rick ()
 * Final QA release
 * 
 * Revision 6.0  86/11/10  15:22:58  15:22:58  rick ()
 * QA #2 release
 * 
 * Revision 5.1  86/11/07  14:02:42  14:02:42  rick ()
 * Added the copyright message.
 * 
 * Revision 5.0  86/10/28  08:23:39  08:23:39  rick ()
 * QA #1.1 release
 * 
 * Revision 4.0  86/10/20  12:09:38  12:09:38  rick ()
 * QA 1 release
 * 
 * Revision 3.2  86/10/17  12:24:12  12:24:12  rick ()
 * Linted
 * 
 * Revision 3.1  86/10/16  11:21:19  11:21:19  rick ()
 * Added register variables.
 * 
 * Revision 3.0  86/10/02  15:59:26  15:59:26  rick ()
 *  Alpha release set to 3.0
 * 
 * Revision 2.0  86/09/16  08:03:58  08:03:58  rick ()
 * *** empty log message ***
 * 
 * Revision 1.1  86/09/03  13:35:20  13:35:20  rick ()
 * Initial revision
 * 
 *
 *****************************************************************************
 *************************************<+>*************************************/



#include <X/Xlib.h>
#include <Xr/defs.h>
#include <Xr/types.h>



/*************************************<->*************************************
 *
 *  _XrTreeSearch (resourceId, parentLink, node)
 *  INT32         resourceId;
 *  xrResource ** parentLink;
 *  xrResource ** node;
 *
 *
 *   Description:
 *   -----------
 *     _XrTreeSearch() provides for the retrieval of a specific resource
 *     from the resource tree pointed at by the parameter parent.
 *
 *
 *   Inputs:
 *   ------
 *     resourceId = The identifier for the resource to be found.
 *
 *     parent     = The pointer to the variable which contains the
 *                  pointer to the head of the tree.  It will be set
 *                  to point to the member of the parent node which
 *                  points at the located resource.
 *
 *     node       = Used for return information, node will be set to
 *                  point to the resource that is found.
 *
 * 
 *   Outputs:
 *   -------
 *     TRUE       = Returned as the value of the function if the 
 *                  resource is found.
 *
 *     FALSE      = Returned as the value of the function if the 
 *                  resource is not found.
 *
 *     parentLink = set to point at the member of the parent node 
 *                  which contains the pointer to the located resource
 *                  It will be invalid if the resource is not found.
 *
 *
 *   Procedures Called
 *   -----------------
 *     None
 *
 *************************************<->***********************************/


xrResource *
_XrTreeSearch (resourceId, parentLink)
INT32 resourceId;
register xrResource *** parentLink;

{
   register xrResource *  node;

   node = **parentLink;

   while (node != NULL)
   {
      if (resourceId < node -> resourceId)
      {
         *parentLink = &(node -> left);
         node = node -> left;
      }
      else if (resourceId > node -> resourceId)
      {
         *parentLink = &(node -> right);
         node = node -> right;
      }
      else
         return (node);
   }         

   return (NULL);
}



/*************************************<->*************************************
 *
 *  _XrTreeInsert (parentLink, node)
 *  xrResource ** parentLink;
 *  xrResource *  node;
 *
 *
 *   Description:
 *   -----------
 *     _XrTreeInsert() adds resource into the tree as a child of parent.
 *
 *
 *   Inputs:
 *   ------
 *     parentLink = The pointer to the variable which contains the 
 *                  pointer to the location in the tree where the 
 *                  resource is to be added.
 *
 *     node   = A pointer to the resoruce structure to be added.
 *
 * 
 *   Outputs:
 *   -------
 *     None
 *
 *
 *   Procedures Called
 *   -----------------
 *     None
 *
 *************************************<->***********************************/


_XrTreeInsert (parentLink, node)
xrResource ** parentLink;
xrResource *  node;

{
   *parentLink = node;
}



/*************************************<->*************************************
 *
 *  _XrTreeDelete (parentLink, node)
 *  xrResource ** parentLink;
 *  xrResource  * node;
 *
 *
 *   Description:
 *   -----------
 *     _XrTreeDelete() removes a resource pointed at by node
 *     from the resource tree.
 *
 *
 *   Inputs:
 *   ------
 *     parentLink = The pointer to the member of the parent of the 
 *                  resource to be removed which contains the pointer
 *                  to the resourse.
 *
 *     node       = Pointer to the resource to be removed.
 *
 * 
 *   Outputs:
 *   -------
 *     None
 *
 *
 *   Procedures Called
 *   -----------------
 *     None
 *
 *************************************<->***********************************/


_XrTreeDelete (parentLink, node)
register xrResource ** parentLink;
register xrResource *  node;

{
   register xrResource * rPtr;
   register xrResource * sPtr;

   if (node -> right == NULL)
      *parentLink = node -> left;
   else if (node -> left == NULL)
      *parentLink = node -> right;
   else
   {
      rPtr = node -> right;
      if (rPtr -> left == NULL)
      {
         rPtr -> left = node -> left;
         *parentLink = rPtr;
      }
      else
      {
         sPtr = rPtr -> left;
         while (sPtr -> left != NULL)
         {
            rPtr = sPtr;
            sPtr = rPtr -> left;
         }
         sPtr -> left = node -> left;
         rPtr -> left = sPtr -> right;
         sPtr -> right = node -> right;
         *parentLink = sPtr;
      }
   }
}

      


/*************************************<->*************************************
 *
 *  _XrTreeDump (ptr)
 *  xrResource * node;
 *
 *
 *   Description:
 *   -----------
 *     _XrTreeDump() is a temporary routine used to print out the
 *     contents of a tree starting as the resource pointed at by node.
 *
 *
 *   Inputs:
 *   ------
 *     node = pointer to the resource which is the starting point for
 *            the dump.
 *
 * 
 *   Outputs:
 *   -------
 *     All of the resources starting at node will be printed.
 *
 *
 *   Procedures Called
 *   -----------------
 *     None
 *
 *************************************<->***********************************/


_XrDumpTree (ptr)
xrResource * ptr;

{
   if (ptr == NULL)
      return;

   if (ptr -> left != NULL)
      _XrDumpTree (ptr -> left);

   printf ("resourceId = %d,	ptr =  %d\n", ptr -> resourceId, ptr);

   if (ptr -> right != NULL)
      _XrDumpTree (ptr -> right);

   return;
}
