klee
MapOfSets.h
Go to the documentation of this file.
1//===-- MapOfSets.h ---------------------------------------------*- C++ -*-===//
2//
3// The KLEE Symbolic Virtual Machine
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef KLEE_MAPOFSETS_H
11#define KLEE_MAPOFSETS_H
12
13#include <cassert>
14#include <vector>
15#include <set>
16#include <map>
17
18// This should really be broken down into TreeOfSets on top of which
19// SetOfSets and MapOfSets are easily implemeted. It should also be
20// parameterized on the underlying set type. Neither are hard to do,
21// just not worth it at the moment.
22//
23// I also broke some STLish conventions because I was bored.
24
25namespace klee {
26
29 template<class K, class V>
30 class MapOfSets {
31 public:
32 class iterator;
33
34 public:
36
37 void clear();
38
39 void insert(const std::set<K> &set, const V &value);
40
41 V *lookup(const std::set<K> &set);
42
43 iterator begin();
44 iterator end();
45
46 void subsets(const std::set<K> &set,
47 std::vector< std::pair<std::set<K>, V> > &resultOut);
48 void supersets(const std::set<K> &set,
49 std::vector< std::pair<std::set<K>, V> > &resultOut);
50
51 template<class Predicate>
52 V *findSuperset(const std::set<K> &set, const Predicate &p);
53 template<class Predicate>
54 V *findSubset(const std::set<K> &set, const Predicate &p);
55
56 private:
57 class Node;
58
60
61 template<class Iterator, class Vector>
62 void findSubsets(Node *n,
63 const std::set<K> &accum,
64 Iterator begin,
65 Iterator end,
66 Vector &resultsOut);
67 template<class Iterator, class Vector>
68 void findSupersets(Node *n,
69 const std::set<K> &accum,
70 Iterator begin,
71 Iterator end,
72 Vector &resultsOut);
73 template<class Predicate>
74 V *findSuperset(Node *n,
75 typename std::set<K>::iterator begin,
76 typename std::set<K>::iterator end,
77 const Predicate &p);
78 template<class Predicate>
79 V *findSubset(Node *n,
80 typename std::set<K>::iterator begin,
81 typename std::set<K>::iterator end,
82 const Predicate &p);
83 };
84
85 /***/
86
87 template<class K, class V>
88 class MapOfSets<K,V>::Node {
89 friend class MapOfSets<K,V>;
90 friend class MapOfSets<K,V>::iterator;
91
92 public:
93 typedef std::map<K, Node> children_ty;
94
95 V value;
96
97 private:
98 bool isEndOfSet;
99 std::map<K, Node> children;
100
101 public:
102 Node() : value(), isEndOfSet(false) {}
103 };
104
105 template<class K, class V>
106 class MapOfSets<K,V>::iterator {
107 typedef std::vector< typename std::map<K, Node>::iterator > stack_ty;
108 friend class MapOfSets<K,V>;
109 private:
113
114 void step() {
115 if (onEntry) {
116 onEntry = false;
117 Node *n = stack.empty() ? root : &stack.back()->second;
118 while (!n->children.empty()) {
119 stack.push_back(n->children.begin());
120 n = &stack.back()->second;
121 if (n->isEndOfSet) {
122 onEntry = true;
123 return;
124 }
125 }
126 }
127
128 while (!stack.empty()) {
129 unsigned size = stack.size();
130 Node *at = size==1 ? root : &stack[size-2]->second;
131 typename std::map<K,Node>::iterator &cur = stack.back();
132 ++cur;
133 if (cur==at->children.end()) {
134 stack.pop_back();
135 } else {
136 Node *n = &cur->second;
137
138 while (!n->isEndOfSet) {
139 assert(!n->children.empty());
140 stack.push_back(n->children.begin());
141 n = &stack.back()->second;
142 }
143
144 onEntry = true;
145 break;
146 }
147 }
148 }
149
150 public:
151 // end()
152 iterator() : onEntry(false) {}
153 // begin()
154 iterator(Node *_n) : root(_n), onEntry(true) {
155 if (!root->isEndOfSet)
156 step();
157 }
158
159 const std::pair<const std::set<K>, const V> operator*() {
160 assert(onEntry || !stack.empty());
161 std::set<K> s;
162 for (typename stack_ty::iterator it = stack.begin(), ie = stack.end();
163 it != ie; ++it)
164 s.insert((*it)->first);
165 Node *n = stack.empty() ? root : &stack.back()->second;
166 return std::make_pair(s, n->value);
167 }
168
169 bool operator==(const iterator &b) {
170 return onEntry==b.onEntry && stack==b.stack;
171 }
172 bool operator!=(const iterator &b) {
173 return !(*this==b);
174 }
175
177 step();
178 return *this;
179 }
180 };
181
182 /***/
183
184 template<class K, class V>
186
187 template<class K, class V>
188 void MapOfSets<K,V>::insert(const std::set<K> &set, const V &value) {
189 Node *n = &root;
190 for (auto const& element : set) {
191 n = &n->children.insert(std::make_pair(element, Node())).first->second;
192 }
193 n->isEndOfSet = true;
194 n->value = value;
195 }
196
197 template<class K, class V>
198 V *MapOfSets<K,V>::lookup(const std::set<K> &set) {
199 Node *n = &root;
200 for (typename std::set<K>::const_iterator it = set.begin(), ie = set.end();
201 it != ie; ++it) {
202 typename Node::children_ty::iterator kit = n->children.find(*it);
203 if (kit==n->children.end()) {
204 return 0;
205 } else {
206 n = &kit->second;
207 }
208 }
209 if (n->isEndOfSet) {
210 return &n->value;
211 } else {
212 return 0;
213 }
214 }
215
216 template<class K, class V>
218 MapOfSets<K,V>::begin() { return iterator(&root); }
219
220 template<class K, class V>
223
224 template<class K, class V>
225 template<class Iterator, class Vector>
227 const std::set<K> &accum,
228 Iterator begin,
229 Iterator end,
230 Vector &resultsOut) {
231 if (n->isEndOfSet) {
232 resultsOut.push_back(std::make_pair(accum, n->value));
233 }
234
235 for (Iterator it=begin; it!=end;) {
236 K elt = *it;
237 typename Node::children_ty::iterator kit = n->children.find(elt);
238 it++;
239 if (kit!=n->children.end()) {
240 std::set<K> nacc = accum;
241 nacc.insert(elt);
242 findSubsets(&kit->second, nacc, it, end, resultsOut);
243 }
244 }
245 }
246
247 template<class K, class V>
248 void MapOfSets<K,V>::subsets(const std::set<K> &set,
249 std::vector< std::pair<std::set<K>,
250 V> > &resultOut) {
251 findSubsets(&root, std::set<K>(), set.begin(), set.end(), resultOut);
252 }
253
254 template<class K, class V>
255 template<class Iterator, class Vector>
257 const std::set<K> &accum,
258 Iterator begin,
259 Iterator end,
260 Vector &resultsOut) {
261 if (begin==end) {
262 if (n->isEndOfSet)
263 resultsOut.push_back(std::make_pair(accum, n->value));
264 for (typename Node::children_ty::iterator it = n->children.begin(),
265 ie = n->children.end(); it != ie; ++it) {
266 std::set<K> nacc = accum;
267 nacc.insert(it->first);
268 findSupersets(&it->second, nacc, begin, end, resultsOut);
269 }
270 } else {
271 K elt = *begin;
272 Iterator next = begin;
273 ++next;
274 for (typename Node::children_ty::iterator it = n->children.begin(),
275 ie = n->children.end(); it != ie; ++it) {
276 std::set<K> nacc = accum;
277 nacc.insert(it->first);
278 if (elt==it->first) {
279 findSupersets(&it->second, nacc, next, end, resultsOut);
280 } else if (it->first<elt) {
281 findSupersets(&it->second, nacc, begin, end, resultsOut);
282 } else {
283 break;
284 }
285 }
286 }
287 }
288
289 template<class K, class V>
290 void MapOfSets<K,V>::supersets(const std::set<K> &set,
291 std::vector< std::pair<std::set<K>, V> > &resultOut) {
292 findSupersets(&root, std::set<K>(), set.begin(), set.end(), resultOut);
293 }
294
295 template<class K, class V>
296 template<class Predicate>
298 typename std::set<K>::iterator begin,
299 typename std::set<K>::iterator end,
300 const Predicate &p) {
301 if (n->isEndOfSet && p(n->value)) {
302 return &n->value;
303 } else if (begin==end) {
304 return 0;
305 } else {
306 typename Node::children_ty::iterator kend = n->children.end();
307 typename Node::children_ty::iterator
308 kbegin = n->children.lower_bound(*begin);
309 typename std::set<K>::iterator it = begin;
310 if (kbegin==kend)
311 return 0;
312 for (;;) { // kbegin!=kend && *it <= kbegin->first
313 while (*it < kbegin->first) {
314 ++it;
315 if (it==end)
316 return 0;
317 }
318 if (*it == kbegin->first) {
319 ++it;
320 V *res = findSubset(&kbegin->second, it, end, p);
321 if (res || it==end)
322 return res;
323 }
324 while (kbegin->first < *it) {
325 ++kbegin;
326 if (kbegin==kend)
327 return 0;
328 }
329 }
330 }
331 }
332
333 template<class K, class V>
334 template<class Predicate>
336 typename std::set<K>::iterator begin,
337 typename std::set<K>::iterator end,
338 const Predicate &p) {
339 if (begin==end) {
340 if (n->isEndOfSet && p(n->value))
341 return &n->value;
342 for (typename Node::children_ty::iterator it = n->children.begin(),
343 ie = n->children.end(); it != ie; ++it) {
344 V *res = findSuperset(&it->second, begin, end, p);
345 if (res) return res;
346 }
347 } else {
348 typename Node::children_ty::iterator kmid =
349 n->children.lower_bound(*begin);
350 for (typename Node::children_ty::iterator it = n->children.begin(),
351 ie = n->children.end(); it != ie; ++it) {
352 V *res = findSuperset(&it->second, begin, end, p);
353 if (res) return res;
354 }
355 if (kmid!=n->children.end() && *begin==kmid->first) {
356 V *res = findSuperset(&kmid->second, ++begin, end, p);
357 if (res) return res;
358 }
359 }
360 return 0;
361 }
362
363 template<class K, class V>
364 template<class Predicate>
365 V *MapOfSets<K,V>::findSuperset(const std::set<K> &set, const Predicate &p) {
366 return findSuperset(&root, set.begin(), set.end(), p);
367 }
368
369 template<class K, class V>
370 template<class Predicate>
371 V *MapOfSets<K,V>::findSubset(const std::set<K> &set, const Predicate &p) {
372 return findSubset(&root, set.begin(), set.end(), p);
373 }
374
375 template<class K, class V>
377 root.isEndOfSet = false;
378 root.value = V();
379 root.children.clear();
380 }
381
382}
383
384#endif /* KLEE_MAPOFSETS_H */
std::map< K, Node > children
Definition: MapOfSets.h:99
std::map< K, Node > children_ty
Definition: MapOfSets.h:93
const std::pair< const std::set< K >, const V > operator*()
Definition: MapOfSets.h:159
iterator & operator++()
Definition: MapOfSets.h:176
std::vector< typename std::map< K, Node >::iterator > stack_ty
Definition: MapOfSets.h:107
bool operator==(const iterator &b)
Definition: MapOfSets.h:169
bool operator!=(const iterator &b)
Definition: MapOfSets.h:172
iterator begin()
Definition: MapOfSets.h:218
V * lookup(const std::set< K > &set)
Definition: MapOfSets.h:198
V * findSuperset(const std::set< K > &set, const Predicate &p)
Definition: MapOfSets.h:365
V * findSuperset(Node *n, typename std::set< K >::iterator begin, typename std::set< K >::iterator end, const Predicate &p)
Definition: MapOfSets.h:335
void findSubsets(Node *n, const std::set< K > &accum, Iterator begin, Iterator end, Vector &resultsOut)
Definition: MapOfSets.h:226
void insert(const std::set< K > &set, const V &value)
Definition: MapOfSets.h:188
iterator end()
Definition: MapOfSets.h:222
V * findSubset(Node *n, typename std::set< K >::iterator begin, typename std::set< K >::iterator end, const Predicate &p)
Definition: MapOfSets.h:297
V * findSubset(const std::set< K > &set, const Predicate &p)
Definition: MapOfSets.h:371
void supersets(const std::set< K > &set, std::vector< std::pair< std::set< K >, V > > &resultOut)
Definition: MapOfSets.h:290
void subsets(const std::set< K > &set, std::vector< std::pair< std::set< K >, V > > &resultOut)
Definition: MapOfSets.h:248
void findSupersets(Node *n, const std::set< K > &accum, Iterator begin, Iterator end, Vector &resultsOut)
Definition: MapOfSets.h:256
Definition: main.cpp:291