A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
iterator_deletions.hpp
Go to the documentation of this file.
1 #ifndef GENESIS_UTILS_MATH_TWOBIT_VECTOR_ITERATOR_DELETIONS_H_
2 #define GENESIS_UTILS_MATH_TWOBIT_VECTOR_ITERATOR_DELETIONS_H_
3 
4 /*
5  Genesis - A toolkit for working with phylogenetic data.
6  Copyright (C) 2014-2018 Lucas Czech and HITS gGmbH
7 
8  This program is free software: you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation, either version 3 of the License, or
11  (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program. If not, see <http://www.gnu.org/licenses/>.
20 
21  Contact:
22  Lucas Czech <lucas.czech@h-its.org>
23  Exelixis Lab, Heidelberg Institute for Theoretical Studies
24  Schloss-Wolfsbrunnenweg 35, D-69118 Heidelberg, Germany
25 */
26 
37 
38 #include <assert.h>
39 #include <iterator>
40 
41 namespace genesis {
42 namespace utils {
43 
44 // =================================================================================================
45 // Iterator Deletions
46 // =================================================================================================
47 
52 {
53 public:
54 
55  // -----------------------------------------------------
56  // Typedefs
57  // -----------------------------------------------------
58 
59  using iterator_category = std::forward_iterator_tag;
62 
63  // -----------------------------------------------------
64  // Constructors and Rule of Five
65  // -----------------------------------------------------
66 
68  : origin_( nullptr )
69  , vec_()
70  , pos_( 0 )
71  , cur_( TwobitVector::ValueType::A )
72  , hash_( 0 )
73  {}
74 
76  : origin_( &vector )
77  , vec_( vector )
78  , pos_( 0 )
79  , cur_( vector[ 0 ] )
80  {
81  // Remove the first value (we stored it in the initializer),
82  // and do a first hash calculation. Later iterations will just update
83  // all of this.
84  vec_.remove_at( 0 );
85  hash_ = vec_.hash();
86  }
87 
88  ~IteratorDeletions() = default;
89 
90  IteratorDeletions( IteratorDeletions const& ) = default;
91  IteratorDeletions( IteratorDeletions&& ) = default;
92 
93  IteratorDeletions& operator= ( IteratorDeletions const& ) = default;
95 
96  // -----------------------------------------------------
97  // Operators
98  // -----------------------------------------------------
99 
101  {
102  return vec_;
103  }
104 
106  {
107  return &vec_;
108  }
109 
111  {
112  // Toy example:
113  // Original: ACGT
114  // CGT --> pos = 0, cur = A
115  // AGT --> pos = 1, cur = C
116  // ACT --> pos = 2, cur = G
117  // ACG --> pos = 3, cur = T
118 
119  // If we are not done yet:
120  if( pos_ < vec_.size() ) {
121  // We will swap the value at the current position. So first, get it.
122  auto tmp = vec_.get( pos_ );
123 
124  // Update the hash: Remove the current value, and store the new one.
125  hash_ ^= ((
126  static_cast< TwobitVector::WordType >( tmp ) ^
127  static_cast< TwobitVector::WordType >( cur_ )
128  ) << ( 2 * ( pos_ % TwobitVector::kValuesPerWord ))
129  );
130 
131  // Now do the swap and move to the next position, so that next time,
132  // we will swap the next value.
133  vec_.set( pos_, cur_ );
134  cur_ = tmp;
135  ++pos_;
136 
137  // If we are done, set everything to zero, so that the iterator
138  // is equal to the default-constructed end-iterator.
139  } else {
140  origin_ = nullptr;
141  vec_.clear();
142  pos_ = 0;
144  hash_ = 0;
145  }
146 
147  return *this;
148  }
149 
151  {
152  self_type tmp = *this;
153  ++(*this);
154  return tmp;
155  }
156 
157  bool operator == ( self_type const& other ) const
158  {
159  return ( origin_ == other.origin_ ) && ( pos_ == other.pos_ );
160  }
161 
162  bool operator != ( self_type const& other ) const
163  {
164  return !( other == *this );
165  }
166 
167  // -----------------------------------------------------
168  // Members
169  // -----------------------------------------------------
170 
174  size_t position() const
175  {
176  return pos_;
177  }
178 
183  {
184  return hash_;
185  }
186 
190  TwobitVector const& vector() const
191  {
192  return vec_;
193  }
194 
195 private:
196 
197  // Store the location of the original vector. This is mainly used for quickly checking
198  // whether two iterators refer to the same underlying vector.
199  // (We do not want to do a full vector equality check at each iteration.)
200  TwobitVector const* origin_;
201 
202  // The current vector, which always has a missing value (compared to the original vector).
203  TwobitVector vec_;
204 
205  // The position that is currently deleted.
206  size_t pos_;
207 
208  // The value that is currently deleted (need it to restore it later).
210 
211  // The hash value of the current vector.
213 
214 };
215 
216 // =================================================================================================
217 // Range Wrapper
218 // =================================================================================================
219 
221 {
222  return {
223  IteratorDeletions( vector ),
225  };
226 }
227 
228 } // namespace utils
229 } // namespace genesis
230 
231 #endif // include guard
TwobitVector const & vector() const
Get the current vector.
bool operator!=(self_type const &other) const
static const size_t kValuesPerWord
Constant that holds the number of values (of tyoe ValueType) that are stored in a single word in the ...
size_t size() const
Return the size of the vector, that is, how many values (of type ValueType) it currently holds...
size_t position() const
Get the position that is currently deleted.
void remove_at(size_t index)
Remove the value at a position.
Take a TwobitVector sequence and iterate over all possible deletions of its values.
uint64_t WordType
Underlying word type for the bitvector.
void set(size_t index, ValueType value)
Set a value at a position in the vector.
IteratorDeletions(TwobitVector const &vector)
utils::Range< IteratorDeletions > iterate_deletions(TwobitVector const &vector)
TwobitVector::WordType hash() const
Get the hash value of the current vector.
WordType hash() const
Calculate a hash value of the vector, based on its size() and the xor of all its words.
bool operator==(self_type const &other) const
void clear()
Clear the vector, so that it contains no data.
ValueType
Value Type enumeration for the elements of a TwobitVector.
IteratorDeletions & operator=(IteratorDeletions const &)=default
std::forward_iterator_tag iterator_category
ValueType get(size_t index) const
Get the value at a position in the vector.