klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 __UTIL_MAPOFSETS_H__
11 #define __UTIL_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 
25 namespace klee {
26 
29  template<class K, class V>
30  class MapOfSets {
31  public:
32  class iterator;
33 
34  public:
35  MapOfSets();
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 
59  Node root;
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() : 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:
111  bool onEntry;
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 (typename std::set<K>::const_iterator it = set.begin(), ie = set.end();
191  it != ie; ++it)
192  n = &n->children.insert(std::make_pair(*it, Node())).first->second;
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>
217  typename MapOfSets<K,V>::iterator
218  MapOfSets<K,V>::begin() { return iterator(&root); }
219 
220  template<class K, class V>
221  typename MapOfSets<K,V>::iterator
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
std::vector< typename std::map< K, Node >::iterator > stack_ty
Definition: MapOfSets.h:107
iterator end()
Definition: MapOfSets.h:222
std::map< K, Node > children_ty
Definition: MapOfSets.h:93
void supersets(const std::set< K > &set, std::vector< std::pair< std::set< K >, V > > &resultOut)
Definition: MapOfSets.h:290
void insert(const std::set< K > &set, const V &value)
Definition: MapOfSets.h:188
iterator & operator++()
Definition: MapOfSets.h:176
bool operator!=(const iterator &b)
Definition: MapOfSets.h:172
V * findSubset(const std::set< K > &set, const Predicate &p)
Definition: MapOfSets.h:371
V * findSuperset(const std::set< K > &set, const Predicate &p)
Definition: MapOfSets.h:365
bool operator==(const iterator &b)
Definition: MapOfSets.h:169
V * lookup(const std::set< K > &set)
Definition: MapOfSets.h:198
void findSubsets(Node *n, const std::set< K > &accum, Iterator begin, Iterator end, Vector &resultsOut)
Definition: MapOfSets.h:226
const std::pair< const std::set< K >, const V > operator*()
Definition: MapOfSets.h:159
void subsets(const std::set< K > &set, std::vector< std::pair< std::set< K >, V > > &resultOut)
Definition: MapOfSets.h:248
std::map< K, Node > children
Definition: MapOfSets.h:99
void findSupersets(Node *n, const std::set< K > &accum, Iterator begin, Iterator end, Vector &resultsOut)
Definition: MapOfSets.h:256
iterator begin()
Definition: MapOfSets.h:218