#include "UT_Assert.h"
#include "UT_IteratorRange.h"
#include <SYS/SYS_Types.h>
#include <algorithm>
#include <iterator>
#include <limits>
#include <type_traits>
#include <stddef.h>

Include dependency graph for UT_Algorithm.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	UT_CycleDetect< T >

class	UT_CycleDetect< T >::AutoScope

class	UT_CycleDetectEx< T >

Functions
template<typename InputIt >
void	UTgetArrayMinMax (InputIt begin, InputIt end, typename std::iterator_traits< InputIt >::value_type &min, typename std::iterator_traits< InputIt >::value_type &max)
	Get the min/max values of an array. More...

template<typename InputIt , typename OutputIt >
void	UTnormalizeArray (InputIt begin, InputIt end, OutputIt d_begin)
	Normalize an array. More...

template<typename T >
size_t	UTfastSelectLow (T a, T b, size_t src1, size_t src2)
	Selects between arguments 'src1/src2' based on the lower of 'a/b'. More...

template<typename ForwardIt , typename T >
ForwardIt	UTfastUpperBound (ForwardIt first, ForwardIt last, const T &value)

template<typename Map , typename Key , typename CreateValueCB >
Map::mapped_type &	UTfindOrInsert (Map &map, const Key &key, CreateValueCB create_value)

template<typename Map , typename Key >
Map::mapped_type &	UTfindOrInsert (Map &map, const Key &key)

template<class RandomIt , class RandomFunc >
void	UTshuffle (RandomIt first, RandomIt last, RandomFunc &&r)

Function Documentation

template<typename T >

size_t UTfastSelectLow	(	T	a,
		T	b,
		size_t	src1,
		size_t	src2
	)

inline

Selects between arguments 'src1/src2' based on the lower of 'a/b'.

Definition at line 267 of file UT_Algorithm.h.

template<typename ForwardIt , typename T >

ForwardIt UTfastUpperBound	(	ForwardIt	first,
		ForwardIt	last,
		const T &	value
	)

inline

Fast upper bound search. Adapted from "How We Beat C++ STL Binary Search" Reference: https://realm.io/news/how-we-beat-cpp-stl-binary-search/

Definition at line 292 of file UT_Algorithm.h.

template<typename Map , typename Key , typename CreateValueCB >

Map::mapped_type& UTfindOrInsert	(	Map &	map,
		const Key &	key,
		CreateValueCB	create_value
	)

Find the value associated with the key. If the key is not found in the map, a value is created with the given callback function and then inserted into the map before returning.

Definition at line 339 of file UT_Algorithm.h.

template<typename Map , typename Key >

Map::mapped_type& UTfindOrInsert	(	Map &	map,
		const Key &	key
	)

Version of UTfindOrInsert() that creates a default-constructed value. This is similar to operator[], but it only converts the provided key to the map's key type when an insertion is necessary (this may incur an extra lookup versus the operator[] implementation when insertion is required). This can be useful to e.g. avoid unnecessary UT_StringHolder conversions with a UT_StringMap.

Definition at line 356 of file UT_Algorithm.h.

template<typename InputIt >

void UTgetArrayMinMax	(	InputIt	begin,
		InputIt	end,
		typename std::iterator_traits< InputIt >::value_type &	min,
		typename std::iterator_traits< InputIt >::value_type &	max
	)

inline

Get the min/max values of an array.

Definition at line 232 of file UT_Algorithm.h.

template<typename InputIt , typename OutputIt >

void UTnormalizeArray	(	InputIt	begin,
		InputIt	end,
		OutputIt	d_begin
	)

inline

Normalize an array.

Definition at line 250 of file UT_Algorithm.h.

template<class RandomIt , class RandomFunc >

void UTshuffle	(	RandomIt	first,
		RandomIt	last,
		RandomFunc &&	r
	)

Reorder the elements in the given range [first, last) such that each possible permutation of those elements has equal probability of appearance.

This function should be used instead of std::random_shuffle() and std::shuffle(), which may produce different results with different standard library implementations. std::random_shuffle() was also removed in C++17.

Definition at line 371 of file UT_Algorithm.h.

Classes

Functions

Function Documentation