linear_arrangement.hpp

/*********************************************************************
 *
 * Linear Arrangement Library - A library that implements a collection
 * algorithms for linear arrangments of graphs.
 *
 * Copyright (C) 2019 - 2024
 *
 * This file is part of Linear Arrangement Library. The full code is available
 * at:
 *      https://github.com/LAL-project/linear-arrangement-library.git
 *
 * Linear Arrangement Library is free software: you can redistribute it
 * and/or modify it under the terms of the GNU Affero General Public License
 * as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Linear Arrangement Library 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 Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Linear Arrangement Library.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Contact:
 *
 *     Lluís Alemany Puig (lluis.alemany.puig@upc.edu)
 *         LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/lalemany/
 *
 *     Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
 *         LQMC (Quantitative, Mathematical, and Computational Linguisitcs)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Office 220, Omega building
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/rferrericancho/
 *
 ********************************************************************/
 
#pragma once
 
// C++ includes
#if defined DEBUG
#include <cassert>
#endif
#include <vector>
 
// lal includes
#include <lal/basic_types.hpp>
#include <lal/detail/array.hpp>
 
namespace lal {
 
class linear_arrangement {
public:
    linear_arrangement() noexcept = default;
    linear_arrangement(std::size_t n) noexcept
        : m_memory(2*n, n+1),
          m_n{n},
          m_direct{m_memory.begin()},
          m_inverse{m_memory.begin() + m_n}
    { }
 
    linear_arrangement(const std::vector<position>& dir_arr) noexcept
        : m_memory(2*dir_arr.size()),
          m_n{dir_arr.size()},
          m_direct{m_memory.begin()},
          m_inverse{m_memory.begin() + m_n}
    {
        // construct m_direct and m_inverse
        from_data<true>(dir_arr.begin(), dir_arr.end());
    }
 
    linear_arrangement(const linear_arrangement& arr) noexcept
        : m_memory(arr.m_memory),
          m_n{arr.m_n},
          m_direct{m_memory.begin()},
          m_inverse{m_memory.begin() + m_n}
    { }
    linear_arrangement& operator= (const linear_arrangement& arr) noexcept {
        m_memory = arr.m_memory;
        m_n = arr.m_n;
        m_direct = m_memory.begin();
        m_inverse = m_memory.begin() + m_n;
        return *this;
    }
 
    linear_arrangement& operator= (const std::vector<position>& dir_arr) noexcept {
        m_memory.resize(2*dir_arr.size());
        m_n = dir_arr.size();
        m_direct = m_memory.begin();
        m_inverse = m_memory.begin() + m_n;
        // construct m_direct and m_inverse
        from_data<true>(dir_arr.begin(), dir_arr.end());
        return *this;
    }
 
    linear_arrangement(linear_arrangement&& arr) noexcept
        : m_memory(std::move(arr.m_memory)),
          m_n{arr.m_n},
          m_direct{std::move(arr.m_direct)},
          m_inverse{std::move(arr.m_inverse)}
    {
        // invalidate data
        arr.m_n = 0;
        arr.m_direct = nullptr;
        arr.m_inverse = nullptr;
    }
    linear_arrangement& operator= (linear_arrangement&& arr) noexcept {
        // steal data
        m_memory = std::move(arr.m_memory);
        m_n = arr.m_n;
        m_direct = arr.m_direct;
        m_inverse = arr.m_inverse;
        // invalidate data
        arr.m_n = 0;
        arr.m_direct = nullptr;
        arr.m_inverse = nullptr;
        return *this;
    }
 
    virtual ~linear_arrangement() noexcept = default;
 
    static linear_arrangement from_direct(const std::vector<position>& v) noexcept {
        return from_direct(v.begin(), v.end(), v.size());
    }
 
#if !defined __LAL_SWIG_PYTHON
    template <typename It>
    static linear_arrangement from_direct(It begin, It end) noexcept {
        return from_direct(begin, end, std::distance(begin, end));
    }
 
    template <typename It>
    static linear_arrangement from_direct(It begin, It end, std::size_t size) noexcept {
        linear_arrangement arr(size);
        arr.from_data<true>(begin, end);
        return arr;
    }
#endif
 
    static linear_arrangement from_inverse(const std::vector<node>& v) noexcept {
        return from_inverse(v.begin(), v.end(), v.size());
    }
 
#if !defined __LAL_SWIG_PYTHON
    template <typename It>
    static linear_arrangement from_inverse(It begin, It end) noexcept {
        return from_inverse(
            begin, end,
            static_cast<std::size_t>(std::distance(begin, end))
        );
    }
 
    template <typename It>
    static linear_arrangement from_inverse(It begin, It end, std::size_t size) noexcept {
        linear_arrangement arr(size);
        arr.from_data<false>(begin, end);
        return arr;
    }
#endif
 
    bool operator< (const linear_arrangement& arr) const noexcept {
        if (size() != arr.size()) { return size() < arr.size(); }
 
        for (std::size_t i = 0; i < size() - 1; ++i) {
            if (m_direct[i] != arr.m_direct[i]) {
                return m_direct[i] < arr.m_direct[i];
            }
        }
        return m_direct[size() - 1] < arr.m_direct[size() - 1];
    }
 
    position operator[] (const node_t& u) const noexcept
    { return get_position_of(*u); }
 
    node operator[] (const position_t& p) const noexcept
    { return get_node_at(*p); }
 
    void clear() noexcept {
        m_memory.clear();
        m_n = 0;
        m_direct = nullptr;
        m_inverse = nullptr;
    }
 
    position get_position_of(const node u) const noexcept
    { return m_direct[u]; }
 
    node get_node_at(const position p) const noexcept
    { return m_inverse[p]; }
 
    void resize(std::size_t n) noexcept {
        m_memory.resize(2*n, n + 1);
        m_n = n;
        set_pointers();
    }
 
    template <
        typename NODE, typename POSITION,
        std::enable_if_t<
            (std::is_integral_v<NODE> or std::is_same_v<NODE, node_t>)
            and
            (std::is_integral_v<POSITION> or std::is_same_v<POSITION, position_t>)
        ,
        bool> = true
    >
    void assign(const NODE u, const POSITION p) noexcept {
#if defined DEBUG
        assert(u < m_n);
        assert(p < m_n);
#endif
        if constexpr (std::is_same_v<NODE, node_t> and std::is_same_v<POSITION, position_t>) {
            m_direct[*u] = *p;
            m_inverse[*p] = *u;
        }
        else if constexpr (std::is_same_v<NODE, node_t>) {
            m_direct[*u] = p;
            m_inverse[p] = *u;
        }
        else if constexpr (std::is_same_v<POSITION, position_t>) {
            m_direct[u] = *p;
            m_inverse[*p] = u;
        }
        else {
            m_direct[u] = p;
            m_inverse[p] = u;
        }
    }
 
    template <
        typename what,
        std::enable_if_t<
            std::is_same_v<what, node_t> or std::is_same_v<what, position_t>
        ,
        bool> = true
    >
    void swap(const what u_t, const what v_t) noexcept {
        if constexpr (std::is_same_v<what, node_t>) {
            // swap vertices
            const position pu = m_direct[*u_t];
            const position pv = m_direct[*v_t];
            assign(u_t, pv);
            assign(v_t, pu);
        }
        else {
            // swap positions
            const node u = m_inverse[*u_t];
            const node v = m_inverse[*v_t];
            assign(u, v_t);
            assign(v, u_t);
        }
    }
 
    void shift_left() noexcept {
        const node_t u0 = m_inverse[0];
        // shift every vertex one position to the left
        for (position pu = 0; pu < m_n - 1; ++pu) {
            const node u = get_node_at(pu + 1);
            assign(u, pu);
        }
        // put the first vertex at the last position
        assign(u0, m_n - 1);
    }
 
    void shift_right() noexcept {
        const node_t ulast = m_inverse[m_n - 1];
        // shift every vertex one position to the left
        for (position pu = m_n - 1; pu > 0; --pu) {
            const node u = get_node_at(pu - 1);
            assign(u, pu);
        }
        // put the last vertex at the first position
        assign(ulast, 0ull);
    }
 
    void mirror() noexcept {
        for (position_t i = 0ull; i < m_n/2; ++i) {
            swap(i, m_n - 1ull - i);
        }
    }
 
    std::size_t size() const noexcept { return m_n; }
 
    static linear_arrangement identity(std::size_t n) noexcept
    {
        linear_arrangement arr(n);
        arr.identity();
        return arr;
    }
 
    void identity() noexcept {
        for (std::size_t i = 0; i < m_n; ++i) { assign(i,i); }
    }
 
    void update_direct() noexcept {
        for (position pu = 0; pu < m_n; ++pu) {
            m_direct[ m_inverse[pu] ] = pu;
        }
    }
 
    void update_inverse() noexcept {
        for (node u = 0; u < m_n; ++u) {
            m_inverse[ m_direct[u] ] = u;
        }
    }
 
    node *begin_direct() noexcept { return m_direct; }
    const node *begin_direct() const noexcept { return m_direct; }
    node *end_direct() noexcept { return m_direct + m_n; }
    const node *end_direct() const noexcept { return m_direct + m_n; }
 
    node *begin_inverse() noexcept { return m_inverse; }
    const node *begin_inverse() const noexcept { return m_inverse; }
    node *end_inverse() noexcept { return m_inverse + m_n; }
    const node *end_inverse() const noexcept { return m_inverse + m_n; }
 
    std::vector<position> direct_as_vector() const noexcept
    { return {begin_direct(), end_direct()}; }
 
    std::vector<node> inverse_as_vector() const noexcept
    { return {begin_inverse(), end_inverse()}; }
 
private:
 
    void set_pointers() noexcept {
        m_direct = m_memory.begin();
        m_inverse = m_memory.begin() + m_n;
    }
 
    template <bool from_direct_arr, typename It>
    void from_data(const It begin, const It end) noexcept
    {
#if defined DEBUG
        assert(m_direct != nullptr);
        assert(m_inverse != nullptr);
#endif
        std::size_t i = 0;
        if constexpr (from_direct_arr) {
            for (It it = begin; it != end; ++it, ++i) {
                m_direct[i] = *it;
                m_inverse[*it] = i;
            }
        }
        else {
            for (It it = begin; it != end; ++it, ++i) {
                m_direct[*it] = i;
                m_inverse[i] = *it;
            }
        }
    }
 
protected:
    detail::array<uint64_t> m_memory;
    std::size_t m_n = 0;
 
    position *m_direct = nullptr;
    node *m_inverse = nullptr;
};
 
} // -- namespace lal