You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
407 lines
12 KiB
407 lines
12 KiB
#pragma once
|
|
|
|
#include "compressed_vector_tuple.hpp"
|
|
#include "../../utils/pointer_wrapper.hpp"
|
|
|
|
namespace detail::monotic_graph
|
|
{
|
|
template <typename Graph>
|
|
class edge_iterator;
|
|
|
|
template <typename Graph>
|
|
class node_proxy;
|
|
|
|
template <typename Graph>
|
|
class node_container_proxy;
|
|
|
|
template <typename Graph>
|
|
class edge_proxy
|
|
{
|
|
friend class edge_iterator<Graph>;
|
|
using index_type = typename Graph::index_type;
|
|
using edge_property_type = typename Graph::edge_property_type;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_edge_index{};
|
|
|
|
public:
|
|
node_proxy<Graph> to()
|
|
{
|
|
const auto to = m_graph_ptr->m_edges.template fetch<0>(m_edge_index).to;
|
|
assert(to == Graph::invalid_index);
|
|
return node_proxy<Graph>(m_graph_ptr, static_cast<index_type>(to));
|
|
}
|
|
|
|
node_proxy<Graph> to() const
|
|
{
|
|
const auto to = m_graph_ptr->m_edges.template fetch<0>(m_edge_index).to;
|
|
assert(to == Graph::invalid_index);
|
|
return node_proxy<Graph>(m_graph_ptr, static_cast<index_type>(to));
|
|
}
|
|
|
|
edge_property_type& property()
|
|
{
|
|
static_assert(Graph::has_edge_property, "called monotic graph does not have edge property.");
|
|
return m_graph_ptr->m_edges.template fetch<1>(m_edge_index);
|
|
}
|
|
|
|
const edge_property_type& property() const
|
|
{
|
|
static_assert(Graph::has_edge_property, "called monotic graph does not have edge property.");
|
|
return m_graph_ptr->m_edges.template fetch<1>(m_edge_index);
|
|
}
|
|
};
|
|
|
|
template <typename Graph>
|
|
class edge_iterator
|
|
{
|
|
using index_type = typename Graph::index_type;
|
|
static constexpr auto invalid_index = Graph::invalid_index;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_edge_index{};
|
|
|
|
public:
|
|
using iterator_category = std::forward_iterator_tag;
|
|
using value_type = edge_proxy<Graph>;
|
|
using difference_type = std::ptrdiff_t;
|
|
using pointer = value_type*;
|
|
using reference = value_type;
|
|
|
|
bool operator==(const edge_iterator& other) const
|
|
{
|
|
return m_graph_ptr == other.m_graph_ptr && m_edge_index == other.m_edge_index;
|
|
}
|
|
|
|
bool operator!=(const edge_iterator& other) const { return !(*this == other); }
|
|
|
|
edge_proxy<Graph> operator*() const { return edge_proxy<Graph>(m_graph_ptr, m_edge_index); }
|
|
|
|
edge_proxy<Graph> operator->() const { return edge_proxy<Graph>(m_graph_ptr, m_edge_index); }
|
|
|
|
edge_iterator& operator++()
|
|
{
|
|
if (m_edge_index != invalid_index) { m_edge_index = m_graph_ptr->m_edges.template fetch<0>(m_edge_index).next; }
|
|
return *this;
|
|
}
|
|
|
|
edge_iterator operator++(int)
|
|
{
|
|
edge_iterator tmp = *this;
|
|
++(*this);
|
|
return tmp;
|
|
}
|
|
};
|
|
|
|
template <typename Graph>
|
|
class edge_range
|
|
{
|
|
using index_type = typename Graph::index_type;
|
|
static constexpr auto invalid_index = Graph::invalid_index;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_edge_index{};
|
|
|
|
public:
|
|
bool empty() const { return begin() == end(); }
|
|
|
|
edge_iterator<Graph> begin() { return edge_iterator<Graph>(m_graph_ptr, m_edge_index); }
|
|
|
|
edge_iterator<Graph> end() { return edge_iterator<Graph>(m_graph_ptr, invalid_index); }
|
|
|
|
edge_iterator<Graph> begin() const { return edge_iterator<Graph>(m_graph_ptr, m_edge_index); }
|
|
|
|
edge_iterator<Graph> end() const { return edge_iterator<Graph>(m_graph_ptr, invalid_index); }
|
|
};
|
|
|
|
template <typename Graph>
|
|
class node_proxy
|
|
{
|
|
friend class node_container_proxy<Graph>;
|
|
using index_type = typename Graph::index_type;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_node_index{};
|
|
|
|
public:
|
|
auto index() const { return m_node_index; }
|
|
|
|
auto& property()
|
|
{
|
|
static_assert(Graph::has_node_property, "called monotic graph does not have node property.");
|
|
return m_graph_ptr->m_nodes.template fetch<1>(m_node_index);
|
|
}
|
|
|
|
auto& property() const
|
|
{
|
|
static_assert(Graph::has_node_property, "called monotic graph does not have node property.");
|
|
return m_graph_ptr->m_nodes.template fetch<1>(m_node_index);
|
|
}
|
|
|
|
edge_range<Graph> edges()
|
|
{
|
|
return edge_range<Graph>(m_graph_ptr, m_graph_ptr->m_nodes.template fetch<0>(m_node_index).first_edge);
|
|
}
|
|
|
|
edge_range<Graph> edges() const
|
|
{
|
|
return edge_range<Graph>(m_graph_ptr, m_graph_ptr->m_nodes.template fetch<0>(m_node_index).first_edge);
|
|
}
|
|
};
|
|
|
|
template <typename Graph>
|
|
bool operator==(const node_proxy<Graph>& lhs, const node_proxy<Graph>& rhs)
|
|
{
|
|
return lhs.m_graph_ptr == rhs.m_graph_ptr && lhs.m_node_index == rhs.m_node_index;
|
|
}
|
|
|
|
template <typename Graph>
|
|
class node_iterator
|
|
{
|
|
using index_type = typename Graph::index_type;
|
|
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
index_type m_node_index{};
|
|
|
|
public:
|
|
using iterator_category = std::random_access_iterator_tag;
|
|
using value_type = node_proxy<Graph>;
|
|
using difference_type = std::ptrdiff_t;
|
|
using pointer = value_type*;
|
|
using reference = value_type;
|
|
|
|
bool operator==(const node_iterator& other) const
|
|
{
|
|
return m_graph_ptr == other.m_graph_ptr && m_node_index == other.m_node_index;
|
|
}
|
|
|
|
bool operator!=(const node_iterator& other) const { return !(*this == other); }
|
|
|
|
bool operator<(const node_iterator& other) const { return m_node_index < other.m_node_index; }
|
|
|
|
bool operator<=(const node_iterator& other) const { return m_node_index <= other.m_node_index; }
|
|
|
|
bool operator>(const node_iterator& other) const { return m_node_index > other.m_node_index; }
|
|
|
|
bool operator>=(const node_iterator& other) const { return m_node_index >= other.m_node_index; }
|
|
|
|
node_proxy<Graph> operator*() { return node_proxy<Graph>(m_graph_ptr, m_node_index); }
|
|
|
|
node_proxy<Graph> operator*() const { return node_proxy<Graph>(m_graph_ptr, m_node_index); }
|
|
|
|
node_proxy<Graph> operator->() { return node_proxy<Graph>(m_graph_ptr, m_node_index); }
|
|
|
|
node_proxy<Graph> operator->() const { return node_proxy<Graph>(m_graph_ptr, m_node_index); }
|
|
|
|
node_iterator& operator++()
|
|
{
|
|
++m_node_index;
|
|
return *this;
|
|
}
|
|
|
|
node_iterator operator++(int)
|
|
{
|
|
node_iterator tmp = *this;
|
|
++m_node_index;
|
|
return tmp;
|
|
}
|
|
|
|
node_iterator& operator--()
|
|
{
|
|
--m_node_index;
|
|
return *this;
|
|
}
|
|
|
|
node_iterator operator--(int)
|
|
{
|
|
node_iterator tmp = *this;
|
|
--m_node_index;
|
|
return tmp;
|
|
}
|
|
|
|
node_iterator& operator+=(difference_type n)
|
|
{
|
|
m_node_index += static_cast<index_type>(n);
|
|
return *this;
|
|
}
|
|
|
|
node_iterator& operator-=(difference_type n)
|
|
{
|
|
m_node_index -= static_cast<index_type>(n);
|
|
return *this;
|
|
}
|
|
|
|
node_iterator operator+(difference_type n) const
|
|
{
|
|
return node_iterator(m_graph_ptr, static_cast<index_type>(m_node_index + n));
|
|
}
|
|
|
|
node_iterator operator-(difference_type n) const
|
|
{
|
|
return node_iterator(m_graph_ptr, static_cast<index_type>(m_node_index - n));
|
|
}
|
|
|
|
difference_type operator-(const node_iterator& other) const
|
|
{
|
|
return static_cast<difference_type>(m_node_index) - static_cast<difference_type>(other.m_node_index);
|
|
}
|
|
|
|
node_proxy<Graph> operator[](difference_type n) const
|
|
{
|
|
return node_proxy<Graph>(m_graph_ptr, static_cast<index_type>(m_node_index + n));
|
|
}
|
|
};
|
|
|
|
template <typename Graph>
|
|
class node_container_proxy
|
|
{
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
|
|
public:
|
|
using iterator = node_iterator<Graph>;
|
|
using const_iterator = node_iterator<Graph>;
|
|
using index_type = typename Graph::index_type;
|
|
|
|
template <typename size_type>
|
|
void reserve(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
m_graph_ptr->m_nodes.reserve(static_cast<size_t>(size));
|
|
}
|
|
|
|
template <typename size_type>
|
|
void resize(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
m_graph_ptr->m_nodes.resize(static_cast<size_t>(size));
|
|
}
|
|
|
|
bool empty() const { return m_graph_ptr->m_nodes.empty(); }
|
|
|
|
auto size() const { return m_graph_ptr->m_nodes.size(); }
|
|
|
|
void clear() { return m_graph_ptr->m_nodes.clear(); }
|
|
|
|
void shrink_to_fit() { return m_graph_ptr->m_nodes.shrink_to_fit(); }
|
|
|
|
template <typename size_type>
|
|
node_proxy<Graph> operator[](size_type index)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
return node_proxy<Graph>(m_graph_ptr, static_cast<index_type>(index));
|
|
}
|
|
|
|
template <typename size_type>
|
|
node_proxy<Graph> operator[](size_type index) const
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
return node_proxy<Graph>(m_graph_ptr, static_cast<index_type>(index));
|
|
}
|
|
|
|
iterator begin() { return iterator(m_graph_ptr, 0); }
|
|
|
|
iterator end() { return iterator(m_graph_ptr, static_cast<index_type>(m_graph_ptr->m_nodes.size())); }
|
|
|
|
const_iterator begin() const { return const_iterator(m_graph_ptr, 0); }
|
|
|
|
const_iterator end() const { return const_iterator(m_graph_ptr, static_cast<index_type>(m_graph_ptr->m_nodes.size())); }
|
|
|
|
template <typename container>
|
|
void set_properties(container&& cont)
|
|
{
|
|
static_assert(Graph::has_node_property, "called monotic graph does not have node property.");
|
|
resize(cont.size());
|
|
m_graph_ptr->m_nodes.template raw<1>() = cont;
|
|
}
|
|
};
|
|
|
|
template <typename Graph>
|
|
class edge_container_proxy
|
|
{
|
|
pointer_wrapper<Graph> m_graph_ptr{};
|
|
|
|
public:
|
|
template <typename size_type>
|
|
void reserve(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
m_graph_ptr->m_edges.reserve(static_cast<size_t>(size));
|
|
}
|
|
|
|
template <typename size_type>
|
|
void resize(size_type size)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
m_graph_ptr->m_edges.resize(static_cast<size_t>(size));
|
|
}
|
|
|
|
bool empty() const { return m_graph_ptr->m_edges.empty(); }
|
|
|
|
auto size() const { return static_cast<typename Graph::size_type>(m_graph_ptr->m_edges.size()); }
|
|
|
|
void clear() { m_graph_ptr->m_edges.clear(); }
|
|
|
|
void shrink_to_fit() { m_graph_ptr->m_edges.shrink_to_fit(); }
|
|
};
|
|
|
|
template <typename IndexType, typename NodeProperty, typename EdgeProperty>
|
|
class graph
|
|
{
|
|
private:
|
|
static_assert(std::is_integral_v<IndexType>);
|
|
static constexpr auto invalid_index = std::numeric_limits<IndexType>::max();
|
|
|
|
struct node {
|
|
IndexType first_edge{invalid_index};
|
|
};
|
|
|
|
struct edge {
|
|
IndexType to{};
|
|
IndexType next{invalid_index};
|
|
};
|
|
|
|
compressed_vector_tuple<node, NodeProperty> m_nodes{};
|
|
compressed_vector_tuple<edge, EdgeProperty> m_edges{};
|
|
|
|
public:
|
|
using index_type = IndexType;
|
|
using node_property_type = NodeProperty;
|
|
using edge_property_type = EdgeProperty;
|
|
static constexpr bool has_node_property = !std::is_void_v<node_property_type>;
|
|
static constexpr bool has_edge_property = !std::is_void_v<edge_property_type>;
|
|
|
|
node_container_proxy<graph> nodes() { return node_container_proxy<graph>(this); }
|
|
|
|
node_container_proxy<graph> nodes() const { return node_container_proxy<graph>(this); }
|
|
|
|
edge_container_proxy<graph> edges() { return edge_container_proxy<graph>(this); }
|
|
|
|
edge_container_proxy<graph> edges() const { return edge_container_proxy<graph>(this); }
|
|
|
|
template <typename size_type, typename... Args>
|
|
void add_edge(size_type from, size_type to, Args&&... args)
|
|
{
|
|
static_assert(std::is_integral_v<size_type>);
|
|
static_assert(has_edge_property || sizeof...(args) == 0);
|
|
|
|
auto cur_edge_index = m_edges.template size<0>();
|
|
auto& next = m_nodes.template fetch<0>(from).first_edge;
|
|
|
|
m_edges.template emplace_back<0>(static_cast<index_type>(to), next);
|
|
if constexpr (has_edge_property) m_edges.template emplace_back<1>(std::forward<Args>(args)...);
|
|
|
|
next = static_cast<index_type>(cur_edge_index);
|
|
}
|
|
|
|
private:
|
|
friend class node_proxy<graph>;
|
|
friend class edge_proxy<graph>;
|
|
friend class edge_iterator<graph>;
|
|
friend class edge_range<graph>;
|
|
friend class node_container_proxy<graph>;
|
|
friend class edge_container_proxy<graph>;
|
|
};
|
|
} // namespace detail::monotic_graph
|
|
|
|
template <typename index_type, typename node_property = void, typename edge_property = void>
|
|
using monotic_graph = detail::monotic_graph::graph<index_type, node_property, edge_property>;
|