succinct_monotone_stack.h

#pragma once

 
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
 
namespace pixie::rmq::utils {

class SuccinctIncreasingStack {
 public:
  explicit SuccinctIncreasingStack(std::size_t capacity)
      : words_(word_count(capacity)),
        nonempty_words_(word_count(words_.size())),
        nonempty_super_words_(word_count(nonempty_words_.size())),
        capacity_(capacity) {}

  bool empty() const { return size_ == 0; }

  std::size_t top() const {
    assert(!empty());
    return top_key_;
  }

  void push(std::size_t key) {
    assert(key < capacity_);
    assert(empty() || top() < key);
 
    const std::size_t block = block_index(key);
    words_[block] |= std::uint64_t{1} << block_position(key);
    set_nonempty(block);
    top_key_ = key;
    ++size_;
  }

  void pop() {
    assert(!empty());
 
    const std::size_t block = block_index(top_key_);
    std::uint64_t word = words_[block];
    word &= ~(std::uint64_t{1} << block_position(top_key_));
    words_[block] = word;
 
    --size_;
    if (size_ == 0) {
      if (word == 0) {
        clear_nonempty(block);
      }
      top_key_ = 0;
      return;
    }
 
    if (word != 0) {
      top_key_ = block * kBlockBits + highest_bit(word);
      return;
    }
 
    clear_nonempty(block);
    const std::size_t previous_block = previous_nonempty_block(block);
    const std::uint64_t previous_word = words_[previous_block];
    assert(previous_word != 0);
    top_key_ = previous_block * kBlockBits + highest_bit(previous_word);
  }
 
 private:
  static constexpr std::size_t kBlockBits = 64;
  static constexpr std::size_t kBlockShift = 6;
  static constexpr std::size_t kBlockMask = kBlockBits - 1;
 
  static std::size_t word_count(std::size_t bit_count) {
    return (bit_count + kBlockBits - 1) / kBlockBits;
  }
 
  static std::size_t block_index(std::size_t key) { return key >> kBlockShift; }
 
  static std::size_t block_position(std::size_t key) {
    return key & kBlockMask;
  }
 
  static std::size_t highest_bit(std::uint64_t word) {
    assert(word != 0);
    return static_cast<std::size_t>(std::bit_width(word) - 1);
  }
 
  static std::uint64_t low_bits(std::size_t count) {
    return count == 0 ? 0 : ((std::uint64_t{1} << count) - 1);
  }
 
  void set_nonempty(std::size_t block) {
    const std::size_t summary = block_index(block);
    const std::uint64_t bit = std::uint64_t{1} << block_position(block);
    if ((nonempty_words_[summary] & bit) == 0) {
      nonempty_words_[summary] |= bit;
      nonempty_super_words_[block_index(summary)] |= std::uint64_t{1}
                                                     << block_position(summary);
    }
  }
 
  void clear_nonempty(std::size_t block) {
    const std::size_t summary = block_index(block);
    nonempty_words_[summary] &= ~(std::uint64_t{1} << block_position(block));
    if (nonempty_words_[summary] == 0) {
      nonempty_super_words_[block_index(summary)] &=
          ~(std::uint64_t{1} << block_position(summary));
    }
  }
 
  std::size_t previous_nonempty_block(std::size_t block) const {
    assert(block > 0);
    std::size_t summary = block_index(block);
    const std::size_t summary_position = block_position(block);
    if (summary_position != 0) {
      const std::uint64_t same_summary =
          nonempty_words_[summary] & low_bits(summary_position);
      if (same_summary != 0) {
        return summary * kBlockBits + highest_bit(same_summary);
      }
    }
 
    std::size_t super = block_index(summary);
    const std::size_t super_position = block_position(summary);
    std::uint64_t super_mask =
        super_position == 0
            ? 0
            : nonempty_super_words_[super] & low_bits(super_position);
    while (super_mask == 0) {
      assert(super > 0);
      --super;
      super_mask = nonempty_super_words_[super];
    }
 
    const std::size_t previous_summary =
        super * kBlockBits + highest_bit(super_mask);
    assert(previous_summary < nonempty_words_.size());
    const std::uint64_t previous_summary_word =
        nonempty_words_[previous_summary];
    assert(previous_summary_word != 0);
    return previous_summary * kBlockBits + highest_bit(previous_summary_word);
  }
 
  std::vector<std::uint64_t> words_;
  std::vector<std::uint64_t> nonempty_words_;
  std::vector<std::uint64_t> nonempty_super_words_;
  std::size_t capacity_ = 0;
  std::size_t size_ = 0;
  std::size_t top_key_ = 0;
};
 
}  // namespace pixie::rmq::utils