HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
IndexSet.h
Go to the documentation of this file.
1 /* Copyright (C) 2012,2013 IBM Corp.
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 2 of the License, or
5  * (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10  * See the GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License along
13  * with this program; if not, write to the Free Software Foundation, Inc.,
14  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15  */
16 #ifndef _IndexSet
17 #define _IndexSet
18 
23 #include <vector>
24 #include <iostream>
25 #include <cassert>
26 
27 using namespace std;
28 
36 class IndexSet {
37 
38  vector<bool> rep;
39  // NOTE: modern versions of C++ are supposed
40  // to implement this efficiently as a "specialized template class".
41  // Older versions of C++ define the equivalent class bit_vector.
42 
43  long _first, _last, _card;
44 
45  // Invariant: if _card == 0, then _first = 0, _last = -1;
46  // otherwise, _first (resp. _last) is the lowest (resp. highest)
47  // index in the set.
48  // In any case, the vector rep always defines the characterstic
49  // function of the set.
50 
51  // private helper function
52  void intervalConstructor(long low, long high);
53 
54 public:
55 
56  /*** constructors ***/
57 
58  // @brief No-argument constructor, creates empty set
59  IndexSet() {
60  _first = 0; _last = -1; _card = 0;
61  }
62 
63  // @brief Constructs an interval, low to high
64  IndexSet(long low, long high) {
65  intervalConstructor(low, high);
66  }
67 
68  // @brief Constructs a singleton set
69  explicit
70  IndexSet(long j) {
71  intervalConstructor(j, j);
72  }
73 
74  // copy constructor: use the built-in copy constructor
75 
76  /*** asignment ***/
77 
78  // assignment: use the built-in assignment operator
79 
81  long first() const { return _first; }
82 
84  long last() const { return _last; }
85 
87  long next(long j) const;
88 
89  // @brief Returns the previous element before j, if any; otherwise j-1
90  long prev(long j) const;
91 
93  long card() const { return _card; }
94 
96  bool contains(long j) const;
97 
99  bool contains(const IndexSet& s) const;
100 
102  bool disjointFrom(const IndexSet& s) const;
103 
104  /*** comparison ***/
105 
106  bool operator==(const IndexSet& s) const;
107 
108  bool operator!=(const IndexSet& s) const {
109  return !(*this == s);
110  }
111 
112  /*** update methods ***/
113 
115  void clear();
116 
118  void insert(long j);
119 
121  void remove(long j);
122 
124  void insert(const IndexSet& s);
125 
127  void remove(const IndexSet& s);
128 
130  void retain(const IndexSet& s);
131 
133  static const IndexSet& emptySet();
134 };
135 
136 // some high-level convenience methods...not very efficient...
137 // not sure if we really need these
138 
140 IndexSet operator|(const IndexSet& s, const IndexSet& t);
141 
143 IndexSet operator&(const IndexSet& s, const IndexSet& t);
144 
146 IndexSet operator^(const IndexSet& s, const IndexSet& t);
147 
149 IndexSet operator/(const IndexSet& s, const IndexSet& t);
150 
151 // I/O operator
152 ostream& operator << (ostream& str, const IndexSet& set);
153 istream& operator >> (istream& str, IndexSet& set);
154 
156 long card(const IndexSet& s);
157 
158 inline bool empty(const IndexSet& s) { return s.card()==0; }
159 
161 bool operator<=(const IndexSet& s1, const IndexSet& s2);
162 
164 bool operator<(const IndexSet& s1, const IndexSet& s2);
165 
167 bool operator>=(const IndexSet& s1, const IndexSet& s2);
168 
170 bool operator>(const IndexSet& s1, const IndexSet& s2);
171 
173 inline bool disjoint(const IndexSet& s1, const IndexSet& s2)
174 { return s1.disjointFrom(s2); }
175 
176 #endif