/* NAME:
**	MiscPriorityQueue:Object
**
**	COPYRIGHT 1992 BY ONYSCHUK AND ASSOCIATES
**	ALL RIGHTS RESERVED.
**
** REVISION HISTORY:
**	Sun Aug 16 14:14:03 EDT 1992	Mark Onyschuk
**					Starting point.
**
** DESCRIPTION:
**	A priority queue which dequeues objects sorted by
**	unsigned integer priorities.
**
**	NOTE: priority(0) > priority(1) > priority(2) > ... 
**
** DISCLAIMER:
**	This is free software; you can redistribute it and/or modify
**	it under the terms of the MiscKit license; either version
**	1, 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.
*/

#import <misckit/MiscPriorityQueue.h>
#import <appkit/appkit.h> // for free()


/* DEFINITIONS **********************************************************/

#define DEFAULTSIZE	8


/* MACROS ***************************************************************/

#define OBJECTAT(z)	(heap[z].object)
#define PRIORITYOF(z)	(heap[z].priority)

#define HEAPMALLOC(q)	\
	((NODE*)NXZoneMalloc([self zone],sizeof(NODE)*(q)))
#define HEAPREALLOC(q)	\
	((NODE*)NXZoneRealloc([self zone],heap,sizeof(NODE)*(q)))
#define HEAPFREE()	\
	(NXZoneFree([self zone],heap))


@implementation MiscPriorityQueue

/* INITIALIZING A PRIORITY QUEUE ****************************************/

- init
{
    return [self initCount:DEFAULTSIZE];
}

- initCount:(unsigned)count
{
    if ((self = [super init]) != nil)
    {
	top  = 0;
    	size = (count < 1) ? 1 : count;
	heap = HEAPMALLOC(size + 1);
    }
    return self;
}


/* FREEING A PRIORITY QUEUE *********************************************/

- free
{
    HEAPFREE();
    return [super free];
}

- copyFromZone:(NXZone *)zone
{
    int i;
    MiscPriorityQueue *copy;
    
    copy = [[[self class] allocFromZone:zone] initCount:size];
    
    for (i = top; i > 0; i--)
    {
    	((NODE *)(copy->heap))[i].object   = heap[i].object;
    	((NODE *)(copy->heap))[i].priority = heap[i].priority;
    }
    
    copy->top  = top;
    copy->size = size;
    
    return copy;
}


/* ADDING/REMOVING OBJECTS FROM A PRIORITY QUEUE ************************/

/* NAME:
**	- addObject:withPriority;
**
** ARGUMENTS:
**	anObject		object to be queued
**	priority		unsigned integer priority
**
** LAST EDITED:
**	Sun Aug 23 15:17:03 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Adds an object to the priority queue.
**
** ALGORITHM:
**	begin
**	    top <- top + 1
**
**	    if top > size(heap)
**	    begin
**		size(heap) = size(heap * 2)
**	    end
**
**	    heap[top].object <- anObject
**	    heap[top].priority <- priority
**
**	    i = top;
**	    j = parentOf(i);
**
**	    while (i <> 1) && (priorityOf(i) < priorityOf(j))
**	    begin
**		swap objects and priorities of i and j
**
**		i <- j;
**		j <- parentOf(i);
**	    end
**	end
**
** RETURNS:
**	self;
*/

- addObject:anObject withPriority:(unsigned int)priority
{
    int		i,
    		j;
    NODE 	temp;    


    top += 1;
        
    if (top > size)
    {
    	size *= 2;
	heap  = HEAPREALLOC(size + 1);
    }	

    
    OBJECTAT(top) = anObject;
    PRIORITYOF(top) = priority;
    
    for (i=top, j=i/2; (i>1) && (PRIORITYOF(i) < PRIORITYOF(j)); i=j, j=i/2)
    { 
	temp.object = OBJECTAT(i);
	temp.priority = PRIORITYOF(i);
	
	OBJECTAT(i) = OBJECTAT(j);
	PRIORITYOF(i) = PRIORITYOF(j);
	
	OBJECTAT(j) = temp.object;
	PRIORITYOF(j) = temp.priority;
    }
    
    return self;    
}

/* NAME:
**	- removeObject;
**
** ARGUMENTS:
**	none
**
** LAST EDITED:
**	Sun Aug 23 15:17:03 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Removes an object from the priority queue.
**
** ALGORITHM:
**	begin
**	    if (isEmpty(heap))
**		return nil
**
**	    anObject <- objectAt(1)
**
**	    move the top object and priority to the beginning (1)
**	    top <- top - 1
**	    i <- 1
**
**	    while (i <= top / 2)
**	    begin
**		j = objectOfMaxPriority(i*2, i*2 + 1)
**
**		if (priorityOf(i) > priorityOf(j))
**		begin
**		    swap objects and priorities of i and j
**		    i <- j
**		end else begin
**		    return anObject
**		end
**	    end
**	    return anObject
**	end
**
** RETURNS:
**	object from the queue with top priority, or
**	nil if the queue is empty.
*/

- removeObject;
{
    int		i,
    		j;

    NODE	temp;
    
    id		anObject;
    
        

    if (top == 0)
    	return nil;

    anObject  = OBJECTAT(1);
    
         
    OBJECTAT(1) = OBJECTAT(top);
    PRIORITYOF(1) = PRIORITYOF(top);
    
    
    i    = 1;
    top -= 1;

    while (i <= top/2)
    {
    	if ((PRIORITYOF(i*2) < PRIORITYOF((i*2) + 1)) || ((i*2) == top))
	    j =  i*2;
	else
	    j = (i*2) + 1;
    
    	if (PRIORITYOF(i) > PRIORITYOF(j))
	{
	    temp.object = OBJECTAT(i);
	    temp.priority = PRIORITYOF(i);
	    
	    OBJECTAT(i) = OBJECTAT(j);
	    PRIORITYOF(i) = PRIORITYOF(j);
	    
	    OBJECTAT(j) = temp.object;
	    PRIORITYOF(j) = temp.priority;
	    
	    i = j;
	}
	else
	{
	    return anObject;
	}
    }
    return anObject;
}    
    

/* DETERMINING THE HIGHEST PRIORITY IN A PRIORITY QUEUE *****************/

/* NAME:
**	- (unsigned)highestPriority
**
** ARGUMENTS:
**	none.
**
** DESCRIPTION:
**	Returns the highest priority occurring in the priority
**	queue.
**
** RETURNS:
**	the highest priority occurring in the queue, or
**	the latest priority occurring in the queue if the queue is empty.
*/

- (unsigned)highestPriority
{
    return PRIORITYOF(1);
}

    
/* COUNTING THE NUMBER OF OBJECTS IN A PRIORITY QUEUE *******************/

/* NAME:
**	-(int)count;
**
** ARGUMENTS:
**	none.
**
** LAST EDITED:
**	Sun Aug 23 15:17:03 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Returns the number of objects currently queued.
**
** RETURNS:
**	count of objects currently in the queue.
*/

- (unsigned int)count
{
    return top;
}


/* COMPARING AND COMBINING PRIORITY QUEUES ******************************/

/* NAME:
**	- (BOOL)isEqual:anObject
**
** ARGUMENTS:
**	anObject		a MiscPriorityQueue
**
** LAST MODIFIED:
**	Sun Aug 23 15:17:03 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Compares <anObject> with the reciever and returns YES if
**	<anObject> is a MiscPriorityQueue, and both <anObject> and self
**	contain the same objects in the same order.
**
** RETURNS:
**	YES if <anObject> is equal to the receiver, or
**	NO otherwise.
*/

- (BOOL)isEqual:anObject
{
    int i;
    
    if (anObject == self)
    	return YES;
	
    if (([anObject isKindOf:[self class]]) &&
    	((i = [anObject count]) == [self count]))
    {
    	/* we make copies because priority queues are partially
	** ordered trees and the contents of one queue and another
	** though equal might be arranged different order inside the
	** tree.
	*/
	id copyA = [self copy];
	id copyB = [anObject copy];

	while ((i--) && ([copyA removeObject] == [copyB removeObject]))
	    ;

	return (i < 0) ? YES : NO;
    }
    return NO;
}


/* NAME:
**	- appendQueue:(MiscPriorityQueue *)otherQueue
**
** ARGUMENTS:
**	otherQueue		source queue
**
** LAST MODIFIED:
**	Sun Aug 23 15:17:03 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Appends the contents of <otherQueue> to the reciever.
**
** RETURNS:
**	self.
*/

- appendQueue:(MiscPriorityQueue *)otherQueue
{
    int i;

    for (i = otherQueue->top; i > 0; i--)
    	[self addObject : ((NODE *)(otherQueue->heap))[i].object
	   withPriority : ((NODE *)(otherQueue->heap))[i].priority];

    return self;
}


/* GETTING AND SETTING THE CAPACITY OF A PRIORITY QUEUE *****************/

/* NAME:
**	-(unsigned int)capacity
**
** ARGUMENTS:
**	none.
**
** LAST EDITED:
**	Sun Aug 23 15:17:03 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Returns the maximum number of objects that can be stored in the
**	Queue without allocating more memory for it. When new memory is
**	allocated, it's taken from the same zone that was specified
**	when the Queue was created.
**
** RETURNS:
**	capacity.
*/

- (unsigned int)capacity
{
    return size;
}

/* NAME:
**	- setAvailableCapacity:(unsigned int)capacity
**
** ARGUMENTS:
**	capacity			unsigned integer
**
** LAST MODIFIED:
**	Tue Sep  1 15:56:18 EDT 1992	Mark Onyschuk
**
** DESCRIPTION:
**	Allocates or reallocates heap memory to contain
**	<capacity> objects.
**
** RETURNS:
**	nil if <capacity> is less than <top>, or
**	self otherwise.
*/

- setAvailableCapacity:(unsigned int)capacity
{
    if (capacity < top)
    	return nil;

    size  = capacity;
    heap  = HEAPREALLOC(size + 1);
    
    return self;
}


/* EMPTYING A PRIORITY QUEUE ********************************************/

- empty
{
    top = 0;
    return self;
}

- freeObjects
{
    for (; top > 0; top--)
    	[OBJECTAT(top) free];

    return self;
}   


/* SENDING MESSAGES TO OBJECTS ******************************************/

- makeObjectsPerform:(SEL)aSelector
{
    int	i;
    
    for (i = top; i > 0; i--)
    	if ([OBJECTAT(i) respondsTo:aSelector])
	    [OBJECTAT(i) perform:aSelector];
    
    return self;
}

- makeObjectsPerform:(SEL)aSelector with:anObject
{
    int	i;
    
    for (i = top; i > 0; i--)
    	if ([OBJECTAT(i) respondsTo:aSelector])
	    [OBJECTAT(i) perform:aSelector with:anObject];

    return self;
}


/* READING AND WRITING TYPED STREAMS ************************************/

- read:(NXTypedStream *)stream
{
    int i;
    
    [super read:stream];
    
    NXReadType(stream, "i", &size);
    NXReadType(stream, "i", &top);

    if (heap)
    	free(heap);

    heap = (NODE *)HEAPMALLOC(size+1);
    
    for (i = 1; i <= top; i ++)
    {
	OBJECTAT(i) = NXReadObject(stream);
    	NXReadType(stream, "i", &(PRIORITYOF(i)));
    }
    
    return self;
}

- write:(NXTypedStream *)stream
{
    int i;
    
    [super write:stream];
    
    NXWriteType(stream, "i", &size);
    NXWriteType(stream, "i", &top);

    for (i = 1; i < top; i ++)
    {
    	NXWriteObject(stream, OBJECTAT(i));
	NXWriteType(stream, "i", &(PRIORITYOF(i))); 
    }
    
    return self;
}

@end
