#include <bdlb_topologicalsortutil.h>
|
| template<class INPUT_ITER , class OUTPUT_ITER , class UNSORTED_OUT_ITER > |
| bool | sort (INPUT_ITER relationsBegin, INPUT_ITER relationsEnd, OUTPUT_ITER resultOutIter, UNSORTED_OUT_ITER unsortedOutIter) |
| |
|
| template<class INPUT_ITER , class OUTPUT_ITER , class UNSORTED_OUTPUT_ITER > |
| static bool | sort (INPUT_ITER relationsBegin, INPUT_ITER relationsEnd, OUTPUT_ITER resultOutIter, UNSORTED_OUTPUT_ITER unsortedOutIter) |
| |
| template<class NODE_TYPE > |
| static bool | sort (bsl::vector< NODE_TYPE > *result, bsl::vector< NODE_TYPE > *unsorted, const bsl::vector< bsl::pair< NODE_TYPE, NODE_TYPE > > &relations) |
| |
This struct TopologicalSortUtil provides a namespace for topological sorting functions.
◆ sort() [1/3]
template<class NODE_TYPE >
Sort the elements of NODE_TYPE in topological order determined by the specified relations and load the resulting linear ordered set to the specified result. If the sort is unsuccessful, load the elements that have not been ordered to the specified unsorted list. The input relations are provided as pairs of the form (U, V) where U precedes V in the output. Return false if sort fails due to a cycle in the input else return true if sort successful. Note that even if the method returns false, result may contain a subset of elements in the right topological order, essentially elements that the routine was able to sort before the cycle was discovered and unsorted will contain the elements that the routine was unable to sort.
◆ sort() [2/3]
template<class INPUT_ITER , class OUTPUT_ITER , class UNSORTED_OUT_ITER >
| bool bdlb::TopologicalSortUtil::sort |
( |
INPUT_ITER |
relationsBegin, |
|
|
INPUT_ITER |
relationsEnd, |
|
|
OUTPUT_ITER |
resultOutIter, |
|
|
UNSORTED_OUT_ITER |
unsortedOutIter |
|
) |
| |
◆ sort() [3/3]
template<class INPUT_ITER , class OUTPUT_ITER , class UNSORTED_OUTPUT_ITER >
| static bool bdlb::TopologicalSortUtil::sort |
( |
INPUT_ITER |
relationsBegin, |
|
|
INPUT_ITER |
relationsEnd, |
|
|
OUTPUT_ITER |
resultOutIter, |
|
|
UNSORTED_OUTPUT_ITER |
unsortedOutIter |
|
) |
| |
|
static |
Sort the input elements in topological order and write the resulting linear ordered set into the specified resultOutIter. If the sort is unsuccessful (the input is not an acyclic directed graph) write the elements that have not been sorted to the specified unsortedOutIter output. The input elements are provided as a sequence of (conceptual or physical) pairs between the specified relationsBegin and relationsEnd of the form (U, V), where U and V are nodes, and U precedes V in the output. Return true on success, and false if the sort fails due to a cycle in the input. The type bsl::iterator_traits<INPUT_ITER>::value_type must either be bsl or std::pair where the first_type and second_type are the same as bsl::iterator_traits<OUTPUT_ITER>::value_type or TopologicalSortUtilEdgeTraits must be specialized for the type, i.e., the supplied bsl::iterator_traits<INPUT_ITER>::value_type must support the following syntax:
typedef typename bsl::iterator_traits<INPUT_ITER>::value_type
IterValue;
typedef typename bsl::iterator_traits<RESULT_ITER>::value_type
ResultValue;
typedef typename Traits::NodeType NodeType;
for (INPUT_ITER it = relationshipPairsBegin;
it != relationshipPairsEnd;
++it) {
*result++ = Traits::from(*it);
*result++ = Traits::to(*it);
}
Definition bdlb_topologicalsortutil.h:530
Note that when the method returns false, resultOutIter may contain a subset of the elements in the right topological order, essentially the elements that the routine was able to sort before the cycle was discovered. In that case, the elements that the routine was unable to sort were written to the unsortedOutIter output iterator, in an unspecified order.
The documentation for this struct was generated from the following file:
1.9.8