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