Collections.subproj/CFBinaryHeap.h

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*      CFBinaryHeap.h
  26         Copyright (c) 1998-2003, Apple, Inc. All rights reserved.
  27 */
  28 /*!
  29         @header CFBinaryHeap
  30         CFBinaryHeap implements a container which stores values sorted using
  31         a binary search algorithm.  CFBinaryHeaps can be useful as priority
  32         queues.
  33 */
  34
  35 #if !defined(__COREFOUNDATION_CFBINARYHEAP__)
  36 #define __COREFOUNDATION_CFBINARYHEAP__ 1
  37
  38 #include <CoreFoundation/CFBase.h>
  39
  40 #if defined(__cplusplus)
  41 extern "C" {
  42 #endif
  43
  44 typedef struct {
  45     CFIndex     version;
  46     void *      info;
  47     const void *(*retain)(const void *info);
  48     void        (*release)(const void *info);
  49     CFStringRef (*copyDescription)(const void *info);
  50 } CFBinaryHeapCompareContext;
  51
  52 /*!
  53         @typedef CFBinaryHeapCallBacks
  54         Structure containing the callbacks for values of a CFBinaryHeap.
  55         @field version The version number of the structure type being passed
  56                 in as a parameter to the CFBinaryHeap creation functions.
  57                 This structure is version 0.
  58         @field retain The callback used to add a retain for the binary heap
  59                 on values as they are put into the binary heap.
  60                 This callback returns the value to use as the value in the
  61                 binary heap, which is usually the value parameter passed to
  62                 this callback, but may be a different value if a different
  63                 value should be added to the binary heap. The binary heap's
  64                 allocator is passed as the first argument.
  65         @field release The callback used to remove a retain previously added
  66                 for the binary heap from values as they are removed from
  67                 the binary heap. The binary heap's allocator is passed as the
  68                 first argument.
  69         @field copyDescription The callback used to create a descriptive
  70                 string representation of each value in the binary heap. This
  71                 is used by the CFCopyDescription() function.
  72         @field compare The callback used to compare values in the binary heap for
  73                 equality in some operations.
  74 */
  75 typedef struct {
  76     CFIndex     version;
  77     const void *(*retain)(CFAllocatorRef allocator, const void *ptr);
  78     void        (*release)(CFAllocatorRef allocator, const void *ptr);
  79     CFStringRef (*copyDescription)(const void *ptr);
  80     CFComparisonResult  (*compare)(const void *ptr1, const void *ptr2, void *context);
  81 } CFBinaryHeapCallBacks;
  82
  83 /*!
  84         @constant kCFStringBinaryHeapCallBacks
  85         Predefined CFBinaryHeapCallBacks structure containing a set
  86         of callbacks appropriate for use when the values in a CFBinaryHeap
  87         are all CFString types.
  88 */
  89 CF_EXPORT const CFBinaryHeapCallBacks kCFStringBinaryHeapCallBacks;
  90
  91 /*!
  92         @typedef CFBinaryHeapApplierFunction
  93         Type of the callback function used by the apply functions of
  94                 CFBinaryHeap.
  95         @param value The current value from the binary heap.
  96         @param context The user-defined context parameter given to the apply
  97                 function.
  98 */
  99 typedef void (*CFBinaryHeapApplierFunction)(const void *val, void *context);
 100
 101 /*!
 102         @typedef CFBinaryHeapRef
 103         This is the type of a reference to CFBinaryHeaps.
 104 */
 105 typedef struct __CFBinaryHeap * CFBinaryHeapRef;
 106
 107 /*!
 108         @function CFBinaryHeapGetTypeID
 109         Returns the type identifier of all CFBinaryHeap instances.
 110 */
 111 CF_EXPORT CFTypeID      CFBinaryHeapGetTypeID(void);
 112
 113 /*!
 114         @function CFBinaryHeapCreate
 115         Creates a new mutable or fixed-mutable binary heap with the given values.
 116         @param allocator The CFAllocator which should be used to allocate
 117                 memory for the binary heap and its storage for values. This
 118                 parameter may be NULL in which case the current default
 119                 CFAllocator is used. If this reference is not a valid
 120                 CFAllocator, the behavior is undefined.
 121         @param capacity The maximum number of values that can be contained
 122                 by the CFBinaryHeap. The binary heap starts empty, and can grow to this
 123                 number of values (and it can have less). If this parameter
 124                 is 0, the binary heap's maximum capacity is unlimited (or rather,
 125                 only limited by address space and available memory
 126                 constraints). If this parameter is negative, the behavior is
 127                 undefined.
 128         @param callBacks A pointer to a CFBinaryHeapCallBacks structure
 129                 initialized with the callbacks for the binary heap to use on
 130                 each value in the binary heap. A copy of the contents of the
 131                 callbacks structure is made, so that a pointer to a structure
 132                 on the stack can be passed in, or can be reused for multiple
 133                 binary heap creations. If the version field of this callbacks
 134                 structure is not one of the defined ones for CFBinaryHeap, the
 135                 behavior is undefined. The retain field may be NULL, in which
 136                 case the CFBinaryHeap will do nothing to add a retain to values
 137                 as they are put into the binary heap. The release field may be
 138                 NULL, in which case the CFBinaryHeap will do nothing to remove
 139                 the binary heap's retain (if any) on the values when the
 140                 heap is destroyed or a key-value pair is removed. If the
 141                 copyDescription field is NULL, the binary heap will create a
 142                 simple description for a value. If the equal field is NULL, the
 143                 binary heap will use pointer equality to test for equality of
 144                 values. This callbacks parameter itself may be NULL, which is
 145                 treated as if a valid structure of version 0 with all fields
 146                 NULL had been passed in. Otherwise,
 147                 if any of the fields are not valid pointers to functions
 148                 of the correct type, or this parameter is not a valid
 149                 pointer to a CFBinaryHeapCallBacks callbacks structure,
 150                 the behavior is undefined. If any of the values put into the
 151                 binary heap is not one understood by one of the callback functions
 152                 the behavior when that callback function is used is undefined.
 153         @param compareContext A pointer to a CFBinaryHeapCompareContext structure.
 154         @result A reference to the new CFBinaryHeap.
 155 */
 156 CF_EXPORT CFBinaryHeapRef       CFBinaryHeapCreate(CFAllocatorRef allocator, CFIndex capacity, const CFBinaryHeapCallBacks *callBacks, const CFBinaryHeapCompareContext *compareContext);
 157
 158 /*!
 159         @function CFBinaryHeapCreateCopy
 160         Creates a new mutable or fixed-mutable binary heap with the values from the given binary heap.
 161         @param allocator The CFAllocator which should be used to allocate
 162                 memory for the binary heap and its storage for values. This
 163                 parameter may be NULL in which case the current default
 164                 CFAllocator is used. If this reference is not a valid
 165                 CFAllocator, the behavior is undefined.
 166         @param capacity The maximum number of values that can be contained
 167                 by the CFBinaryHeap. The binary heap starts empty, and can grow to this
 168                 number of values (and it can have less). If this parameter
 169                 is 0, the binary heap's maximum capacity is unlimited (or rather,
 170                 only limited by address space and available memory
 171                 constraints). If this parameter is negative, or less than the number of
 172                 values in the given binary heap, the behavior is undefined.
 173         @param heap The binary heap which is to be copied. The values from the
 174                 binary heap are copied as pointers into the new binary heap (that is,
 175                 the values themselves are copied, not that which the values
 176                 point to, if anything). However, the values are also
 177                 retained by the new binary heap. The count of the new binary will
 178                 be the same as the given binary heap. The new binary heap uses the same
 179                 callbacks as the binary heap to be copied. If this parameter is
 180                 not a valid CFBinaryHeap, the behavior is undefined.
 181         @result A reference to the new mutable or fixed-mutable binary heap.
 182 */
 183 CF_EXPORT CFBinaryHeapRef       CFBinaryHeapCreateCopy(CFAllocatorRef allocator, CFIndex capacity, CFBinaryHeapRef heap);
 184
 185 /*!
 186         @function CFBinaryHeapGetCount
 187         Returns the number of values currently in the binary heap.
 188         @param heap The binary heap to be queried. If this parameter is not a valid
 189                 CFBinaryHeap, the behavior is undefined.
 190         @result The number of values in the binary heap.
 191 */
 192 CF_EXPORT CFIndex       CFBinaryHeapGetCount(CFBinaryHeapRef heap);
 193
 194 /*!
 195         @function CFBinaryHeapGetCountOfValue
 196         Counts the number of times the given value occurs in the binary heap.
 197         @param heap The binary heap to be searched. If this parameter is not a
 198                 valid CFBinaryHeap, the behavior is undefined.
 199         @param value The value for which to find matches in the binary heap. The
 200                 compare() callback provided when the binary heap was created is
 201                 used to compare. If the compare() callback was NULL, pointer
 202                 equality (in C, ==) is used. If value, or any of the values
 203                 in the binary heap, are not understood by the compare() callback,
 204                 the behavior is undefined.
 205         @result The number of times the given value occurs in the binary heap.
 206 */
 207 CF_EXPORT CFIndex       CFBinaryHeapGetCountOfValue(CFBinaryHeapRef heap, const void *value);
 208
 209 /*!
 210         @function CFBinaryHeapContainsValue
 211         Reports whether or not the value is in the binary heap.
 212         @param heap The binary heap to be searched. If this parameter is not a
 213                 valid CFBinaryHeap, the behavior is undefined.
 214         @param value The value for which to find matches in the binary heap. The
 215                 compare() callback provided when the binary heap was created is
 216                 used to compare. If the compare() callback was NULL, pointer
 217                 equality (in C, ==) is used. If value, or any of the values
 218                 in the binary heap, are not understood by the compare() callback,
 219                 the behavior is undefined.
 220         @result true, if the value is in the specified binary heap, otherwise false.
 221 */
 222 CF_EXPORT Boolean       CFBinaryHeapContainsValue(CFBinaryHeapRef heap, const void *value);
 223
 224 /*!
 225         @function CFBinaryHeapGetMinimum
 226         Returns the minimum value is in the binary heap.  If the heap contains several equal
 227                 minimum values, any one may be returned.
 228         @param heap The binary heap to be searched. If this parameter is not a
 229                 valid CFBinaryHeap, the behavior is undefined.
 230         @result A reference to the minimum value in the binary heap, or NULL if the
 231                 binary heap contains no values.
 232 */
 233 CF_EXPORT const void *  CFBinaryHeapGetMinimum(CFBinaryHeapRef heap);
 234
 235 /*!
 236         @function CFBinaryHeapGetMinimumIfPresent
 237         Returns the minimum value is in the binary heap, if present.  If the heap contains several equal
 238                 minimum values, any one may be returned.
 239         @param heap The binary heap to be searched. If this parameter is not a
 240                 valid CFBinaryHeap, the behavior is undefined.
 241         @param value A C pointer to pointer-sized storage to be filled with the minimum value in
 242                 the binary heap.  If this value is not a valid C pointer to a pointer-sized block
 243                 of storage, the result is undefined.  If the result of the function is false, the value
 244                 stored at this address is undefined.
 245         @result true, if a minimum value was found in the specified binary heap, otherwise false.
 246 */
 247 CF_EXPORT Boolean       CFBinaryHeapGetMinimumIfPresent(CFBinaryHeapRef heap, const void **value);
 248
 249 /*!
 250         @function CFBinaryHeapGetValues
 251         Fills the buffer with values from the binary heap.
 252         @param heap The binary heap to be queried. If this parameter is not a
 253                 valid CFBinaryHeap, the behavior is undefined.
 254         @param values A C array of pointer-sized values to be filled with
 255                 values from the binary heap. The values in the C array are ordered
 256                 from least to greatest. If this parameter is not a valid pointer to a
 257                 C array of at least CFBinaryHeapGetCount() pointers, the behavior is undefined.
 258 */
 259 CF_EXPORT void          CFBinaryHeapGetValues(CFBinaryHeapRef heap, const void **values);
 260
 261 /*!
 262         @function CFBinaryHeapApplyFunction
 263         Calls a function once for each value in the binary heap.
 264         @param heap The binary heap to be operated upon. If this parameter is not a
 265                 valid CFBinaryHeap, the behavior is undefined.
 266         @param applier The callback function to call once for each value in
 267                 the given binary heap. If this parameter is not a
 268                 pointer to a function of the correct prototype, the behavior
 269                 is undefined. If there are values in the binary heap which the
 270                 applier function does not expect or cannot properly apply
 271                 to, the behavior is undefined.
 272         @param context A pointer-sized user-defined value, which is passed
 273                 as the second parameter to the applier function, but is
 274                 otherwise unused by this function. If the context is not
 275                 what is expected by the applier function, the behavior is
 276                 undefined.
 277 */
 278 CF_EXPORT void          CFBinaryHeapApplyFunction(CFBinaryHeapRef heap, CFBinaryHeapApplierFunction applier, void *context);
 279
 280 /*!
 281         @function CFBinaryHeapAddValue
 282         Adds the value to the binary heap.
 283         @param heap The binary heap to which the value is to be added. If this parameter is not a
 284                 valid mutable CFBinaryHeap, the behavior is undefined.
 285                 If the binary heap is a fixed-capacity binary heap and it
 286                 is full before this operation, the behavior is undefined.
 287         @param value The value to add to the binary heap. The value is retained by
 288                 the binary heap using the retain callback provided when the binary heap
 289                 was created. If the value is not of the sort expected by the
 290                 retain callback, the behavior is undefined.
 291 */
 292 CF_EXPORT void          CFBinaryHeapAddValue(CFBinaryHeapRef heap, const void *value);
 293
 294 /*!
 295         @function CFBinaryHeapRemoveMinimumValue
 296         Removes the minimum value from the binary heap.
 297         @param heap The binary heap from which the minimum value is to be removed. If this
 298                 parameter is not a valid mutable CFBinaryHeap, the behavior is undefined.
 299 */
 300 CF_EXPORT void          CFBinaryHeapRemoveMinimumValue(CFBinaryHeapRef heap);
 301
 302 /*!
 303         @function CFBinaryHeapRemoveAllValues
 304         Removes all the values from the binary heap, making it empty.
 305         @param heap The binary heap from which all of the values are to be
 306                 removed. If this parameter is not a valid mutable CFBinaryHeap,
 307                 the behavior is undefined.
 308 */
 309 CF_EXPORT void          CFBinaryHeapRemoveAllValues(CFBinaryHeapRef heap);
 310
 311 #if defined(__cplusplus)
 312 }
 313 #endif
 314
 315 #endif /* ! __COREFOUNDATION_CFBINARYHEAP__ */
 316