Algorithms

Generic algorithms. More...

Classes
struct	utl::binaryFunction< Arg1, Arg2, Result >
	Abstraction for binary functions. More...
struct	utl::subtract< T >
	Subtraction function. More...
struct	utl::subtractReverse< T >
	Reverse subtraction function. More...
class	utl::MultiKeyObject
	Allows multi-key sort algorithms to be used with objects. More...

Enumerations
enum	utl::sort_t {   utl::sort_heapSort, utl::sort_insertionSort, utl::sort_mergeSort, utl::sort_quickSort,   utl::sort_none }
	Specifies a sort algorithm. More...

Functions
size_t	utl::binarySearch (const RandIt &begin, const RandIt &end, const Object &key, const Ordering *ordering=nullptr, uint_t findType=find_first)
	Binary search an ordered sequence for a key. More...
void	utl::clobber (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, const Ordering *ordering=nullptr)
	Where lhs and rhs intersect, make the lhs version of the object equal to the rhs version ("clobber" it with the rhs version). More...
int	utl::compare (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, const Ordering *ordering=nullptr)
	Compare two sorted sequences. More...
void	utl::copy (FwdIt &out, const FwdIt &begin, const FwdIt &end, bool cloning=false, const Predicate *pred=nullptr, bool predVal=true)
	Copy objects from one sequence into another. More...
void	utl::copy (Object **out, const FwdIt &begin, const FwdIt &end, bool cloning=false, const Predicate *pred=nullptr, bool predVal=true)
	Copy objects from one sequence to another. More...
void	utl::copy (FwdIt &out, const Vector< Object *> &in, bool cloning=false, const Predicate *pred=nullptr, bool predVal=true)
	Copy objects from a Vector to a sequence. More...
size_t	utl::count (const FwdIt &begin, const FwdIt &end, const Predicate *pred=nullptr, bool predVal=true)
	Count objects that satisfy a Predicate. More...
void	utl::difference (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, FwdIt &out, const Ordering *ordering=nullptr, bool cloning=false, bool outIsLHS=false)
	Determine the difference between two sorted sequences. More...
void	utl::dump (const FwdIt &begin, const FwdIt &end, Stream &os, uint_t level=uint_t_max, bool key=false, bool printClassName=false, uint_t indent=0, const char *separator=nullptr)
	Dump objects to the given stream (with Object::dump()). More...
void	utl::heapSort (const BidIt &begin, const BidIt &end, const Ordering *ordering=nullptr, size_t size=size_t_max)
	Heap-sort a sequence. More...
void	utl::heapSort (Object **array, size_t begin, size_t end, const Ordering *ordering=nullptr)
	Heap-sort a sequence. More...
void	utl::insertionSort (const FwdIt &begin, const FwdIt &end, const Ordering *ordering=nullptr, size_t size=size_t_max)
	Insertion-sort a sequence. More...
void	utl::insertionSort (Object **array, size_t begin, size_t end, const Ordering *ordering=nullptr)
	Insertion-sort (part of) an array. More...
void	utl::intersect (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, FwdIt &out, const Ordering *ordering=nullptr, bool cloning=false, bool multiSet=false, bool outIsLHS=false)
	Determine the intersection of two sorted sequences. More...
size_t	utl::intersectCard (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, const Ordering *ordering=nullptr, bool multiSet=false)
	Determine the cardinality of the intersection of two sorted sequences. More...
bool	utl::intersects (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, const Ordering *ordering=nullptr)
	Determine whether the intersection of two sorted sequences is non-empty. More...
bool	utl::isSorted (const FwdIt &begin, const FwdIt &end, const Ordering *ordering=nullptr)
	Determine whether the given sequence is sorted. More...
bool	utl::isSubSet (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, const Ordering *ordering=nullptr)
	Determine whether the lhs sorted sequence is a subset of the rhs sorted sequence. More...
bool	utl::isSuperSet (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, const Ordering *ordering=nullptr)
	Determine whether the lhs sorted sequence is a superset of the rhs sorted sequence. More...
void	utl::linearSearch (const FwdIt &begin, const FwdIt &end, const Object &key, FwdIt &out, const Ordering *ordering=nullptr, uint_t findType=find_first)
	Linear search a sequence for a key. More...
void	utl::linearSearchSorted (const FwdIt &begin, const FwdIt &end, const Object &key, FwdIt &out, const Ordering *ordering=nullptr, uint_t findType=find_first)
	Linear search a sorted sequence for a key. More...
void	utl::merge (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, FwdIt &out, const Ordering *ordering=nullptr, bool cloning=false)
	Merge two sorted sequences into a single sorted sequence. More...
void	utl::mergeSort (const FwdIt &begin, const FwdIt &end, const Ordering *ordering=nullptr, size_t size=size_t_max)
	Merge-sort a sequence. More...
void	utl::mergeSort (Object **array, size_t begin, size_t end, const Ordering *ordering=nullptr)
	Merge-sort (part of) an array. More...
void	utl::multiKeyQuickSort (const FwdIt &begin, const FwdIt &end, bool key=true, bool reverse=false, size_t size=size_t_max)
	Multi-key quick-sort a sequence. More...
void	utl::quickSort (const FwdIt &begin, const FwdIt &end, const Ordering *ordering=nullptr, size_t size=size_t_max)
	Quick-sort a sequence. More...
void	utl::quickSort (Object **array, size_t begin, size_t end, const Ordering *ordering=nullptr)
	Quick-sort (part of) a sequence. More...
void	utl::remove (FwdIt &begin, const FwdIt &end, bool cmp=false, const Predicate *pred=nullptr, bool predVal=false)
	Remove objects from a sequence. More...
void	utl::reverse (const BidIt &begin, const BidIt &end)
	Reverse a sequence. More...
void	utl::serializeIn (FwdIt &out, size_t numItems, Stream &is, uint_t mode=ser_default, const RunTimeClass *rtc=nullptr)
	Serialize objects from an input stream. More...
void	utl::serializeOut (const FwdIt &begin, const FwdIt &end, Stream &os, uint_t mode=ser_default, bool boxed=true)
	Serialize objects to an output stream. More...
void	utl::sort (const FwdIt &begin, const FwdIt &end, const Ordering *ordering=nullptr, uint_t algorithm=sort_quickSort, size_t size=size_t_max)
	Sort a sequence using a given algorithm. More...
void	utl::sort (Object **array, size_t begin, size_t end, const Ordering *ordering=nullptr, uint_t algorithm=sort_quickSort)
	Sort a sequence using a given algorithm. More...
void	utl::swap (FwdIt &lhs, FwdIt &rhs)
	Swap two objects. More...
void	utl::swap (RandIt &it, size_t lhsIdx, size_t rhsIdx)
	Swap two objects in a random-access sequence. More...
void	utl::symmetricDifference (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, FwdIt &out, const Ordering *ordering=nullptr, bool cloning=false)
	Determine the symmetric difference of two sorted sequences. More...
void	utl::symmetricDifference (const FwdIt &lhsBegin, const FwdIt &lhsEnd, const FwdIt &rhsBegin, const FwdIt &rhsEnd, FwdIt &lhsOut, FwdIt &rhsOut, const Ordering *ordering=nullptr, bool lhsCloning=false, bool rhsCloning=false)
	Determine the symmetric difference of two sorted sequences. More...
String	utl::toString (const FwdIt &begin, const FwdIt &end, const String &sep, bool key=false)
	Obtain a string representation of a sequence (via Object::toString()). More...
void	utl::unique (const FwdIt &begin, const FwdIt &end, FwdIt &out, const Ordering *ordering=nullptr, bool cloning=false, bool outIsSrc=false)
	Remove duplicate objects from a sorted sequence. More...
template<class T , class P , class C >
void	utl::multiKeyInsertionSort (P *array, C cmp, size_t begin, size_t end, size_t depth=0)
	Multi-key insertion-sort (part of) the given sequence. More...
template<class T , class P , class C >
size_t	utl::multiKeyMedianOfThree (P *array, C cmp, size_t l, size_t m, size_t h, size_t depth=0)
	Perform median-of-three partitioning. More...
template<class T , class P , class C >
void	utl::multiKeyQuickSort (P *array, C cmp, size_t begin, size_t end, size_t depth=0)
	Multi-key quick-sort (part of) the given sequence. More...
template<class T , class C >
size_t	utl::binarySearch (const T *array, size_t begin, size_t end, const T &key, C cmpFn, uint_t findType=find_first)
	Binary search an ordered sequence for a key. More...

Detailed Description

Generic algorithms.

Enumeration Type Documentation

sort_t

enum utl::sort_t

Specifies a sort algorithm.

Enumerator
sort_heapSort	heap sort
sort_insertionSort	insertion sort
sort_mergeSort	merge sort
sort_quickSort	quick sort
sort_none	do not sort

Definition at line 20 of file algorithms.h.

Function Documentation

binarySearch() [1/2]

size_t utl::binarySearch	(	const RandIt &	begin,
		const RandIt &	end,
		const Object &	key,
		const Ordering *	ordering = nullptr,
		uint_t	findType = find_first
	)

Binary search an ordered sequence for a key.

Returns

index of matching object (size_t_max if none found)

Parameters

begin	begin iterator
end	end iterator
key	key to search for
ordering	(optional) ordering
findType	(optional : find_first) search type (see utl::find_t)

clobber()

void utl::clobber	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		const Ordering *	ordering = nullptr
	)

Where lhs and rhs intersect, make the lhs version of the object equal to the rhs version ("clobber" it with the rhs version).

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
ordering	(optional) ordering

compare()

int utl::compare	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		const Ordering *	ordering = nullptr
	)

Compare two sorted sequences.

Objects in each sequence are compared until they are unequal or the end of one or both sequences is reached.

Returns

< 0 if lhs < rhs, 0 if lhs = rhs, > 0 if lhs > rhs

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
ordering	(optional) ordering

copy() [1/3]

void utl::copy	(	FwdIt &	out,
		const FwdIt &	begin,
		const FwdIt &	end,
		bool	cloning = false,
		const Predicate *	pred = nullptr,
		bool	predVal = true
	)

Copy objects from one sequence into another.

Parameters

out	output iterator
begin	begin of source sequence
end	end of source sequence
cloning	(optional : false) clone source objects?
pred	(optional) predicate : require (pred(sourceObject) == predVal)
predVal	(optional : true) predicate value

copy() [2/3]

void utl::copy	(	Object **	out,
		const FwdIt &	begin,
		const FwdIt &	end,
		bool	cloning = false,
		const Predicate *	pred = nullptr,
		bool	predVal = true
	)

Copy objects from one sequence to another.

Parameters

out	output vector
begin	begin of source sequence
end	end of source sequence
cloning	(optional : false) clone source objects?
pred	(optional) predicate : require (pred(sourceObject) == predVal)
predVal	(optional : true) predicate value

copy() [3/3]

void utl::copy	(	FwdIt &	out,
		const Vector< Object *> &	in,
		bool	cloning = false,
		const Predicate *	pred = nullptr,
		bool	predVal = true
	)

Copy objects from a Vector to a sequence.

Parameters

out	output sequence
in	source vector
cloning	(optional : false) clone source objects?
pred	(optional) predicate : require (pred(sourceObject) == predVal)
predVal	(optional : true) predicate value

count()

size_t utl::count	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Predicate *	pred = nullptr,
		bool	predVal = true
	)

Count objects that satisfy a Predicate.

Parameters

begin	begin of sequence
end	end of sequence
pred	(optional) predicate : require (pred(object) == predVal)
predVal	(optional : true) predicate value

Referenced by utl::Collection::contains(), utl::TCollection< Vertex >::toString(), and utl::Semaphore::V().

difference()

void utl::difference	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		bool	cloning = false,
		bool	outIsLHS = false
	)

Determine the difference between two sorted sequences.

The difference consists of objects that exist in the lhs sequence but not the rhs sequence.

See also

symmetricDifference

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
out	output sequence
ordering	(optional) ordering
cloning	(optional : false) clone source objects?
outIsLHS	(optional : false) output sequence == lhs sequence?

Referenced by utl::SortedCollection::operator-=(), and utl::SortedCollection::remove().

dump()

void utl::dump	(	const FwdIt &	begin,
		const FwdIt &	end,
		Stream &	os,
		uint_t	level = uint_t_max,
		bool	key = false,
		bool	printClassName = false,
		uint_t	indent = 0,
		const char *	separator = nullptr
	)

Dump objects to the given stream (with Object::dump()).

See also

Object::getKey

Parameters

begin	begin of sequence
end	end of sequence
os	output stream
level	(optional) verbosity
key	(optional : false) dump keys instead of objects?
printClassName	(optional : false) print each object's class name?
indent	(optional : 0) indent each object?
separator	(optional) string to visually separate objects

Referenced by utl::BinTreeNode::BinTreeNode(), utl::BitArray::BitArray(), utl::Directory::Directory(), utl::SpanAllocator< T, D >::dump(), utl::FSobject::FSobject(), utl::Collection::operator-=(), and utl::TCollection< Vertex >::serialize().

heapSort() [1/2]

void utl::heapSort	(	const BidIt &	begin,
		const BidIt &	end,
		const Ordering *	ordering = nullptr,
		size_t	size = size_t_max
	)

Heap-sort a sequence.

See also

Heap

Parameters

begin	begin of sequence
end	end of sequence
ordering	(optional) ordering
size	(optional) size of sequence

heapSort() [2/2]

void utl::heapSort	(	Object **	array,
		size_t	begin,
		size_t	end,
		const Ordering *	ordering = nullptr
	)

Heap-sort a sequence.

See also

Heap

Parameters

array	sequence to be sorted
begin	index of first object
end	index of last object + 1
ordering	(optional) ordering

insertionSort() [1/2]

void utl::insertionSort	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Ordering *	ordering = nullptr,
		size_t	size = size_t_max
	)

Insertion-sort a sequence.

Parameters

begin	begin of sequence
end	end of sequence
ordering	(optional) ordering
size	(optional) size of sequence

Referenced by utl::BWTencoder::BWTencoder(), and utl::List::pushBack().

insertionSort() [2/2]

void utl::insertionSort	(	Object **	array,
		size_t	begin,
		size_t	end,
		const Ordering *	ordering = nullptr
	)

Insertion-sort (part of) an array.

Parameters

array	sequence to be sorted
begin	index of first object
end	index of last object + 1
ordering	(optional) ordering

intersect()

void utl::intersect	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		bool	cloning = false,
		bool	multiSet = false,
		bool	outIsLHS = false
	)

Determine the intersection of two sorted sequences.

The intersection consists of objects that exist in both of the sorted sequences.

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
out	output sequence
ordering	(optional) ordering
cloning	(optional : false) clone source objects?
multiSet	(optional : false) can an rhs object have multiple matching lhs objects?
outIsLHS	(optional : false) output sequence == lhs sequence?

Referenced by utl::StringVars::container(), and utl::SortedCollection::operator &=().

intersectCard()

size_t utl::intersectCard	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		const Ordering *	ordering = nullptr,
		bool	multiSet = false
	)

Determine the cardinality of the intersection of two sorted sequences.

Returns

number of objects that exist in both sequences

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
ordering	(optional) ordering
multiSet	(optional : false) can an rhs object have multiple matching lhs objects?

Referenced by utl::SortedCollection::intersect().

intersects()

bool utl::intersects	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		const Ordering *	ordering = nullptr
	)

Determine whether the intersection of two sorted sequences is non-empty.

Returns

true if intersection exists, false otherwise

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
ordering	(optional) ordering

Referenced by utl::SortedCollection::intersect().

isSorted()

bool utl::isSorted	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Ordering *	ordering = nullptr
	)

Determine whether the given sequence is sorted.

Returns

true if the sequence is sorted, false otherwise

Parameters

begin	begin of sequence
end	end of sequence
ordering	(optional) ordering

isSubSet()

bool utl::isSubSet	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		const Ordering *	ordering = nullptr
	)

Determine whether the lhs sorted sequence is a subset of the rhs sorted sequence.

Returns

true if lhs is a subset of rhs, false otherwise

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
ordering	(optional) ordering

Referenced by utl::SortedCollection::intersect(), and utl::SortedCollection::operator<=().

isSuperSet()

bool utl::isSuperSet	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		const Ordering *	ordering = nullptr
	)

Determine whether the lhs sorted sequence is a superset of the rhs sorted sequence.

Returns

true if lhs is a superset of rhs, false otherwise

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
ordering	(optional) ordering

Referenced by utl::SortedCollection::operator>=().

linearSearch()

void utl::linearSearch	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Object &	key,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		uint_t	findType = find_first
	)

Linear search a sequence for a key.

Parameters

begin	begin iterator
end	end iterator
key	key to search for
out	output iterator
ordering	(optional) ordering
findType	(optional : find_first) search type (see utl::find_t)

linearSearchSorted()

void utl::linearSearchSorted	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Object &	key,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		uint_t	findType = find_first
	)

Linear search a sorted sequence for a key.

Since the sequence is known to be sorted, an unsuccessful search can terminate more quickly.

Parameters

begin	begin iterator
end	end iterator
key	key to search for
out	output iterator
ordering	(optional) ordering
findType	(optional : find_first) search type (see utl::find_t)

merge()

void utl::merge	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		bool	cloning = false
	)

Merge two sorted sequences into a single sorted sequence.

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
out	output iterator
ordering	(optional) ordering
cloning	(optional : false) clone source objects?

Referenced by utl::SpanCol< T, D >::add(), utl::SortedCollection::isSuperSet(), utl::Span< Time, Duration >::operator+=(), utl::List::pushBack(), and utl::SpanCol< T, D >::remove().

mergeSort() [1/2]

void utl::mergeSort	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Ordering *	ordering = nullptr,
		size_t	size = size_t_max
	)

Merge-sort a sequence.

Parameters

begin	begin of sequence
end	end of sequence
ordering	(optional) ordering
size	(optional) size of sequence

Referenced by utl::List::pushBack().

mergeSort() [2/2]

void utl::mergeSort	(	Object **	array,
		size_t	begin,
		size_t	end,
		const Ordering *	ordering = nullptr
	)

Merge-sort (part of) an array.

Parameters

array	sequence to be sorted
begin	index of first object
end	index of last object + 1
ordering	(optional) ordering

multiKeyQuickSort() [1/2]

void utl::multiKeyQuickSort	(	const FwdIt &	begin,
		const FwdIt &	end,
		bool	key = true,
		bool	reverse = false,
		size_t	size = size_t_max
	)

Multi-key quick-sort a sequence.

Every object in the sequence must be a String (key = false) or have a String as its key (key = true).

See also

Object::getKey

Parameters

begin	begin of sequence
end	end of sequence
key	(optional : true) objects' strings are their keys?
reverse	(optional : false) reverse sort?
size	(optional) size of sequence

Referenced by utl::BWTencoder::BWTencoder(), and utl::SortedCollection::operator>=().

quickSort() [1/2]

void utl::quickSort	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Ordering *	ordering = nullptr,
		size_t	size = size_t_max
	)

Quick-sort a sequence.

Parameters

begin	begin of sequence
end	end of sequence
ordering	(optional) ordering
size	(optional) size of sequence

Referenced by utl::BWTencoder::BWTencoder().

quickSort() [2/2]

void utl::quickSort	(	Object **	array,
		size_t	begin,
		size_t	end,
		const Ordering *	ordering = nullptr
	)

Quick-sort (part of) a sequence.

Parameters

array	sequence to be sorted
begin	index of first object
end	index of last object + 1
ordering	(optional) ordering

remove()

void utl::remove	(	FwdIt &	begin,
		const FwdIt &	end,
		bool	cmp = false,
		const Predicate *	pred = nullptr,
		bool	predVal = false
	)

Remove objects from a sequence.

Parameters

begin	begin of sequence
end	end of sequence
cmp	(optional : false) compare objects (via Object::compare())?
pred	(optional) predicate : require (pred(object) == predVal)
predVal	(optional : true) predicate value

Referenced by utl::SpanCol< T, D >::add(), utl::SpanAllocator< T, D >::alloc(), utl::Stack< T >::pop(), utl::SpanAllocator< T, D >::remove(), utl::SpanCol< T, D >::remove(), utl::TRBtree< Span< T, D > >::remove(), utl::TSkipList< T >::remove(), and utl::SortedCollection::remove().

reverse()

void utl::reverse	(	const BidIt &	begin,
		const BidIt &	end
	)

Reverse a sequence.

Parameters

begin	begin of sequence
end	end of sequence

Referenced by utl::DequeIt::DequeIt(), utl::ArrayIt::getArray(), utl::HeapIt::getIdx(), utl::ListIt::getNode(), utl::HashtableIt::getNode(), utl::SortedCollection::insert(), utl::Vector< uint_t >::insert(), utl::ArrayIt::operator-(), utl::BidIt::operator--(), utl::BidIt::operator-=(), utl::String::replace(), utl::DequeIt::set(), utl::ListIt::setNode(), utl::BinTreeIt::setNode(), utl::SkipListIt::setNode(), utl::BinTreeIt::tree(), and utl::SkipListIt::update().

serializeIn()

void utl::serializeIn	(	FwdIt &	out,
		size_t	numItems,
		Stream &	is,
		uint_t	mode = ser_default,
		const RunTimeClass *	rtc = nullptr
	)

Serialize objects from an input stream.

If a RunTimeClass is specified, it is assumed that the objects were serialized "unboxed" (without their type information), and all objects are assumed to be of the given class.

See also

Object::serialize

Parameters

out	output iterator
numItems	number of objects to serialize
is	input stream
mode	(optional : ser_default) serialization mode
rtc	(optional) run-time class for type being serialized

serializeOut()

void utl::serializeOut	(	const FwdIt &	begin,
		const FwdIt &	end,
		Stream &	os,
		uint_t	mode = ser_default,
		bool	boxed = true
	)

Serialize objects to an output stream.

See also

Object::serialize

Parameters

begin	begin of sequence
end	end of sequence
os	output stream
mode	(optional : ser_default) serialization mode
boxed	(optional : true) serialize with type information?

sort() [1/2]

void utl::sort	(	const FwdIt &	begin,
		const FwdIt &	end,
		const Ordering *	ordering = nullptr,
		uint_t	algorithm = sort_quickSort,
		size_t	size = size_t_max
	)

Sort a sequence using a given algorithm.

Parameters

begin	begin of sequence
end	end of sequence
ordering	(optional) ordering
algorithm	(optional : sort_quickSort) see utl::sort_t
size	(optional) size of sequence

Referenced by utl::List::setSorted(), utl::Array::setSorted(), and utl::SortedCollection::sort().

sort() [2/2]

void utl::sort	(	Object **	array,
		size_t	begin,
		size_t	end,
		const Ordering *	ordering = nullptr,
		uint_t	algorithm = sort_quickSort
	)

Sort a sequence using a given algorithm.

Parameters

array	sequence to be sorted
begin	begin of sequence
end	end of sequence
ordering	(optional) ordering
algorithm	(optional : sort_quickSort) see utl::sort_t

swap() [1/2]

void utl::swap ( FwdIt &  lhs, FwdIt &  rhs  )

inline

Swap two objects.

Parameters

lhs	iterator for lhs object
rhs	iterator for rhs object

Definition at line 643 of file algorithms.h.

References utl::FwdIt::set().

swap() [2/2]

void utl::swap ( RandIt &  it, size_t  lhsIdx, size_t  rhsIdx  )

inline

Swap two objects in a random-access sequence.

Parameters

it	iterator for sequence
lhsIdx	index of lhs object
rhsIdx	index of rhs object

Definition at line 661 of file algorithms.h.

References utl::RandIt::get(), utl::RandIt::set(), utl::symmetricDifference(), utl::toString(), and utl::unique().

symmetricDifference() [1/2]

void utl::symmetricDifference	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		bool	cloning = false
	)

Determine the symmetric difference of two sorted sequences.

The symmetric difference consists of objects that exist in exactly one of the sorted sequences.

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
out	output iterator
ordering	(optional) ordering
cloning	(optional : false) clone source objects?

Referenced by utl::SortedCollection::isSuperSet().

symmetricDifference() [2/2]

void utl::symmetricDifference	(	const FwdIt &	lhsBegin,
		const FwdIt &	lhsEnd,
		const FwdIt &	rhsBegin,
		const FwdIt &	rhsEnd,
		FwdIt &	lhsOut,
		FwdIt &	rhsOut,
		const Ordering *	ordering = nullptr,
		bool	lhsCloning = false,
		bool	rhsCloning = false
	)

Determine the symmetric difference of two sorted sequences.

The symmetric difference consists of objects that exist in exactly one of the sorted sequences.

Parameters

lhsBegin	begin of lhs sequence
lhsEnd	end of lhs sequence
rhsBegin	begin of rhs sequence
rhsEnd	end of rhs sequence
lhsOut	output iterator for lhs objects
rhsOut	output iterator for rhs objects
ordering	(optional) ordering
lhsCloning	(optional : false) clone lhs objects?
rhsCloning	(optional : false) clone rhs objects?

Referenced by utl::swap().

toString()

String utl::toString	(	const FwdIt &	begin,
		const FwdIt &	end,
		const String &	sep,
		bool	key = false
	)

Obtain a string representation of a sequence (via Object::toString()).

See also

Object::getKey

Parameters

begin	begin iterator
end	end iterator
sep	separator (e.g. ", ")
key	(optional : false) invoke Object::toString() on object keys?

Referenced by utl::BitArrayElem::BitArrayElem(), utl::Bool::Bool(), utl::Bytes::Bytes(), utl::Pair::clear(), utl::Decimal::Decimal(), utl::Duration::Duration(), utl::Float::Float(), utl::Number< double >::Number(), utl::Collection::operator-=(), utl::Number< double >::serialize(), utl::Object::serializeBoxed(), utl::Time::setCurrent(), utl::String::String(), utl::swap(), utl::Integer< uint64_t >::toDecimal(), utl::Integer< uint64_t >::toHex(), utl::Integer< uint64_t >::toOctal(), utl::Number< double >::toString(), utl::TCollection< Vertex >::toString(), utl::Collection::toString(), utl::UnixModeMask::UnixModeMask(), and utl::URI::URI().

unique()

void utl::unique	(	const FwdIt &	begin,
		const FwdIt &	end,
		FwdIt &	out,
		const Ordering *	ordering = nullptr,
		bool	cloning = false,
		bool	outIsSrc = false
	)

Remove duplicate objects from a sorted sequence.

Parameters

begin	begin iterator
end	end iterator
out	output iterator
ordering	(optional) ordering
cloning	(optional : false) clone source objects?
outIsSrc	(optional : false) output sequence == source sequence?

Referenced by utl::SortedCollection::isSuperSet(), and utl::swap().

multiKeyInsertionSort()

template<class T , class P , class C >

void utl::multiKeyInsertionSort	(	P *	array,
		C	cmp,
		size_t	begin,
		size_t	end,
		size_t	depth = 0
	)

Multi-key insertion-sort (part of) the given sequence.

The portion to be sorted is described by the index range [begin,end).

See also

multiKeyQuickSort

Parameters

array	sequence of multi-key objects to be sorted
cmp	binary key comparison function
begin	begin index
end	end index
depth	current depth

Definition at line 161 of file algorithms_inl.h.

Referenced by utl::BWTencoder::BWTencoder().

multiKeyMedianOfThree()

template<class T , class P , class C >

size_t utl::multiKeyMedianOfThree	(	P *	array,
		C	cmp,
		size_t	l,
		size_t	m,
		size_t	h,
		size_t	depth = 0
	)

Perform median-of-three partitioning.

Parameters

array	sequence to partition
cmp	binary comparison function
l	low index
m	mid index
h	high index
depth	current depth

Definition at line 203 of file algorithms_inl.h.

multiKeyQuickSort() [2/2]

template<class T , class P , class C >

void utl::multiKeyQuickSort	(	P *	array,
		C	cmp,
		size_t	begin,
		size_t	end,
		size_t	depth = 0
	)

Multi-key quick-sort (part of) the given sequence.

The portion to be sorted is described by the index range [begin,end).

Parameters

array	sequence of multi-key objects to be sorted
cmp	binary key comparison function
begin	begin index
end	end index
depth	current depth

See also

multiKeyInsertionSort

Definition at line 239 of file algorithms_inl.h.

References ASSERTD, utl::min(), and utl::swap().

binarySearch() [2/2]

template<class T , class C >

size_t utl::binarySearch	(	const T *	array,
		size_t	begin,
		size_t	end,
		const T &	key,
		C	cmpFn,
		uint_t	findType = find_first
	)

Binary search an ordered sequence for a key.

Returns

index of matching object (size_t_max if none found)

Parameters

array	sequence to be searched
begin	begin index
end	end index
key	key to search for
cmpFn	comparison function
findType	(optional : find_first) search type (see utl::find_t)

Definition at line 421 of file algorithms_inl.h.

References utl::find_first, utl::find_ip, utl::find_last, and utl::size_t_max.