//
//  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 "../Risk.h"

RCSID ("$Id: SNHeap.m,v 1.1.1.1 1997/12/09 07:19:16 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;

    //NSLog (@"before: current: %d, maximum: %d", current_size, maximum_size);
    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;
    }
    //NSLog (@" after: current: %d, maximum: %d", current_size, maximum_size);

    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;
}

//----------------------------------------------------------------------

- (void) insertObjectsFromEnumerator:(NSEnumerator *)objectEnumerator
{
    id object;

    while (object = [objectEnumerator nextObject])
    {
        [self insertObject:object];
    }
}

//----------------------------------------------------------------------

// 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;
}

//----------------------------------------------------------------------

// Cheezy method -- need to redo

- (void) removeAllObjects
{
    while (current_size > 0)
    {
        [self extractObject];
    }
}

//----------------------------------------------------------------------

- (int) count
{
    return current_size;
}

//----------------------------------------------------------------------

- (void) heapifyFromObject:anObject
{
    int l;

    for (l = 0; l < current_size; l++)
    {
        if (data[l] == anObject)
        {
            NSLog (@"Heapifying from %d", l);
            [self heapify:l];
            break;
        }
    }
}

//----------------------------------------------------------------------

- (void) removeObject:anObject
{
    int l;

    for (l = 0; l < current_size; l++)
    {
        if (data[l] == anObject)
        {
            current_size--;
            data[l] = data[current_size];
            [self heapify:l];
            break;
        }
    }
}

//----------------------------------------------------------------------

- (NSString *) description
{
    NSMutableArray *array;
    int l;

    array = [NSMutableArray array];
    for (l = 0; l < current_size; l++)
        [array addObject:data[l]];

    return [NSString stringWithFormat:@"%@", array];
}

@end
