src/libpspp/heap.h

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU General Public License as
   6    published by the Free Software Foundation; either version 2 of the
   7    License, or (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful, but
  10    WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17    02110-1301, USA. */
  18
  19 /* Embedded priority queue, implemented as a heap.
  20
  21    Operations have the following cost, where N is the number of
  22    nodes already in the heap:
  23
  24         - Insert: O(lg N).
  25
  26         - Find minimum: O(1).
  27
  28         - Delete any node in the heap: O(lg N).
  29
  30         - Change value of an node: O(lg N) in general; O(1) in
  31           the typically common case where the node does not
  32           change its position relative to other nodes.
  33
  34         - Search for a node: O(N).  (Not implemented; if you need
  35           such a routine, use a different data structure or
  36           maintain a separate index.)
  37
  38    A heap data structure is structured as a packed array.  If an
  39    array is a natural data structure for your application, then
  40    use the push_heap, pop_heap, make_heap, sort_heap, and is_heap
  41    functions declared in libpspp/array.h.  Otherwise, if your
  42    data structure is more dynamic, this implementation may be
  43    easier to use.
  44
  45    An embedded heap is represented as `struct heap'.  Each node
  46    in the heap, presumably a structure type, must include a
  47    `struct heap_node' member.
  48
  49    Here's an example of a structure type that includes a `struct
  50    heap_node':
  51
  52      struct foo
  53        {
  54          struct heap_node node;   // Heap node member.
  55          int x;                   // Another member.
  56        };
  57
  58    Here's an example of how to find the minimum value in such a
  59    heap and delete it:
  60
  61      struct heap *h = ...;
  62      if (!heap_is_empty (h))
  63        {
  64          struct foo *foo = heap_data (heap_minimum (h), struct foo, node);
  65          printf ("Minimum is %d.\n", foo->x);
  66          heap_delete (h, &foo->node);
  67        }
  68      else
  69        printf ("Heap is empty.\n");
  70 */
  71
  72 #ifndef LIBPSPP_HEAP_H
  73 #define LIBPSPP_HEAP_H 1
  74
  75 #include <stdbool.h>
  76 #include <stddef.h>
  77
  78 struct pool;
  79
  80 /* Returns the data structure corresponding to the given heap
  81    NODE, assuming that NODE is embedded as the given MEMBER name
  82    in data type STRUCT. */
  83 #define heap_data(NODE, STRUCT, MEMBER)                                 \
  84         ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
  85
  86 /* A node in a heap.  Opaque.
  87    One of these structures must be embedded in your heap node. */
  88 struct heap_node
  89   {
  90     size_t idx;
  91   };
  92
  93 /* Returns negative if A < B, zero if A == B, positive if A > B. */
  94 typedef int heap_compare_func (const struct heap_node *a,
  95                                const struct heap_node *b, const void *aux);
  96
  97 struct heap *heap_create (heap_compare_func *, const void *aux);
  98 struct heap *heap_create_pool (struct pool *,
  99                                heap_compare_func *, const void *aux);
 100 void heap_destroy (struct heap *);
 101 bool heap_is_empty (const struct heap *);
 102 size_t heap_count (const struct heap *);
 103 void heap_moved (struct heap *, struct heap_node *);
 104 struct heap_node *heap_minimum (const struct heap *);
 105 void heap_insert (struct heap *, struct heap_node *);
 106 void heap_delete (struct heap *, struct heap_node *);
 107 void heap_changed (struct heap *, struct heap_node *);
 108
 109 #endif /* libpspp/heap.h */