SortedCollection that stores objects in an array. More...

#include <Array.h>

Inheritance diagram for utl::Array:

[legend]

Public Member Functions
	Array (size_t size, size_t increment=size_t_max, bool owner=true, bool multiSet=true, bool keepSorted=false, Ordering *ordering=nullptr)
	Constructor. More...

	Array (bool owner, bool multiSet=true, bool keepSorted=false, Ordering *ordering=nullptr)
	Constructor. More...

virtual void	copy (const Object &rhs)
	Copy another instance. More...

virtual void	steal (Object &rhs)
	"Steal" the internal representation from another instance. More...

Misc. Read-Only
virtual size_t	innerAllocatedSize () const
	Get the "inner" allocated size. More...

size_t	firstNull () const
	Return the index of the first null object in the array. More...

Object *	get (size_t idx) const
	Get the object at the given index. More...

size_t	totalSize () const
	Get the size of the array (which is only as large as needed). More...

bool	hasHole () const
	Determine whether there are one or more "holes" in the array. More...

bool	isKeptSorted () const
	Return the keepSorted flag. More...

bool	isSorted () const
	Return the sorted flag. More...

Misc. Modification
void	removeHoles (size_t low=0, size_t high=size_t_max)
	Remove "holes" within [low,high). More...

void	economize ()
	Make the allocation exactly large enough to contain the last non-null Object*. More...

void	excise ()
	Same as clear(), but in addition the Object*[] array is deleted. More...

void	reserve (size_t minSize)
	Reserve allocation space. More...

void	set (size_t idx, const Object &object, size_t firstNull=size_t_max)
	Set the object at the given index. More...

void	set (size_t idx, const Object *object, size_t firstNull=size_t_max)
	Set the object at the given index. More...

void	setIncrement (size_t increment)
	Set the growth increment. More...

void	setKeepSorted (bool keepSorted)
	Set the keepSorted flag. More...

void	setSorted (bool sorted)
	Set the sorted flag. More...

void	shuffle (size_t low=0, size_t high=size_t_max, randutils::mt19937_64_rng *rng=nullptr)
	Randomly shuffle objects within [low,high). More...

void	sort ()

virtual void	sort (uint_t algorithm)
	Sort the collection using the given algorithm. More...

Searching
virtual Object *	find (const Object &key) const
	Find an object matching a given key. More...

size_t	findIndex (const Object &key, uint_t findType=uint_t_max, size_t low=0, size_t high=size_t_max) const
	Search [low,high) for an object matching the given key. More...

iterator	findIt (const Object &key) const
	Find the object matching the given key. More...

void	findIt (const Object &key, BidIt &it) const

virtual void	findIt (const Object &key, BidIt &it)
	Find an object matching a given key. More...

iterator	findFirstIt (const Object &key, bool insert=false) const
	Find the first object matching the given key. More...

void	findFirstIt (const Object &key, BidIt &it, bool insert) const

virtual void	findFirstIt (const Object &key, BidIt &it, bool insert=false)
	Find the first object matching the given key. More...

iterator	findLastIt (const Object &key) const
	Find the last object matching the given key. More...

void	findLastIt (const Object &key, BidIt &it) const

virtual void	findLastIt (const Object &key, BidIt &it)
	Find the last object matching the given key. More...

Adding Objects
bool	add (const Object &object)

virtual bool	add (const Object *object)
	Add an object to the collection. More...

bool	add (const Object *object, bool keepSorted)
	Add an object, specify the keepSorted flag for the addition. More...

void	add (const Collection &collection)

void	add (size_t idx, size_t num=1)
	Add null entries, shifting other objects out of the way to make room. More...

void	add (size_t idx, const Object &object)
	Add an object at a given index. More...

void	add (size_t idx, const Object *object)
	Add an object at a given index. More...

void	insert (const Object &object, iterator it)

void	insert (const Object *object, iterator it)

void	insert (const Object &object, const BidIt &it)

virtual void	insert (const Object *object, const BidIt &it)
	Insert an object before the pointed-to location. More...

Removing Objects
virtual void	clear ()
	Remove all objects from the array. More...

bool	remove (const Object *key)

virtual bool	remove (const Object &key)
	Remove the object matching the given key. More...

bool	remove (const Object &key, bool relocate, bool preserveOrder=true)
	Remove the object matching the given key. More...

void	remove (size_t idx, bool relocate=true, bool preserveOrder=true)
	Remove the object at the given index. More...

void	removeIt (iterator it, bool relocate=true, bool preserveOrder=true)
	Remove the object referred to by the given iterator. More...

void	removeIt (iterator begin, iterator end, bool relocate=true, bool preserveOrder=true)
	Remove objects in the range [begin,end). More...

virtual void	removeIt (BidIt &it)
	Remove the object the given iterator points to. More...

virtual void	removeIt (BidIt &begin, BidIt &end)

void	removeItems (size_t idx, size_t num, bool relocate=true, bool preserveOrder=true)
	Remove one or more objects starting at the given index. More...

Replacing Objects
void	replace (iterator it, const Object *newObject, bool keepSorted=true)
	Replace the object at `it` with `newObject`. More...

void	replace (base_iterator &it, const Object *newObject)
	Replace the object at `it` with `newObject`. More...

void	replace (size_t idx, const Object *newObject)
	Replace object at `idx` with `newObject`. More...

bool	replace (const Object &oldObject, const Object *newObject)
	Replace oldObject with newObject. More...

bool	replace (const Object oldObject, const Object newObject)
	Replace oldObject with newObject. More...

Relocating Objects
void	relocate (iterator destIt, iterator srcIt)
	Relocate an object to a new position. More...

void	relocate (size_t destIdx, size_t srcIdx)
	Relocate an object to a new position. More...

Iterators
iterator	begin () const

iterator	end () const

virtual RandIt *	beginNew () const
	Return a const iterator pointing to the beginning of the collection. More...

virtual RandIt *	beginNew ()
	Return an iterator pointing to the beginning of the collection. More...

virtual RandIt *	endNew () const
	Return a const iterator pointing to the end of the collection. More...

virtual RandIt *	endNew ()
	Return an iterator pointing to the end of the collection. More...

size_t	indexOf (iterator it) const

bool	isValid (iterator it) const

Operators
Object *	operator[] (size_t idx) const
	Array access operator. More...

Object *	operator[] (int idx) const

Object *	operator[] (size_t idx)

Object *	operator[] (int idx)

Object &	operator() (size_t idx) const
	Array access operator (returning reference instead of pointer). More...

Object &	operator() (size_t idx)

Object &	operator() (int idx) const

Object &	operator() (int idx)

Object *	operator[] (const Object *object)
	Add-or-find access operator (returns Object*). More...

Object &	operator() (const Object *object)
	Add-or-find access operator (returns Object&). More...

virtual void	sanityCheck () const

Public Member Functions inherited from utl::SortedCollection
void	clobber (const SortedCollection *rhs)
	Where self and rhs intersect, make self's object equal to the rhs version (i.e. More...

virtual int	compare (const Object &rhs) const
	Compare with another SortedCollection by comparing contained objects. More...

virtual Object *	addOrFind (const Object *object)
	Add the given object, or find a matching object already contained. More...

virtual bool	addOrUpdate (const Object *object)
	Add or update the given object. More...

void	insert (const Object &object, const BidIt &it)
	Insert an object before the pointed-to location. More...

void	reverse ()
	Reverse the order of the contained objects. More...

void	setOrdering (const Ordering &ordering, uint_t algorithm=sort_quickSort)
	Set the ordering, and optionally sort the collection to reflect the new ordering. More...

virtual void	setOrdering (Ordering *ordering, uint_t algorithm=sort_quickSort)
	Set the ordering, and optionally sort the collection to reflect the new ordering. More...

void	findEqualRange (const Object &key, BidIt &begin, BidIt &end) const
	Find the range elements [begin,end) that match a given key. More...

virtual void	findEqualRange (const Object &key, BidIt &begin, BidIt &end)
	Find the range of elements [begin,end) that match a given key. More...

void	findFirstIt (const Object &key, BidIt &it, bool insert=false) const
	Find the first object matching the given key. More...

void	findLastIt (const Object &key, BidIt &it) const
	Find the last object matching the given key. More...

Object *	findLinear (const Object &key) const
	Linear search for an object matching the given key. More...

Object *	findLinearSorted (const Object &key) const
	Linear search for an object matching the given key. More...

bool	remove (const Object *key)

void	remove (const SortedCollection *rhs)
	Remove objects that have a match in rhs. More...

virtual void	removeIt (BidIt &begin, const BidIt &end)
	Remove part of the collection. More...

SortedCollection &	operator-= (const SortedCollection &rhs)
	Remove objects that have a match in rhs. More...

Collection *	difference (const SortedCollection rhs, Collection out=nullptr) const
	Determine the difference between self and rhs. More...

void	intersect (const SortedCollection *rhs)
	Set self to the intersection of self and rhs. More...

Collection *	intersection (const SortedCollection rhs, Collection out=nullptr, bool multiSet=false) const
	Determine the intersection of self and rhs. More...

size_t	intersectCard (const SortedCollection *rhs) const
	Determine the cardinality of the intersection of self and rhs. More...

bool	intersects (const SortedCollection *rhs) const
	Determine whether the intersection of self and rhs is non-empty. More...

bool	isSubSet (const SortedCollection *rhs) const
	Determine whether self is a subset of rhs. More...

bool	isSuperSet (const SortedCollection *rhs) const
	Determine whether self is a superset of rhs. More...

Collection *	merge (const SortedCollection rhs, Collection out=nullptr) const
	Merge with rhs to form a single sorted sequence. More...

Collection *	symmetricDifference (const SortedCollection rhs, Collection out=nullptr) const
	Determine the symmetric difference of self and rhs. More...

void	symmetricDifference (const SortedCollection rhs, Collection lhsOut, Collection *rhsOut) const
	Determine the symmetric difference of self and rhs. More...

Collection *	unique (Collection *out=nullptr)
	Remove duplicate objects. More...

SortedCollection &	operator &= (const SortedCollection *rhs)
	Intersect with rhs. More...

bool	operator<= (const SortedCollection *rhs)
	Determine whether self is a subset of rhs. More...

bool	operator>= (const SortedCollection *rhs)
	Determine whether self is a superset of rhs. More...

bool	testSorted () const
	Determine whether the collection is sorted (often useful for testing). More...

void	multiKeyQuickSort (bool key=true, bool reverse=false)
	Multi-key quick-sort the collection. More...

void	sort ()
	Sort the collection using the quicksort algorithm. More...

Public Member Functions inherited from utl::Collection
void	assertOwner ()
	Assert ownership of contained objects. More...

virtual void	vclone (const Object &rhs)
	Make an exact copy of another instance. More...

virtual void	dump (Stream &os, uint_t level=uint_t_max) const
	Dump a human-readable representation of self to the given output stream. More...

virtual void	serialize (Stream &stream, uint_t io, uint_t mode=ser_default)
	Serialize to or from a stream. More...

void	serialize (const RunTimeClass *rtc, Stream &stream, uint_t io, uint_t mode=ser_default)
	Serialize to/from the given stream. More...

virtual bool	update (const Object *object)
	Update the given object. More...

bool	isOwner () const
	Get the owner flag. More...

void	setOwner (bool owner)
	Set the owner flag. More...

const Ordering *	ordering () const
	Get the ordering. More...

Ordering *	ordering ()
	Get the ordering. More...

void	setOrdering (const Ordering &ordering, uint_t algorithm=sort_quickSort)
	Set the ordering, and optionally sort the collection to reflect the new ordering. More...

bool	empty () const
	Determine whether the collection is empty. More...

bool	isMultiSet () const
	Get the multiSet flag. More...

void	setMultiSet (bool multiSet)
	Set the multiSet flag. More...

bool	isMarked () const
	Get marked flag. More...

void	setMarked (bool marked=true)
	Set marked flag. More...

size_t	items () const
	Get the number of contained objects. More...

size_t	size () const
	Get the number of contained objects. More...

bool	add (const Object &object)
	Add an object to the collection. More...

void	add (const Collection &collection)
	Add another collection's objects. More...

virtual BidIt *	addIt (const Object *object)
	Add an object to the collection. More...

Object *	addOrFind (const Object &object)
	Add the given object, or find a matching object already contained. More...

bool	addOrUpdate (const Object &object)
	Add or update the given object. More...

Collection &	copyItems (const Collection src, const Predicate pred=nullptr, bool predVal=true)
	Copy objects from another collection. More...

Collection &	copyItems (const ListNode src, const Predicate pred=nullptr, bool predVal=true)
	Copy objects from a double-linked list. More...

Collection &	copyItems (const SlistNode src, const Predicate pred=nullptr, bool predVal=true)
	Copy objects from a single-linked list. More...

Collection &	stealItems (Collection *src)
	"Steal" items from another collection. More...

Collection &	operator+= (const Object &rhs)
	Add an object to the collection. More...

Collection &	operator+= (const Object *rhs)
	Add an object to the collection. More...

Collection &	operator+= (const Collection &rhs)
	Add another collection's objects. More...

Collection &	operator-= (const Object &rhs)
	Remove an object from the collection. More...

void	dump (Stream &os, uint_t level, bool key, bool printClassName, uint_t indent, const char *separator) const
	Dump contained objects to a stream. More...

virtual String	toString () const
	Obtain a string representation by invoking Object::toString() on all contained objects.

String	toString (bool key) const
	Obtain a string representation by invoking Object::toString() on all contained objects (or their keys). More...

String	toString (const char *sep, bool key=false) const
	Obtain a string represenation by invoking Object::toString() on all contained objects (or their keys). More...

String	toString (const String &sep, bool key=false) const
	Obtain a string represenation of the collection by invoking Object::toString() on all contained objects (or their keys). More...

iterator	begin () const
	Return a const iterator pointing to the first object in the collection. More...

iterator	begin ()
	Return an iterator pointing to the first object in the collection. More...

virtual BidIt *	createIt () const
	Create a const iterator. More...

virtual BidIt *	createIt ()
	Create an iterator. More...

iterator	end () const
	Return a const iterator pointing to the end of the collection. More...

iterator	end ()
	Return an iterator pointing to the end of the collection. More...

bool	contains (const Object *key) const
	Determine whether the collection contains an object matching the given key. More...

bool	contains (const Object &key) const
	Determine whether the collection contains an object matching the given key. More...

size_t	count (const Predicate *pred=nullptr, bool predVal=true) const
	Count contained objects. More...

Object *	find (const Object *key) const
	Find an object matching a given key. More...

void	findIt (const Object &key, BidIt &it) const
	Find an object matching a given key. More...

Object *	first () const
	Return the first object (nullptr if empty). More...

bool	has (const Object *key) const
	See contains(). More...

bool	has (const Object &key) const
	See contains(). More...

Object *	last () const
	Get the last object (nullptr if empty). More...

bool	remove (const Object *key)
	Remove the object matching the given key. More...

Object *	take (BidIt &it)
	Remove the object the given iterator points to, but do not delete the object even if the collection owns its objects. More...

Object *	operator[] (const Object *object)
	add-or-find access operator (returns Object*). More...

Object &	operator() (const Object *object)
	add-or-find access operator (returns Object&). More...

Public Member Functions inherited from utl::Object
void	clear ()
	Revert to initial state. More...

void	dumpWithClassName (Stream &os, uint_t indent=4, uint_t level=uint_t_max) const
	Front-end for dump() that prints the object's class name. More...

virtual const Object &	getKey () const
	Get the key for this object. More...

bool	hasKey () const
	Determine whether or not the object has a key. More...

virtual const Object &	getProxiedObject () const
	Get the proxied object (= self if none). More...

virtual Object &	getProxiedObject ()
	Get the proxied object (= self if none). More...

virtual size_t	hash (size_t size) const
	Get the hash code for the object. More...

bool	_isA (const RunTimeClass *runTimeClass) const
	Determine whether self's class is a descendent of the given class. More...

	operator String () const
	Conversion to String. More...

size_t	allocatedSize () const
	Get the total allocated size of this object. More...

virtual void	addOwnedIt (const class FwdIt *it) const
	Notify self that it owns the given iterator. More...

virtual void	removeOwnedIt (const class FwdIt *it) const
	Notify self that the given owned iterator has been destroyed. More...

bool	operator< (const Object &rhs) const
	Less-than operator. More...

bool	operator<= (const Object &rhs) const
	Less-than-or-equal-to operator. More...

bool	operator> (const Object &rhs) const
	Greater-than operator. More...

bool	operator>= (const Object &rhs) const
	Greater-than-or-equal-to operator. More...

bool	operator== (const Object &rhs) const
	Equal-to operator. More...

bool	operator!= (const Object &rhs) const
	Unequal-to operator. More...

void	serializeIn (Stream &is, uint_t mode=ser_default)
	Serialize from an input stream. More...

void	serializeOut (Stream &os, uint_t mode=ser_default) const
	Serialize to an output stream. More...

void	serializeOutBoxed (Stream &os, uint_t mode=ser_default) const
	Serialize a boxed object to an output stream. More...

Additional Inherited Members
Static Public Member Functions inherited from utl::Object
static Object *	serializeInNullable (Stream &is, uint_t mode=ser_default)
	Serialize a nullptr-able object from an input stream. More...

static void	serializeOutNullable (const Object *object, Stream &os, uint_t mode=ser_default)
	Serialize a nullptr-able object to an output stream. More...

static void	serializeNullable (Object *&object, Stream &stream, uint_t io, uint_t mode=ser_default)
	Serialize a nullptr-able object to or from a stream. More...

static Object *	serializeInBoxed (Stream &is, uint_t mode=ser_default)
	Serialize a boxed object from an input stream. More...

static void	serializeBoxed (Object *&object, Stream &stream, uint_t io, uint_t mode=ser_default)
	Serialize a boxed object to or from a stream. More...

Protected Member Functions inherited from utl::FlagsMI
	FlagsMI ()
	Constructor. More...

virtual	~FlagsMI ()
	Destructor. More...

void	copyFlags (const FlagsMI &rhs)
	Copy the given flags. More...

void	copyFlags (const FlagsMI &rhs, uint_t lsb, uint_t msb)
	Copy (some of) the given flags. More...

void	copyFlags (uint64_t flags, uint_t lsb, uint_t msb)
	Copy (some of) the given flags. More...

bool	getFlag (uint_t flagNum) const
	Get a user-defined flag. More...

void	setFlag (uint_t flagNum, bool val)
	Set a user-defined flag. More...

uint64_t	getFlagsNumber (uint64_t mask, uint64_t shift=0)
	Get a multi-bit value in the flags data (which is stored as one 64-bit integer). More...

void	setFlagsNumber (uint64_t mask, uint64_t shift, uint64_t num)
	Set a multi-bit value in the flags data (which is stored as one 64-bit integer). More...

uint64_t	getFlags () const
	Get the flags. More...

void	setFlags (uint64_t flags)
	Set the flags. More...

Detailed Description

SortedCollection that stores objects in an array.

Due to its storage representation, Array is able to provide random-access to its contained objects.

Attributes

size : The number of objects that can be contained before it will be necessary to grow the array.

increment : When the array is to be grown, the growth increment determines the amount of growth. For example, if increment = 4, the array will always be grown by a multiple of 4. As a special case, if increment = size_t_max, the array will be doubled in size until it is >= the required size.

keepSorted flag : If keepSorted = true, then sortedness will be maintained by methods that add or remove objects.

sorted flag : If sorted = true, the array is assumed to be sorted. When the array is known to be sorted, it allows searches to be done much more efficiently (using a O(log n) binary search).

Note that when you set keepSorted = true, you also implicitly set sorted = true. Likewise, when you set sorted = false, you implicitly set keepSorted = false.

Performance Considerations

Remember that setting keepSorted = true imposes a performance penalty. If you don't require the array to be sorted, make sure it's set to false. Also, even if you do need the array to be sorted, you may be able to set keepSorted = false. Consider this code:

RBtree myTree;
myTree += objectA;
myTree += objectB;
myTree += objectC;
Array myArray(false);        // keepSorted = false by default
myArray = myTree;            // copy myTree's contents
ASSERT(myTree == myArray);   // array's objects are sorted

Since the tree's objects are sorted, and the array will have the same ordering, we know the array is sorted. Having keepSorted = true would have been pointless, unless we wanted our array to have an ordering different from our tree's. Even in that case, it would likely be better to leave keepSorted = false, and just sort() the array after copying the tree's objects.

"Holes" and Removal Operations

A "hole" in an array consists of one or more null entries followed by a non-null entry. It's generally best to avoid creating such holes in an array, but it's up to you to decide what's appropriate. When you remove objects, you can specify a relocate flag. The meaning of this flag depends on the keepSorted flag. Consider the following array of integers.

0 1 2 3 4

Now suppose we do array.remove(2, false). Since we specified relocate = false, no objects are relocated as a result of removing 2:

0 1 <null> 3 4

Thus, we have created a hole in the array. Suppose we instead did array.remove(2, true, false) (relocate = true, keepSorted = false). Here's what we'd end up with:

0 1 4 3

We didn't create a hole, and yet we didn't preserve the sortedness of the array. Finally, suppose we did array.remove(2, true, true) (relocate = true, keepSorted = true). Here's what we'd end up with:

0 1 3 4

This is the most expensive way (it is O(n)), but it does preserve the sortedness of the array without creating a hole.

Advantages

random access
add() for unsorted array is O(1)
find() for sorted array is O(log n)
remove() for unsorted array is O(1)
low memory usage (as little as one pointer per contained object)

Disadvantages

add() for sorted array is O(n)
find() for unsorted array is O(n)
remove() for sorted array is O(n)

Author: Adam McKee

Definition at line 116 of file Array.h.

Constructor & Destructor Documentation

◆ Array() [1/2]

utl::Array::Array	(	size_t	size,
		size_t	increment = `size_t_max`,
		bool	owner = `true`,
		bool	multiSet = `true`,
		bool	keepSorted = `false`,
		Ordering *	ordering = `nullptr`
	)

Constructor.

Parameters

size	initial size
increment	(optional : size_max) growth increment
owner	(optional : true) owner flag
multiSet	(optional : true) multiSet flag
keepSorted	(optional : false) keepSorted flag
ordering	(optional) ordering

◆ Array() [2/2]

utl::Array::Array	(	bool	owner,
		bool	multiSet = `true`,
		bool	keepSorted = `false`,
		Ordering *	ordering = `nullptr`
	)

Constructor.

Parameters

owner	(optional : true) owner flag
multiSet	(optional : true) multiSet flag
keepSorted	(optional : false) keepSorted flag
ordering	(optional) ordering

Member Function Documentation

◆ copy()

virtual void utl::Array::copy ( const Object & rhs )

virtual

Copy another instance.

When you override copy(), you should usually call the superclass's copy().

Parameters

rhs	object to copy

Reimplemented from utl::Collection.

◆ steal()

virtual void utl::Array::steal ( Object & rhs )

virtual

"Steal" the internal representation from another instance.

The default implementation just calls vclone(), so you have to override this if you want a "move" capability.

Reimplemented from utl::Collection.

◆ innerAllocatedSize()

virtual size_t utl::Array::innerAllocatedSize ( ) const

virtual

Get the "inner" allocated size.

Reimplemented from utl::Collection.

◆ firstNull()

size_t utl::Array::firstNull ( ) const

inline

Return the index of the first null object in the array.

Definition at line 161 of file Array.h.

◆ get()

Object* utl::Array::get ( size_t idx ) const

inline

Get the object at the given index.

Returns: object at given index (nullptr if none)

Parameters

idx	array index

Definition at line 172 of file Array.h.

◆ totalSize()

size_t utl::Array::totalSize ( ) const

inline

Get the size of the array (which is only as large as needed).

Definition at line 179 of file Array.h.

◆ hasHole()

bool utl::Array::hasHole ( ) const

inline

Determine whether there are one or more "holes" in the array.

Definition at line 186 of file Array.h.

◆ isKeptSorted()

bool utl::Array::isKeptSorted ( ) const

inline

Return the keepSorted flag.

Definition at line 193 of file Array.h.

◆ isSorted()

bool utl::Array::isSorted ( ) const

inline

Return the sorted flag.

Definition at line 200 of file Array.h.

References utl::size_t_max.

◆ removeHoles()

void utl::Array::removeHoles	(	size_t	low = `0`,
		size_t	high = `size_t_max`
	)

Remove "holes" within [low,high).

Parameters

low	(optional : 0) low index
high	(optional : size_t_max) high index

◆ economize()

void utl::Array::economize ( )

inline

Make the allocation exactly large enough to contain the last non-null Object*.

Definition at line 217 of file Array.h.

◆ excise()

void utl::Array::excise ( )

inline

Same as clear(), but in addition the Object*[] array is deleted.

Call this method instead of clear() when you want to minimize memory usage as much as possible.

Definition at line 227 of file Array.h.

◆ reserve()

void utl::Array::reserve ( size_t minSize )

inline

Reserve allocation space.

Parameters

minSize required minimum size

Definition at line 238 of file Array.h.

◆ set() [1/2]

void utl::Array::set	(	size_t	idx,
		const Object &	object,
		size_t	firstNull = `size_t_max`
	)

inline

Set the object at the given index.

If isOwner(), a copy of the object will be made.

Parameters

idx	array index
object	object
firstNull	(optional) new index of first null (if known by caller)

Definition at line 250 of file Array.h.

References utl::size_t_max.

◆ set() [2/2]

void utl::Array::set	(	size_t	idx,
		const Object *	object,
		size_t	firstNull = `size_t_max`
	)

Set the object at the given index.

Parameters

idx	array index
object	object
firstNull	(optional) new index of first null (if known by caller)

◆ setIncrement()

void utl::Array::setIncrement ( size_t increment )

inline

Set the growth increment.

Definition at line 265 of file Array.h.

◆ setKeepSorted()

void utl::Array::setKeepSorted ( bool keepSorted )

inline

Set the keepSorted flag.

keepSorted = true implies sorted = true.

Definition at line 272 of file Array.h.

◆ setSorted()

void utl::Array::setSorted ( bool sorted )

inline

Set the sorted flag.

sorted = false implies keepSorted = false.

Definition at line 280 of file Array.h.

References const_cast_this, IFDEBUG, utl::FwdIt::setConst(), utl::size_t_max, utl::sort(), utl::sort_quickSort, and utl::uint_t_max.

◆ shuffle()

void utl::Array::shuffle	(	size_t	low = `0`,
		size_t	high = `size_t_max`,
		randutils::mt19937_64_rng *	rng = `nullptr`
	)

Randomly shuffle objects within [low,high).

Parameters

low	low index
high	high index
rng	random number generator

◆ sort()

virtual void utl::Array::sort ( uint_t algorithm )

virtual

Sort the collection using the given algorithm.

See also: utl::sort

Parameters

algorithm sort algorithm (see utl::sort_t)

Reimplemented from utl::SortedCollection.

◆ find()

virtual Object* utl::Array::find ( const Object & key ) const

virtual

Find an object matching a given key.

Returns: found object (nullptr if none)

Parameters

key	search key

Reimplemented from utl::Collection.

◆ findIndex()

size_t utl::Array::findIndex	(	const Object &	key,
		uint_t	findType = `uint_t_max`,
		size_t	low = `0`,
		size_t	high = `size_t_max`
	)		const

Search [low,high) for an object matching the given key.

This method may also be used to find an insertion point for a new object.

Returns: index of found object (size_t_max if none)

Parameters

key	search key
findType	(optional) search type (see utl::find_t)
low	(optional : 0) low index for search
high	(optional : size_t_max) high index for search.

◆ findIt() [1/2]

iterator utl::Array::findIt ( const Object & key ) const

Find the object matching the given key.

Returns: iterator pointing to found object (= end if none)

Parameters

key	search key

◆ findIt() [2/2]

virtual void utl::Array::findIt	(	const Object &	key,
		BidIt &	it
	)

virtual

Find an object matching a given key.

Parameters

key	search key
it	result iterator (= end() if no object found)

Reimplemented from utl::Collection.

Reimplemented in utl::TArray< T >, utl::TArray< REnode >, utl::TArray< utl::String >, utl::TArray< utl::Span< size_t > >, utl::TArray< LogStream >, utl::TArray< Terminal >, and utl::TArray< utl::Stream >.

◆ findFirstIt() [1/2]

iterator utl::Array::findFirstIt	(	const Object &	key,
		bool	insert = `false`
	)		const

Find the first object matching the given key.

Returns: const iterator for found object (= end if none found)

Parameters

key	search key
insert	(optional : false) find insertion point?

◆ findFirstIt() [2/2]

virtual void utl::Array::findFirstIt	(	const Object &	key,
		BidIt &	it,
		bool	insert = `false`
	)

virtual

Find the first object matching the given key.

Parameters

key	search key
it	result iterator (= end if no object found)
insert	(optional : false) find insertion point?

Reimplemented from utl::SortedCollection.

Reimplemented in utl::TArray< T >, utl::TArray< REnode >, utl::TArray< utl::String >, utl::TArray< utl::Span< size_t > >, utl::TArray< LogStream >, utl::TArray< Terminal >, and utl::TArray< utl::Stream >.

◆ findLastIt() [1/2]

iterator utl::Array::findLastIt ( const Object & key ) const

Find the last object matching the given key.

Returns: const iterator for found object (= end if none found)

Parameters

key	search key

◆ findLastIt() [2/2]

virtual void utl::Array::findLastIt	(	const Object &	key,
		BidIt &	it
	)

virtual

Find the last object matching the given key.

Parameters

key	search key
it	result iterator (= end if no object found)

Reimplemented from utl::SortedCollection.

Reimplemented in utl::TArray< T >, utl::TArray< REnode >, utl::TArray< utl::String >, utl::TArray< utl::Span< size_t > >, utl::TArray< LogStream >, utl::TArray< Terminal >, and utl::TArray< utl::Stream >.

◆ add() [1/5]

virtual bool utl::Array::add ( const Object * object )

inlinevirtual

Add an object to the collection.

Returns: true if successful, false otherwise

Parameters

object object to add

Implements utl::Collection.

Definition at line 380 of file Array.h.

◆ add() [2/5]

bool utl::Array::add	(	const Object *	object,
		bool	keepSorted
	)

Add an object, specify the keepSorted flag for the addition.

Returns: true if object was added, false otherwise

Parameters

object	object to be added
keepSorted	should addition maintain sortedness?

◆ add() [3/5]

void utl::Array::add	(	size_t	idx,
		size_t	num = `1`
	)

Add null entries, shifting other objects out of the way to make room.

Parameters

idx	index where null entries are to be added
num	number of null entries to add

◆ add() [4/5]

void utl::Array::add	(	size_t	idx,
		const Object &	object
	)

inline

Add an object at a given index.

Other objects will be shifted over to make room if necessary. If isOwner(), a copy of the object will be made.

Parameters

idx	index where object should be added
object	object to add

Definition at line 413 of file Array.h.

References ASSERTD, and utl::clone().

◆ add() [5/5]

void utl::Array::add	(	size_t	idx,
		const Object *	object
	)

Add an object at a given index.

Other objects will be shifted over to make room if necessary.

Parameters

idx	index where object should be added
object	object to add

◆ insert()

virtual void utl::Array::insert	(	const Object *	object,
		const BidIt &	it
	)

virtual

Insert an object before the pointed-to location.

Parameters

object	object being inserted
it	reference location

Reimplemented from utl::SortedCollection.

Reimplemented in utl::TArray< T >, utl::TArray< REnode >, utl::TArray< utl::String >, utl::TArray< utl::Span< size_t > >, utl::TArray< LogStream >, utl::TArray< Terminal >, and utl::TArray< utl::Stream >.

◆ clear()

virtual void utl::Array::clear ( )

virtual

Remove all objects from the array.

Implements utl::Collection.

◆ remove() [1/3]

virtual bool utl::Array::remove ( const Object & key )

inlinevirtual

Remove the object matching the given key.

Returns: true if object found and removed, false otherwise

Parameters

key	search key

Reimplemented from utl::SortedCollection.

Definition at line 456 of file Array.h.

◆ remove() [2/3]

bool utl::Array::remove	(	const Object &	key,
		bool	relocate,
		bool	preserveOrder = `true`
	)

Remove the object matching the given key.

Returns: true if object found and removed

Parameters

key	search key
relocate	relocate objects to avoid creating a hole?
preserveOrder	(optional : true) preserve existing order of objects?

◆ remove() [3/3]

void utl::Array::remove	(	size_t	idx,
		bool	relocate = `true`,
		bool	preserveOrder = `true`
	)

Remove the object at the given index.

Parameters

idx	index of object to be removed
relocate	(optional : true) relocate objects to avoid creating a hole?
preserveOrder	(optional : true) preserve existing order of objects?

◆ removeIt() [1/3]

void utl::Array::removeIt	(	iterator	it,
		bool	relocate = `true`,
		bool	preserveOrder = `true`
	)

Remove the object referred to by the given iterator.

Parameters

it	iterator pointing to the object that will be removed
relocate	(optional : true) relocate objects to avoid creating a hole?
preserveOrder	(optional : true) preserve existing order of objects?

◆ removeIt() [2/3]

void utl::Array::removeIt	(	iterator	begin,
		iterator	end,
		bool	relocate = `true`,
		bool	preserveOrder = `true`
	)

Remove objects in the range [begin,end).

Parameters

begin	the beginning of the subsequence to be removed
end	end end of the subsequence to be removed
relocate	(optional : true) relocate objects to avoid creating a hole?
preserveOrder	(optional : true) preserve existing order of objects?

◆ removeIt() [3/3]

virtual void utl::Array::removeIt ( BidIt & it )

virtual

Remove the object the given iterator points to.

Parameters

it iterator

Reimplemented from utl::SortedCollection.

Reimplemented in utl::TArray< T >, utl::TArray< REnode >, utl::TArray< utl::String >, utl::TArray< utl::Span< size_t > >, utl::TArray< LogStream >, utl::TArray< Terminal >, and utl::TArray< utl::Stream >.

◆ removeItems()

void utl::Array::removeItems	(	size_t	idx,
		size_t	num,
		bool	relocate = `true`,
		bool	preserveOrder = `true`
	)

Remove one or more objects starting at the given index.

Parameters

idx	of first object to be removed
num	number of objects to be removed
relocate	(optional : true) relocate objects to avoid creating a hole?
preserveOrder	(optional : true) preserve existing order of objects?

◆ replace() [1/5]

void utl::Array::replace	(	iterator	it,
		const Object *	newObject,
		bool	keepSorted = `true`
	)

Replace the object at it with newObject.

Parameters

it	iterator pointing to object to be replaced
newObject	replacement object
keepSorted	(optional : true) maintain sortedness?

◆ replace() [2/5]

void utl::Array::replace	(	base_iterator &	it,
		const Object *	newObject
	)

Replace the object at it with newObject.

Parameters

it	iterator pointing to object to be replaced
newObject	replacement object

◆ replace() [3/5]

void utl::Array::replace	(	size_t	idx,
		const Object *	newObject
	)

inline

Replace object at idx with newObject.

Parameters

idx	index of object to be replaced
newObject	replacement object

Definition at line 532 of file Array.h.

◆ replace() [4/5]

bool utl::Array::replace	(	const Object &	oldObject,
		const Object *	newObject
	)

inline

Replace oldObject with newObject.

Returns: true iff replacement was performed

Parameters

oldObject	object to be replaced
newObject	replacement object

Definition at line 544 of file Array.h.

◆ replace() [5/5]

bool utl::Array::replace	(	const Object *	oldObject,
		const Object *	newObject
	)

Replace oldObject with newObject.

Returns: true iff replacement was performed

Parameters

oldObject	object to be replaced
newObject	replacement object

◆ relocate() [1/2]

void utl::Array::relocate	(	iterator	destIt,
		iterator	srcIt
	)

inline

Relocate an object to a new position.

Parameters

destIt	iterator pointing to object that will immediately follow the relocated object
srcIt	iterator pointing to object that will be relocated

Definition at line 566 of file Array.h.

◆ relocate() [2/2]

void utl::Array::relocate	(	size_t	destIdx,
		size_t	srcIdx
	)

inline

Relocate an object to a new position.

Parameters

destIdx	index of object that will immediately follow the relocated object
srcIdx	index of object to be relocated

Definition at line 577 of file Array.h.

References ASSERTD.

◆ beginNew() [1/2]

RandIt * utl::Array::beginNew ( ) const

inlinevirtual

Return a const iterator pointing to the beginning of the collection.

Implements utl::Collection.

Definition at line 186 of file ArrayIt.h.

References IFDEBUG.

◆ beginNew() [2/2]

RandIt * utl::Array::beginNew ( )

inlinevirtual

Return an iterator pointing to the beginning of the collection.

Implements utl::Collection.

Definition at line 196 of file ArrayIt.h.

◆ endNew() [1/2]

RandIt * utl::Array::endNew ( ) const

inlinevirtual

Return a const iterator pointing to the end of the collection.

Implements utl::Collection.

Definition at line 204 of file ArrayIt.h.

References IFDEBUG, and utl::size_t_max.

◆ endNew() [2/2]

RandIt * utl::Array::endNew ( )

inlinevirtual

Return an iterator pointing to the end of the collection.

Implements utl::Collection.

Definition at line 214 of file ArrayIt.h.

References utl::size_t_max.

◆ operator[]() [1/2]

Object* utl::Array::operator[] ( size_t idx ) const

inline

Array access operator.

See also: Array::get

Returns: object at given index (nullptr if none)

Parameters

idx	index of requested object

Definition at line 629 of file Array.h.

◆ operator()() [1/2]

Object& utl::Array::operator() ( size_t idx ) const

inline

Array access operator (returning reference instead of pointer).

When you use this method make sure there's an object at the given index.

Returns: reference to object at given index

Parameters

idx	array index

Definition at line 666 of file Array.h.

References ASSERTD, and const_self.

◆ operator[]() [2/2]

Object* utl::Array::operator[] ( const Object * object )

inline

Add-or-find access operator (returns Object*).

Definition at line 698 of file Array.h.

◆ operator()() [2/2]

Object& utl::Array::operator() ( const Object * object )

inline

Add-or-find access operator (returns Object&).

Definition at line 704 of file Array.h.

References utl::deInit(), utl::init(), and utl::size_t_max.

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

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Array() [1/2]

◆ Array() [2/2]

Member Function Documentation

◆ copy()

◆ steal()

◆ innerAllocatedSize()

◆ firstNull()

◆ get()

◆ totalSize()

◆ hasHole()

◆ isKeptSorted()

◆ isSorted()

◆ removeHoles()

◆ economize()

◆ excise()

◆ reserve()

◆ set() [1/2]

◆ set() [2/2]

◆ setIncrement()

◆ setKeepSorted()

◆ setSorted()

◆ shuffle()

◆ sort()

◆ find()

◆ findIndex()

◆ findIt() [1/2]

◆ findIt() [2/2]

◆ findFirstIt() [1/2]

◆ findFirstIt() [2/2]

◆ findLastIt() [1/2]

◆ findLastIt() [2/2]

◆ add() [1/5]

◆ add() [2/5]

◆ add() [3/5]

◆ add() [4/5]

◆ add() [5/5]

◆ insert()

◆ clear()

◆ remove() [1/3]

◆ remove() [2/3]

◆ remove() [3/3]

◆ removeIt() [1/3]

◆ removeIt() [2/3]

◆ removeIt() [3/3]

◆ removeItems()

◆ replace() [1/5]

◆ replace() [2/5]

◆ replace() [3/5]

◆ replace() [4/5]

◆ replace() [5/5]

◆ relocate() [1/2]

◆ relocate() [2/2]

◆ beginNew() [1/2]

◆ beginNew() [2/2]

◆ endNew() [1/2]

◆ endNew() [2/2]

◆ operator[]() [1/2]

◆ operator()() [1/2]

◆ operator[]() [2/2]

◆ operator()() [2/2]