1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
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.
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.
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
19 /* Embedded priority queue, implemented as a heap.
21 Operations have the following cost, where N is the number of
22 nodes already in the heap:
28 - Delete any node in the heap: O(lg N).
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.
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.)
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
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.
49 Here's an example of a structure type that includes a `struct
54 struct heap_node node; // Heap node member.
55 int x; // Another member.
58 Here's an example of how to find the minimum value in such a
62 if (!heap_is_empty (h))
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);
69 printf ("Heap is empty.\n");
72 #ifndef LIBPSPP_HEAP_H
73 #define LIBPSPP_HEAP_H 1
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)))
86 /* A node in a heap. Opaque.
87 One of these structures must be embedded in your heap node. */
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);
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 *);
109 #endif /* libpspp/heap.h */