Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
bitset.h
Go to the documentation of this file.
1 #ifndef BITSET_H
2 #define BITSET_H
3 
4 #include <stdint.h>
5 
6 namespace frechet { namespace data {
7 
16 class BitSet {
17 private:
19  int _size;
21  int numWords;
23  uint64_t* bits;
24 
25 public:
27  BitSet();
30  BitSet(int asize);
33  BitSet(const BitSet& that);
34  //BitSet(BitSet&& that);
36  ~BitSet();
40  BitSet& operator= (const BitSet& that);
41  //BitSet& operator= (BitSet&& that);
45  BitSet& swap (BitSet& that);
46 
48  int size() const;
53  int count() const;
55  void clear();
56 
59  bool contains(int offset) const;
62  void add(int offset);
65  void remove(int offset);
66 
69  bool operator[] (int offset) const { return contains(offset); }
73  BitSet& operator+= (int offset) { add(offset); return *this; }
77  BitSet& operator-= (int offset) { remove(offset); return *this; }
78 
80  void add_lf(int offset);
82  void remove_lf(int offset);
83 
84 
93  class iterator {
94  public:
96  iterator();
99  iterator(const iterator& that);
100 
104  iterator& operator= (const iterator& that);
105 
109  bool operator== (const iterator& that) const;
110 
112  bool valid() const;
114  int operator* () const;
115 
118  iterator& operator++ (/*pre-increment*/);
121  iterator operator++ (int/*post-increment*/);
122 
125  iterator& operator-- (/*pre-decrement*/);
128  iterator operator-- (int/*post-decrement*/);
129 
133  iterator& operator+= (int n);
137  iterator operator+ (int n) const;
138 
142  iterator& operator-= (int n);
146  iterator operator- (int n);
147 
151  int operator- (const iterator& that);
152 
153  private:
154  friend class BitSet;
156  const BitSet* parent;
158  int _offset;
162  iterator(const BitSet* aparent,int start);
163  };
165  iterator begin() const;
167  iterator end() const { return iterator(this,_size); }
168 
170  iterator first() const { return begin(); }
172  iterator last() const {
173  iterator it = end();
174  if (it._offset > 0) --it;
175  return it;
176  }
177 
178 private:
181  void copyBits(const BitSet& that);
184  void stealBits(BitSet&& that);
185 
188  int next(int index) const;
191  int prev(int off) const;
192 
196  static int numberOfTrailingZeros(uint64_t word);
200  static int numberOfLeadingZeros(uint64_t word);
204  static int bitCount(uint64_t word);
210  static int64_t compare_and_swap(volatile int64_t* value, int64_t old_value, int64_t update_value);
211 };
212 
213 } } // namespace
214 
215 #endif // BITSET_H
~BitSet()
destructor, releases all data
Definition: bitset.cpp:33
an iterator over a BitSet
Definition: bitset.h:93
iterator & operator-=(int n)
skip operator
Definition: bitset.cpp:255
static int numberOfTrailingZeros(uint64_t word)
compute number of trailing zeros in a 64 bit word
Definition: bitset.cpp:313
BitSet & operator+=(int offset)
assign true
Definition: bitset.h:73
iterator begin() const
Definition: bitset.cpp:128
static int64_t compare_and_swap(volatile int64_t *value, int64_t old_value, int64_t update_value)
atomic compare-and-swap
Definition: bitset.cpp:298
global definitions for all algorithms.
iterator operator-(int n)
skip operator
Definition: bitset.cpp:261
int next(int index) const
find next index with a set (true) bit
Definition: bitset.cpp:151
iterator first() const
Definition: bitset.h:170
void remove(int offset)
assign false
Definition: bitset.cpp:83
iterator & operator+=(int n)
skip operator
Definition: bitset.cpp:243
iterator operator+(int n) const
skip operator
Definition: bitset.cpp:249
void stealBits(BitSet &&that)
steal data
Definition: bitset.cpp:144
int numWords
number of allocated words (1 word = 64 bits)
Definition: bitset.h:21
void clear()
assign false to all bits
Definition: bitset.cpp:67
uint64_t * bits
bit data
Definition: bitset.h:23
void remove_lf(int offset)
lock-free add operator; not used and not tested!
Definition: bitset.cpp:108
int prev(int off) const
find previos index with a set (true) bit
Definition: bitset.cpp:174
iterator last() const
Definition: bitset.h:172
bool contains(int offset) const
Definition: bitset.cpp:71
static int numberOfLeadingZeros(uint64_t word)
compute number of leading zeros in a 64 bit word
Definition: bitset.cpp:321
void add(int offset)
assign true
Definition: bitset.cpp:77
iterator & operator--()
pre-decrement; move to the previous set (true) bit
Definition: bitset.cpp:232
iterator end() const
Definition: bitset.h:167
int _offset
current offset
Definition: bitset.h:158
BitSet & operator=(const BitSet &that)
assigment operator
Definition: bitset.cpp:38
bool operator[](int offset) const
Definition: bitset.h:69
static int bitCount(uint64_t word)
compute number of set bits in a 64 bit word
Definition: bitset.cpp:329
void copyBits(const BitSet &that)
copy data
Definition: bitset.cpp:130
iterator()
empty constructor; creates an invalid iterator
Definition: bitset.cpp:196
A simple bit vector of fixed size.
Definition: bitset.h:16
BitSet()
default constructor; creates an empty set
Definition: bitset.cpp:11
iterator & operator=(const iterator &that)
assignment operator
Definition: bitset.cpp:200
BitSet & swap(BitSet &that)
swap contents with other object
Definition: bitset.cpp:44
int _size
number of valid bits
Definition: bitset.h:19
bool operator==(const iterator &that) const
equality comparator
Definition: bitset.cpp:206
int count() const
This methods is expensive, as it scans the whole array.
Definition: bitset.cpp:58
void add_lf(int offset)
lock-free add operator; not used and not tested!
Definition: bitset.cpp:89
int size() const
Definition: bitset.cpp:56
const BitSet * parent
parent BitSet
Definition: bitset.h:156
BitSet & operator-=(int offset)
assign false
Definition: bitset.h:77
iterator & operator++()
pre-increment; move to the next set (true) bit
Definition: bitset.cpp:221