w-ary Tree Set
(data_structure/w_ary_tree_set.cpp)

• View this file on GitHub
• Last update: 2021-09-16 02:20:28+09:00

機能

• $\mathtt{pred}(k)$
  • $k$ より真に小さい中で最も大きいもの
  • 無い場合 -1 (unsigned の -1 が返るので注意)
• $\mathtt{succ}(k)$
  • $k$ 以上の中で最も小さいもの
  • 無い場合 -1 (unsigned の -1 が返るので注意)

Depends on

• other/ceildiv.cpp
• other/int_alias.cpp

Verified with

• test/w_ary_tree_set.pred.test.cpp
• test/w_ary_tree_set.test.cpp

Code

#include "other/ceildiv.cpp"
#include "other/int_alias.cpp"

#include <array>
#include <type_traits>

namespace w_ary_tree_set_impl {
constexpr usize calc_c(usize n) {
  usize ret = 1;
  while (n > 64) {
    ret *= 64;
    n /= 64;
  }
  return ret;
}
usize bsf(const u64 x) {
#ifdef __GNUC__
  return __builtin_ctzll(x);
#else
  unsigned long ret;
  if (_BitScanForward(&ret, x & ~(~static_cast<u64>(0) << 32))) {
    return ret;
  } else {
    _BitScanForward(&ret, x >> 32);
    return ret + 32;
  }
#endif
}
usize bsr(const u64 x) {
#ifdef __GNUC__
  return 63 - __builtin_clzll(x);
#else
  unsigned long ret;
  if (_BitScanReverse(&ret, x >> 32)) {
    return ret + 32;
  } else {
    _BitScanReverse(&ret, x & ~(~static_cast<u64>(0) << 32));
    return ret;
  }
#endif
}

template <usize N, class D = void> class w_ary_tree_set {
  static constexpr usize C = calc_c(N);

  u64 map;
  std::array<w_ary_tree_set<C>, ceildiv(N, C)> child;

public:
  w_ary_tree_set() : map(0), child() {}

  bool insert(const usize key) {
    const usize pos = key / C;
    map |= static_cast<u64>(1) << pos;
    return child[pos].insert(key % C);
  }

  bool erase(const usize key) {
    const usize pos = key / C;
    const bool ret = child[pos].erase(key % C);
    if (child[pos]._get_map() == 0) {
      map &= ~(static_cast<u64>(1) << pos);
    }
    return ret;
  }

  bool contains(const usize key) const {
    return child[key / C].contains(key % C);
  }

  usize min() const {
    const usize pos = bsf(map);
    return pos * C + child[pos].min();
  }

  usize max() const {
    const usize pos = bsr(map);
    return pos * C + child[pos].max();
  }

  usize pred(const usize key) const {
    const usize pos = key / C;
    const usize t = child[pos].pred(key % C);
    if (t != -1) {
      return pos * C + t;
    }
    const u64 masked = map & ~(~static_cast<u64>(0) << pos);
    if (masked == 0) {
      return -1;
    }
    const usize pos2 = bsr(masked);
    return pos2 * C + child[pos2].max();
  }

  usize succ(const usize key) const {
    const usize pos = key / C;
    const usize t = child[pos].succ(key % C);
    if (t != -1) {
      return pos * C + t;
    }
    const u64 masked = map & ~(~static_cast<u64>(0) >> (63 - pos));
    if (masked == 0) {
      return -1;
    }
    const usize pos2 = bsf(masked);
    return pos2 * C + child[pos2].min();
  }

  u64 _get_map() const { return map; }
};

template <usize N>
class w_ary_tree_set<N, typename std::enable_if<(N <= 64)>::type> {
  u64 map;

public:
  w_ary_tree_set() : map(0) {}

  bool insert(const usize key) {
    const u64 pop = static_cast<u64>(1) << key;
    if ((map & pop) != 0) {
      return false;
    } else {
      map |= pop;
      return true;
    }
  }

  bool erase(const usize key) {
    const u64 pop = static_cast<u64>(1) << key;
    if ((map & pop) != 0) {
      map &= ~pop;
      return true;
    } else {
      return false;
    }
  }

  bool contains(const usize key) const {
    return (map & static_cast<u64>(1) << key) != 0;
  }

  usize min() const { return bsf(map); }

  usize max() const { return bsr(map); }

  usize pred(const usize key) const {
    const u64 masked = map & ~(~static_cast<u64>(0) << key);
    if (masked == 0) {
      return -1;
    }
    return bsr(masked);
  }

  usize succ(const usize key) const {
    const u64 masked = map & (~static_cast<u64>(0) << key);
    if (masked == 0) {
      return -1;
    }
    return bsf(masked);
  }

  u64 _get_map() const { return map; }
};

} // namespace w_ary_tree_set_impl


template <usize N>
using w_ary_tree_set = w_ary_tree_set_impl::w_ary_tree_set<N>;

/**
 * @brief w-ary Tree Set
 * @docs docs/w_ary_tree_set.md
 */

#line 1 "other/ceildiv.cpp"
template <class T> constexpr T ceildiv(const T &n, const T &d) {
  return n / d + (n % d != 0 ? 1 : 0);
}
#line 2 "other/int_alias.cpp"

#include <cstddef>
#include <cstdint>

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 3 "data_structure/w_ary_tree_set.cpp"

#include <array>
#include <type_traits>

namespace w_ary_tree_set_impl {
constexpr usize calc_c(usize n) {
  usize ret = 1;
  while (n > 64) {
    ret *= 64;
    n /= 64;
  }
  return ret;
}
usize bsf(const u64 x) {
#ifdef __GNUC__
  return __builtin_ctzll(x);
#else
  unsigned long ret;
  if (_BitScanForward(&ret, x & ~(~static_cast<u64>(0) << 32))) {
    return ret;
  } else {
    _BitScanForward(&ret, x >> 32);
    return ret + 32;
  }
#endif
}
usize bsr(const u64 x) {
#ifdef __GNUC__
  return 63 - __builtin_clzll(x);
#else
  unsigned long ret;
  if (_BitScanReverse(&ret, x >> 32)) {
    return ret + 32;
  } else {
    _BitScanReverse(&ret, x & ~(~static_cast<u64>(0) << 32));
    return ret;
  }
#endif
}

template <usize N, class D = void> class w_ary_tree_set {
  static constexpr usize C = calc_c(N);

  u64 map;
  std::array<w_ary_tree_set<C>, ceildiv(N, C)> child;

public:
  w_ary_tree_set() : map(0), child() {}

  bool insert(const usize key) {
    const usize pos = key / C;
    map |= static_cast<u64>(1) << pos;
    return child[pos].insert(key % C);
  }

  bool erase(const usize key) {
    const usize pos = key / C;
    const bool ret = child[pos].erase(key % C);
    if (child[pos]._get_map() == 0) {
      map &= ~(static_cast<u64>(1) << pos);
    }
    return ret;
  }

  bool contains(const usize key) const {
    return child[key / C].contains(key % C);
  }

  usize min() const {
    const usize pos = bsf(map);
    return pos * C + child[pos].min();
  }

  usize max() const {
    const usize pos = bsr(map);
    return pos * C + child[pos].max();
  }

  usize pred(const usize key) const {
    const usize pos = key / C;
    const usize t = child[pos].pred(key % C);
    if (t != -1) {
      return pos * C + t;
    }
    const u64 masked = map & ~(~static_cast<u64>(0) << pos);
    if (masked == 0) {
      return -1;
    }
    const usize pos2 = bsr(masked);
    return pos2 * C + child[pos2].max();
  }

  usize succ(const usize key) const {
    const usize pos = key / C;
    const usize t = child[pos].succ(key % C);
    if (t != -1) {
      return pos * C + t;
    }
    const u64 masked = map & ~(~static_cast<u64>(0) >> (63 - pos));
    if (masked == 0) {
      return -1;
    }
    const usize pos2 = bsf(masked);
    return pos2 * C + child[pos2].min();
  }

  u64 _get_map() const { return map; }
};

template <usize N>
class w_ary_tree_set<N, typename std::enable_if<(N <= 64)>::type> {
  u64 map;

public:
  w_ary_tree_set() : map(0) {}

  bool insert(const usize key) {
    const u64 pop = static_cast<u64>(1) << key;
    if ((map & pop) != 0) {
      return false;
    } else {
      map |= pop;
      return true;
    }
  }

  bool erase(const usize key) {
    const u64 pop = static_cast<u64>(1) << key;
    if ((map & pop) != 0) {
      map &= ~pop;
      return true;
    } else {
      return false;
    }
  }

  bool contains(const usize key) const {
    return (map & static_cast<u64>(1) << key) != 0;
  }

  usize min() const { return bsf(map); }

  usize max() const { return bsr(map); }

  usize pred(const usize key) const {
    const u64 masked = map & ~(~static_cast<u64>(0) << key);
    if (masked == 0) {
      return -1;
    }
    return bsr(masked);
  }

  usize succ(const usize key) const {
    const u64 masked = map & (~static_cast<u64>(0) << key);
    if (masked == 0) {
      return -1;
    }
    return bsf(masked);
  }

  u64 _get_map() const { return map; }
};

} // namespace w_ary_tree_set_impl


template <usize N>
using w_ary_tree_set = w_ary_tree_set_impl::w_ary_tree_set<N>;

/**
 * @brief w-ary Tree Set
 * @docs docs/w_ary_tree_set.md
 */

Back to top page