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)
	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 Compare >
void	sortGroupsBy (Compare comp)
	Sort the elements in each equivalence class in ascending order. More...

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

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

Private Member Functions
void	initializeEncodedGroups ()

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

Private Attributes
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 62 of file src/ufo/utils/RecursiveSplitter.h.

Constructor & Destructor Documentation

◆ RecursiveSplitter()

ufo::RecursiveSplitter::RecursiveSplitter ( size_t numIds )

explicit

Initialize partitioning of an array of numIds elements.

Initially, all elements are assumed to belong to the same 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 280 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 275 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 285 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 37 of file RecursiveSplitter.cc.

Here is the caller graph for this function:

◆ groups()

GroupRange ufo::RecursiveSplitter::groups ( ) const

inline

Return the range of equivalence classes.

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

Here is the caller graph for this function:

◆ initializeEncodedGroups()

void ufo::RecursiveSplitter::initializeEncodedGroups ( )

private

Definition at line 24 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 293 of file src/ufo/utils/RecursiveSplitter.h.

Here is the caller graph for this function:

◆ shuffleGroups() [1/2]

void ufo::RecursiveSplitter::shuffleGroups ( )

Randomly shuffle the elements of each equivalence class.

This overload uses the defaul seed.

Definition at line 87 of file RecursiveSplitter.cc.

Here is the call graph for this function:

◆ shuffleGroups() [2/2]

void ufo::RecursiveSplitter::shuffleGroups ( unsigned int seed )

Randomly shuffle the elements of each equivalence class.

Parameters

seed	Seed with which to initialise the random number generator used by the shuffling algorithm if this hasn't been done before (in a previous call to shuffleGroups() or another function calling util::shuffle()).

Definition at line 77 of file RecursiveSplitter.cc.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sortGroupsBy()

template<typename Compare >

void ufo::RecursiveSplitter::sortGroupsBy ( Compare comp )

Sort the elements in each equivalence class in ascending order.

The elements are compared using the binary comparison function comp. This function needs to satisfy the same requirements as the comp argument of std::sort().

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

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ encodedGroups_

std::vector<size_t> ufo::RecursiveSplitter::encodedGroups_

private

Encoded locations of multi-element equivalence classes in orderedIds_.

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

◆ orderedIds_

std::vector<size_t> ufo::RecursiveSplitter::orderedIds_

private

Indices of elements of the partitioned array ordered by equivalence class.

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

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

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RecursiveSplitter()

Member Function Documentation

◆ groupBy() [1/3]

◆ groupBy() [2/3]

◆ groupBy() [3/3]

◆ groupByImpl()

◆ groups()

◆ initializeEncodedGroups()

◆ multiElementGroups()

◆ shuffleGroups() [1/2]

◆ shuffleGroups() [2/2]

◆ sortGroupsBy()

Member Data Documentation

◆ encodedGroups_

◆ orderedIds_