Nebula 1995 August/NEBULA.mdf/SourceCode/PriorityQueue/PriorityQueue.m

Text File | 1992-11-10 | 10.0 KB | 543 lines

/* NAME:
**    PriorityQueue: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 GNU General Public License as
**    published by the Free Software Foundation; 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.  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.
*/

#import "PriorityQueue.h"


/* 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 PriorityQueue

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

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

- initCount:(int)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;
    PriorityQueue *copy;

    copy = [[PriorityQueue 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 PriorityQueue
**
** 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 PriorityQueue, 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:(PriorityQueue *)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:(PriorityQueue *)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