bdlb::TopologicalSortUtil_Helper< INPUT_ITER > Class Template Reference

#include <bdlb_topologicalsortutil.h>

List of all members.

Classes
struct	Links
Public Member Functions
	BSLMF_NESTED_TRAIT_DECLARATION (TopologicalSortUtil_Helper, bslma::UsesBslmaAllocator)
	TopologicalSortUtil_Helper (INPUT_ITER relationsBegin, INPUT_ITER relationsEnd, bslma::Allocator *allocator=0)
template<class OUTPUT_ITER >
bool	processNextNodeInOrder (OUTPUT_ITER *resultOutIter_p)
template<class OUTPUT_ITER , class UNSORTED_OUT_ITER >
bool	sortImpl (OUTPUT_ITER resultOutIter, UNSORTED_OUT_ITER unsortedOutIter)

---

Detailed Description

template<class INPUT_ITER>
class bdlb::TopologicalSortUtil_Helper< INPUT_ITER >

This class template provides data structures required to sort the partial unsorted edges into a total ordered set of nodes. The value type of the nodes(*) must be hashable and equality comparable by bsl::hash, and bsl::equal_to respectively.

(*) The value type is determined by first getting the iterator's value type using bsl::iterator_traits<INPUT_ITER>ValueType and then using TopologicalSortUtilEdgeTraits::ValueType on that result.

See Component bdlb_topologicalsortutil

---

Constructor & Destructor Documentation

template<class INPUT_ITER >

bdlb::TopologicalSortUtil_Helper< INPUT_ITER >::TopologicalSortUtil_Helper	(	INPUT_ITER	relationsBegin,
		INPUT_ITER	relationsEnd,
		bslma::Allocator *	allocator = 0
	)			[explicit]

Create a helper class that holds the different data structures required to sort in topological order the directed acyclic graph described by the specified relationsBegin and relationsEnd. Optionally, specify an allocator for needed memory. If allocator is 0, use the globally supply default allocator instead.

---

Member Function Documentation

template<class INPUT_ITER >

bdlb::TopologicalSortUtil_Helper< INPUT_ITER >::BSLMF_NESTED_TRAIT_DECLARATION	(	TopologicalSortUtil_Helper< INPUT_ITER >	,
		bslma::UsesBslmaAllocator
	)

template<class INPUT_ITER >

template<class OUTPUT_ITER >

bool bdlb::TopologicalSortUtil_Helper< INPUT_ITER >::processNextNodeInOrder

(

OUTPUT_ITER *

resultOutIter_p

)

Write the next element in order that doesn't have any predecessors into the specified resultOutIter_p output iterator then increment it and return true. If there are still elements left but all of them still have predecessors do nothing and return false. The behavior is undefined unless !d_workSet.empty().

template<class INPUT_ITER >

template<class OUTPUT_ITER , class UNSORTED_OUT_ITER >

bool bdlb::TopologicalSortUtil_Helper< INPUT_ITER >::sortImpl	(	OUTPUT_ITER	resultOutIter,
		UNSORTED_OUT_ITER	unsortedOutIter
	)

Sort the input elements provided during construction in topological order and write the resulting linear ordered set into the specified resultOutIter and return true. If the sort is unsuccessful (the input is not an acyclic directed graph) write the nodes that have not been sorted to the specified unsortedOutIter output and return false. See TopologicalSortUtil::sort "iterators overload" for more detailed specification.

---

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

• bdlb_topologicalsortutil.h