Line data Source code
1 0 : /*
2 :
3 : OOPriorityQueue.m
4 :
5 :
6 : Copyright (C) 2007-2013 Jens Ayton
7 :
8 : Permission is hereby granted, free of charge, to any person obtaining a copy
9 : of this software and associated documentation files (the "Software"), to deal
10 : in the Software without restriction, including without limitation the rights
11 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : copies of the Software, and to permit persons to whom the Software is
13 : furnished to do so, subject to the following conditions:
14 :
15 : The above copyright notice and this permission notice shall be included in all
16 : copies or substantial portions of the Software.
17 :
18 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24 : SOFTWARE.
25 :
26 : */
27 :
28 : #include <assert.h>
29 :
30 : #import "OOPriorityQueue.h"
31 : #import "OOFunctionAttributes.h"
32 :
33 :
34 : /* Capacity grows by 50% each time. kMinCapacity must be at least 2 or Bad
35 : Things will happen. Some examples of growth patterns based on kMinCapacity:
36 : 2: 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066...
37 : 4: 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599...
38 : 8: 8 12 18 27 40 60 90 135 202 303 454 681 1021 1531 2296...
39 : 16: 16 24 36 54 81 121 181 271 406 609 913 1369 2053 3079...
40 : 32: 32 48 72 108 162 243 364 546 819 1228 1842 2763 4144...
41 :
42 : Special cases: when an OOPriorityQueue is copied, the copy's capacity is
43 : set to the same as its count, which may be less than kMinCapacity. However,
44 : when it is grown, it will be set to at least kMinCapacity (except in the
45 : case of a reallocation failure, in which case an attempt will be made to
46 : grow capacity by one element).
47 : */
48 0 : enum
49 : {
50 : kMinCapacity = 16
51 : };
52 :
53 :
54 : /* Functions to navigate the binary heap.
55 : Using one-based indices, the following hold:
56 : * The left child of a node, L(n), is 2n.
57 : * The right child of a node, R(n), is 2n + 1.
58 : * The parent of a node, P(n), is n/2 for n > 1.
59 :
60 : Using zero-based indices, we must convert to and from one-based indices to
61 : perform these calculations, giving:
62 : * Lz(n) = L(n+1)-1 = (2(n+1))-1 = 2n+1
63 : * Rz(n) = R(n+1)-1 = (2(n+1)+1)-1 = 2n+2
64 : * Pz(n) = P(n+1)-1 = ((n+1)/2)-1
65 : */
66 :
67 :
68 : OOINLINE NSUInteger PQLeftChild(NSUInteger n) INLINE_CONST_FUNC;
69 : OOINLINE NSUInteger PQRightChild(NSUInteger n) INLINE_CONST_FUNC;
70 : OOINLINE NSUInteger PQParent(NSUInteger n) INLINE_CONST_FUNC;
71 :
72 0 : OOINLINE NSUInteger PQLeftChild(NSUInteger n)
73 : {
74 : return (n << 1) + 1;
75 : }
76 :
77 0 : OOINLINE NSUInteger PQRightChild(NSUInteger n)
78 : {
79 : return (n << 1) + 2;
80 : }
81 :
82 :
83 0 : OOINLINE NSUInteger PQParent(NSUInteger n)
84 : {
85 : return ((n + 1) >> 1) - 1;
86 : }
87 :
88 :
89 0 : typedef NSComparisonResult (*CompareIMP)(id self, SEL _cmd, id other);
90 :
91 :
92 0 : OOINLINE NSComparisonResult PQCompare(id a, id b, SEL comparator)
93 : {
94 : CompareIMP compare = NULL;
95 : NSComparisonResult result;
96 :
97 : // This is equivalent to [a performSelector:comparator withObject:b], except the resulting value isn't an object.
98 : compare = (CompareIMP)[a methodForSelector:comparator];
99 : result = compare(a, comparator, b);
100 : return result;
101 : }
102 :
103 :
104 : // Private priority queue methods.
105 : @interface OOPriorityQueue (Private)
106 :
107 0 : - (void) makeObjectsPerformSelector:(SEL)selector;
108 :
109 0 : - (void) bubbleUpFrom:(NSUInteger)i;
110 0 : - (void) bubbleDownFrom:(NSUInteger)i;
111 :
112 0 : - (void) growBuffer;
113 0 : - (void) shrinkBuffer;
114 :
115 0 : - (void)removeObjectAtIndex:(NSUInteger)i;
116 :
117 : #if OO_DEBUG
118 : - (void) appendDebugDataToString:(NSMutableString *)string index:(NSUInteger)i depth:(NSUInteger)depth;
119 : #endif
120 :
121 : @end
122 :
123 :
124 : // NSEnumerator subclass to pull objects from queue.
125 0 : @interface OOPriorityQueueEnumerator: NSEnumerator
126 : {
127 : @private
128 0 : OOPriorityQueue *_queue;
129 : }
130 :
131 0 : - (id) initWithPriorityQueue:(OOPriorityQueue *)queue;
132 :
133 : @end
134 :
135 :
136 : @implementation OOPriorityQueue
137 :
138 : + (instancetype) queueWithComparator:(SEL)comparator
139 : {
140 : return [[[self alloc] initWithComparator:comparator] autorelease];
141 : }
142 :
143 :
144 : - (id) initWithComparator:(SEL)comparator
145 : {
146 : if (comparator == NULL)
147 : {
148 : [self release];
149 : return nil;
150 : }
151 :
152 : self = [super init];
153 : if (self != nil)
154 : {
155 : _comparator = comparator;
156 : }
157 :
158 : return self;
159 : }
160 :
161 :
162 0 : - (id) init
163 : {
164 : return [self initWithComparator:@selector(compare:)];
165 : }
166 :
167 :
168 0 : - (void) dealloc
169 : {
170 : [self makeObjectsPerformSelector:@selector(release)];
171 : free(_heap);
172 :
173 : [super dealloc];
174 : }
175 :
176 :
177 0 : - (NSString *) description
178 : {
179 : return [NSString stringWithFormat:@"<%@ %p>{count=%lu, capacity=%lu}", [self class], self, _count, _capacity];
180 : }
181 :
182 :
183 : #if OO_DEBUG
184 : - (NSString *) debugDescription
185 : {
186 : NSMutableString *result = nil;
187 :
188 : result = [NSMutableString string];
189 : [result appendFormat:@"<%@ %p> (count=%lu, capacity=%lu, comparator=%@)", [self class], self, _count, _capacity, NSStringFromSelector(_comparator)];
190 :
191 : if (_count != 0)
192 : {
193 : [result appendString:@"\n{\n"];
194 : [self appendDebugDataToString:result index:0 depth:0];
195 : [result appendString:@"}"];
196 : }
197 : else
198 : {
199 : [result appendString:@" {}"];
200 : }
201 : return result;
202 : }
203 : #endif
204 :
205 :
206 0 : - (BOOL) isEqual:(id)object
207 : {
208 : NSUInteger i;
209 : OOPriorityQueue *selfCopy = nil, *otherCopy = nil;
210 : BOOL identical = YES;
211 :
212 : if (object == self) return YES;
213 : if (![object isKindOfClass:[self class]]) return NO;
214 :
215 : if (_count != [object count]) return NO;
216 : if (_count == 0) return YES;
217 :
218 : selfCopy = [self copy];
219 : otherCopy = [object copy];
220 : i = _count;
221 : while (i--)
222 : {
223 : if (![[selfCopy nextObject] isEqual:[otherCopy nextObject]])
224 : {
225 : identical = NO;
226 : break;
227 : }
228 : }
229 : [selfCopy release];
230 : [otherCopy release];
231 :
232 : return identical;
233 : }
234 :
235 :
236 0 : - (NSUInteger) hash
237 : {
238 : if (_count == 0) return NSNotFound;
239 : return _count ^ [_heap[0] hash];
240 : }
241 :
242 :
243 0 : - (id) copyWithZone:(NSZone *)zone
244 : {
245 : OOPriorityQueue *copy = nil;
246 :
247 : copy = [[self class] allocWithZone:zone];
248 : if (copy != nil)
249 : {
250 : copy->_comparator = _comparator;
251 : copy->_count = _count;
252 : copy->_capacity = _count;
253 :
254 : copy->_heap = malloc(_count * sizeof(id));
255 : if (copy->_heap != NULL)
256 : {
257 : memcpy(copy->_heap, _heap, _count * sizeof(id));
258 : [copy makeObjectsPerformSelector:@selector(retain)];
259 : }
260 : else if (_count != 0)
261 : {
262 : [copy release];
263 : copy = nil;
264 : }
265 : }
266 :
267 : return copy;
268 : }
269 :
270 :
271 : - (void) addObject:(id)object
272 : {
273 : NSUInteger i;
274 :
275 : // Validate object
276 : if (object == nil)
277 : {
278 : [NSException raise:NSInvalidArgumentException
279 : format:@"Attempt to insert nil into OOPriorityQueue."];
280 : }
281 :
282 : if (![object respondsToSelector:_comparator])
283 : {
284 : [NSException raise:NSInvalidArgumentException
285 : format:@"Attempt to insert object (%@) which does not support comparator %@ into OOPriorityQueue.",
286 : object, NSStringFromSelector(_comparator)];
287 : }
288 :
289 : // Ensure there is sufficent space.
290 : if (_count == _capacity) [self growBuffer];
291 :
292 : // insert object at end of buffer.
293 : i = _count++;
294 : _heap[i] = object;
295 :
296 : [self bubbleUpFrom:i];
297 : [object retain];
298 : }
299 :
300 :
301 : - (void) removeObject:(id)object
302 : {
303 : NSUInteger i;
304 :
305 : /* Perform linear search for object (using comparator). A depth-first
306 : search could skip leaves of lower priority, but I don't expect this to
307 : be called very often.
308 : */
309 :
310 : if (object == nil) return;
311 :
312 : for (i = 0; i < _count; ++i)
313 : {
314 : if (PQCompare(object, _heap[i], _comparator) == 0)
315 : {
316 : [self removeObjectAtIndex:i];
317 : }
318 : }
319 : }
320 :
321 :
322 : - (void) removeExactObject:(id)object
323 : {
324 : NSUInteger i;
325 :
326 : if (object == nil) return;
327 :
328 : for (i = 0; i < _count; ++i)
329 : {
330 : if (object == _heap[i])
331 : {
332 : [self removeObjectAtIndex:i];
333 : }
334 : }
335 : }
336 :
337 :
338 : - (NSUInteger) count
339 : {
340 : return _count;
341 : }
342 :
343 :
344 : - (id) nextObject
345 : {
346 : id result = [self peekAtNextObject];
347 : [self removeNextObject];
348 : return result;
349 : }
350 :
351 :
352 : - (id) peekAtNextObject
353 : {
354 : if (_count == 0) return nil;
355 : // return [[_heap[0] retain] autorelease];
356 : return _heap[0];
357 : }
358 :
359 :
360 : - (void) removeNextObject
361 : {
362 : [self removeObjectAtIndex:0];
363 : }
364 :
365 :
366 : - (void) addObjects:(id)collection
367 : {
368 : id value = nil;
369 :
370 : if ([collection respondsToSelector:@selector(objectEnumerator)]) collection = [collection objectEnumerator];
371 : if (![collection respondsToSelector:@selector(nextObject)]) return;
372 :
373 : while ((value = [collection nextObject])) [self addObject:value];
374 : }
375 :
376 :
377 : - (NSArray *) sortedObjects
378 : {
379 : return [[self objectEnumerator] allObjects];
380 : }
381 :
382 :
383 : - (NSEnumerator *) objectEnumerator
384 : {
385 : return [[[OOPriorityQueueEnumerator alloc] initWithPriorityQueue:self] autorelease];
386 : }
387 :
388 : @end
389 :
390 :
391 : @implementation OOPriorityQueue (Private)
392 :
393 : - (void) makeObjectsPerformSelector:(SEL)selector
394 : {
395 : NSUInteger i;
396 :
397 : if (selector == NULL) return;
398 :
399 : for (i = 0; i != _count; ++i)
400 : {
401 : [_heap[i] performSelector:selector];
402 : }
403 : }
404 :
405 :
406 : - (void) bubbleUpFrom:(NSUInteger)i
407 : {
408 : NSUInteger pi;
409 : id obj = nil, par = nil;
410 :
411 : while (0 < i)
412 : {
413 : pi = PQParent(i);
414 : obj = _heap[i];
415 : par = _heap[pi];
416 :
417 : if (PQCompare(obj, par, _comparator) < 0)
418 : {
419 : _heap[i] = par;
420 : _heap[pi] = obj;
421 : i = pi;
422 : }
423 : else break;
424 : }
425 : }
426 :
427 :
428 : - (void) bubbleDownFrom:(NSUInteger)i
429 : {
430 : NSUInteger end = _count - 1;
431 : NSUInteger li, ri, next;
432 : id obj = nil;
433 :
434 : obj = _heap[i];
435 : while (PQLeftChild(i) <= end)
436 : {
437 : li = PQLeftChild(i);
438 : ri = PQRightChild(i);
439 :
440 : // If left child has lower priority than right child, or there is only one child...
441 : if (li == end || PQCompare(_heap[li], _heap[ri], _comparator) < 0)
442 : {
443 : next = li;
444 : }
445 : else
446 : {
447 : next = ri;
448 : }
449 :
450 : if (PQCompare(_heap[next], obj, _comparator) < 0)
451 : {
452 : // Exchange parent with lowest-priority child
453 : _heap[i] = _heap[next];
454 : _heap[next] = obj;
455 : i = next;
456 : }
457 : else break;
458 : }
459 : }
460 :
461 :
462 : - (void) growBuffer
463 : {
464 : id *newBuffer = NULL;
465 : NSUInteger newCapacity;
466 :
467 : newCapacity = _capacity * 3 / 2;
468 : if (newCapacity < kMinCapacity) newCapacity = kMinCapacity;
469 :
470 : // Note: realloc(NULL, size) with non-zero size is equivalent to malloc(size), so this is OK starting from a NULL buffer.
471 : newBuffer = realloc(_heap, newCapacity * sizeof(id));
472 : if (newBuffer == NULL)
473 : {
474 : // Attempt to grow by just one waffer-thin slot.
475 : newCapacity = _capacity + 1;
476 : newBuffer = realloc(_heap, newCapacity * sizeof(id));
477 :
478 : if (newBuffer == NULL)
479 : {
480 : // Failed to grow.
481 : [NSException raise:NSMallocException
482 : format:@"Could not expand capacity of OOPriorityQueue."];
483 : }
484 : }
485 :
486 : _heap = newBuffer;
487 : _capacity = newCapacity;
488 :
489 : assert(_count < _capacity);
490 : }
491 :
492 :
493 : - (void)shrinkBuffer
494 : {
495 : NSUInteger amountToRemove;
496 : id *newBuffer = NULL;
497 : NSUInteger newCapacity;
498 :
499 : if (kMinCapacity < _capacity)
500 : {
501 : // Remove two thirds of free space, if at least three slots are free.
502 : amountToRemove = (_capacity - _count) * 2 / 3;
503 : if (2 < amountToRemove)
504 : {
505 : newCapacity = _capacity - amountToRemove;
506 : newBuffer = realloc(_heap, newCapacity * sizeof(id));
507 : if (newBuffer != NULL)
508 : {
509 : _heap = newBuffer;
510 : _capacity = newCapacity;
511 : }
512 : }
513 : }
514 : }
515 :
516 :
517 : - (void)removeObjectAtIndex:(NSUInteger)i
518 : {
519 : id object = nil;
520 :
521 : if (_count <= i) return;
522 :
523 : object = _heap[i];
524 : if (i < --_count)
525 : {
526 : // Overwrite object with last object in array
527 : _heap[i] = _heap[_count];
528 :
529 : // Push previously-last object down until tree is partially ordered.
530 : [self bubbleDownFrom:i];
531 : }
532 : else
533 : {
534 : // Special case: removing last (or only) object. No bubbling needed.
535 : }
536 :
537 : [object autorelease];
538 : if (_count * 2 <= _capacity) [self shrinkBuffer];
539 : }
540 :
541 :
542 : #if OO_DEBUG
543 : - (void) appendDebugDataToString:(NSMutableString *)string index:(NSUInteger)i depth:(NSUInteger)depth
544 : {
545 : NSUInteger spaces;
546 :
547 : if (_count <= i) return;
548 :
549 : spaces = 2 + depth;
550 : while (spaces--) [string appendString:@" "];
551 : [string appendString:[_heap[i] description]];
552 : [string appendString:@"\n"];
553 :
554 : [self appendDebugDataToString:string index:PQLeftChild(i) depth:depth + 1];
555 : [self appendDebugDataToString:string index:PQRightChild(i) depth:depth + 1];
556 : }
557 : #endif
558 :
559 : @end
560 :
561 :
562 : @implementation OOPriorityQueueEnumerator
563 :
564 : - (id) initWithPriorityQueue:(OOPriorityQueue *)queue
565 : {
566 : if (queue == nil)
567 : {
568 : [self release];
569 : return nil;
570 : }
571 :
572 : self = [super init];
573 : if (self != nil)
574 : {
575 : _queue = [queue retain];
576 : }
577 : return self;
578 : }
579 :
580 :
581 0 : - (void) dealloc
582 : {
583 : [_queue release];
584 :
585 : [super dealloc];
586 : }
587 :
588 :
589 0 : - (id) nextObject
590 : {
591 : id value = [_queue nextObject];
592 : if (value == nil)
593 : {
594 : // Maintain enumerator semantics by ensuring we don't start returning new values after returning nil.
595 : [_queue release];
596 : _queue = nil;
597 : }
598 : return value;
599 : }
600 :
601 : @end
602 :
603 :
604 : #if DEBUG_GRAPHVIZ
605 : @implementation OOPriorityQueue (DebugGraphViz)
606 :
607 :
608 : static NSString *EscapedString(NSString *string)
609 : {
610 : NSString *srcStrings[] =
611 : {
612 : //Note: backslash must be first.
613 : @"\\", @"\"", @"\'", @"\r", @"\n", @"\t", nil
614 : };
615 : NSString *subStrings[] =
616 : {
617 : //Note: must be same order.
618 : @"\\\\", @"\\\"", @"\\\'", @"\\r", @"\\n", @"\\t", nil
619 : };
620 :
621 : NSString **src = srcStrings, **sub = subStrings;
622 : NSMutableString *mutable = nil;
623 : NSString *result = nil;
624 :
625 : mutable = [string mutableCopy];
626 : while (*src != nil)
627 : {
628 : [mutable replaceOccurrencesOfString:*src++
629 : withString:*sub++
630 : options:0
631 : range:NSMakeRange(0, [mutable length])];
632 : }
633 :
634 : if ([mutable length] == [string length])
635 : {
636 : result = string;
637 : }
638 : else
639 : {
640 : result = [[mutable copy] autorelease];
641 : }
642 : [mutable release];
643 : return result;
644 : }
645 :
646 :
647 : - (NSString *) generateGraphViz
648 : {
649 : NSMutableString *result = nil;
650 : NSUInteger i;
651 : id node = nil;
652 : NSString *desc = nil;
653 :
654 : result = [NSMutableString string];
655 :
656 : // Header
657 : [result appendString:
658 : @"// OOPriorityQueue partially ordered tree dump\n\n"
659 : "digraph heap\n"
660 : "{\n"
661 : "\tgraph [charset=\"UTF-8\", label=\"OOPriorityQueue heap dump\", labelloc=t, labeljust=l];\n"
662 : "\tnode [shape=record];\n\t\n\t"];
663 :
664 : // Nodes
665 : for (i = 0; i < _count; ++i)
666 : {
667 : node = _heap[i];
668 : desc = [node description];
669 : if ([desc length] > 70)
670 : {
671 : desc = [[desc substringToIndex:64] stringByAppendingString:@"..."];
672 : }
673 :
674 : [result appendFormat:@"\tnode_%lu [label=\"<f0> | <f1> %@ | <f2>\"];\n", i, EscapedString(desc)];
675 : }
676 :
677 : // Arcs
678 : for (i = 0; PQLeftChild(i) < _count; ++i)
679 : {
680 : [result appendFormat:@"\tnode_%lu:f0 -> node_%lu:f1;\n", i, PQLeftChild(i)];
681 : if (PQRightChild(i) < _count) [result appendFormat:@"\tnode_%lu:f2 -> node_%lu:f1;\n", i, PQRightChild(i)];
682 : }
683 :
684 : [result appendString:@"}\n"];
685 :
686 : return result;
687 : }
688 :
689 :
690 : - (void) writeGraphVizToURL:(NSURL *)url
691 : {
692 : NSString *graphViz = nil;
693 : NSData *data = nil;
694 :
695 : graphViz = [self generateGraphViz];
696 : data = [graphViz dataUsingEncoding:NSUTF8StringEncoding];
697 :
698 : if (data != nil)
699 : {
700 : [data writeToURL:url atomically:YES];
701 : }
702 : }
703 :
704 :
705 : - (void) writeGraphVizToPath:(NSString *)path
706 : {
707 : [self writeGraphVizToURL:[NSURL fileURLWithPath:path]];
708 : }
709 :
710 : @end
711 : #endif
|
