/*
 *  LISTREE.C             version 1.0
 *
 *  Converts sorted linked lists to balanced binary trees, and binary trees to
 *  sorted linked lists.  These routines are non-recursive, so we don't have to
 *  worry about stack size for large lists/trees.
 *
 *  Written for the Commodore Amiga 1000, version 1.3
 *  using Lattice C v4.0 by Davide P. Cervone
 */

#define NULL    0L

/*
 *  ListItem is what must be at the head of each item in the list.
 *  It also doubles as the left and right pointers of the binary tree.
 */

struct ListItem
{
   struct ListItem *li_Next;
   struct ListItem *li_Prev;
};
#define li_Left     li_Next
#define li_Right    li_Prev
#define li_BackUp   li_Left

#define SKIP_MISSING_NODE   (1<<1)
#define NO_MISSING_NODE     (1<<0)


/*
 *  *ListToTree()
 *
 *  Count the items in the list, if they weren't already counted for us.
 *  Find the smallest power of two greater than the count.  If there were
 *  exactly this many (minus one) items in the list, it would make a perfect
 *  balanced binary tree.  If there are not this many, we will use this basic
 *  form, but leave some of the lowest level empty.  We proceed by assuming
 *  that it has the full number, and skip items when necessary.
 *    As we build the tree, all the nodes to the left of the current node will
 *  be correct, nodes on the right may be modified as we go, however, and
 *  we will use the li_Right pointer to maintain back pointers to previous
 *  higher-up nodes in the tree (this takes the place of the recusion stack).
 *  At any given point, anything interior to the current tree is correctly 
 *  linked, but the nodes along the right-hand (of every level) have their
 *  li_Right pointers pointing upeward to the level above (towards the root).
 *    In a perfect binary tree, the binary representation of item's position
 *  in the list is used to determine its position in the tree:  the position
 *  of the least-significant 1 bit in the number tells which level of the tree
 *  that item should be in.  For example, if the number is 100 (binary), then
 *  the item is at the third level from the bottom of the tree.  The trick will
 *  be to assign numbers to the items in a list that is not of a perfect length.
 *
 *  The main loop counts off the numbers in the perfect-sized list.
 *    The next loop finds the node's level within the tree by looking along
 *      the back pointers (held in li_Right) until we reach the correct level.
 *      PreviousNode will point to the node to the left of the current item,
 *      and CurrentNode will become the back pointer for the current item.
 *    The only nodes that will be missing from a perfect balanced tree will
 *      be in the bottom level, so if the current item is to be in the bottom
 *      level (mask == 1) we check for whether we need to skip this position
 *      in the tree:  we could simply check whether num > Count, but this
 *      would leave all the missing items at one end of the level; we would
 *      prefer them to be more evenly intermixed, so we reverse the bits in
 *      num and then do the check.
 *    If the number is not to be skipped, and there is an item to add,
 *      We link the previous node into the left of the current node
 *      and make li_Right point back to the next level up.
 *      Indicate that no nodes are to be skipped.
 *    Otherwise indicate that a node (in the perfect tree) is to be skipped.
 *  The loop is repeated until every node is placed in the tree.  The very last
 *  pass in the loop causes the right-hand nodes to become properly linked, 
 *  and leaves the pointer to the top-most node in the PreviousNode pointer.
 *  This is returned as the root of the tree.
 */

struct ListItem *ListToTree(CurrentItem,Count)
struct ListItem *CurrentItem;
int Count;
{
   struct ListItem *NextItem;
   struct ListItem *CurrentNode = NULL;
   struct ListItem *NextNode, *PreviousNode;
   int num,temp,mask;
   int MaxCount;
   int MaskStart = NO_MISSING_NODE;
   
   if (Count == 0)
      for (NextItem=CurrentItem; NextItem; NextItem=NextItem->li_Next,Count++);

   for (MaxCount=1; MaxCount<=Count; MaxCount<<=1);
   
   for (num = 1; num <= MaxCount; num++)
   {
      PreviousNode = NULL;
      for (mask = MaskStart; (num & mask) == 0; mask <<= 1)
      {
         NextNode = CurrentNode->li_Right;
         CurrentNode->li_Right = PreviousNode;
         PreviousNode = CurrentNode;
         CurrentNode = NextNode;
      }
      if (mask == 1)
         for (temp=MaxCount | num; (temp>>=1)>1; mask = (mask<<1) | (temp & 1));
        else
         mask = 0;
      if (mask <= Count)
      {
         if (CurrentItem)
         {
            NextItem = CurrentItem->li_Next;
            CurrentItem->li_Left = PreviousNode;
            CurrentItem->li_Right = CurrentNode;
            CurrentNode = CurrentItem;
            CurrentItem = NextItem;
         }
         MaskStart = NO_MISSING_NODE;
      } else {
         MaskStart = SKIP_MISSING_NODE;
      }
   }
   return(PreviousNode);
}


/*
 *  *TreeToList()
 *
 *  Start at the root of the tree, and an empty list
 *  While there are more items in the tree
 *    While there are nodes to the left
 *      Save a pointer to where we last were in the tree
 *      Move to the left in the tree
 *    At this point, we have moved as far down the left side of the tree
 *      as possible, at the same time saving our return path
 *    Now repeat the following:
 *      Link the node into the linked list and make it the new list-head
 *      The next item will be the one to its right, if any
 *      If there is no item to the right
 *        Back up to the previous item (and recover the pointer to the node
 *          before that)
 *    Repeat this as long as there are no nodes on the right, and as long
 *      as there is still a current node to work with.
 *    At this point, we have moved back up the left-hand side of the tree,
 *      adding nodes to the list until we come to one with a right-hand
 *      branch.  The current node is not the first one on the right, and
 *      we are ready to go down its left-hand side.  This continues until
 *      all nodes are added to the list.  Note that as we proceed, the
 *      PrevItem pointer may point farther and farther away in the tree.
 *  Return the completed list.
 */

struct ListItem *TreeToList(theRoot)
struct ListItem *theRoot;
{
   struct ListItem *CurItem  = theRoot;
   struct ListItem *PrevItem = NULL;
   struct ListItem *list     = NULL;
   struct ListItem *NextItem = NULL;

   while (CurItem != NULL)
   {
      while ((NextItem = CurItem->li_Left) != NULL)
      {
         CurItem->li_BackUp = PrevItem;
         PrevItem = CurItem;
         CurItem = NextItem;
      }
      do
      {
         if (list) list->li_Right = CurItem;
         CurItem->li_Left = list;
         list = CurItem;
         NextItem = CurItem = CurItem->li_Right;
         if (CurItem == NULL)
         {
            CurItem = PrevItem;
            if (PrevItem) PrevItem = PrevItem->li_BackUp;
         }
      } while (NextItem == NULL && CurItem != NULL);
   }
   return(list);
}