Custom edge list class. Returns const-iterators which only return DirectedEdge const *'s and non-const-iterators which can return either const or non-const DirectedEdge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of DirectedEdgeListElements. 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 <Digraph.hh>

Public Member Functions
	DirectedEdgeList (boost::unordered_object_pool< DirectedEdgeListElement > &edge_list_element_pool)

	~DirectedEdgeList ()

void	push_back (DirectedEdge *edgeptr)
	create a new edge-list element and insert it at the front of the list More...

void	push_front (DirectedEdge *edgeptr)
	create a new edge-list element and insert it at the end of the list More...

DirectedEdgeListIterator	insert (DirectedEdgeListIterator const &element_to_insert_before, DirectedEdge *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...

DirectedEdgeListIterator	begin ()
	returns a non-const iterator to the front of the list More...

DirectedEdgeListConstIterator	begin () const
	returns a const iterator to the front of the list More...

DirectedEdgeListConstIterator	const_begin () const
	returns a const iterator to the front of the list More...

DirectedEdgeListIterator	last ()
	returns a non-const iterator to the last element in the list More...

DirectedEdgeListConstIterator	last () const
	returns a const iterator to the last element in the list More...

DirectedEdgeListConstIterator	const_last () const
	returns a const iterator to the last element in the list More...

DirectedEdgeListIterator	end ()
	returns a non-const iterator to the end of the list More...

DirectedEdgeListConstIterator	end () const
	returns a const iterator to the end of the list More...

DirectedEdgeListConstIterator	const_end () const
	returns a const iterator to the end of the list More...

void	erase (DirectedEdgeListIterator to_erase)
	removes an element from the list pointed to by the input iterator More...

bool	is_end_element (DirectedEdgeListElement const *element) const
	method invoked by the DirectedEdgeListIterator class: is an iterator the special end iterator for a list? More...

platform::Size	size () const
	O(N) More...

Private Member Functions
	DirectedEdgeList (DirectedEdgeList const &)
	Uncopyable – private and unimplemented copy ctor. More...

DirectedEdgeList const &	operator= (DirectedEdgeList const &)
	Uncopyable – private and unimplemented assignment operator. More...

Private Attributes
boost::unordered_object_pool < DirectedEdgeListElement > &	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 Digraph, the graph deletes its nodes (and their edge lists) before it deletes itself. More...

DirectedEdgeListElement *	end_
	The special "end" position in the list. More...

Detailed Description

Custom edge list class. Returns const-iterators which only return DirectedEdge const *'s and non-const-iterators which can return either const or non-const DirectedEdge*'s. Manages its own memory using an unordered-object-pool for fast insertion and deletion of DirectedEdgeListElements. 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::DirectedEdgeList::DirectedEdgeList ( boost::unordered_object_pool< DirectedEdgeListElement > & edge_list_element_pool )

References end_, utility::graph::DirectedEdgeListElement::next_, and utility::graph::DirectedEdgeListElement::previous_.

utility::graph::DirectedEdgeList::~DirectedEdgeList ( )

References begin(), edge_list_element_pool_, end(), and end_.

utility::graph::DirectedEdgeList::DirectedEdgeList ( DirectedEdgeList const & )

private

Uncopyable – private and unimplemented copy ctor.

Member Function Documentation

DirectedEdgeListIterator utility::graph::DirectedEdgeList::begin ( )

inline

returns a non-const iterator to the front of the list

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

DirectedEdgeListConstIterator utility::graph::DirectedEdgeList::begin ( ) const

inline

returns a const iterator to the front of the list

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

DirectedEdgeListConstIterator utility::graph::DirectedEdgeList::const_begin ( ) const

inline

returns a const iterator to the front of the list

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

Referenced by utility::graph::DirectedNode::const_edge_list_begin(), utility::graph::Digraph::const_edge_list_begin(), utility::graph::DirectedNode::const_incoming_edge_list_begin(), utility::graph::Digraph::getTotalMemoryUsage(), and utility::graph::DirectedNode::print().

DirectedEdgeListConstIterator utility::graph::DirectedEdgeList::const_end ( ) const

inline

returns a const iterator to the end of the list

References end_.

Referenced by utility::graph::DirectedNode::const_edge_list_end(), utility::graph::Digraph::const_edge_list_end(), utility::graph::DirectedNode::const_outgoing_edge_list_end(), utility::graph::Digraph::getTotalMemoryUsage(), and utility::graph::DirectedNode::print().

DirectedEdgeListConstIterator utility::graph::DirectedEdgeList::const_last ( ) const

inline

returns a const iterator to the last element in the list

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

DirectedEdgeListIterator utility::graph::DirectedEdgeList::end ( )

inline

returns a non-const iterator to the end of the list

References end_.

Referenced by utility::graph::DirectedNode::add_outgoing_edge(), utility::graph::Digraph::delete_everything(), utility::graph::DirectedNode::drop_all_edges(), utility::graph::Digraph::drop_all_edges(), utility::graph::DirectedNode::edge_list_end(), utility::graph::Digraph::edge_list_end(), utility::graph::DirectedNode::find_edge_to(), utility::graph::DirectedNode::outgoing_edge_list_end(), utility::graph::Digraph::output_connectivity(), utility::graph::Digraph::output_dimacs(), size(), and ~DirectedEdgeList().

DirectedEdgeListConstIterator utility::graph::DirectedEdgeList::end ( ) const

inline

returns a const iterator to the end of the list

References end_.

void utility::graph::DirectedEdgeList::erase ( DirectedEdgeListIterator to_erase )

removes an element from the list pointed to by the input iterator

References debug_assert, edge_list_element_pool_, utility::graph::DirectedEdgeListIterator::element_, utility::graph::DirectedEdgeListElement::next_, utility::graph::DirectedEdgeListIterator::owner_, and utility::graph::DirectedEdgeListElement::previous_.

Referenced by utility::graph::DirectedNode::drop_edge(), and utility::graph::Digraph::drop_edge().

DirectedEdgeListIterator utility::graph::DirectedEdgeList::insert	(	DirectedEdgeListIterator const &	element_to_insert_before,
		DirectedEdge *	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::DirectedEdgeListIterator::element_, utility::graph::DirectedEdgeListElement::next_, utility::graph::DirectedEdgeListIterator::owner_, and utility::graph::DirectedEdgeListElement::previous_.

Referenced by utility::graph::DirectedNode::add_incoming_edge(), and utility::graph::DirectedNode::add_outgoing_edge().

bool utility::graph::DirectedEdgeList::is_end_element ( DirectedEdgeListElement const * element ) const

inline

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

References end_.

Referenced by utility::graph::DirectedEdgeListIterator::valid(), and utility::graph::DirectedEdgeListConstIterator::valid().

DirectedEdgeListIterator utility::graph::DirectedEdgeList::last ( )

inline

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

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

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

DirectedEdgeListConstIterator utility::graph::DirectedEdgeList::last ( ) const

inline

returns a const iterator to the last element in the list

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

DirectedEdgeList const& utility::graph::DirectedEdgeList::operator= ( DirectedEdgeList const & )

private

Uncopyable – private and unimplemented assignment operator.

void utility::graph::DirectedEdgeList::push_back ( DirectedEdge * 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::DirectedEdgeListElement::next_, and utility::graph::DirectedEdgeListElement::previous_.

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

void utility::graph::DirectedEdgeList::push_front ( DirectedEdge * 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::DirectedEdgeListElement::next_, and utility::graph::DirectedEdgeListElement::previous_.

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

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

O(N)

References begin(), and end().

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

Member Data Documentation

boost::unordered_object_pool< DirectedEdgeListElement >& utility::graph::DirectedEdgeList::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 Digraph, the graph deletes its nodes (and their edge lists) before it deletes itself.

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

DirectedEdgeListElement* utility::graph::DirectedEdgeList::end_

private

The special "end" position in the list.

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

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

src/utility/graph/Digraph.hh
src/utility/graph/Digraph.cc

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation