UFO
ufo::RecursiveSplitter Class Reference

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
categoriesA 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
seedSeed 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:
ufo::RecursiveSplitter::RecursiveSplitter
RecursiveSplitter(size_t numIds)
Initialize partitioning of an array of numIds elements.
Definition: RecursiveSplitter.cc:18