simple_cycle.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2013 Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_SIMPLE_CYCLE_HPP
#define PAAL_SIMPLE_CYCLE_HPP

#include "paal/data_structures/bimap.hpp"

#include <cassert>
#include <vector>
#include <iterator>

namespace paal {
namespace data_structures {

template <typename CycleEl, typename IdxT = int> class simple_cycle {
  public:
    using cycle_el_pair = std::pair<CycleEl, CycleEl>;
    using cycle_element = CycleEl;

    template <typename Iter> simple_cycle(Iter begin, Iter end) {
        if (begin == end) {
            return;
        }

        std::size_t size = std::distance(begin, end);

        m_predecessor_map.reserve(size);
        m_successor_map.reserve(size);

        IdxT prev_idx = add(*(begin++));
        IdxT firstIdx = prev_idx;
        for (; begin != end; ++begin) {
            IdxT lastIdx = add(*begin);
            link(prev_idx, lastIdx);
            prev_idx = lastIdx;
        }
        link(prev_idx, firstIdx);
    }

    void flip(const CycleEl &begin, const CycleEl &end) {
        IdxT e1 = to_idx(begin);
        IdxT b1 = prev_idx(e1);
        IdxT b2 = to_idx(end);
        IdxT e2 = next_idx(b2);

        partial_reverse(b2, e1);
        link(b1, b2);
        link(e1, e2);
    }

    std::size_t size() const { return m_predecessor_map.size(); }

    CycleEl next(const CycleEl &ce) const {
        return from_idx(next_idx(to_idx(ce)));
    }

    // TODO use iterator_fascade
    class vertex_iterator
        : public std::iterator<std::forward_iterator_tag, CycleEl, ptrdiff_t,
                               CycleEl *, const CycleEl &> {
      public:

        vertex_iterator(const simple_cycle &cm, CycleEl ce)
            : m_cycle(&cm), m_idx(m_cycle->to_idx(ce)), m_first(m_idx) {}

        vertex_iterator() : m_cycle(NULL), m_idx(-1) {}

        vertex_iterator &operator++() {
            m_idx = next_idx(m_idx);

            if (m_idx == m_first) {
                m_idx = -1;
            }

            return *this;
        }

        vertex_iterator operator++(int) {
            vertex_iterator i(*this);
            operator++();
            return i;
        }

        bool operator!=(vertex_iterator ei) const { return !operator==(ei); }

        bool operator==(vertex_iterator ei) const { return m_idx == ei.m_idx; }

        const CycleEl *const operator->() const { return &operator*(); }

        const CycleEl &operator*() const { return m_cycle->from_idx(m_idx); }

      private:

        IdxT next_idx(IdxT i) const { return m_cycle->next_idx(i); }

        const simple_cycle *m_cycle;
        IdxT m_idx;
        IdxT m_first;
    };

    using vertices =  boost::iterator_range<vertex_iterator>;

    vertex_iterator vbegin(const CycleEl &el) const {
        return vertex_iterator(*this, el);
    }

    vertex_iterator vbegin() const { return vbegin(from_idx(0)); }

    vertex_iterator vend() const { return vertex_iterator(); }

    vertices get_vertices_range(const CycleEl &el) const {
        return vertices(vbegin(el), vend());
    }

    vertices get_vertices_range() const {
        return get_vertices_range(from_idx(0));
    }

    // TODO use iterator_fascade
    class edge_iterator
        : public std::iterator<std::forward_iterator_tag, cycle_el_pair,
                               ptrdiff_t, cycle_el_pair *, const cycle_el_pair &> {
      public:
        edge_iterator(const simple_cycle &cm, CycleEl ce)
            : m_cycle(&cm), m_idx(m_cycle->to_idx(ce)), m_first(m_idx) {

            move_curr();
        }

        edge_iterator() : m_cycle(NULL), m_idx(-1) {}

        edge_iterator &operator++() {
            m_idx = next_idx(m_idx);
            move_curr();

            if (m_idx == m_first) {
                m_idx = -1;
            }

            return *this;
        }

        edge_iterator operator++(int) {
            edge_iterator i(*this);
            operator++();
            return i;
        }

        bool operator!=(edge_iterator ei) const { return !operator==(ei); }

        bool operator==(edge_iterator ei) const { return m_idx == ei.m_idx; }

        const cycle_el_pair *const operator->() const { return &m_curr; }

        const cycle_el_pair &operator*() const { return m_curr; }

      private:
        void move_curr() {
            m_curr.first = m_cycle->from_idx(m_idx);
            m_curr.second = m_cycle->from_idx(next_idx(m_idx));
        }

        IdxT next_idx(IdxT i) const { return m_cycle->next_idx(i); }

        const simple_cycle *m_cycle;
        IdxT m_idx;
        IdxT m_first;
        cycle_el_pair m_curr;
    };

    using edges = boost::iterator_range<edge_iterator>;

    edges get_edge_range(const CycleEl &el) const {
        return edges(edge_iterator(*this, el), edge_iterator());
    }

    edges get_edge_range() const {
        return get_edge_range(from_idx(0));
    }

  protected:
    void link(IdxT x, IdxT y) {
        m_successor_map[x] = y;
        m_predecessor_map[y] = x;
    }

    void partial_reverse(IdxT x, IdxT y) {
        if (x == y) return;
        IdxT t_next = prev_idx(x);
        IdxT t;
        do {
            t = t_next;
            t_next = prev_idx(t);
            link(x, t);
            x = t;
        } while (t != y);
    }

    IdxT to_idx(const CycleEl &ce) const { return m_cycle_idx.get_idx(ce); }

    IdxT next_idx(IdxT i) const { return m_successor_map[i]; }

    IdxT prev_idx(IdxT i) const { return m_predecessor_map[i]; }

    const CycleEl &from_idx(IdxT i) const { return m_cycle_idx.get_val(i); }

    IdxT add(const CycleEl &el) {
        m_predecessor_map.push_back(-1);
        m_successor_map.push_back(-1);
        return m_cycle_idx.add(el);
    }

    bimap<CycleEl, IdxT> m_cycle_idx;

    using SorsMap = std::vector<IdxT>;

    SorsMap m_predecessor_map;
    SorsMap m_successor_map;
};

template <typename CycleEl, typename IdxT = int>
class Simplecycle_start_from_last_change : public simple_cycle<CycleEl, IdxT> {
    using Base = simple_cycle<CycleEl, IdxT>;

  public:
    template <typename Iter>
    Simplecycle_start_from_last_change(Iter b, Iter e)
        : Base(b, e), m_last_id(0) {}

    void flip(const CycleEl &begin, const CycleEl &end) {
        IdxT e1 = to_idx(begin);
        m_last_id = prev_idx(e1);
        Base::flip(begin, end);
    }

    typename Base::vertex_iterator vbegin() const {
        return Base::vbegin(from_idx(m_last_id));
    }

  private:
    IdxT m_last_id;
};

} // data_structures
} // paal

#endif // PAAL_SIMPLE_CYCLE_HPP