Rosetta  2020.37
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Private Member Functions | Private Attributes | List of all members
utility::graph::EdgeList Class Reference

Custom edge list class. Returns const-iterators which only return Edge const *'s and non-const-iterators which can return either const or non-const Edge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of EdgeListElements. Implemented as a doubly linked list, though there's no practical way to start at the end of a list and work backward since decrementing the end iterator is not a valid operation. More...

#include <Graph.hh>

Public Member Functions

 EdgeList (boost::unordered_object_pool< EdgeListElement > &edge_list_element_pool)
 
 ~EdgeList ()
 
void push_back (Edge *edgeptr)
 create a new edge-list element and insert it at the front of the list More...
 
void push_front (Edge *edgeptr)
 create a new edge-list element and insert it at the end of the list More...
 
EdgeListIterator insert (EdgeListIterator const &element_to_insert_before, Edge *edgeptr)
 insert a new edge-list element in the list infront of the input iterator and return an iterator to the position of the new element More...
 
EdgeListIterator begin ()
 returns a non-const iterator to the front of the list More...
 
EdgeListConstIterator begin () const
 returns a const iterator to the front of the list More...
 
EdgeListConstIterator const_begin () const
 returns a const iterator to the front of the list More...
 
EdgeListIterator last ()
 returns a non-const iterator to the last element in the list More...
 
EdgeListConstIterator last () const
 returns a const iterator to the last element in the list More...
 
EdgeListConstIterator const_last () const
 returns a const iterator to the last element in the list More...
 
EdgeListIterator end ()
 returns a non-const iterator to the end of the list More...
 
EdgeListConstIterator end () const
 returns a const iterator to the end of the list More...
 
EdgeListConstIterator const_end () const
 returns a const iterator to the end of the list More...
 
void erase (EdgeListIterator to_erase)
 removes an element from the list pointed to by the input iterator More...
 
bool is_end_element (EdgeListElement const *element) const
 method invoked by the EdgeListIterator class: is an iterator the special end iterator for a list? More...
 
platform::Size size () const
 O(N) More...
 

Private Member Functions

 EdgeList (EdgeList const &)
 Uncopyable – private and unimplemented copy ctor. More...
 
EdgeList const & operator= (EdgeList const &)
 Uncopyable – private and unimplemented assignment operator. More...
 

Private Attributes

boost::unordered_object_pool
< EdgeListElement > & 
edge_list_element_pool_
 this edge-list-element-pool reference is handed to the list to draw from. This pool must outlive the edge-list itself. To guarantee this, for the case of class Graph, the graph deletes its nodes (and their edge lists) before it deletes itself. More...
 
EdgeListElementend_
 The special "end" position in the list. More...
 

Detailed Description

Custom edge list class. Returns const-iterators which only return Edge const *'s and non-const-iterators which can return either const or non-const Edge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of EdgeListElements. Implemented as a doubly linked list, though there's no practical way to start at the end of a list and work backward since decrementing the end iterator is not a valid operation.

Constructor & Destructor Documentation

utility::graph::EdgeList::EdgeList ( boost::unordered_object_pool< EdgeListElement > &  edge_list_element_pool)
utility::graph::EdgeList::~EdgeList ( )
utility::graph::EdgeList::EdgeList ( EdgeList const &  )
private

Uncopyable – private and unimplemented copy ctor.

Member Function Documentation

EdgeListIterator utility::graph::EdgeList::begin ( )
inline
EdgeListConstIterator utility::graph::EdgeList::begin ( ) const
inline

returns a const iterator to the front of the list

References end_, and utility::graph::EdgeListElement::next_.

EdgeListConstIterator utility::graph::EdgeList::const_begin ( ) const
inline
EdgeListConstIterator utility::graph::EdgeList::const_end ( ) const
inline
EdgeListConstIterator utility::graph::EdgeList::const_last ( ) const
inline

returns a const iterator to the last element in the list

References end_, and utility::graph::EdgeListElement::previous_.

EdgeListIterator utility::graph::EdgeList::end ( )
inline
EdgeListConstIterator utility::graph::EdgeList::end ( ) const
inline

returns a const iterator to the end of the list

References end_.

void utility::graph::EdgeList::erase ( EdgeListIterator  to_erase)
EdgeListIterator utility::graph::EdgeList::insert ( EdgeListIterator const &  element_to_insert_before,
Edge edgeptr 
)

insert a new edge-list element in the list infront of the input iterator and return an iterator to the position of the new element

References debug_assert, edge_list_element_pool_, utility::graph::EdgeListIterator::element_, utility::graph::EdgeListElement::next_, utility::graph::EdgeListIterator::owner_, and utility::graph::EdgeListElement::previous_.

Referenced by utility::graph::Node::add_edge().

bool utility::graph::EdgeList::is_end_element ( EdgeListElement const *  element) const
inline

method invoked by the EdgeListIterator class: is an iterator the special end iterator for a list?

References end_.

Referenced by utility::graph::EdgeListIterator::valid(), and utility::graph::EdgeListConstIterator::valid().

EdgeListIterator utility::graph::EdgeList::last ( )
inline

returns a non-const iterator to the last element in the list

References end_, and utility::graph::EdgeListElement::previous_.

Referenced by utility::graph::Graph::add_edge().

EdgeListConstIterator utility::graph::EdgeList::last ( ) const
inline

returns a const iterator to the last element in the list

References end_, and utility::graph::EdgeListElement::previous_.

EdgeList const& utility::graph::EdgeList::operator= ( EdgeList const &  )
private

Uncopyable – private and unimplemented assignment operator.

void utility::graph::EdgeList::push_back ( Edge edgeptr)

create a new edge-list element and insert it at the front of the list

References debug_assert, edge_list_element_pool_, end_, utility::graph::EdgeListElement::next_, and utility::graph::EdgeListElement::previous_.

Referenced by utility::graph::Graph::add_edge().

void utility::graph::EdgeList::push_front ( Edge edgeptr)

create a new edge-list element and insert it at the end of the list

References debug_assert, edge_list_element_pool_, end_, utility::graph::EdgeListElement::next_, and utility::graph::EdgeListElement::previous_.

Referenced by utility::graph::Graph::add_edge().

platform::Size utility::graph::EdgeList::size ( ) const

O(N)

References begin(), and end().

Referenced by utility::graph::Graph::output_dimacs().

Member Data Documentation

boost::unordered_object_pool< EdgeListElement >& utility::graph::EdgeList::edge_list_element_pool_
private

this edge-list-element-pool reference is handed to the list to draw from. This pool must outlive the edge-list itself. To guarantee this, for the case of class Graph, the graph deletes its nodes (and their edge lists) before it deletes itself.

Referenced by erase(), insert(), push_back(), push_front(), and ~EdgeList().

EdgeListElement* utility::graph::EdgeList::end_
private

The special "end" position in the list.

Referenced by begin(), const_begin(), const_end(), const_last(), EdgeList(), end(), is_end_element(), last(), push_back(), push_front(), and ~EdgeList().


The documentation for this class was generated from the following files: