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...

EdgeListElement *	end_
	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 )

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

utility::graph::EdgeList::~EdgeList ( )

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

utility::graph::EdgeList::EdgeList ( EdgeList const & )

private

Uncopyable – private and unimplemented copy ctor.

Member Function Documentation

EdgeListIterator utility::graph::EdgeList::begin ( )

inline

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

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

Referenced by utility::graph::Node::add_edge(), utility::graph::Graph::add_edge(), utility::graph::Graph::delete_everything(), utility::graph::Node::drop_all_edges(), utility::graph::Graph::drop_all_edges(), utility::graph::Node::edge_list_begin(), utility::graph::Graph::edge_list_begin(), utility::graph::Node::find_edge(), utility::graph::Node::lower_edge_list_begin(), size(), and ~EdgeList().

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

returns a const iterator to the front of the list

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

Referenced by utility::graph::Node::const_edge_list_begin(), utility::graph::Graph::const_edge_list_begin(), utility::graph::Node::const_lower_edge_list_begin(), utility::graph::Graph::getTotalMemoryUsage(), and utility::graph::Node::print().

EdgeListConstIterator utility::graph::EdgeList::const_end ( ) const

inline

returns a const iterator to the end of the list

References end_.

Referenced by utility::graph::Node::const_edge_list_end(), utility::graph::Graph::const_edge_list_end(), utility::graph::Node::const_upper_edge_list_end(), utility::graph::Graph::getTotalMemoryUsage(), and utility::graph::Node::print().

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

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

References end_.

Referenced by utility::graph::Node::add_edge(), utility::graph::Graph::delete_everything(), utility::graph::Node::drop_all_edges(), utility::graph::Graph::drop_all_edges(), utility::graph::Node::edge_list_end(), utility::graph::Graph::edge_list_end(), utility::graph::Node::find_edge(), size(), utility::graph::Node::upper_edge_list_end(), and ~EdgeList().

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 )

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

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::drop_edge(), and utility::graph::Graph::drop_edge().

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:

src/utility/graph/Graph.hh
src/utility/graph/Graph.cc

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation