gui: Allow File|Open to select an encoding for system files.
[pspp] / src / libpspp / heap.h
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, either version 3 of the License, or
7    (at your option) any later version.
8
9    This program is distributed in the hope that it will be useful,
10    but WITHOUT ANY WARRANTY; without even the implied warranty of
11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12    GNU 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, see <http://www.gnu.org/licenses/>. */
16
17 /* Embedded priority queue, implemented as a heap.
18
19    Operations have the following cost, where N is the number of
20    nodes already in the heap:
21
22         - Insert: O(lg N).
23
24         - Find minimum: O(1).
25
26         - Delete any node in the heap: O(lg N).
27
28         - Change value of an node: O(lg N) in general; O(1) in
29           the typically common case where the node does not
30           change its position relative to other nodes.
31
32         - Search for a node: O(N).  (Not implemented; if you need
33           such a routine, use a different data structure or
34           maintain a separate index.)
35
36    A heap data structure is structured as a packed array.  If an
37    array is a natural data structure for your application, then
38    use the push_heap, pop_heap, make_heap, sort_heap, and is_heap
39    functions declared in libpspp/array.h.  Otherwise, if your
40    data structure is more dynamic, this implementation may be
41    easier to use.
42
43    An embedded heap is represented as `struct heap'.  Each node
44    in the heap, presumably a structure type, must include a
45    `struct heap_node' member.
46
47    Here's an example of a structure type that includes a `struct
48    heap_node':
49
50      struct foo
51        {
52          struct heap_node node;   // Heap node member.
53          int x;                   // Another member.
54        };
55
56    Here's an example of how to find the minimum value in such a
57    heap and delete it:
58
59      struct heap *h = ...;
60      if (!heap_is_empty (h))
61        {
62          struct foo *foo = heap_data (heap_minimum (h), struct foo, node);
63          printf ("Minimum is %d.\n", foo->x);
64          heap_delete (h, &foo->node);
65        }
66      else
67        printf ("Heap is empty.\n");
68 */
69
70 #ifndef LIBPSPP_HEAP_H
71 #define LIBPSPP_HEAP_H 1
72
73 #include "libpspp/cast.h"
74 #include <stdbool.h>
75 #include <stddef.h>
76
77 struct pool;
78
79 /* Returns the data structure corresponding to the given heap
80    NODE, assuming that NODE is embedded as the given MEMBER name
81    in data type STRUCT. */
82 #define heap_data(NODE, STRUCT, MEMBER)                         \
83         (CHECK_POINTER_HAS_TYPE (NODE, struct heap_node *),     \
84          UP_CAST (NODE, 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 */