www.pudn.com > tristripper-1.1.0-beta-5.zip > graph_array.h
// // Copyright (C) 2004 Tanguy Fautré. // For conditions of distribution and use, // see copyright notice in tri_stripper.h // ////////////////////////////////////////////////////////////////////// // SVN: $Id: graph_array.h 86 2005-06-08 17:47:27Z gpsnoopy $ ////////////////////////////////////////////////////////////////////// #ifndef TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H #define TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H #include#include #include #include #include namespace triangle_stripper { namespace detail { // graph_array main class template class graph_array { public: class arc; class node; // New types typedef size_t nodeid; typedef nodetype value_type; typedef std::vector node_vector; typedef typename node_vector::iterator node_iterator; typedef typename node_vector::const_iterator const_node_iterator; typedef typename node_vector::reverse_iterator node_reverse_iterator; typedef typename node_vector::const_reverse_iterator const_node_reverse_iterator; typedef graph_array graph_type; // graph_array::arc class class arc { public: node_iterator terminal() const; protected: friend class graph_array ; arc(node_iterator Terminal); node_iterator m_Terminal; }; // New types typedef std::vector arc_list; typedef typename arc_list::iterator out_arc_iterator; typedef typename arc_list::const_iterator const_out_arc_iterator; // graph_array::node class class node { public: void mark(); void unmark(); bool marked() const; bool out_empty() const; size_t out_size() const; out_arc_iterator out_begin(); out_arc_iterator out_end(); const_out_arc_iterator out_begin() const; const_out_arc_iterator out_end() const; value_type & operator * (); value_type * operator -> (); const value_type & operator * () const; const value_type * operator -> () const; value_type & operator = (const value_type & Elem); protected: friend class graph_array ; friend class std::vector ; node(arc_list & Arcs); arc_list & m_Arcs; size_t m_Begin; size_t m_End; value_type m_Elem; bool m_Marker; }; graph_array(); explicit graph_array(size_t NbNodes); // Node related member functions bool empty() const; size_t size() const; node & operator [] (nodeid i); const node & operator [] (nodeid i) const; node_iterator begin(); node_iterator end(); const_node_iterator begin() const; const_node_iterator end() const; node_reverse_iterator rbegin(); node_reverse_iterator rend(); const_node_reverse_iterator rbegin() const; const_node_reverse_iterator rend() const; // Arc related member functions out_arc_iterator insert_arc(nodeid Initial, nodeid Terminal); out_arc_iterator insert_arc(node_iterator Initial, node_iterator Terminal); // Optimized (overloaded) functions void swap(graph_type & Right); friend void swap(graph_type & Left, graph_type & Right) { Left.swap(Right); } protected: graph_array(const graph_type &); graph_type & operator = (const graph_type &); node_vector m_Nodes; arc_list m_Arcs; }; // Additional "low level", graph related, functions template void unmark_nodes(graph_array & G); ////////////////////////////////////////////////////////////////////////// // graph_array::arc inline functions ////////////////////////////////////////////////////////////////////////// template inline graph_array ::arc::arc(node_iterator Terminal) : m_Terminal(Terminal) { } template inline typename graph_array ::node_iterator graph_array ::arc::terminal() const { return m_Terminal; } ////////////////////////////////////////////////////////////////////////// // graph_array::node inline functions ////////////////////////////////////////////////////////////////////////// template inline graph_array ::node::node(arc_list & Arcs) : m_Arcs(Arcs), m_Begin(std::numeric_limits ::max()), m_End(std::numeric_limits ::max()), m_Marker(false) { } template inline void graph_array ::node::mark() { m_Marker = true; } template inline void graph_array ::node::unmark() { m_Marker = false; } template inline bool graph_array ::node::marked() const { return m_Marker; } template inline bool graph_array ::node::out_empty() const { return (m_Begin == m_End); } template inline size_t graph_array ::node::out_size() const { return (m_End - m_Begin); } template inline typename graph_array ::out_arc_iterator graph_array ::node::out_begin() { return (m_Arcs.begin() + m_Begin); } template inline typename graph_array ::out_arc_iterator graph_array ::node::out_end() { return (m_Arcs.begin() + m_End); } template inline typename graph_array ::const_out_arc_iterator graph_array ::node::out_begin() const { return (m_Arcs.begin() + m_Begin); } template inline typename graph_array ::const_out_arc_iterator graph_array ::node::out_end() const { return (m_Arcs.begin() + m_End); } template inline N & graph_array ::node::operator * () { return m_Elem; } template inline N * graph_array ::node::operator -> () { return &m_Elem; } template inline const N & graph_array ::node::operator * () const { return m_Elem; } template inline const N * graph_array ::node::operator -> () const { return &m_Elem; } template inline N & graph_array ::node::operator = (const N & Elem) { return (m_Elem = Elem); } ////////////////////////////////////////////////////////////////////////// // graph_array inline functions ////////////////////////////////////////////////////////////////////////// template inline graph_array ::graph_array() { } template inline graph_array ::graph_array(const size_t NbNodes) : m_Nodes(NbNodes, node(m_Arcs)) { // optimisation: we consider that, averagely, a triangle may have at least 2 neighbours // otherwise we are just wasting a bit of memory, but not that much m_Arcs.reserve(NbNodes * 2); } template inline bool graph_array ::empty() const { return m_Nodes.empty(); } template inline size_t graph_array ::size() const { return m_Nodes.size(); } template inline typename graph_array ::node & graph_array ::operator [] (const nodeid i) { assert(i < size()); return m_Nodes[i]; } template inline const typename graph_array ::node & graph_array ::operator [] (const nodeid i) const { assert(i < size()); return m_Nodes[i]; } template inline typename graph_array ::node_iterator graph_array ::begin() { return m_Nodes.begin(); } template inline typename graph_array ::node_iterator graph_array ::end() { return m_Nodes.end(); } template inline typename graph_array ::const_node_iterator graph_array ::begin() const { return m_Nodes.begin(); } template inline typename graph_array ::const_node_iterator graph_array ::end() const { return m_Nodes.end(); } template inline typename graph_array ::node_reverse_iterator graph_array ::rbegin() { return m_Nodes.rbegin(); } template inline typename graph_array ::node_reverse_iterator graph_array ::rend() { return m_Nodes.rend(); } template inline typename graph_array ::const_node_reverse_iterator graph_array ::rbegin() const { return m_Nodes.rbegin(); } template inline typename graph_array ::const_node_reverse_iterator graph_array ::rend() const { return m_Nodes.rend(); } template inline typename graph_array ::out_arc_iterator graph_array ::insert_arc(const nodeid Initial, const nodeid Terminal) { assert(Initial < size()); assert(Terminal < size()); return insert_arc(m_Nodes.begin() + Initial, m_Nodes.begin() + Terminal); } template inline typename graph_array ::out_arc_iterator graph_array ::insert_arc(const node_iterator Initial, const node_iterator Terminal) { assert((Initial >= begin()) && (Initial < end())); assert((Terminal >= begin()) && (Terminal < end())); node & Node = * Initial; if (Node.out_empty()) { Node.m_Begin = m_Arcs.size(); Node.m_End = m_Arcs.size() + 1; } else { // we optimise here for make_connectivity_graph() // we know all the arcs for a given node are successively and sequentially added assert(Node.m_End == m_Arcs.size()); ++(Node.m_End); } m_Arcs.push_back(arc(Terminal)); out_arc_iterator it = m_Arcs.end(); return (--it); } template inline void graph_array ::swap(graph_type & Right) { std::swap(m_Nodes, Right.m_Nodes); std::swap(m_Arcs, Right.m_Arcs); } ////////////////////////////////////////////////////////////////////////// // additional functions ////////////////////////////////////////////////////////////////////////// template inline void unmark_nodes(graph_array & G) { std::for_each(G.begin(), G.end(), std::mem_fun_ref(&graph_array ::node::unmark)); } } // namespace detail } // namespace triangle_stripper #endif // TRI_STRIPPER_HEADER_GUARD_GRAPH_ARRAY_H