Partitions an array into groups of elements equivalent according to certain criteria. More...

#include <RecursiveSplitter.h>

Classes
class	Group
	A range of indices of all array elements belonging to a particular equivalence class. More...

class	GroupIterator
	An iterator over all equivalence classes. More...

class	GroupRange
	A range of equivalence classes. More...

class	MultiElementGroupIterator
	An iterator over equivalence classes consisting of more than one element. More...

class	MultiElementGroupRange
	A range of equivalence classes consisting of more than one element. More...

Public Member Functions
	RecursiveSplitter (size_t numIds, bool opsCompatibilityMode=false)
	Initialize partitioning of an array of `numIds` elements. More...

void	groupBy (const std::vector< size_t > &categories)
	Split existing equivalence classes according to a new criterion. More...

void	groupBy (const std::vector< int > &categories)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

void	groupBy (const std::vector< std::string > &categories)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

GroupRange	groups () const
	Return the range of equivalence classes. More...

MultiElementGroupRange	multiElementGroups () const
	Return the range of equivalence classes consisting of more than one element. More...

template<typename UnaryOperation >
void	sortGroupsBy (const UnaryOperation &key)
	Sort the elements in each equivalence class in ascending order. More...

void	shuffleGroups ()
	Randomly shuffle the elements of each equivalence class. More...

void	setSeed (unsigned int seed, bool force)
	Initialise the random number generator used by shuffleGroups() with a seed. More...

Private Member Functions
void	initializeEncodedGroups ()

template<typename T >
void	groupByImpl (const std::vector< T > &categories)

Private Attributes
bool	opsCompatibilityMode_

std::vector< size_t >	orderedIds_
	Indices of elements of the partitioned array ordered by equivalence class. More...

std::vector< size_t >	encodedGroups_
	Encoded locations of multi-element equivalence classes in orderedIds_. More...

Detailed Description

Partitions an array into groups of elements equivalent according to certain criteria.

Example:

RecursiveSplitter splitter(8);
// Tell the splitter that according to a certain criterion, some elements belong to category #1
// and others to category #2
splitter.groupBy(std::vector<int>({1, 2, 1, 2, 1, 2, 1, 2}));
std::cout << "After first split:" << std::endl;
for (const auto &group : splitter.groups()) {
  std::cout << "  Elements with these indices are equivalent: ";
  for (const auto &index : group)
    std::cout << index << ", ";
  std::cout << std::endl;
}
// Tell the splitter that according to a different criterion, there is a different split between
// categories
splitter.groupBy(std::vector<int>({1, 1, 1, 1, 2, 2, 2, 2}));
std::cout << "After second split:" << std::endl;
for (const auto &group : splitter.groups()) {
  std::cout << "  Elements with these indices are equivalent: ";
  for (const auto &index : group)
    std::cout << index << ", ";
  std::cout << std::endl;
}

Output:

After first split:
  Elements with these indices are equivalent: 0, 2, 4, 6,
  Elements with these indices are equivalent: 1, 3, 5, 7,
After second split:
  Elements with these indices are equivalent: 0, 2,
  Elements with these indices are equivalent: 4, 6,
  Elements with these indices are equivalent: 1, 3,
  Elements with these indices are equivalent: 5, 7,

Definition at line 63 of file src/ufo/utils/RecursiveSplitter.h.

Constructor & Destructor Documentation

◆ RecursiveSplitter()

ufo::RecursiveSplitter::RecursiveSplitter	(	size_t	numIds,
		bool	opsCompatibilityMode = `false`
	)

explicit

Initialize partitioning of an array of numIds elements.

Initially, all elements are assumed to belong to the same equivalence class.

By default, all sorting operations performed by this class are done using a stable sorting algorithm, but if opsCompatibilityMode is true, the same algorithm as in the Met Office OPS system (heap sort) is used instead. This has an effect on the order of elements in each equivalence class.

Definition at line 18 of file RecursiveSplitter.cc.

Here is the call graph for this function:

Member Function Documentation

◆ groupBy() [1/3]

void ufo::RecursiveSplitter::groupBy ( const std::vector< int > & categories )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 286 of file src/ufo/utils/RecursiveSplitter.h.

Here is the call graph for this function:

◆ groupBy() [2/3]

void ufo::RecursiveSplitter::groupBy ( const std::vector< size_t > & categories )

inline

Split existing equivalence classes according to a new criterion.

Parameters

categories A vector assigning each element of the partitioned array to a unique category.

Each existing equivalence class E consisting of N_E elements with indices E_i (0 <= i < N_E) is split into one or more classes according to the equivalence relation

E_i'th element is equivalent to E_j'th element if and only if categories[E_i] == categories[E_j].

Definition at line 281 of file src/ufo/utils/RecursiveSplitter.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ groupBy() [3/3]

void ufo::RecursiveSplitter::groupBy ( const std::vector< std::string > & categories )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 291 of file src/ufo/utils/RecursiveSplitter.h.

Here is the call graph for this function:

◆ groupByImpl()

template<typename T >

template void ufo::RecursiveSplitter::groupByImpl ( const std::vector< T > & categories )

private

Definition at line 38 of file RecursiveSplitter.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ groups()

GroupRange ufo::RecursiveSplitter::groups ( ) const

inline

Return the range of equivalence classes.

Definition at line 296 of file src/ufo/utils/RecursiveSplitter.h.

Here is the caller graph for this function:

◆ initializeEncodedGroups()

void ufo::RecursiveSplitter::initializeEncodedGroups ( )

private

Definition at line 25 of file RecursiveSplitter.cc.

Here is the caller graph for this function:

◆ multiElementGroups()

MultiElementGroupRange ufo::RecursiveSplitter::multiElementGroups ( ) const

inline

Return the range of equivalence classes consisting of more than one element.

Definition at line 299 of file src/ufo/utils/RecursiveSplitter.h.

Here is the caller graph for this function:

◆ setSeed()

void ufo::RecursiveSplitter::setSeed	(	unsigned int	seed,
		bool	force
	)

Initialise the random number generator used by shuffleGroups() with a seed.

Parameters

seed	Seed with which to initialise the generator.
force	If false, the seed will only be reset if the program has not made any calls to util::shuffle() yet.

Definition at line 94 of file RecursiveSplitter.cc.

Here is the caller graph for this function: