ftp.nice.ch/pub/next/developer/resources/libraries/libcoll.931026.s.tar.gz#/libcoll-931026/RBTree.m

This is RBTree.m in view mode; [Download] [Up]

/* Implementation for Objective-C Red-Black Tree 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/RBTree.h>
#include <coll/IndexedCollectionPrivate.h>
#include <objc/objc-api.h>

@implementation RBTree

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

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

  [super sortAddElement:newElement byCalling:aFunc];
  [newElement.id_u setRed];
  while (newElement.id_u != _contents_root 
	 && [[newElement.id_u parentNode] isRed])
    {
      if ([newElement.id_u parentNode] == 
	  [[[newElement.id_u parentNode] parentNode] leftNode])
	{
	  y = [[[newElement.id_u parentNode] parentNode] leftNode];
	  if ([y isRed])
	    {
	      [[newElement.id_u parentNode] setBlack];
	      [y setBlack];
	      [[[newElement.id_u parentNode] parentNode] setRed];
	      newElement.id_u = [[newElement.id_u parentNode] parentNode];
	    }
	  else 
	    {
	      if (newElement.id_u == [[newElement.id_u parentNode] rightNode])
		{
		  newElement.id_u = [newElement.id_u parentNode];
		  [self leftRotateAroundNode:newElement.id_u];
		}
	      [[newElement.id_u parentNode] setBlack];
	      [[[newElement.id_u parentNode] parentNode] setRed];
	      [self rightRotateAroundNode:
		    [[newElement.id_u parentNode] parentNode]];
	    }
	}
      else
	{
	  y = [[[newElement.id_u parentNode] parentNode] rightNode];
	  if ([y isRed])
	    {
	      [[newElement.id_u parentNode] setBlack];
	      [y setBlack];
	      [[[newElement.id_u parentNode] parentNode] setRed];
	      newElement.id_u = [[newElement.id_u parentNode] parentNode];
	    }
	  else 
	    {
	      if (newElement.id_u == [[newElement.id_u parentNode] leftNode])
		{
		  newElement.id_u = [newElement.id_u parentNode];
		  [self rightRotateAroundNode:newElement.id_u];
		}
	      [[newElement.id_u parentNode] setBlack];
	      [[[newElement.id_u parentNode] parentNode] setRed];
	      [self leftRotateAroundNode:
		    [[newElement.id_u parentNode] parentNode]];
	    }
	}
    }
  [_contents_root setBlack];
  return self;
}

- (elt) removeElement: (elt)oldElement
{
  [self notImplemented:_cmd];
  [super removeElement:oldElement];
  return oldElement;
}


/* Override methods that could violate assumptions of RBTree structure.
   Perhaps I shouldn't DISALLOW this, let users have the power to do 
   whatever they want. */

/***
- insertElement: (elt)newElement before: (elt)oldElement
{
  INSERTION_ERROR(nil);
  return self;
}

- insertElement: (elt)newElement after: (elt)oldElement
{
  INSERTION_ERROR(nil);
  return self;
}

- insertElement: (elt)newElement atIndex: (unsigned)index
{
  INSERTION_ERROR(nil);
  return self;
}

- appendElement: (elt)newElement
{
  INSERTION_ERROR(nil);
  return self;
}
****/

@end

These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.