lib/marisa_alpha/bitvector.cc

#include "bitvector.h"
#include "popcount.h"

namespace marisa_alpha {
namespace {

const UInt8 SelectTable[8][256] = {
  {
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  },
  {
    7, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
    7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
    6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    7, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
    7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
    6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
    6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
    5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
  },
  {
    7, 7, 7, 7, 7, 7, 7, 2, 7, 7, 7, 3, 7, 3, 3, 2,
    7, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
    7, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
    7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
    7, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
    7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
    7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
    6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
    7, 7, 7, 7, 7, 7, 7, 2, 7, 7, 7, 3, 7, 3, 3, 2,
    7, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
    7, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
    7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
    7, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
    7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
    7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
    6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2
  },
  {
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3,
    7, 7, 7, 7, 7, 7, 7, 4, 7, 7, 7, 4, 7, 4, 4, 3,
    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 3,
    7, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 3,
    7, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3,
    7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 3,
    7, 7, 7, 7, 7, 7, 7, 4, 7, 7, 7, 4, 7, 4, 4, 3,
    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 3,
    7, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 3,
    7, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3,
    7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3
  },
  {
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 4,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 4,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5,
    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 4,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
    7, 7, 7, 7, 7, 7, 7, 5, 7, 7, 7, 5, 7, 5, 5, 4,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 4,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5,
    7, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4
  },
  {
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 5,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 6, 7, 6, 6, 5
  },
  {
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6
  },
  {
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
  }
};

}  // namespace

BitVector::BitVector()
    : blocks_(), size_(0), ranks_(), select0s_(), select1s_() {}

void BitVector::build() {
  Vector<Rank> ranks;
  const UInt32 num_blocks = (size_ / 512) + (((size_ % 512) != 0) ? 1 : 0);
  ranks.resize(num_blocks + 1);
  Vector<UInt32> select0s;
  Vector<UInt32> select1s;
  UInt32 num_0s = 0;
  UInt32 num_1s = 0;
  for (UInt32 i = 0; i < size_; ++i) {
    if ((i % 64) == 0) {
      UInt32 rank_id = i / 512;
      switch ((i / 64) % 8) {
        case 0: {
          ranks[rank_id].set_abs(num_1s);
          break;
        }
        case 1: {
          ranks[rank_id].set_rel1(num_1s - ranks[rank_id].abs());
          break;
        }
        case 2: {
          ranks[rank_id].set_rel2(num_1s - ranks[rank_id].abs());
          break;
        }
        case 3: {
          ranks[rank_id].set_rel3(num_1s - ranks[rank_id].abs());
          break;
        }
        case 4: {
          ranks[rank_id].set_rel4(num_1s - ranks[rank_id].abs());
          break;
        }
        case 5: {
          ranks[rank_id].set_rel5(num_1s - ranks[rank_id].abs());
          break;
        }
        case 6: {
          ranks[rank_id].set_rel6(num_1s - ranks[rank_id].abs());
          break;
        }
        case 7: {
          ranks[rank_id].set_rel7(num_1s - ranks[rank_id].abs());
          break;
        }
      }
    }
    if ((*this)[i]) {
      if ((num_1s % 512) == 0) {
        select1s.push_back(i);
      }
      ++num_1s;
    } else {
      if ((num_0s % 512) == 0) {
        select0s.push_back(i);
      }
      ++num_0s;
    }
  }
  if ((size_ % 512) != 0) {
    UInt32 rank_id = (size_ - 1) / 512;
    switch (((size_ - 1) / 64) % 8) {
      case 0: {
        ranks[rank_id].set_rel1(num_1s - ranks[rank_id].abs());
      }
      case 1: {
        ranks[rank_id].set_rel2(num_1s - ranks[rank_id].abs());
      }
      case 2: {
        ranks[rank_id].set_rel3(num_1s - ranks[rank_id].abs());
      }
      case 3: {
        ranks[rank_id].set_rel4(num_1s - ranks[rank_id].abs());
      }
      case 4: {
        ranks[rank_id].set_rel5(num_1s - ranks[rank_id].abs());
      }
      case 5: {
        ranks[rank_id].set_rel6(num_1s - ranks[rank_id].abs());
      }
      case 6: {
        ranks[rank_id].set_rel7(num_1s - ranks[rank_id].abs());
        break;
      }
    }
  }
  ranks.back().set_abs(num_1s);
  select0s.push_back(size_);
  select1s.push_back(size_);
  select0s.shrink();
  select1s.shrink();

  blocks_.shrink();
  ranks_.swap(&ranks);
  select0s_.swap(&select0s);
  select1s_.swap(&select1s);
}

void BitVector::mmap(Mapper *mapper, const char *filename,
    long offset, int whence) {
  MARISA_ALPHA_THROW_IF(mapper == NULL, MARISA_ALPHA_PARAM_ERROR);
  Mapper temp_mapper;
  temp_mapper.open(filename, offset, whence);
  map(temp_mapper);
  temp_mapper.swap(mapper);
}

void BitVector::map(const void *ptr, std::size_t size) {
  Mapper mapper(ptr, size);
  map(mapper);
}

void BitVector::map(Mapper &mapper) {
  BitVector temp;
  temp.blocks_.map(mapper);
  mapper.map(&temp.size_);
  temp.ranks_.map(mapper);
  temp.select0s_.map(mapper);
  temp.select1s_.map(mapper);
  temp.swap(this);
}

void BitVector::load(const char *filename,
    long offset, int whence) {
  Reader reader;
  reader.open(filename, offset, whence);
  read(reader);
}

void BitVector::fread(std::FILE *file) {
  Reader reader(file);
  read(reader);
}

void BitVector::read(int fd) {
  Reader reader(fd);
  read(reader);
}

void BitVector::read(std::istream &stream) {
  Reader reader(&stream);
   read(reader);
}

void BitVector::read(Reader &reader) {
  BitVector temp;
  temp.blocks_.read(reader);
  reader.read(&temp.size_);
  temp.ranks_.read(reader);
  temp.select0s_.read(reader);
  temp.select1s_.read(reader);
  temp.swap(this);
}

void BitVector::save(const char *filename, bool trunc_flag,
    long offset, int whence) const {
  Writer writer;
  writer.open(filename, trunc_flag, offset, whence);
  write(writer);
}

void BitVector::fwrite(std::FILE *file) const {
  Writer writer(file);
  write(writer);
}

void BitVector::write(int fd) const {
  Writer writer(fd);
  write(writer);
}

void BitVector::write(std::ostream &stream) const {
  Writer writer(&stream);
  write(writer);
}

void BitVector::write(Writer &writer) const {
  blocks_.write(writer);
  writer.write(size_);
  ranks_.write(writer);
  select0s_.write(writer);
  select1s_.write(writer);
}

UInt32 BitVector::rank1(UInt32 i) const {
  MARISA_ALPHA_DEBUG_IF(i > size_, MARISA_ALPHA_PARAM_ERROR);
  const Rank &rank = ranks_[i / 512];
  UInt32 offset = rank.abs();
  switch ((i / 64) % 8) {
    case 1: {
      offset += rank.rel1();
      break;
    }
    case 2: {
      offset += rank.rel2();
      break;
    }
    case 3: {
      offset += rank.rel3();
      break;
    }
    case 4: {
      offset += rank.rel4();
      break;
    }
    case 5: {
      offset += rank.rel5();
      break;
    }
    case 6: {
      offset += rank.rel6();
      break;
    }
    case 7: {
      offset += rank.rel7();
      break;
    }
  }
  switch ((i / 32) % 2) {
    case 1: {
      offset += PopCount(blocks_[(i / 32) - 1]).lo32();
    }
    case 0: {
      offset += PopCount(blocks_[i / 32] & ((1U << (i % 32)) - 1)).lo32();
      break;
    }
  }
  return offset;
}

UInt32 BitVector::select0(UInt32 i) const {
  UInt32 select_id = i / 512;
  MARISA_ALPHA_DEBUG_IF((select_id + 1) >= select0s_.size(),
      MARISA_ALPHA_PARAM_ERROR);
  if ((i % 512) == 0) {
    return select0s_[select_id];
  }
  UInt32 begin = select0s_[select_id] / 512;
  UInt32 end = (select0s_[select_id + 1] + 511) / 512;
  if (begin + 10 >= end) {
    while (i >= ((begin + 1) * 512) - ranks_[begin + 1].abs()) {
      ++begin;
    }
  } else {
    while (begin + 1 < end) {
      UInt32 middle = (begin + end) / 2;
      if (i < (middle * 512) - ranks_[middle].abs()) {
        end = middle;
      } else {
        begin = middle;
      }
    }
  }
  const UInt32 rank_id = begin;
  i -= (rank_id * 512) - ranks_[rank_id].abs();

  const Rank &rank = ranks_[rank_id];
  UInt32 block_id = rank_id * 16;
  if (i < (256U - rank.rel4())) {
    if (i < (128U - rank.rel2())) {
      if (i >= (64U - rank.rel1())) {
        block_id += 2;
        i -= 64 - rank.rel1();
      }
    } else if (i < (192U - rank.rel3())) {
      block_id += 4;
      i -= 128 - rank.rel2();
    } else {
      block_id += 6;
      i -= 192 - rank.rel3();
    }
  } else if (i < (384U - rank.rel6())) {
    if (i < (320U - rank.rel5())) {
      block_id += 8;
      i -= 256 - rank.rel4();
    } else {
      block_id += 10;
      i -= 320 - rank.rel5();
    }
  } else if (i < (448U - rank.rel7())) {
    block_id += 12;
    i -= 384 - rank.rel6();
  } else {
    block_id += 14;
    i -= 448 - rank.rel7();
  }

  UInt32 block = ~blocks_[block_id];
  PopCount count(block);
  if (i >= count.lo32()) {
    ++block_id;
    i -= count.lo32();
    block = ~blocks_[block_id];
    count = PopCount(block);
  }

  UInt32 bit_id = block_id * 32;
  if (i < count.lo16()) {
    if (i >= count.lo8()) {
      bit_id += 8;
      block >>= 8;
      i -= count.lo8();
    }
  } else if (i < count.lo24()) {
    bit_id += 16;
    block >>= 16;
    i -= count.lo16();
  } else {
    bit_id += 24;
    block >>= 24;
    i -= count.lo24();
  }
  return bit_id + SelectTable[i][block & 0xFF];
}

UInt32 BitVector::select1(UInt32 i) const {
  UInt32 select_id = i / 512;
  MARISA_ALPHA_DEBUG_IF((select_id + 1) >= select1s_.size(),
      MARISA_ALPHA_PARAM_ERROR);
  if ((i % 512) == 0) {
    return select1s_[select_id];
  }
  UInt32 begin = select1s_[select_id] / 512;
  UInt32 end = (select1s_[select_id + 1] + 511) / 512;
  if (begin + 10 >= end) {
    while (i >= ranks_[begin + 1].abs()) {
      ++begin;
    }
  } else {
    while (begin + 1 < end) {
      UInt32 middle = (begin + end) / 2;
      if (i < ranks_[middle].abs()) {
        end = middle;
      } else {
        begin = middle;
      }
    }
  }
  const UInt32 rank_id = begin;
  i -= ranks_[rank_id].abs();

  const Rank &rank = ranks_[rank_id];
  UInt32 block_id = rank_id * 16;
  if (i < rank.rel4()) {
    if (i < rank.rel2()) {
      if (i >= rank.rel1()) {
        block_id += 2;
        i -= rank.rel1();
      }
    } else if (i < rank.rel3()) {
      block_id += 4;
      i -= rank.rel2();
    } else {
      block_id += 6;
      i -= rank.rel3();
    }
  } else if (i < rank.rel6()) {
    if (i < rank.rel5()) {
      block_id += 8;
      i -= rank.rel4();
    } else {
      block_id += 10;
      i -= rank.rel5();
    }
  } else if (i < rank.rel7()) {
    block_id += 12;
    i -= rank.rel6();
  } else {
    block_id += 14;
    i -= rank.rel7();
  }

  UInt32 block = blocks_[block_id];
  PopCount count(block);
  if (i >= count.lo32()) {
    ++block_id;
    i -= count.lo32();
    block = blocks_[block_id];
    count = PopCount(block);
  }

  UInt32 bit_id = block_id * 32;
  if (i < count.lo16()) {
    if (i >= count.lo8()) {
      bit_id += 8;
      block >>= 8;
      i -= count.lo8();
    }
  } else if (i < count.lo24()) {
    bit_id += 16;
    block >>= 16;
    i -= count.lo16();
  } else {
    bit_id += 24;
    block >>= 24;
    i -= count.lo24();
  }
  return bit_id + SelectTable[i][block & 0xFF];
}

void BitVector::clear() {
  BitVector().swap(this);
}

void BitVector::swap(BitVector *rhs) {
  MARISA_ALPHA_THROW_IF(rhs == NULL, MARISA_ALPHA_PARAM_ERROR);
  blocks_.swap(&rhs->blocks_);
  Swap(&size_, &rhs->size_);
  ranks_.swap(&rhs->ranks_);
  select0s_.swap(&rhs->select0s_);
  select1s_.swap(&rhs->select1s_);
}

}  // namespace marisa_alpha