A library for working with phylogenetic and population genetic data.
v0.32.0
utils/math/bitvector/operators.cpp
Go to the documentation of this file.
1 /*
2  Genesis - A toolkit for working with phylogenetic data.
3  Copyright (C) 2014-2022 Lucas Czech
4 
5  This program is free software: you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation, either version 3 of the License, or
8  (at your option) any later version.
9 
10  This program is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU General Public License for more details.
14 
15  You should have received a copy of the GNU General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  Contact:
19  Lucas Czech <lczech@carnegiescience.edu>
20  Department of Plant Biology, Carnegie Institution For Science
21  260 Panama Street, Stanford, CA 94305, USA
22 */
23 
32 
33 #include <cassert>
34 #include <iostream>
35 #include <stdexcept>
36 #include <string>
37 
38 namespace genesis {
39 namespace utils {
40 
41 // =================================================================================================
42 // Bitvector Operators
43 // =================================================================================================
44 
45 Bitvector bitwise_and( Bitvector const& lhs, Bitvector const& rhs, bool use_larger )
46 {
47  if(( use_larger ) ^ ( lhs.size() < rhs.size() )) {
48  auto result = Bitvector( lhs.size(), rhs );
49  result &= lhs;
50  return result;
51  } else {
52  auto result = Bitvector( rhs.size(), lhs );
53  result &= rhs;
54  return result;
55  }
56 }
57 
58 Bitvector bitwise_or( Bitvector const& lhs, Bitvector const& rhs, bool use_larger )
59 {
60  if(( use_larger ) ^ ( lhs.size() < rhs.size() )) {
61  auto result = Bitvector( lhs.size(), rhs );
62  result |= lhs;
63  return result;
64  } else {
65  auto result = Bitvector( rhs.size(), lhs );
66  result |= rhs;
67  return result;
68  }
69 }
70 
71 Bitvector bitwise_xor( Bitvector const& lhs, Bitvector const& rhs, bool use_larger )
72 {
73  if(( use_larger ) ^ ( lhs.size() < rhs.size() )) {
74  auto result = Bitvector( lhs.size(), rhs );
75  result ^= lhs;
76  return result;
77  } else {
78  auto result = Bitvector( rhs.size(), lhs );
79  result ^= rhs;
80  return result;
81  }
82 }
83 
84 Bitvector set_minus( Bitvector const& lhs, Bitvector const& rhs )
85 {
86  return lhs & (~rhs);
87 }
88 
90 {
91  return (lhs | rhs) & ~(lhs & rhs);
92 }
93 
94 bool is_strict_subset( Bitvector const& sub, Bitvector const& super )
95 {
96  // Not really efficient. We could stop early in the comparison instead.
97  // But as of now, we do not need the speed, so let's keep it simple instead.
98  // Same for the other variants of this function below.
99  return ((sub & super) == sub) && (sub.count() < super.count());
100 }
101 
102 bool is_strict_superset( Bitvector const& super, Bitvector const& sub )
103 {
104  return is_strict_subset( sub, super );
105 }
106 
107 bool is_subset( Bitvector const& sub, Bitvector const& super )
108 {
109  return (sub == super) || is_strict_subset(sub, super);
110 }
111 
112 bool is_superset( Bitvector const& super, Bitvector const& sub )
113 {
114  return (super == sub) || is_strict_superset(super, sub);
115 }
116 
117 // bool lexicographically_compare_helper_( Bitvector const& lhs, Bitvector const& rhs, bool on_equal )
118 // {
119 // // Deactivated at the moment, as this does not take care of the typical little endian-ness
120 // // of modern computers, and hence yields wrong results...
121 //
122 // // Local helper function to avoid code duplication.
123 // if( lhs.size() != rhs.size() ) {
124 // throw std::runtime_error(
125 // "Cannot use lexicographical comparison functions on Bitvectors of different size."
126 // );
127 // }
128 // for( size_t i = 0; i < lhs.data().size(); ++i ) {
129 // if( lhs.data()[i] < rhs.data()[i] ) {
130 // return true;
131 // } else if( lhs.data()[i] > rhs.data()[i] ) {
132 // return false;
133 // }
134 // }
135 //
136 // // If we are here, all of the above comparisons shows that lhs == rhs.
137 // assert( lhs == rhs );
138 // return on_equal;
139 // }
140 //
141 // bool is_lexicographically_less( Bitvector const& lhs, Bitvector const& rhs )
142 // {
143 // return lexicographically_compare_helper_( lhs, rhs, false );
144 // }
145 //
146 // bool is_lexicographically_less_or_equal( Bitvector const& lhs, Bitvector const& rhs )
147 // {
148 // return lexicographically_compare_helper_( lhs, rhs, true );
149 // }
150 //
151 // bool is_lexicographically_greater( Bitvector const& lhs, Bitvector const& rhs )
152 // {
153 // return lexicographically_compare_helper_( rhs, lhs, false );
154 // }
155 //
156 // bool is_lexicographically_greater_or_equal( Bitvector const& lhs, Bitvector const& rhs )
157 // {
158 // return lexicographically_compare_helper_( rhs, lhs, true );
159 // }
160 
161 std::ostream& operator << (std::ostream& s, Bitvector const& bv)
162 {
163  for( size_t i = 0; i < bv.size(); ++i ) {
164  s << (bv.get(i) ? "1" : "0");
165  }
166  return s;
167 }
168 
169 std::istream& operator >> ( std::istream& in, Bitvector& bv )
170 {
171  // We need two steps, as we have to construct the bitvector with a known size.
172  // First, bring the bits into string form...
173  std::string str;
174  auto c = in.peek();
175  while( c == '0' || c == '1' ) {
176  str += c;
177  (void) in.get();
178  c = in.peek();
179  }
180 
181  // ... then, create the bitvector.
182  bv = Bitvector( str.size() );
183  for( size_t i = 0; i < str.size(); ++i ) {
184  if( str[i] == '1' ) {
185  bv.set(i);
186  }
187  }
188  return in;
189 }
190 
191 } // namespace utils
192 } // namespace genesis
genesis::utils::operator>>
std::istream & operator>>(std::istream &in, Bitvector &bv)
Extraction operator that inputs a Bitvector from a string of '0's and '1's, and stops at the first ch...
Definition: utils/math/bitvector/operators.cpp:169
genesis::utils::Bitvector::set
void set(size_t index)
Set the value of a single bit to true, with boundary check.
Definition: bitvector.hpp:184
genesis::utils::Bitvector::get
bool get(size_t index) const
Return the value of a single bit, with boundary check.
Definition: bitvector.hpp:167
genesis::utils::operator<<
std::ostream & operator<<(std::ostream &os, Color const &color)
Write a textual representation of the Color the a stream, in the format "(r, g, b,...
Definition: utils/color/functions.cpp:129
genesis::utils::is_superset
bool is_superset(Bitvector const &super, Bitvector const &sub)
Superset or equal.
Definition: utils/math/bitvector/operators.cpp:112
genesis::utils::is_strict_subset
bool is_strict_subset(Bitvector const &sub, Bitvector const &super)
Strict subset.
Definition: utils/math/bitvector/operators.cpp:94
operators.hpp
genesis
Container namespace for all symbols of genesis in order to keep them separate when used as a library.
Definition: placement/formats/edge_color.cpp:42
genesis::utils::set_minus
Bitvector set_minus(Bitvector const &lhs, Bitvector const &rhs)
Definition: utils/math/bitvector/operators.cpp:84
genesis::utils::bitwise_or
Bitvector bitwise_or(Bitvector const &lhs, Bitvector const &rhs, bool use_larger)
Take the bitwise or of two Bitvectors of potentially different size.
Definition: utils/math/bitvector/operators.cpp:58
genesis::utils::is_subset
bool is_subset(Bitvector const &sub, Bitvector const &super)
Subset or equal.
Definition: utils/math/bitvector/operators.cpp:107
genesis::utils::symmetric_difference
Bitvector symmetric_difference(Bitvector const &lhs, Bitvector const &rhs)
Definition: utils/math/bitvector/operators.cpp:89
genesis::utils::Bitvector::count
size_t count() const
Count the number of set bits in the Bitvector, that is, its Hamming weight, or population count (popc...
Definition: bitvector.cpp:314
genesis::utils::bitwise_and
Bitvector bitwise_and(Bitvector const &lhs, Bitvector const &rhs, bool use_larger)
Take the bitwise and of two Bitvectors of potentially different size.
Definition: utils/math/bitvector/operators.cpp:45
genesis::utils::is_strict_superset
bool is_strict_superset(Bitvector const &super, Bitvector const &sub)
Strict superset.
Definition: utils/math/bitvector/operators.cpp:102
genesis::utils::Bitvector::size
size_t size() const
Return the size (number of bits) of this Bitvector.
Definition: bitvector.hpp:304
genesis::utils::bitwise_xor
Bitvector bitwise_xor(Bitvector const &lhs, Bitvector const &rhs, bool use_larger)
Take the bitwise xor of two Bitvectors of potentially different size.
Definition: utils/math/bitvector/operators.cpp:71
genesis::utils::Bitvector
Definition: bitvector.hpp:50