SheafSystem  0.0.0.0
int_set.cc
1 
2 //
3 // Copyright (c) 2014 Limit Point Systems, Inc.
4 //
5 // Licensed under the Apache License, Version 2.0 (the "License");
6 // you may not use this file except in compliance with the License.
7 // You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
17 
18 // Implementation for class int_set
19 
20 #include "SheafSystem/int_set.h"
21 #include "SheafSystem/assert_contract.h"
22 #include "SheafSystem/subposet.h"
23 #include "SheafSystem/index_iterator.h"
24 #include "SheafSystem/std_iostream.h"
25 #include "SheafSystem/std_algorithm.h"
26 
27 using namespace std;
28 
32 {
33 
34  // Preconditions:
35 
36 
37  // Body:
38 
39 
40  // Postconditions:
41 
42 }
43 
44 
47 int_set(const int_set& other)
48  : set<int>(other)
49 {
50 
51  // Preconditions:
52 
53 
54  // Body:
55 
56 
57  // Postconditions:
58 
59 }
60 
61 
64 int_set(const int* xmbrs, int xct)
65 {
66 
67  // Preconditions:
68 
69  require(xmbrs != 0);
70  require(xct > 0);
71 
72 
73  // Body:
74 
75  for(int i=0;i<xct;i++)
76  {
77  insert(xmbrs[i]);
78  }
79 
80  // Postconditions:
81 
82  ensure(unexecutable("for all i in xmbrs: this find(i) != end()"));
83 
84  // Exit:
85 
86  return;
87 }
88 
89 
93 {
94 
95  // Preconditions:
96 
97 
98  // Body:
99 
100 
101  // Postconditions:
102 
103 }
104 
106 void
108 insert_members(const int* xmbrs, int xct)
109 {
110 
111  // Preconditions:
112 
113  require(xmbrs != 0);
114  require(xct > 0);
115 
116 
117  // Body:
118 
119  for(int i=0;i<xct;i++)
120  {
121  insert(xmbrs[i]);
122  }
123 
124  // Postconditions:
125 
126  ensure(unexecutable("for all i in xmbrs: this find(i) != end()")) ;
127 
128  // Exit:
129 
130  return;
131 }
132 
133 
135 void
138 {
139  // Preconditions:
140 
141  require(xmbrs != 0);
142 
143  // Body:
144 
146  while(!itr.is_done())
147  {
148  insert(itr.index().pod());
149 
150  itr.next();
151  }
152 
153  // Postconditions:
154 
155  ensure(unexecutable("for all i in xmbrs: this find(i) != end()"));
156 
157  // Exit:
158 
159  return;
160 }
161 
162 
163 
164 
165 
167 bool
170 {
171  bool result;
172 
173  // Preconditions:
174 
175  // Body:
176 
177  // true if size() == 1 , but
178  // size() is O(size()) performance, so
179  // ask the question in a more efficient way
180 
181  const_iterator itr = begin();
182  result = !empty() ? ++itr == end() : false;
183 
184 
185  // Postconditions:
186 
187  // Exit
188 
189  return result;
190 }
191 
192 
193 
194 
195 
196 
197 
199 bool
201 set_includes(const int_set* other, bool this_is_much_larger) const
202 {
203  bool result;
204 
205  // Preconditions:
206 
207  require(other != 0);
208 
209  // Body:
210 
211  if(this_is_much_larger)
212  {
213  int_set::const_iterator itr = other->begin();
214  int_set::const_iterator other_end = other->end();
215  int_set::const_iterator this_end = end();
216 
217  result = true;
218  while(result && itr != other_end)
219  {
220  result = (find(*itr) != this_end);
221  itr++;
222  }
223  }
224  else
225  {
226  result = includes(begin(), end(), other->begin(), other->end());
227  }
228 
229 
230  // Postconditions:
231 
232  // Exit
233 
234  return result;
235 }
236 
237 
238 
239 
240 
241 
242 
246 set_union(const int_set* other) const
247 {
248  int_set* result;
249 
250  // Preconditions:
251 
252  require(other != 0);
253 
254  // Body:
255 
256  result = new int_set;
257  set_union_pa(other, result);
258 
259  // Postconditions:
260 
261  ensure(result != 0);
262 
263  // Exit
264 
265  return result;
266 }
267 
268 
269 
270 
272 void
274 set_union_pa(const int_set* other, int_set* result) const
275 {
276 
277  // Preconditions:
278 
279  require(other != 0);
280  require(result != 0);
281 
282  // Body:
283 
284  ::set_union(begin(), end(), other->begin(), other->end(), inserter(*result, result->begin()));
285 
286  // Postconditions:
287 
288  // Exit
289 
290  return;
291 }
292 
293 
295 void
297 set_union_sa(const int_set* other)
298 {
299 
300  // Preconditions:
301 
302  require(other != 0);
303 
304  // Body:
305 
306  const_iterator oitr = other->begin();
307 
308  while(oitr != other->end())
309  {
310  insert(*oitr);
311  oitr++;
312  }
313 
314  // Postconditions:
315 
316  // Exit
317 
318  return;
319 }
320 
321 
322 
323 
324 
325 
329 set_intersection(const int_set* other) const
330 {
331  int_set* result;
332 
333  // Preconditions:
334 
335  require(other != 0);
336 
337  // Body:
338 
339  result = new int_set;
340  set_intersection_pa(other, result);
341 
342  // Postconditions:
343 
344  ensure(result != 0);
345 
346  // Exit
347 
348  return result;
349 }
350 
351 
352 
353 
355 void
357 set_intersection_pa(const int_set* other, int_set* result) const
358 {
359 
360  // Preconditions:
361 
362  require(other != 0);
363  require(result != 0);
364 
365  // Body:
366 
367  ::set_intersection(begin(), end(), other->begin(), other->end(), inserter(*result, result->begin()));
368 
369  // Postconditions:
370 
371  // Exit
372 
373  return;
374 }
375 
376 
378 void
381 {
382 
383  // Preconditions:
384 
385  require(other != 0);
386 
387  // Body:
388 
389 
390  iterator sitr = begin();
391  const_iterator oitr = other->begin();
392  iterator tmp;
393 
394 
395  int smbr, ombr;
396 
397  while(sitr != end() && oitr != other->end())
398  {
399  smbr = *sitr;
400  ombr = *oitr;
401 
402  if( smbr < ombr )
403  {
404  // erasing member that iterator points to
405  // invalidates iterator; increment past it first.
406  tmp = sitr;
407  sitr++;
408  erase(tmp);
409  }
410  else if( smbr == ombr )
411  {
412  sitr++;
413  oitr++;
414  }
415  else
416  {
417  oitr++;
418  }
419 
420  }
421 
422 
423  if(sitr != end())
424  erase(sitr, end());
425 
426  // Postconditions:
427 
428  // Exit
429 
430  return;
431 }
432 
433 
434 
435 
439 set_difference(const int_set* other) const
440 {
441  int_set* result;
442 
443  // Preconditions:
444 
445  require(other != 0);
446 
447  // Body:
448 
449  result = new int_set;
450  set_difference_pa(other, result);
451 
452  // Postconditions:
453 
454  ensure(result != 0);
455 
456  // Exit
457 
458  return result;
459 }
460 
461 
462 
463 
465 void
467 set_difference_pa(const int_set* other, int_set* result) const
468 {
469 
470  // Preconditions:
471 
472  require(other != 0);
473  require(result != 0);
474 
475  // Body:
476 
477  ::set_difference(begin(), end(), other->begin(), other->end(), inserter(*result, result->begin()));
478 
479  // Postconditions:
480 
481  // Exit
482 
483  return;
484 }
485 
486 
488 void
490 set_difference_sa(int_set* other, bool this_is_much_larger)
491 {
492 
493  // Preconditions:
494 
495  require(other != 0);
496 
497  // Body:
498 
499 
500  iterator sitr = begin();
501  iterator oitr = other->begin();
502  iterator tmp;
503 
504  if(this_is_much_larger)
505  {
506  // This algorithm has performance other->size()*log(size())
507  // Faster than below if this is much larger than other
508  while(oitr != other->end())
509  {
510  erase(*oitr);
511  oitr++;
512  }
513  }
514  else
515  {
516  // This algorithm has performance other->size() + size();
517  // faster than above if other->size() is comparable to size().
518 
519  int smbr, ombr;
520 
521  while(sitr != end() && oitr != other->end())
522  {
523  smbr = *sitr;
524  ombr = *oitr;
525 
526  if( smbr < ombr )
527  {
528  sitr++;
529  }
530  else if( smbr == ombr )
531  {
532  // Erasing member that iterator points to
533  // invalidates iterator; increment past it first.
534 
535  tmp = sitr;
536  sitr++;
537  erase(tmp);
538  oitr++;
539  }
540  else
541  {
542  oitr++;
543  }
544 
545  }
546  }
547 
548  // Postconditions:
549 
550  // Exit
551 
552  return;
553 }
554 
555 
556 
557 
559 void
561 print() const
562 {
563  cout << *this;
564 }
565 
566 
567 
568 
569 // Non-member functions
570 
571 
572 
573 
574 std::ostream &
575 sheaf::
576 operator << (std::ostream &os, const int_set& c)
577 {
578  copy(c.begin(), c.end(), ostream_iterator<int>(os, " "));
579  return os;
580 }
void set_intersection_sa(const int_set *other)
Intersection of this with other, self-allocated version.
Definition: int_set.cc:380
An STL set representation for a set of integers.
Definition: int_set.h:47
A client handle for a subposet.
Definition: subposet.h:86
~int_set()
Destructor.
Definition: int_set.cc:92
const pod_type & pod() const
The "plain old data" storage of this; the value in the external id space.
Definition: scoped_index.h:672
void set_union_sa(const int_set *other)
union of this with other, self-allocated version.
Definition: int_set.cc:297
bool is_singleton() const
True if set contains only a single member.
Definition: int_set.cc:169
const scoped_index & index() const
The current item in the subset.
bool set_includes(const int_set *other, bool this_is_much_larger=false) const
True if this cover set includes other; If this_is_much_larger then assume this cover set is much larg...
Definition: int_set.cc:201
STL namespace.
void next()
Makes item the next member of the subset.
void print() const
Prints membership to cout. Intended for debugging.
Definition: int_set.cc:561
int_set * set_intersection(const int_set *other) const
Intersection of this with other, auto-allocated version.
Definition: int_set.cc:329
void set_union_pa(const int_set *other, int_set *result) const
union of this with other, pre-allocated version.
Definition: int_set.cc:274
int_set * set_union(const int_set *other) const
union of this with other, auto-allocated version.
Definition: int_set.cc:246
int_set * set_difference(const int_set *other) const
Difference of this and other (this minus other), auto-allocated version. If this_is_much_larger then ...
Definition: int_set.cc:439
void set_intersection_pa(const int_set *other, int_set *result) const
Intersection of this with other, pre-allocated version.
Definition: int_set.cc:357
void set_difference_sa(int_set *other, bool this_is_much_larger=false)
Difference of this and other (this minus other), self-allocated version. If this_is_much_larger then ...
Definition: int_set.cc:490
Iterates over the subset of Zn defined by the characteristic function host().
void set_difference_pa(const int_set *other, int_set *result) const
Difference of this and other (this minus other), pre-allocated version. If this_is_much_larger then a...
Definition: int_set.cc:467
bool is_done() const
True if iteration finished.
SHEAF_DLL_SPEC std::ostream & operator<<(std::ostream &os, const dof_descriptor_array &p)
Insert dof_descriptor_array& p into ostream& os.
void insert_members(const int *xmbrs, int xct)
Insert the members with indices in xmbrs.
Definition: int_set.cc:108
int_set()
Default constructor.
Definition: int_set.cc:31
virtual index_iterator indexed_member_iterator() const
An iterator for members of this poset; index version.
Definition: subposet.cc:934