#ifndef SCANN_UTILS_BIT_ITERATOR_H_
#define SCANN_UTILS_BIT_ITERATOR_H_
#include <cstdint>
#include "scann/oss_wrappers/scann_bits.h"
#include "scann/utils/types.h"
namespace research_scann {
template <typename StorageT, typename PositionT = uint32_t>
class BitIterator {
public:
BitIterator() {}
explicit inline BitIterator(StorageT whitelist_storage);
PositionT value() const { return value_; }
inline void Next();
bool Done() const { return cur_whitelist_word_ == 0; }
private:
inline void NextNonzeroWord();
StorageT whitelist_array_;
size_t whitelist_array_position_ = 0;
PositionT word_base_ = 0;
PositionT value_ = 0;
using WordType = decay_t<decltype(whitelist_array_[0])>;
WordType cur_whitelist_word_ = 0;
};
namespace bits_internal {
template <typename Int>
inline int FindLSBSetNonZero(Int x) {
DCHECK_NE(x, 0);
if (sizeof(x) * CHAR_BIT > 32) {
return bits::FindLSBSetNonZero64(x);
} else {
return bits::FindLSBSetNonZero(x);
}
}
}
template <typename StorageT, typename PositionT>
BitIterator<StorageT, PositionT>::BitIterator(StorageT whitelist_storage)
: whitelist_array_(std::move(whitelist_storage)), value_(0) {
NextNonzeroWord();
if (cur_whitelist_word_ == 0) return;
value_ = word_base_ + bits_internal::FindLSBSetNonZero(cur_whitelist_word_);
}
template <typename StorageT, typename PositionT>
void BitIterator<StorageT, PositionT>::Next() {
cur_whitelist_word_ &= cur_whitelist_word_ - 1;
if (cur_whitelist_word_ == 0) {
++whitelist_array_position_;
NextNonzeroWord();
if (cur_whitelist_word_ == 0) return;
}
value_ = word_base_ + bits_internal::FindLSBSetNonZero(cur_whitelist_word_);
}
template <typename StorageT, typename PositionT>
void BitIterator<StorageT, PositionT>::NextNonzeroWord() {
static constexpr size_t kBitsPerWord = sizeof(cur_whitelist_word_) * CHAR_BIT;
for (; whitelist_array_position_ < whitelist_array_.size();
++whitelist_array_position_) {
cur_whitelist_word_ = whitelist_array_[whitelist_array_position_];
if (cur_whitelist_word_ != 0) {
word_base_ = whitelist_array_position_ * kBitsPerWord;
return;
}
}
}
}
#endif