////////////////////////////////////////////////////////////////////////////////
/// DISCLAIMER
///
/// Copyright 2017 ArangoDB GmbH, Cologne, Germany
///
/// Licensed under the Apache License, Version 2.0 (the "License");
/// you may not use this file except in compliance with the License.
/// You may obtain a copy of the License at
///
///     http://www.apache.org/licenses/LICENSE-2.0
///
/// Unless required by applicable law or agreed to in writing, software
/// distributed under the License is distributed on an "AS IS" BASIS,
/// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
/// See the License for the specific language governing permissions and
/// limitations under the License.
///
/// Copyright holder is ArangoDB GmbH, Cologne, Germany
///
/// @author Andrey Abramov
/// @author Vasiliy Nabatchikov
////////////////////////////////////////////////////////////////////////////////

#pragma once

#include "utils/bitset.hpp"

namespace irs {

////////////////////////////////////////////////////////////////////////////////
/// @brief a growable implementation of a bitset
////////////////////////////////////////////////////////////////////////////////
class bitvector final {
 public:
  using word_t = bitset::word_t;

  bitvector() = default;
  explicit bitvector(size_t bits) : size_{bits} { resize(bits); }
  bitvector(const bitvector& other) { *this = other; }
  bitvector(bitvector&& other) noexcept
    : set_{std::move(other.set_)}, size_{std::exchange(other.size_, 0)} {}

  bool operator==(const bitvector& rhs) const noexcept {
    if (this->size() != rhs.size()) {
      return false;
    }

    return 0 == std::memcmp(this->begin(), rhs.begin(), this->size());
  }

  bitvector& operator=(const bitvector& other) {
    if (this != &other) {
      if (set_.words() < other.set_.words()) {
        bitset set(other.set_.words() * bits_required<word_t>());

        set.memset(other.set_.begin(), other.set_.words() * sizeof(word_t));
        set_ = std::move(set);
      } else {  // optimization, reuse existing container
        set_.clear();
        set_.memset(other.set_.begin(), other.set_.words() * sizeof(word_t));
      }

      size_ = other.size_;
    }

    return *this;
  }

  bitvector& operator=(bitvector&& other) noexcept {
    if (this != &other) {
      set_ = std::move(other.set_);
      size_ = std::exchange(other.size_, 0);
    }

    return *this;
  }

  bitvector& operator&=(const bitvector& other) {
    if (this == &other || !other.size()) {
      return *this;  // nothing to do
    }

    reserve(other.size_);
    size_ = std::max(size_, other.size_);

    auto* data = const_cast<word_t*>(begin());
    auto last_word = bitset::word(other.size() - 1);  // -1 for bit offset

    for (size_t i = 0; i < last_word; ++i) {
      IRS_ASSERT(i < set_.words() && i < other.set_.words());
      *(data + i) &= *(other.data() + i);
    }

    // for the last word consider only those bits included in 'other.size()'
    auto last_word_bits = other.size() % bits_required<word_t>();
    const auto mask = (word_t(1) << last_word_bits) -
                      1;  // set all bits that are not part of 'other.size()'

    IRS_ASSERT(last_word < set_.words() && last_word < other.set_.words());
    *(data + last_word) &= (*(other.data() + last_word) & mask);
    std::memset(
      data + last_word + 1, 0,
      (set_.words() - last_word - 1) * sizeof(word_t));  // unset tail words

    return *this;
  }

  bitvector& operator|=(const bitvector& other) {
    if (this == &other || !other.size()) {
      return *this;  // nothing to do
    }

    reserve(other.size_);
    size_ = std::max(size_, other.size_);

    auto* data = const_cast<word_t*>(begin());
    auto last_word = bitset::word(other.size() - 1);  // -1 for bit offset

    for (size_t i = 0; i <= last_word; ++i) {
      IRS_ASSERT(i < set_.words() && i < other.set_.words());
      *(data + i) |= *(other.data() + i);
    }

    return *this;
  }

  bitvector& operator^=(const bitvector& other) {
    if (!other.size()) {
      return *this;  // nothing to do
    }

    reserve(other.size_);
    size_ = std::max(size_, other.size_);

    auto* data = const_cast<word_t*>(begin());
    auto last_word = bitset::word(other.size() - 1);  // -1 for bit offset

    for (size_t i = 0; i < last_word; ++i) {
      IRS_ASSERT(i < set_.words() && i < other.set_.words());
      *(data + i) ^= *(other.data() + i);
    }

    // for the last word consider only those bits included in 'other.size()'
    auto last_word_bits = other.size() % bits_required<word_t>();
    auto mask = ~word_t(0);

    // clear trailing bits
    if (last_word_bits) {
      mask = ~(mask << last_word_bits);  // unset all bits that are not part of
                                         // 'other.size()'
    }

    IRS_ASSERT(last_word < set_.words() && last_word < other.set_.words());
    *(data + last_word) ^= (*(other.data() + last_word) & mask);

    return *this;
  }

  bitvector& operator-=(const bitvector& other) {
    if (!other.size()) {
      return *this;  // nothing to do
    }

    reserve(other.size_);
    size_ = std::max(size_, other.size_);
    auto* data = const_cast<word_t*>(begin());
    auto last_word = bitset::word(other.size() - 1);  // -1 for bit offset

    for (size_t i = 0; i < last_word; ++i) {
      IRS_ASSERT(i < set_.words() && i < other.set_.words());
      *(data + i) &= ~(*(other.data() + i));
    }

    // for the last word consider only those bits included in 'other.size()'
    auto last_word_bits = other.size() % bits_required<word_t>();
    auto mask = ~word_t(0);

    // clear trailing bits
    if (last_word_bits) {
      mask = ~(mask << last_word_bits);  // unset all bits that are not part of
                                         // 'other.size()'
    }

    IRS_ASSERT(last_word < set_.words() && last_word < other.set_.words());
    *(data + last_word) &= ~(*(other.data() + last_word) & mask);

    return *this;
  }

  bool all() const noexcept { return set_.count() == size(); }
  bool any() const noexcept { return set_.any(); }
  const word_t* begin() const noexcept { return set_.data(); }
  size_t capacity() const noexcept { return set_.capacity(); }
  void clear() noexcept {
    set_.clear();
    size_ = 0;
  }
  word_t count() const noexcept { return set_.count(); }
  const word_t* data() const noexcept { return set_.data(); }
  const word_t* end() const noexcept { return set_.end(); }

  template<typename T>
  void memset(const T& value) noexcept {
    memset(&value, sizeof(value));
  }

  void memset(const void* src, size_t size) noexcept {
    auto bits = bits_required<uint8_t>() * size;  // size is in bytes

    reserve(bits);
    std::memcpy(const_cast<word_t*>(begin()), src,
                std::min(size, set_.words() * sizeof(word_t)));
    size_ = std::max(size_, bits);
  }

  bool none() const noexcept { return set_.none(); }

  // reserve at least this many bits
  void reserve(size_t bits) {
    const auto words = bitset::word(bits - 1) + 1;

    if (!bits || words <= set_.words()) {
      return;  // nothing to do
    }

    auto set = bitset(words * bits_required<word_t>());

    if (data()) {
      set.memset(begin(), set_.words() * sizeof(word_t));  // copy original
    }

    set_ = std::move(set);
  }

  void resize(size_t bits, bool preserve_capacity = false) {
    const auto words =
      bitset::word(bits) + 1;  // +1 for count instead of offset

    size_ = bits;

    if (words > set_.words()) {
      reserve(bits);

      return;
    }

    if (preserve_capacity) {
      std::memset(
        const_cast<word_t*>(begin()) + words, 0,
        (set_.words() - words) * sizeof(word_t));  // clear trailing words
    } else if (words < set_.words()) {
      auto set = bitset(words * bits_required<word_t>());

      set.memset(begin(), set.words() * sizeof(word_t));  // copy original
      set_ = std::move(set);
    }

    auto last_word_bits = bits % bits_required<word_t>();

    // clear trailing bits
    if (last_word_bits) {
      auto* last_word = begin() + words - 1;
      const auto mask =
        ~(~word_t(0)
          << last_word_bits);  // set all bits up to and including max bit

      const_cast<word_t&>(*last_word) &= mask;  // keep only bits up to max bit
    }
  }

  void reset(size_t i, bool set) {
    if (!set && bitset::word(i) >= set_.words()) {
      size_ = std::max(size(), i + 1);

      return;  // nothing to do
    }

    resize(std::max(size(), i + 1), true);  // ensure capacity
    set_.reset(i, set);
  }

  void shrink_to_fit() {
    auto words = set_.words();

    if (!words) {
      return;  // nothing to do, no buffer
    }

    while (words && 0 == *(begin() + words - 1)) {
      --words;
    }

    if (!words) {
      auto set = bitset();  // create empty set

      set_ = std::move(set);
      size_ = 0;

      return;
    }

    if (words != set_.words()) {
      auto set = bitset(words * bits_required<word_t>());

      set.memset(begin(), set.words() * sizeof(word_t));  // copy original
      set_ = std::move(set);
    }

    size_ = (set_.words() * bits_required<word_t>()) -
            std::countl_zero(*(begin() + set_.words() - 1));
  }

  void set(size_t i) { reset(i, true); }
  size_t size() const noexcept { return size_; }
  bool empty() const noexcept { return 0 == size_; }

  bool test(size_t i) const noexcept {
    return bitset::word(i) < set_.words() && set_.test(i);
  }

  void unset(size_t i) { reset(i, false); }

  size_t words() const noexcept { return set_.words(); }

  template<typename Visitor>
  bool visit(Visitor visitor) const {
    for (size_t i = 0; i < size_; ++i) {
      if (set_.test(i) && !visitor(i)) {
        return false;
      }
    }
    return true;
  }

  void To(bitset& set) noexcept {
    set = std::move(set_);
    size_ = 0;
  }

 private:
  bitset set_;
  size_t size_{0};  // number of bits requested in a bitset
};

static_assert(std::is_nothrow_move_constructible_v<bitvector>);

}  // namespace irs
