Line data    Source code

       1           0 : /*
       2             : 
       3             : OOPriorityQueue.h
       4             : 
       5             : A prority queue is a collection into which objects may be inserted in any
       6             : order, but (primarily) extracted in sorted order. The order is defined by the
       7             : comparison selector specified at creation time, which is assumed to have the
       8             : same signature as a compare method used for array sorting:
       9             : - (NSComparisonResult)compare:(id)other
      10             : and must define a partial order on the objects in the priority queue. The
      11             : behaviour when provided with an inconsistent comparison method is undefined.
      12             : 
      13             : The implementation is the standard one, a binary heap. It is described in
      14             : detail in most algorithm textbooks.
      15             : 
      16             : This collection is *not* thread-safe.
      17             : 
      18             : 
      19             : Copyright (C) 2007-2013 Jens Ayton
      20             : 
      21             : Permission is hereby granted, free of charge, to any person obtaining a copy
      22             : of this software and associated documentation files (the "Software"), to deal
      23             : in the Software without restriction, including without limitation the rights
      24             : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
      25             : copies of the Software, and to permit persons to whom the Software is
      26             : furnished to do so, subject to the following conditions:
      27             : 
      28             : The above copyright notice and this permission notice shall be included in all
      29             : copies or substantial portions of the Software.
      30             : 
      31             : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      32             : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
      33             : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
      34             : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
      35             : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
      36             : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
      37             : SOFTWARE.
      38             : 
      39             : */
      40             : 
      41             : #import "OOCocoa.h"
      42             : 
      43             : #ifndef OO_PQ_STRONG
      44             : #if __has_feature(objc_arc)
      45             : #define OO_PQ_STRONG __strong
      46             : #else
      47             : #define OO_PQ_STRONG
      48             : #endif
      49             : #endif
      50             : 
      51             : 
      52           0 : @interface OOPriorityQueue: NSObject <NSCopying>
      53             : {
      54             : @private
      55             :         SEL                                             _comparator;
      56           0 :         OO_PQ_STRONG id                 *_heap;
      57           0 :         NSUInteger                              _count,
      58           0 :                                                         _capacity;
      59           0 : }
      60             : 
      61             : // Note: -init is equivalent to -initWithComparator:@selector(compare:)
      62             : + (instancetype) queueWithComparator:(SEL)comparator;
      63           0 : - (id) initWithComparator:(SEL)comparator;
      64           0 : 
      65             : - (void) addObject:(id)object;                  // May throw NSInvalidArgumentException or NSMallocException.
      66           0 : - (void) removeObject:(id)object;               // Uses comparator (looking for NSOrderedEqual) to find object. Note: relatively expensive.
      67           0 : - (void) removeExactObject:(id)object;  // Uses pointer comparison to find object. Note: still relatively expensive.
      68           0 : 
      69             : - (NSUInteger) count;
      70           0 : 
      71             : - (id) nextObject;
      72           0 : - (id) peekAtNextObject;                                // Returns next object without removing it.
      73           0 : - (void) removeNextObject;
      74           0 : 
      75             : - (void) addObjects:(id)collection;             // collection must respond to -nextObject, or implement -objectEnumerator to return something that implements -nextObject -- such as an NSEnumerator.
      76           0 : 
      77             : - (NSArray *) sortedObjects;                    // Returns the objects in -nextObject order and empties the heap. To get the objects without emptying the heap, copy the priority queue first.
      78           0 : - (NSEnumerator *) objectEnumerator;    // Enumerator which pulls objects off the heap until it's empty. Note however that the queue itself behaves like an enumerator, as -nextObject has similar semantics (except that the enumerator's -nextObject can never start returning objects after it returns nil).
      79           0 : 
      80             : @end