Quelle uf.hpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2020 James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

// This file defines a class UF used to make an equivalence relation on the
// integers {0, .., n - 1}, using the UNION-FIND METHOD: new pairs can be added
// and the appropriate classes combined quickly.

// The implementation here is based on the implementation in the datastructures
// package for GAP (v0.2.5) by Markus Pfeiffer, Max Horn, Christopher
// Jefferson, Steve Linton.

// An earlier version of the UF class was written by M. Young.

#ifndef LIBSEMIGROUPS_UF_HPP_
#define LIBSEMIGROUPS_UF_HPP_

#include <algorithm>      // for for_each
#include <array>          // for array
#include <cstddef>        // for size_t
#include <numeric>        // for iota
#include <unordered_map>  // for unordered_map
#include <vector>         // for vector

#include "adapters.hpp"  // for Hash
#include "config.hpp"    // for LIBSEMIGROUPS_SIZEOF_VOID_P
#include "debug.hpp"     // for LIBSEMIGROUPS_ASSERT
#include "iterator.hpp"  // for ConstIteratorStateless
#include "types.hpp"     // for SmallestInteger

namespace libsemigroups {
  namespace detail {

#if LIBSEMIGROUPS_SIZEOF_VOID_P == 8
    constexpr size_t RANK_BITS = 6;
#else
    constexpr size_t RANK_BITS = 5;
#endif

    template <typename T>
    class UF {
      ////////////////////////////////////////////////////////////////////////
      // Aliases - private
      ////////////////////////////////////////////////////////////////////////

      using node_type = typename T::value_type;
      using rank_type = typename T::value_type;

     public:
      ////////////////////////////////////////////////////////////////////////
      // Aliases - public
      ////////////////////////////////////////////////////////////////////////
      using size_type      = size_t;
      using container_type = T;
      using index_type     = typename T::value_type;

      ////////////////////////////////////////////////////////////////////////
      // Constructors + destructor
      ////////////////////////////////////////////////////////////////////////

      // not noexcept because the constructors of std::vector and std::array
      // aren't
      explicit UF(container_type&& c) : _data(std::move(c)) {
        init_data(_data.begin(), _data.end());
      }

      // not noexcept because the constructors of std::vector and std::array
      // aren't
      explicit UF(container_type const& c) : _data(c) {
        init_data(_data.begin(), _data.end());
      }

      // not noexcept because the constructors of std::vector and std::array
      // aren't
      explicit UF(size_type size = 0) : _data() {
        set_data_capacity(_data, size);
        std::iota(_data.begin(), _data.end(), 0);
        init_data(_data.begin(), _data.end());
      }

      // not noexcept because the constructors of std::vector and std::array
      // aren't
      UF(UF const&)            = default;
      UF& operator=(UF const&) = default;
      UF(UF&&)                 = default;
      UF& operator=(UF&&)      = default;
      ~UF()                    = default;

      ////////////////////////////////////////////////////////////////////////
      // Union-Find
      ////////////////////////////////////////////////////////////////////////

      // not noexcept because std::array::operator[] and
      // std::vector::operator[] aren't
      index_type find(index_type x) const {
        LIBSEMIGROUPS_ASSERT(x < _data.size());
        while (true) {
          index_type y = index(_data[x]);
          LIBSEMIGROUPS_ASSERT(0 <= y && y < _data.size());
          if (y == x) {
            return y;
          }
          index_type z = index(_data[y]);
          LIBSEMIGROUPS_ASSERT(0 <= z && z < _data.size());
          if (y == z) {
            return y;
          }
          _data[x] = node(z) | rank(_data[x]);
          x        = z;
        }
      }

      // not noexcept because UF::find isn't
      void unite(index_type x, index_type y) {
        LIBSEMIGROUPS_ASSERT(x < _data.size());
        LIBSEMIGROUPS_ASSERT(y < _data.size());
        x = find(x);
        y = find(y);
        if (x == y) {
          return;
        }
        rank_type rx = rank(_data[x]);
        rank_type ry = rank(_data[y]);
        if (rx > ry) {
          _data[y] = node(x) | ry;
        } else {
          _data[x] = node(y) | rx;
          if (rx == ry) {
            _data[y] = node(y) | (ry + 1);
          }
        }
      }

      ////////////////////////////////////////////////////////////////////////
      // operators
      ////////////////////////////////////////////////////////////////////////

      // not noexcept because UF::contains isn't
      bool operator==(UF const& that) const {
        return contains(that) && that.contains(*this);
      }

      // not noexcept because UF::operator== isn't
      bool operator!=(UF const& that) const {
        return !(*this == that);
      }

      // not noexcept because find isn't
      // if this contains that
      bool contains(UF const& that) const {
        LIBSEMIGROUPS_ASSERT(size() == that.size());
        // reps of that to reps of this
        std::unordered_map<index_type, index_type> lookup;

        for (index_type i = 0; i < size(); ++i) {
          index_type j  = that.find(i);
          auto       it = lookup.find(j);
          if (it == lookup.end()) {
            lookup.emplace(j, find(i));
          } else if (it->second != find(i)) {
            return false;
          }
        }
        return true;
      }

      ////////////////////////////////////////////////////////////////////////
      // Container like
      ////////////////////////////////////////////////////////////////////////

      // noexcept because std::array::size and std::vector::size are noexcept
      size_type size() const noexcept {
        return _data.size();
      }

      // noexcept because std::array::empty and std::vector::empty are noexcept
      bool empty() const noexcept {
        return _data.empty();
      }

      // not noexcept because std::array::operator[] and
      // std::vector::operator[] aren't
      size_type number_of_blocks() const {
        size_type count = 0;
        for (index_type i = 0; i < _data.size(); ++i) {
          if (index(_data[i]) == i) {
            count++;
          }
        }
        return count;
      }

      ////////////////////////////////////////////////////////////////////////
      // Modifiers
      ////////////////////////////////////////////////////////////////////////

      // not noexcept because std::array::operator[] and
      // std::vector::operator[] aren't
      void compress() {
        for (index_type i = 0; i < _data.size(); ++i) {
          index_type j  = find(index(_data[i]));
          rank_type  rk = (j == i ? 0 : 1);
          _data[i]      = node(j) | rk;
        }
      }

      // not noexcept because compress isn't
      void normalize() {
        compress();
        // old -> new class indexing
        std::unordered_map<index_type, index_type> lookup;
        container_type                             data;
        set_data_capacity(data, size());
        for (index_type i = 0; i < size(); ++i) {
          index_type j  = find(i);
          auto       it = lookup.find(j);
          if (it == lookup.end()) {
            lookup.emplace(j, i);
            data[i] = node(i);  // rank 0
          } else {
            data[i] = node(it->second) | 1;
          }
        }
        std::swap(_data, data);
      }

      // not noexcept because unite isn't
      void join(UF const& that) {
        LIBSEMIGROUPS_ASSERT(size() == that.size());
        for (index_type i = 0; i < _data.size(); ++i) {
          unite(index(_data[i]), index(that._data[i]));
        }
      }

      void swap(UF& that) noexcept {
        std::swap(_data, that._data);
      }

      ////////////////////////////////////////////////////////////////////////
      // Iterators
      ////////////////////////////////////////////////////////////////////////

      struct IteratorTraits : ConstIteratorTraits<container_type> {
        using internal_iterator_type = typename ConstIteratorTraits<
            container_type>::internal_iterator_type;
        using state_type = std::pair<internal_iterator_type,   // _data.cbegin()
                                     internal_iterator_type>;  // _data.cend()
        using value_type = index_type;
        using reference  = value_type;
        using const_reference   = value_type const;
        using const_pointer     = value_type const*;
        using pointer           = value_type*;
        using iterator_category = std::bidirectional_iterator_tag;

        struct Deref {
          value_type operator()(state_type, internal_iterator_type const& it)
              const noexcept {
            return index(*it);
          }
        };

        struct PrefixIncrement {
          void operator()(state_type const&       st,
                          internal_iterator_type& it) const noexcept {
            index_type i = std::distance(st.first, it);
            do {
              ++it;
              ++i;
            } while (it != st.second && index(*it) != i);
          }
        };

        struct PrefixDecrement {
          void operator()(state_type const&       st,
                          internal_iterator_type& it) const noexcept {
            index_type i = std::distance(st.first, it);
            do {
              --it;
              --i;
            } while (it != st.first && index(*it) != i);
          }
        };
      };

      using const_iterator = detail::ConstIteratorStateful<IteratorTraits>;
      using const_reverse_iterator = std::reverse_iterator<const_iterator>;

      // not noexcept because std::array::operator[] and
      // std::vector::operator[] aren't
      const_iterator cbegin() const {
        auto it = const_iterator(std::make_pair(_data.cbegin(), _data.cend()),
                                 _data.cbegin());
        return (index(_data[0]) == 0 ? it : ++it);
      }

      // not noexcept because std::array::operator[] and
      // std::vector::operator[] aren't
      const_iterator cend() const {
        return const_iterator(std::make_pair(_data.cbegin(), _data.cend()),
                              _data.cend());
      }

      // not noexcept because cend() isn't
      const_reverse_iterator crbegin() const {
        return const_reverse_iterator(cend());
      }

      // not noexcept because cbegin() isn't
      const_reverse_iterator crend() const {
        return const_reverse_iterator(cbegin());
      }

      struct DataIteratorTraits : ConstIteratorTraits<container_type> {
        using internal_iterator_type = typename ConstIteratorTraits<
            container_type>::internal_iterator_type;
        using value_type      = index_type;
        using reference       = value_type;
        using const_reference = value_type const;
        using const_pointer   = value_type const*;
        using pointer         = value_type*;

        struct Deref {
          value_type
          operator()(internal_iterator_type const& it) const noexcept {
            return index(*it);
          }
        };
      };

      using const_data_iterator
          = detail::ConstIteratorStateless<DataIteratorTraits>;

      // noexcept because _data.cbegin is noexcept
      const_data_iterator cbegin_data() const noexcept {
        return const_data_iterator(_data.cbegin());
      }

      // noexcept because _data.cend is noexcept
      const_data_iterator cend_data() const noexcept {
        return const_data_iterator(_data.cend());
      }

      struct RankIteratorTraits : ConstIteratorTraits<container_type> {
        using internal_iterator_type = typename ConstIteratorTraits<
            container_type>::internal_iterator_type;
        using value_type      = rank_type;
        using reference       = value_type;
        using const_reference = value_type const;
        using const_pointer   = value_type const*;
        using pointer         = value_type*;

        struct Deref {
          value_type
          operator()(internal_iterator_type const& it) const noexcept {
            return rank(*it);
          }
        };
      };

      using const_rank_iterator
          = detail::ConstIteratorStateless<RankIteratorTraits>;

      // noexcept because _data.cbegin is noexcept
      const_rank_iterator cbegin_rank() const noexcept {
        return const_rank_iterator(_data.cbegin());
      }

      // noexcept because _data.cbegin is noexcept
      const_rank_iterator cend_rank() const noexcept {
        return const_rank_iterator(_data.cend());
      }

      size_t hash() const {
        return Hash<container_type>()(_data);
      }

     private:
      ////////////////////////////////////////////////////////////////////////
      // Private
      ////////////////////////////////////////////////////////////////////////

      static constexpr index_type rank_mask
          = ((index_type(1) << RANK_BITS) - index_type(1));

      static inline rank_type rank(node_type i) noexcept {
        return i & rank_mask;
      }

      static inline node_type node(index_type i) noexcept {
        return i << RANK_BITS;
      }

      static inline index_type index(node_type i) noexcept {
        return i >> RANK_BITS;
      }

      template <typename SFINAE = void>
      static auto set_data_capacity(container_type& data, size_t N)
          -> std::enable_if_t<
              std::is_base_of<std::vector<node_type>, container_type>::value,
              SFINAE> {
        data.resize(N, 0);
      }

      template <typename SFINAE = void>
      static auto set_data_capacity(container_type&, size_t const)
          -> std::enable_if_t<
              !std::is_base_of<std::vector<node_type>, container_type>::value,
              SFINAE> {}

     protected:
      ////////////////////////////////////////////////////////////////////////
      // Protected
      ////////////////////////////////////////////////////////////////////////

      // not noexcept because std::for_each can throw
      static void init_data(typename container_type::iterator first,
                            typename container_type::iterator last) {
        std::for_each(first, last, [](index_type& i) { i = node(i); });
      }

      mutable container_type _data;
    };

    template <typename T>
    inline void swap(UF<T>& x, UF<T>& y) noexcept {
      x.swap(y);
    }

    // Dynamic Union-Find
    template <typename T = size_t>
    class Duf : public UF<std::vector<T>> {
     public:
      using UF<std::vector<T>>::UF;
      using size_type = typename UF<std::vector<T>>::size_type;
      // not noexcept because std::vector::resize can throw
      void resize(size_type N) {
        size_type const M = this->size();
        if (N <= M) {
          return;
        }
        this->_data.resize(N);
        std::iota(this->_data.begin() + M, this->_data.end(), M);
        this->init_data(this->_data.begin() + M, this->_data.end());
      }
    };

    // Static Union-Find
    template <size_t N,
              typename T =
                  typename SmallestInteger<N*(RANK_BITS == 5 ? 32 : 64)>::type>
    using Suf = UF<std::array<T, N>>;
  }  // namespace detail

  template <typename T>
  struct Hash<detail::Duf<T>> {
    size_t operator()(detail::Duf<T> const& x) const {
      return x.hash();
    }
  };
}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_UF_HPP_

quality92%

¤ Dauer der Verarbeitung: 0.14 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.