This is SNHeap.m in view mode; [Download] [Up]
//
// $Id: SNHeap.m,v 1.6 1997/10/31 04:52:03 nygard Exp $
//
//
// This file is a part of Empire, a game of exploration and conquest.
// Copyright (C) 1996 Steve Nygard
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program 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 General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
// You may contact the author by:
// e-mail: nygard@telusplanet.net
//
#import "Empire.h"
RCSID ("$Id: SNHeap.m,v 1.6 1997/10/31 04:52:03 nygard Exp $");
#import "SNHeap.h"
static inline int SNLeftIndex (int n)
{
return 2 * n + 1;
}
//----------------------------------------------------------------------
static inline int SNRightIndex (int n)
{
return 2 * n + 2;
}
//----------------------------------------------------------------------
static inline int SNParentIndex (int n)
{
return (n - 1) / 2;
}
//======================================================================
@implementation SNHeap
+ heapUsingFunction:(NSComparisonResult (*)(id,id,void *))comparator context:(void *)aContext
{
id newHeap;
newHeap = [[[SNHeap alloc] initUsingFunction:comparator context:aContext] autorelease];
return newHeap;
}
//----------------------------------------------------------------------
- initUsingFunction:(NSComparisonResult (*)(id, id, void *))comparator context:(void *)aContext
{
[super init];
comparator_function = comparator;
context = aContext;
maximum_size = 8;
data = (id *)malloc (maximum_size * sizeof (id *));
NSAssert (data != NULL, @"Malloc() failed.");
current_size = 0;
return self;
}
//----------------------------------------------------------------------
- (void) dealloc
{
int l;
if (data != NULL)
{
for (l = 0; l < current_size; l++)
{
[data[l] autorelease];
}
free (data);
}
[super dealloc];
}
//----------------------------------------------------------------------
// -1: NSOrderedAscending
// 0:
// 1: NSOrderedDescending
//----------------------------------------------------------------------
- (void) heapify:(int)i
{
int l;
int r;
int smallest;
l = SNLeftIndex (i);
r = SNRightIndex (i);
if (l < current_size && comparator_function (data[l], data[i], context) == NSOrderedAscending)
smallest = l;
else
smallest = i;
if (r < current_size && comparator_function (data[r], data[smallest], context) == NSOrderedAscending)
smallest = r;
if (smallest != i)
{
id tmp = data[i];
data[i] = data[smallest];
data[smallest] = tmp;
[self heapify:smallest];
}
}
//----------------------------------------------------------------------
- (void) insertObject:anObject
{
int i;
id current;
id parent;
if (current_size >= maximum_size)
{
// increase size
id *tmp = (id *)malloc (maximum_size * 2 * sizeof (id *));
NSAssert (tmp != NULL, @"Could not malloc() additional memory");
memcpy (tmp, data, current_size * sizeof (id *));
free (data);
data = tmp;
maximum_size *= 2;
}
NSAssert (current_size < maximum_size, @"Too big!");
[anObject retain];
i = current_size++;
current = data[i] = anObject;
parent = data[SNParentIndex (i)];
while (i > 0 && comparator_function (parent, current, context) == NSOrderedDescending)
{
data[i] = parent;
i = SNParentIndex (i);
parent = data[SNParentIndex (i)];
}
data[i] = current;
}
//----------------------------------------------------------------------
// Return nil if there are no more objects.
//----------------------------------------------------------------------
- extractObject
{
id min;
if (current_size > 0)
{
min = data[0];
data[0] = data[current_size - 1];
current_size--;
[self heapify:0];
[min autorelease];
}
else
{
min = nil;
}
return min;
}
//----------------------------------------------------------------------
- firstObject
{
id min;
if (current_size > 0)
min = data[0];
else
min = nil;
return min;
}
//----------------------------------------------------------------------
- (void) removeAllObjects
{
int l;
for (l = 0; l < current_size; l++)
SNRelease (data[l]);
current_size = 0;
}
//----------------------------------------------------------------------
- (int) count
{
return current_size;
}
@end
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.