1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
////////////////////////////////////////////////////////////////////////////////
//
// CompressedIntegerSet.hh
//
// produced: 21/08/97 jr
// last change: 24/01/99 jr
//
////////////////////////////////////////////////////////////////////////////////
#ifndef COMPRESSEDINTEGERSET_HH
#define COMPRESSEDINTEGERSET_HH
#include <stdlib.h>
#include <memory>
#include "Global.hh"
#include "IntegerSet.hh"
namespace topcom {
#ifndef STL_CONTAINERS
#include "PlainArray.hh"
#include "Array.hh"
typedef Array<block> compressed_type;
#else
#include <vector>
#include "ContainerIO.hh"
typedef std::vector<block_type> compressed_type;
#endif
class __cis_const_iterator; // same as for IntegerSet
class CompressedIntegerSet {
protected:
static unsigned char _S_first_one[256];
private:
IntegerSet _non_zero; // contains positions of non-zero blocks
compressed_type _compressed; // contains the non-zero blocks
public:
// constructors:
CompressedIntegerSet();
CompressedIntegerSet(const CompressedIntegerSet&);
CompressedIntegerSet(const IntegerSet&);
// assignment:
CompressedIntegerSet& operator=(const CompressedIntegerSet&);
// conversion:
operator IntegerSet() const;
// interface wrapper of an IntegerSet in order to make compression transparent:
CompressedIntegerSet(const SparseIntegerSet&); // constructor for SparseIntegerSet
CompressedIntegerSet(const size_type, const size_type); // constructor set containing the given range
CompressedIntegerSet(const size_type elem); // constructor for one-element set
CompressedIntegerSet(const size_type len, const size_type* init); // constructor with given integer array
#ifndef STL_CONTAINERS
CompressedIntegerSet(const Array<size_type>&); // constructor with given Array of integers
CompressedIntegerSet(const PlainArray<size_type>&); // constructor with given PlainArray of integers
#endif
// destructor:
~CompressedIntegerSet(); // destructor
// keys for containers:
const size_type keysize() const;
const size_type key(size_type n) const;
// accessors:
const IntegerSet& non_zero() const;
const compressed_type& compressed() const;
// functions:
const size_type card() const; // cardinality
// boolean functions:
const bool contains(const size_type) const; // membership
const bool superset(const CompressedIntegerSet&) const; // superset relation
const bool subset(const CompressedIntegerSet&) const; // subset relation
const bool disjoint(const CompressedIntegerSet&) const; // disjoint relation
const bool empty() const; // test for empty set
// iterators:
friend class __cis_const_iterator; // same as for IntegerSet
typedef __cis_const_iterator const_iterator;
typedef const_iterator iterator; // no non-const iterators
// iterator functions:
const_iterator begin() const; // iterator on first element
const_iterator end() const; // iterator past last element
const_iterator find(const size_type elem) const; // iterator pointing to elem
// boolean operators:
const bool operator==(const CompressedIntegerSet&) const; // equality
const bool operator!=(const CompressedIntegerSet&) const; // non-equality
const bool operator<(const CompressedIntegerSet&) const; // order on intsets
const bool operator>(const CompressedIntegerSet&) const; // reversed order
const size_type operator[](const size_type) const; // pseudo-random-access
CompressedIntegerSet& clear(); // erase all
CompressedIntegerSet& fill(const size_type, const size_type); // fill in elements from start to stop
// adding and deleting an element:
CompressedIntegerSet& operator+=(const size_type); // add integer
CompressedIntegerSet& operator-=(const size_type); // delete integer
CompressedIntegerSet& operator^=(const size_type); // add if not contained/delete if contained
// union, difference, and intersection with sets:
CompressedIntegerSet& operator+=(const CompressedIntegerSet&); // union
CompressedIntegerSet& operator-=(const CompressedIntegerSet&); // difference
CompressedIntegerSet& operator*=(const CompressedIntegerSet&); // intersection
CompressedIntegerSet& operator^=(const CompressedIntegerSet&); // symmetric difference
// the same but a new set is returned:
CompressedIntegerSet operator+(const size_type) const; // add integer
CompressedIntegerSet operator-(const size_type) const; // delete integer
CompressedIntegerSet operator+(const CompressedIntegerSet&) const; // union
CompressedIntegerSet operator-(const CompressedIntegerSet&) const; // difference
CompressedIntegerSet operator*(const CompressedIntegerSet&) const; // intersection
CompressedIntegerSet operator^(const CompressedIntegerSet&) const; // symmetric difference
// returns the cardinalities
// 0, 1, or 2 (2 or more) of
// the intersection of several CompressedIntegerSet's:
const size_type intersection_card(const CompressedIntegerSet**,
const size_type,
size_type&) const;
const size_type intersection_nonempty(const CompressedIntegerSet**,
const size_type,
size_type&) const;
// iostream:
std::istream& read(std::istream&);
std::ostream& write(std::ostream&) const;
friend std::istream& operator>>(std::istream& ist, CompressedIntegerSet& is) {
return is.read(ist);
}
friend std::ostream& operator<<(std::ostream& ost, const CompressedIntegerSet& is) {
return is.write(ost);
}
private:
// internal functions:
void _compactify();
};
class __cis_const_iterator {
friend class CompressedIntegerSet;
private:
const CompressedIntegerSet* _container;
size_type _current_non_zero;
size_type _current_block;
size_type _current_bit;
public:
__cis_const_iterator();
__cis_const_iterator(const __cis_const_iterator& iter);
__cis_const_iterator(const CompressedIntegerSet& s);
__cis_const_iterator(const CompressedIntegerSet& s, int);
private:
__cis_const_iterator(const CompressedIntegerSet& s,
const size_type current_non_zero,
const size_type current_block,
const size_type current_bit);
public:
~__cis_const_iterator();
__cis_const_iterator& operator=(const __cis_const_iterator& iter);
const bool valid() const;
const bool operator==(const __cis_const_iterator&) const;
const bool operator!=(const __cis_const_iterator&) const;
const size_type operator*() const;
__cis_const_iterator& operator++();
__cis_const_iterator operator++(int);
};
}; // namespace topcom
#endif
// eof CompressedIntegerSet.hh
|
