This is BinaryTree.m in view mode; [Download] [Up]
/* 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
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.