/* Implementation for Objective-C BinaryTree collection object
   Copyright (C) 1993 Free Software Foundation, Inc.

   Written by:  R. Andrew McCallum <mccallum@cs.rochester.edu>
   Dept. of Computer Science, U. of Rochester, Rochester, NY  14627

   This file is part of the GNU Objective-C Collection library.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
   
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/ 

#include <coll/BinaryTree.h>
#include <coll/IndexedCollectionPrivate.h>
#include <objc/objc-api.h>

// do safety checks;
#define SAFE_BinaryTree

@implementation BinaryTree

+ initialize
{
  if (self == [BinaryTree class])
    [self setVersion:-1];	/* alpha release */
  return self;
}

/* This is the designated initializer of this class */
- init
{
  [super initEncoding:@encode(id)];
  _count = 0;
  _contents_root = nil;
  return self;
}

/* Archiving must mimic the above designated initializer */

- _readInit: (TypedStream*)aStream
{
  [super _readInit:aStream];
  _count = 0;
  _contents_root = nil;
  return self;
}

- _writeContents: (TypedStream*)aStream
{
  void archiveElement(elt e)
    {
      objc_write_object(aStream, e.id_u);
    }
  objc_write_type(aStream, @encode(unsigned int), &_count);
  [self withElementsCall:archiveElement];
  // We rely on the nodes to archive their children and parent ptrs;
  objc_write_object_reference(aStream, _contents_root);
  return self;
}

- _readContents: (TypedStream*)aStream
{
  int i;

  objc_read_type(aStream, @encode(unsigned int), &_count);
  for (i = 0; i < _count; i++)
    objc_read_object(aStream, &_contents_root);
  // We rely on the nodes to have archived their children and parent ptrs;
  objc_read_object(aStream, &_contents_root);
  return self;
}

/* Empty copy must empty an allocCopy'ed version of self */
- emptyCopy
{
  BinaryTree *copy = [super emptyCopy];
  copy->_count = 0;
  copy->_contents_root = nil;
  return copy;
}

/* This must work without sending any messages to content objects */
- empty
{
  _count = 0;
  _contents_root = nil;
  return self;
}

/* Override the designated initializer for our superclass IndexedCollection
   to make sure we have object contents */
- initEncoding: (const char *)contentEncoding
{
  if (!ENCODING_IS_OBJECT(contentEncoding))
    [self error:"BinaryTree contents must be objects."];
  return [self init];
}


- leftmostNodeFromNode: aNode
{
  id left;

  if (aNode)
    {
      while ((left = [aNode leftNode]) != nil)
	aNode = left;
    }
  return aNode;
}

- rightmostNodeFromNode: aNode
{
  id right;

  if (aNode)
    while ((right = [aNode rightNode]) != nil)
      {
	aNode = right;
      }
  return aNode;
}

- (elt) firstElement
{
  return [self leftmostNodeFromNode:_contents_root];
}

- (elt) lastElement
{
  return [self rightmostNodeFromNode:_contents_root];
}

- (elt) maxElement
{
  return [self rightmostNodeFromNode:_contents_root];
}

- (elt) minElement
{
  return [self leftmostNodeFromNode:_contents_root];
}

// returns nil is there is no successor;
- (elt) successorElement: (elt)anElement
{
  id tmp;

  // here tmp is the right node;
  if ((tmp = [anElement.id_u rightNode]) != nil)
    return [self leftmostNodeFromNode:tmp];
  // here tmp is the parent;
  tmp = [anElement.id_u parentNode];
  while (tmp != nil && anElement.id_u == [tmp rightNode])
    {
      anElement.id_u = tmp;
      tmp = [tmp parentNode];
    }
  return tmp;
}

// I should make sure that [_contents_root parentNode] == nil;
// Perhaps I should make [_contents_root parentNode] == binaryTreeObj ??;

// returns nil is there is no predecessor;
- (elt) predecessorElement: (elt)anElement
{
  id tmp;

  // here tmp is the left node;
  if ((tmp = [anElement.id_u leftNode]) != nil)
    return [self rightmostNodeFromNode:tmp];
  // here tmp is the parent;
  tmp = [anElement.id_u parentNode];
  while (tmp != nil && anElement.id_u == [tmp leftNode])
    {
      anElement.id_u = tmp;
      tmp = [tmp parentNode];
    }
  return tmp;
}

/* This relies on [_contents_root parentNode] == nil */
- rootFromNode: aNode
{
  id parentNode;
  while ((parentNode = [aNode parentNode]) != nil)
    aNode = parentNode;
  return aNode;
}

/* This relies on [_contents_root parentNode] == nil */
- (unsigned) depthOfNode: aNode
{
  unsigned count = 0;
  
  if (aNode == nil)
    [self error:"in %s, Can't find depth of nil node", sel_get_name(_cmd)];
  do
    {
      aNode = [aNode parentNode];
      count++;
    }
  while (aNode != nil);
  return count;
}

- (unsigned) heightOfNode: aNode
{
  unsigned leftHeight, rightHeight;
  id tmpNode;

  if (aNode == nil)
    [self error:"in %s, Can't find height of nil node", sel_get_name(_cmd)];
  else 
    {
      leftHeight = ((tmpNode = [aNode leftNode])
		    ?
		    (1 + [self heightOfNode:tmpNode])
		    :
		    0);
      rightHeight = ((tmpNode = [aNode rightNode])
		     ?
		     (1 + [self heightOfNode:tmpNode])
		     :
		     0);
      return MAX(leftHeight, rightHeight);
    }
}

- (unsigned) nodeCountUnderNode: aNode
{
  unsigned count = 0;
  if ([aNode leftNode])
    count += 1 + [self nodeCountUnderNode:[aNode leftNode]];
  if ([aNode rightNode])
    count += 1 + [self nodeCountUnderNode:[aNode rightNode]];
  return count;
}

- leftRotateAroundNode: aNode
{
  id y;

  y = [aNode rightNode];
  [aNode setRightNode:[y leftNode]];
  if ([y leftNode] != nil)
    [[y leftNode] setParentNode:aNode];
  [y setParentNode:[aNode parentNode]];
  if ([aNode parentNode] != nil)
    _contents_root = y;
  else
    {
      if (aNode == [[aNode parentNode] leftNode])
	[[aNode parentNode] setLeftNode:y];
      else
	[[aNode parentNode] setRightNode:y];
    }
  [y setLeftNode:aNode];
  [aNode setParentNode:y];
  return self;
}

- rightRotateAroundNode: aNode
{
  id y;

  y = [aNode leftNode];
  [aNode setLeftNode:[y rightNode]];
  if ([y rightNode] != nil)
    [[y rightNode] setParentNode:aNode];
  [y setParentNode:[aNode parentNode]];
  if ([aNode parentNode] != nil)
    _contents_root = y;
  else
    {
      if (aNode == [[aNode parentNode] rightNode])
	[[aNode parentNode] setRightNode:y];
      else
	[[aNode parentNode] setLeftNode:y];
    }
  [y setRightNode:aNode];
  [aNode setParentNode:y];
  return self;
}

- (elt) elementAtIndex: (unsigned)index
{
  elt ret;

  CHECK_INDEX_RANGE_ERROR(index, _count);
  ret = [self firstElement];
  // Not very efficient;  Should be rewritten;
  while (index--)
    ret = [self successorElement:ret];
  return ret;
}

- sortAddElement: (elt)newElement byCalling: (int(*)(elt,elt))aFunc
{
  id theParent, tmpChild;

  [newElement.id_u setLeftNode:nil];
  [newElement.id_u setRightNode:nil];
  theParent = nil;
  tmpChild = _contents_root;
  while (tmpChild != nil)
    {
      theParent = tmpChild;
      if ((*aFunc)(newElement,theParent) < 0)
	tmpChild = [tmpChild leftNode];
      else
	tmpChild = [tmpChild rightNode];
    }
  [newElement.id_u setParentNode:theParent];
  if (theParent == nil)
    _contents_root = newElement.id_u;
  else
    {
      if (COMPARE_ELEMENTS(newElement, theParent) < 0)
	[theParent setLeftNode:newElement.id_u];
      else
	[theParent setRightNode:newElement.id_u];
    }
  _count++;
  return self;
}

- addElement: (elt)newElement
{
  // By default insert in sorted order.  Is this what we want?;
  [self sortAddElement:newElement];
  return self;
}

// NOTE: This gives you the power to put elements in unsorted order;
- insertElement: (elt)newElement before: (elt)oldElement
{
  id tmp;

  #ifdef SAFE_BinaryTree
  if ([self rootFromNode:oldElement.id_u] != _contents_root)
    [self error:"in %s, oldElement not in tree!!", sel_get_name(_cmd)];
  #endif

  [newElement.id_u setRightNode:nil];
  [newElement.id_u setLeftNode:nil];
  if ((tmp = [oldElement.id_u leftNode]))
    {
      [(tmp = [self rightmostNodeFromNode:tmp]) setRightNode:newElement.id_u];
      [newElement.id_u setParentNode:tmp];
    }
  else if (newElement.id_u != nil)
    {
      [oldElement.id_u setLeftNode:newElement.id_u];
      [newElement.id_u setParentNode:oldElement.id_u];
    }
  else
    {
      _contents_root = newElement.id_u;
      [newElement.id_u setParentNode:nil];
    }
  _count++;
  return self;
}

// NOTE: This gives you the power to put elements in unsorted order;
- insertElement: (elt)newElement after: (elt)oldElement
{
  id tmp;

  #ifdef SAFE_BinaryTree
  if ([self rootFromNode:oldElement.id_u] != _contents_root)
    [self error:"in %s, !!!!!!!!", sel_get_name(_cmd)];
  #endif

  [newElement.id_u setRightNode:nil];
  [newElement.id_u setLeftNode:nil];
  if ((tmp = [oldElement.id_u rightNode]))
    {
      [(tmp = [self leftmostNodeFromNode:tmp]) setLeftNode:newElement.id_u];
      [newElement.id_u setParentNode:tmp];
    }
  else if (newElement.id_u != nil)
    {
      [oldElement.id_u setRightNode:newElement.id_u];
      [newElement.id_u setParentNode:oldElement.id_u];
    }
  else
    {
      _contents_root = newElement.id_u;
      [newElement.id_u setParentNode:nil];
    }
  _count++;
  return self;
}

// NOTE: This gives you the power to put elements in unsorted order;
- insertElement: (elt)newElement atIndex: (unsigned)index
{
  CHECK_INDEX_RANGE_ERROR(index, _count+1);
  if (index == _count)
    [self appendElement:newElement];
  else
    [self insertElement:newElement before:[self elementAtIndex:index]];
  return self;
}

// NOTE: This gives you the power to put elements in unsorted order;
- appendElement: (elt)newElement
{
  if (_count == 0)
    {
      _contents_root = newElement.id_u;
      _count = 1;
      [newElement.id_u setLeftNode:nil];
      [newElement.id_u setRightNode:nil];
      [newElement.id_u setParentNode:nil];
    }
  else 
    [self insertElement:newElement after:[self lastElement]];
  return self;
}

- (elt) removeElement: (elt)oldElement
{
  id x, y;

  if ([oldElement.id_u leftNode] == nil || [oldElement.id_u rightNode] == nil)
    y = oldElement.id_u;
  else
    y = [self successorElement:oldElement].id_u;

  if ([y leftNode] != nil)
    x = [y leftNode];
  else
    x = [y rightNode];

  if (x != nil)
    [x setParentNode:[y parentNode]];

  if ([y parentNode] == nil)
    _contents_root = x;
  else
    {
      if (y == [[y parentNode] leftNode])
	[[y parentNode] setLeftNode:x];
      else
	[[y parentNode] setRightNode:x];
    }

  if (y != oldElement.id_u)
    {
      /* put y in the place of oldElement.id_u */
      [y setParentNode:[oldElement.id_u parentNode]];
      [y setLeftNode:[oldElement.id_u leftNode]];
      [y setRightNode:[oldElement.id_u rightNode]];
      if (oldElement.id_u == [[oldElement.id_u parentNode] leftNode])
	[[oldElement.id_u parentNode] setLeftNode:y];
      else
	[[oldElement.id_u parentNode] setRightNode:oldElement.id_u];
      [[oldElement.id_u leftNode] setParentNode:y];
      [[oldElement.id_u rightNode] setParentNode:y];
    }
  [oldElement.id_u setRightNode:nil];
  [oldElement.id_u setLeftNode:nil];
  [oldElement.id_u setParentNode:nil];
  _count--;
  return oldElement;
}

- withElementsCall: (void(*)(elt))aFunc whileTrue: (BOOL*)flag
{
  void traverse(id aNode)
    {
      if (!(*flag) || aNode == nil)
	return;
      traverse([aNode leftNode]);
      (*aFunc)(aNode);
      traverse([aNode rightNode]);
    }
  traverse(_contents_root);
  return self;
}

- withElementsInReverseCall: (void(*)(elt))aFunc whileTrue: (BOOL*)flag
{
  void traverse(id aNode)
    {
      if (*flag || aNode == nil)
	return;
      traverse([aNode rightNode]);
      (*aFunc)(aNode);
      traverse([aNode leftNode]);
    }
  traverse(_contents_root);
  return self;
}

- (BOOL) getNextElement:(elt *)anElementPtr withEnumState: (void**)enumState
{
  if (!(*enumState)) 
    *enumState = [self leftmostNodeFromNode:_contents_root];
  else
    *enumState = [self successorElement:*enumState].id_u;
  *anElementPtr = *enumState;
  if (*enumState)
    return YES;
  return NO;
}

- (BOOL) getPrevElement:(elt *)anElementPtr withEnumState: (void**)enumState
{
  if (!(*enumState)) 
    *enumState = [self rightmostNodeFromNode:_contents_root];
  else
    *enumState = [self predecessorElement:*enumState].id_u;
  *anElementPtr = *enumState;
  if (*enumState)
    return YES;
  return NO;
}

- (unsigned) count
{
  return _count;
}

- (BOOL) nodeIsRightNode: aNode
{
  [self notImplemented:_cmd];
  return NO;
}

- (BOOL) nodeIsLeftNode: aNode
{
  [self notImplemented:_cmd];
  return NO;
}

@end


