gui: Fix behavior of print preview in psppire-output-window.
[pspp] / src / libpspp / range-set.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 /* Bitmap, implemented as a balanced binary tree.
18
19    Each operation has O(lg N) cost, where N is the number of
20    contiguous regions of 1-bits in the bitmap.  Also, a cache
21    reduces the second and subsequent containment tests within a
22    single contiguous region to O(1). */
23
24 #ifndef LIBPSPP_RANGE_SET_H
25 #define LIBPSPP_RANGE_SET_H
26
27 #include <stdbool.h>
28 #include "libpspp/bt.h"
29 #include "libpspp/cast.h"
30
31 /* A set of ranges. */
32 struct range_set
33   {
34     struct pool *pool;                  /* Pool for freeing range_set. */
35     struct bt bt;                       /* Tree of range_set_nodes. */
36
37     /* Cache. */
38     unsigned long int cache_start;      /* Start of region. */
39     unsigned long int cache_end;        /* One past end of region. */
40     bool cache_value;                   /* Is the region in the set? */
41   };
42
43 /* A node in the range set. */
44 struct range_set_node
45   {
46     struct bt_node bt_node;             /* Binary tree node. */
47     unsigned long int start;            /* Start of region. */
48     unsigned long int end;              /* One past end of region. */
49   };
50
51 struct range_set *range_set_create (void);
52 struct range_set *range_set_create_pool (struct pool *);
53 struct range_set *range_set_clone (const struct range_set *, struct pool *);
54 void range_set_destroy (struct range_set *);
55
56 void range_set_insert (struct range_set *,
57                        unsigned long int start, unsigned long int width);
58 void range_set_delete (struct range_set *,
59                        unsigned long int start, unsigned long int width);
60 bool range_set_allocate (struct range_set *, unsigned long int request,
61                          unsigned long int *start, unsigned long int *width);
62 bool range_set_allocate_fully (struct range_set *, unsigned long int request,
63                                unsigned long int *start);
64 bool range_set_contains (const struct range_set *, unsigned long int position);
65 unsigned long int range_set_scan (const struct range_set *,
66                                   unsigned long int start);
67
68 static inline bool range_set_is_empty (const struct range_set *);
69
70 static inline const struct range_set_node *range_set_first (
71   const struct range_set *);
72 static inline const struct range_set_node *range_set_next (
73   const struct range_set *, const struct range_set_node *);
74 static inline const struct range_set_node *range_set_last (
75   const struct range_set *);
76 static inline const struct range_set_node *range_set_prev (
77   const struct range_set *, const struct range_set_node *);
78 static inline unsigned long int range_set_node_get_start (
79   const struct range_set_node *);
80 static inline unsigned long int range_set_node_get_end (
81   const struct range_set_node *);
82 static inline unsigned long int range_set_node_get_width (
83   const struct range_set_node *);
84 \f
85 /* Inline functions. */
86
87 static inline struct range_set_node *range_set_node_from_bt__ (
88   const struct bt_node *);
89 static inline struct range_set_node *range_set_next__ (
90   const struct range_set *, const struct range_set_node *);
91 static inline struct range_set_node *range_set_first__ (
92   const struct range_set *);
93 static inline struct range_set_node *range_set_prev__ (
94   const struct range_set *, const struct range_set_node *);
95 static inline struct range_set_node *range_set_last__ (
96   const struct range_set *);
97
98 /* Returns true if RS contains no 1-bits, false otherwise. */
99 static inline bool
100 range_set_is_empty (const struct range_set *rs)
101 {
102   return bt_count (&rs->bt) == 0;
103 }
104
105 /* Returns the node representing the first contiguous region of
106    1-bits in RS, or a null pointer if RS is empty.
107    Any call to range_set_insert, range_set_delete, or
108    range_set_allocate invalidates the returned node. */
109 static inline const struct range_set_node *
110 range_set_first (const struct range_set *rs)
111 {
112   return range_set_first__ (rs);
113 }
114
115 /* If NODE is nonnull, returns the node representing the next
116    contiguous region of 1-bits in RS following NODE, or a null
117    pointer if NODE is the last region in RS.
118    If NODE is null, returns the first region in RS, as for
119    range_set_first.
120    Any call to range_set_insert, range_set_delete, or
121    range_set_allocate invalidates the returned node. */
122 static inline const struct range_set_node *
123 range_set_next (const struct range_set *rs, const struct range_set_node *node)
124 {
125   return (node != NULL
126           ? range_set_next__ (rs, CONST_CAST (struct range_set_node *, node))
127           : range_set_first__ (rs));
128 }
129
130 /* Returns the node representing the last contiguous region of
131    1-bits in RS, or a null pointer if RS is empty.
132    Any call to range_set_insert, range_set_delete, or
133    range_set_allocate invalidates the returned node. */
134 static inline const struct range_set_node *
135 range_set_last (const struct range_set *rs)
136 {
137   return range_set_last__ (rs);
138 }
139
140 /* If NODE is nonnull, returns the node representing the previous
141    contiguous region of 1-bits in RS following NODE, or a null
142    pointer if NODE is the first region in RS.
143    If NODE is null, returns the last region in RS, as for
144    range_set_last.
145    Any call to range_set_insert, range_set_delete, or
146    range_set_allocate invalidates the returned node. */
147 static inline const struct range_set_node *
148 range_set_prev (const struct range_set *rs, const struct range_set_node *node)
149 {
150   return (node != NULL
151           ? range_set_prev__ (rs, CONST_CAST (struct range_set_node *, node))
152           : range_set_last__ (rs));
153 }
154
155 /* Returns the position of the first 1-bit in NODE. */
156 static inline unsigned long int
157 range_set_node_get_start (const struct range_set_node *node)
158 {
159   return node->start;
160 }
161
162 /* Returns one past the position of the last 1-bit in NODE. */
163 static inline unsigned long int
164 range_set_node_get_end (const struct range_set_node *node)
165 {
166   return node->end;
167 }
168
169 /* Returns the number of contiguous 1-bits in NODE. */
170 static inline unsigned long int
171 range_set_node_get_width (const struct range_set_node *node)
172 {
173   return node->end - node->start;
174 }
175 \f
176 /* Internal helper functions. */
177
178 /* Returns the range_set_node corresponding to the given
179    BT_NODE.  Returns a null pointer if BT_NODE is null. */
180 static inline struct range_set_node *
181 range_set_node_from_bt__ (const struct bt_node *bt_node)
182 {
183   return bt_node ? bt_data (bt_node, struct range_set_node, bt_node) : NULL;
184 }
185
186 /* Returns the next range_set_node in RS after NODE,
187    or a null pointer if NODE is the last node in RS. */
188 static inline struct range_set_node *
189 range_set_next__ (const struct range_set *rs,
190                   const struct range_set_node *node)
191 {
192   return range_set_node_from_bt__ (bt_next (&rs->bt, &node->bt_node));
193 }
194
195 /* Returns the first range_set_node in RS,
196    or a null pointer if RS is empty. */
197 static inline struct range_set_node *
198 range_set_first__ (const struct range_set *rs)
199 {
200   return range_set_node_from_bt__ (bt_first (&rs->bt));
201 }
202
203 /* Returns the previous range_set_node in RS after NODE,
204    or a null pointer if NODE is the first node in RS. */
205 static inline struct range_set_node *
206 range_set_prev__ (const struct range_set *rs,
207                   const struct range_set_node *node)
208 {
209   return range_set_node_from_bt__ (bt_prev (&rs->bt, &node->bt_node));
210 }
211
212 /* Returns the last range_set_node in RS,
213    or a null pointer if RS is empty. */
214 static inline struct range_set_node *
215 range_set_last__ (const struct range_set *rs)
216 {
217   return range_set_node_from_bt__ (bt_last (&rs->bt));
218 }
219
220 #endif /* libpspp/range-set.h */