#include <sortedarray.h>

Inheritance diagram for SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >:

[legend]

Detailed Description

template<typename MYSELF, typename ARRAY, BASESORTFLAGS FLAGS = BASESORTFLAGS::NONE, Bool PARALLEL = false>
class maxon::SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >

Sorted array. The class can be combined with any standard array type. Sorting is done on first read access, e.g. if you access the array by using the index operator. Note that sorted arrays will be extremely slow if read and write access is constantly alternating, as for every write access a sort needs to be done, which needs O(log n) time. In those cases other datastructures will be better suited. Please also take into consideration that sorted arrays are not thread-safe, even for read-access unless you call Sort() once before multiple threads start reading the data (if the array was in a non-sorted state the first read-access will sort it otherwise, which will obviously cause problems)

If the data type to be sorted is unknown to DefaultCompare you should inherit from SortedArray and define a LessThan() and an IsEqual() method for comparison of elements. For example:

class MySortedArray : public SortedArray<MySortedArray, BaseArray<MyType>>
{
public:
  static Bool LessThan(const MyType& a, const MyType& b) { return a < b; }
  static Bool IsEqual(const MyType& a, const MyType& b) { return a == b; }
};
MySortedArray a;
a.Append(x) iferr_return;
a.Append(y) iferr_return;

Note: Note that the classes that will be sorted have special requirements regarding copy and move constructors .; Note that the comparison must fulfill the condition (a < b) == !(b < a). If this is not the case the sort algorithm will crash. To avoid mistakes when comparing tuples use LexicographicalCompare.

Template Parameters

MYSELF	The class itself.
ARRAY	The used array, e.g. BaseArray, BlockArray or PointerArray.
FLAGS	See BASESORTFLAGS, normally can be left at default.
PARALLEL	Use parallel sorting, for details see parallelsort.h.

Note: Note that the array element class has special requirements regarding copy and move constructors .

Public Types
using	TYPE = typename ARRAY::ValueType

using	Iterator = typename ARRAY::Iterator

using	ConstIterator = typename ARRAY::ConstIterator

Public Types inherited from Collection< COLLECTION, VALUETYPE, SUPER >
using	Super = BaseCollection< COLLECTION, SUPER >

using	ValueType = VALUETYPE

Public Types inherited from BaseCollection< COLLECTION, SUPER >
using	IsCollection = std::true_type

using	IsBaseArray = std::false_type

Public Member Functions
	SortedArray ()

	SortedArray (const typename ARRAY::AllocatorType &a)

	~SortedArray ()

	SortedArray (SortedArray &&src)

	MAXON_OPERATOR_MOVE_ASSIGNMENT (SortedArray)

void	Reset ()

void	Flush ()

ResultMem	SetCapacityHint (Int requestedCapacity, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

Int	GetCount () const

Int	GetCapacityCount () const

const TYPE &	operator[] (Int idx) const

template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE ResultRef< TYPE >	Append (ARGS &&... args)

ResultPtr< TYPE >	AppendPtr (TYPE *x)

Bool	PopPtr (TYPE **dst)

ResultPtr< TYPE >	InsertPtr (Int position, TYPE *x)

template<typename... ARGS>
ResultRef< TYPE >	Insert (Int position, ARGS &&... args)

template<typename... ARGS>
ResultMemT< Iterator >	Insert (Iterator position, ARGS &&... args)

template<typename... ARGS>
ResultPtr< TYPE >	InsertBlock (Int position, ARGS &&... args)

template<typename... ARGS>
ResultMemT< Iterator >	InsertBlock (Iterator position, ARGS &&... args)

ResultPtr< TYPE >	Erase (Int position, Int eraseCnt=1)

ResultPtr< TYPE >	ErasePtr (Int position, TYPE **dst)

ResultMem	SwapErase (Int position, Int eraseCnt=1)

Iterator	SwapErase (Iterator position, Int eraseCnt=1)

template<Bool STRIDED>
Int	GetBlock (Int position, Block< TYPE, STRIDED > &block)

template<Bool STRIDED>
Int	GetBlock (Int position, Block< const TYPE, STRIDED > &block) const

Iterator	Erase (Iterator position, Int eraseCnt=1)

template<typename SEARCH >
Bool	EraseKey (const SEARCH &key)

const TYPE *	GetFirst () const

TYPE *	GetFirst ()

const TYPE *	GetLast () const

TYPE *	GetLast ()

ResultMem	Resize (Int newCnt, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::DEFAULT)

Bool	Pop (TYPE *dst=nullptr)

Int	GetIndex (const TYPE &x) const

Result< void >	CopyFrom (const SortedArray &src)

template<typename COLLECTION2 , typename = typename std::enable_if<!STD_IS_REPLACEMENT(same, typename std::decay<COLLECTION2>::type, SortedArray)>::type>
Result< void >	CopyFrom (COLLECTION2 &&other)

void	Swap (Iterator a, Iterator b)

Int	GetMemorySize () const

ConstIterator	Begin () const

Iterator	Begin ()

ConstIterator	End () const

Iterator	End ()

void	SortChanged ()

void	Sort ()

template<typename SEARCH >
TYPE *	FindValue (const SEARCH &key)

template<typename SEARCH >
const TYPE *	FindValue (const SEARCH &key) const

template<typename SEARCH >
Int	FindIndex (const SEARCH &key) const

template<typename SEARCH >
ResultRef< TYPE >	InsertValue (const SEARCH &key)

template<typename SEARCH >
ResultRef< TYPE >	InsertValue (const SEARCH &key, Bool &newElement, Int *index=nullptr)

ARRAY &	GetUnderlyingArray ()

const ARRAY &	GetUnderlyingArray () const

Public Member Functions inherited from ArrayBase< SortedArray< MYSELF, ARRAY, BASESORTFLAGS::NONE, false >, ARRAY::ValueType, EmptyClass, MYSELF >
constexpr MAXON_ATTRIBUTE_FORCE_INLINE	ArrayBase (ARGS &&... args)

ArrayImpl< SortedArray< MYSELF, ARRAY, BASESORTFLAGS::NONE, false > & >	ToArray ()

ArrayImpl< const SortedArray< MYSELF, ARRAY, BASESORTFLAGS::NONE, false > & >	ToArray () const

MAXON_ATTRIBUTE_FORCE_INLINE	operator ArrayImpl< SortedArray< MYSELF, ARRAY, BASESORTFLAGS::NONE, false > & > ()

MAXON_ATTRIBUTE_FORCE_INLINE	operator ArrayImpl< const SortedArray< MYSELF, ARRAY, BASESORTFLAGS::NONE, false > & > () const

Public Member Functions inherited from ArrayBase0< COLLECTION, VALUETYPE, SUPER, HASH >
template<typename... ARGS>
constexpr MAXON_ATTRIBUTE_FORCE_INLINE	ArrayBase0 (ARGS &&... args)

Bool	IsValidIndex (Int index) const

Result< void >	CheckValidIndex (Int index) const

Int	FindIndex (typename ByValueParam< VALUETYPE >::type v, Int start) const

Int	FindLastIndex (typename ByValueParam< VALUETYPE >::type v) const

Int	FindLastIndex (typename ByValueParam< VALUETYPE >::type v, Int start) const

Bool	EraseFirst (typename ByValueParam< VALUETYPE >::type v)

Int	EraseAll (typename ByValueParam< VALUETYPE >::type v)

template<typename COLLECTION2 >
Result< void >	AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)

template<typename COLLECTION2 >
Result< void >	InsertAll (Int index, COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

template<typename COLLECTION2 >
Result< void >	Add (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

template<typename COLLECTION2 >
Result< void >	SubtractImpl (COLLECTION2 &&other, OverloadRank0)

template<typename COLLECTION2 , typename COMPARE >
Bool	IsEqualImpl (const COLLECTION2 &other, COMPARE &&cmp, OverloadRank0) const

HashInt	GetHashCode () const

UniqueHash	GetUniqueHashCode () const

MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< COLLECTION >	Slice (Int start)

MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< const COLLECTION >	Slice (Int start) const

MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< COLLECTION >	Slice (Int start, Int end)

MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< const COLLECTION >	Slice (Int start, Int end) const

BlockIterator< COLLECTION, VALUETYPE, false, false >	GetBlocks ()

BlockIterator< COLLECTION, VALUETYPE, true, false >	GetBlocks () const

BlockIterator< COLLECTION, VALUETYPE, false, true >	GetStridedBlocks ()

BlockIterator< COLLECTION, VALUETYPE, true, true >	GetStridedBlocks () const

Public Member Functions inherited from Collection< COLLECTION, VALUETYPE, SUPER >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	Collection (ARGS &&... args)

ResultOk< void >	VariadicAppend ()

template<typename V , typename... VALUES>
Result< void >	VariadicAppend (V &&value, VALUES &&... rest)

	operator ValueReceiver< const VALUETYPE & > ()

	operator ValueReceiver< VALUETYPE && > ()

	operator ValueReceiver< typename std::conditional< STD_IS_REPLACEMENT (scalar, VALUETYPE)

DummyParamType &	type ()

template<typename FN >
Result< Bool >	ForEach (FN &&callback) const

template<typename FN >
Result< Bool >	ForEach (FN &&callback)

template<typename H = COLLECTION>
H::Iterator	Find (typename ByValueParam< VALUETYPE >::type v)

template<typename H = COLLECTION>
H::ConstIterator	Find (typename ByValueParam< VALUETYPE >::type v) const

Int	FindIndex (typename ByValueParam< VALUETYPE >::type v) const

MAXON_ATTRIBUTE_FORCE_INLINE Bool	Contains (typename ByValueParam< VALUETYPE >::type v) const

Public Member Functions inherited from BaseCollection< COLLECTION, SUPER >
template<typename... ARGS>
MAXON_ATTRIBUTE_FORCE_INLINE	BaseCollection (ARGS &&... args)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type	operator== (const COLLECTION2 &other) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type	operator!= (const COLLECTION2 &other) const

template<typename COMPARE = EqualityCompare, typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value &&!STD_IS_REPLACEMENT(same, typename std::decay< COMPARE >::type, EQUALITY), Bool >::type	IsEqual (const COLLECTION2 &other, COMPARE &&cmp=COMPARE()) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Subtract (COLLECTION2 &&other)

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	Intersect (const COLLECTION2 &other)

template<typename COLLECTION2 >
Bool	Intersects (const COLLECTION2 &other) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Result< void >	CopyFromImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank0)

template<typename COLLECTION2 >
Result< void >	AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)

template<typename COLLECTION2 >
Result< void >	IntersectImpl (COLLECTION2 &&other, OverloadRank0)

MAXON_ATTRIBUTE_FORCE_INLINE Bool	IsEmpty () const

MAXON_ATTRIBUTE_FORCE_INLINE Bool	IsPopulated () const

String	ToString (const FormatStatement *formatStatement=nullptr) const

template<typename COLLECTION2 >
MAXON_ATTRIBUTE_FORCE_INLINE Bool	ContainsAll (COLLECTION2 &&other) const

template<typename COLLECTION2 >
Bool	ContainsAllImpl (COLLECTION2 &&other, OverloadRank0) const

Private Member Functions
	MAXON_DISALLOW_COPY_AND_ASSIGN (SortedArray)

MAXON_ATTRIBUTE_NO_INLINE void	DoSort () const

void	CheckSort () const

Private Attributes
ARRAY	_array

Bool	_sorted

Additional Inherited Members
Static Public Member Functions inherited from Collection< COLLECTION, VALUETYPE, SUPER >
static const VALUETYPE &	GetMapKey (const VALUETYPE &key)

Public Attributes inherited from Collection< COLLECTION, VALUETYPE, SUPER >
	VALUETYPE

Static Public Attributes inherited from ArrayBase0< COLLECTION, VALUETYPE, SUPER, HASH >
static const COLLECTION_KIND	KIND

Member Typedef Documentation

◆ TYPE

using TYPE = typename ARRAY::ValueType

◆ Iterator

using Iterator = typename ARRAY::Iterator

The SortedArray iterator is just a type alias for the underlying array's iterator. This means that using the iterator to access array elements will not sort the array or mark it as being modified.

◆ ConstIterator

using ConstIterator = typename ARRAY::ConstIterator

Constructor & Destructor Documentation

◆ SortedArray() [1/3]

SortedArray ( )

Default constructor. Creates an empty array.

◆ SortedArray() [2/3]

SortedArray ( const typename ARRAY::AllocatorType & a )

explicit

This constructor has to be used if an array should use a custom allocator with member variables.

◆ ~SortedArray()

~SortedArray ( )

Destructs the array with all its elements.

◆ SortedArray() [3/3]

SortedArray ( SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > && src )

Move constructor.

Member Function Documentation

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > )

private

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT ( SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > )

Move assignment operator.

◆ Reset()

void Reset ( )

Deletes all elements (calls destructors and frees memory).

◆ Flush()

void Flush ( )

Deletes all elements, but doesn't free memory (calls destructors though).

◆ SetCapacityHint()

ResultMem SetCapacityHint	(	Int	requestedCapacity,
		COLLECTION_RESIZE_FLAGS	resizeFlags = `COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY`
	)

Prepares the internal buffer(s) to hold at least the given number of elements with as few further memory allocations as possible.

Note: This is just a hint. It does not guarantee that the collection will be able to store the number of indicated elements.

Parameters

[in]	requestedCapacity	The desired internal capacity.
[in]	resizeFlags	If ON_GROW_FIT_TO_SIZE is set, the collection will use only as much memory as needed to hold the data.

Returns: False if allocation failed.

◆ GetCount()

Int GetCount ( ) const

Gets the number of array elements.

Returns: Number of array elements.

◆ GetCapacityCount()

Int GetCapacityCount ( ) const

Gets the number of elements for which memory has been allocated (this is usually bigger than GetCount()).

Returns: Number of array elements for which memory has been allocated.

◆ operator[]()

const TYPE& operator[] ( Int idx ) const

Array (subscript) operator for const objects.

Parameters

[in] idx Element index (if it's out of bounds you will get an error in debug code only, otherwise it will crash).

Returns: Array element.

◆ Append()

MAXON_ATTRIBUTE_FORCE_INLINE ResultRef<TYPE> Append ( ARGS &&... args )

Adds a new element at the end of the array and moves the content of x to it.

Parameters

[in] args Values to be forwarded

Returns: Element pointer or OutOfMemoryError if the allocation failed.

◆ AppendPtr()

ResultPtr<TYPE> AppendPtr ( TYPE * x )

PointerArray specific: Adds a pointer to the new element at the end of the array.

Parameters

[in] x Pointer to new element (SortedArray will take ownership of it).

Returns: Element pointer or OutOfMemoryError if the allocation failed.

◆ PopPtr()

Bool PopPtr ( TYPE ** dst )

PointerArray specific: Removes the last element and returns the pointer.

Parameters

[out] dst Used to return pointer to the last element (must not be null), the caller will take ownership of the element.

Returns: True if successful.

◆ InsertPtr()

ResultPtr<TYPE> InsertPtr	(	Int	position,
		TYPE *	x
	)

PointerArray specific: Inserts a pointer to a new element at index position.

Parameters

[in]	position	Insert index (the array size will increase and the existing elements are moved).
[in]	x	Pointer to new element (SortedArray will take ownership of it).

Returns: Element pointer or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [1/2]

ResultRef<TYPE> Insert	(	Int	position,
		ARGS &&...	args
	)

Inserts a new element at iterator position and initializes it with a copy of x.

Parameters

[in]	position	Insert position.
[in]	args	Values to be forwarded

Returns: Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [2/2]

ResultMemT<Iterator> Insert	(	Iterator	position,
		ARGS &&...	args
	)

Inserts a new element at iterator position and initializes it with a copy of x.

Parameters

[in]	position	Insert position.
[in]	args	Values to be forwarded

Returns: Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ InsertBlock() [1/2]

ResultPtr<TYPE> InsertBlock	(	Int	position,
		ARGS &&...	args
	)

Inserts new elements at index position (all elements from position on are moved by the the count of values).

Parameters

[in]	position	Insert index (the array size will increase and the existing elements are moved).
[in]	args	Block with values to be copied/moved. If the block points to nullptr, only its count is used, and you have to call the constructor of the new elements manually.

Returns: Element pointer or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ InsertBlock() [2/2]

ResultMemT<Iterator> InsertBlock	(	Iterator	position,
		ARGS &&...	args
	)

Inserts new elements at iterator position (all elements from position on are moved by the the count of values).

Parameters

[in]	position	Insert position.
[in]	args	Block with values to be copied/moved. If the block points to nullptr, only its count is used, and you have to call the constructor of the new elements manually.

Returns: Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Erase() [1/2]

ResultPtr<TYPE> Erase	(	Int	position,
		Int	eraseCnt = `1`
	)

Erases (removes and deletes) elements.

Parameters

[in]	position	Erase index (Erase() will fail if out of bounds and return nullptr).
[in]	eraseCnt	Number of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) a nullptr will be returned.

Returns: Pointer to the element that is now at position. If position equals the number of elements after Erase() a valid pointer is returned but you are not allowed to access it. OutOfMemoryError is only returned on failure (position was out of bounds).

◆ ErasePtr()

ResultPtr<TYPE> ErasePtr	(	Int	position,
		TYPE **	dst
	)

PointerArray specific: Extracts a single element from the list and returns its pointer. The caller takes ownership of the element.

Parameters

[in]	position	Erase index (Erase() will fail if out of bounds and return nullptr).
[in,out]	dst	Used to return pointer to the erased element (must not be null).

Returns: Pointer to the element that is now at position. If position equals the that of the element after Erase(), a valid pointer is returned but you are not allowed to access it. A nullptr is only returned on failure (position was out of bounds).

◆ SwapErase() [1/2]

ResultMem SwapErase	(	Int	position,
		Int	eraseCnt = `1`
	)

Erases elements within the array. For sorted arrays this is identical to the Erase function.

Parameters

[in]	position	Erase position.
[in]	eraseCnt	Number of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) false will be returned.

Returns: False if position was out of bounds.

◆ SwapErase() [2/2]

Iterator SwapErase	(	Iterator	position,
		Int	eraseCnt = `1`
	)

Erases elements within the array. For sorted arrays this is identical to the Erase function.

Parameters

[in]	position	Erase position.
[in]	eraseCnt	Number of elements to be erased. If eraseCnt is invalid (higher than allowed or negative) an invalid iterator will be returned.

Returns: Iterator for the element that is now at position (its operator Bool() will return false if something failed).

◆ GetBlock() [1/2]

Int GetBlock	(	Int	position,
		Block< TYPE, STRIDED > &	block
	)

Determines a contiguous block of array elements which contains the element at index. For a BaseArray, this yields the whole array as a block.

Parameters

[in]	position	Element index.
[out]	block	Block which contains the element at `index`.

Returns: Start index of the block. The requested element can be found within the block at index - start index.

◆ GetBlock() [2/2]

Int GetBlock	(	Int	position,
		Block< const TYPE, STRIDED > &	block
	)		const

Determines a contiguous block of array elements which contains the element at position. For a BaseArray, this yields the whole array as a block.

Parameters

[in]	position	Element index.
[out]	block	Block which contains the element at `position`.

Returns: Start index of the block. The requested element can be found within the block at position - start index.

◆ Erase() [2/2]

Iterator Erase	(	Iterator	position,
		Int	eraseCnt = `1`
	)

Erases (removes and deletes) elements.

Parameters

[in]	position	Erase position.
[in]	eraseCnt	Number of elements to be erased (if eraseCnt is higher than what is available at position Erase() will succeed, but remove only the number of available elements).

Returns: Iterator for the element that is now at position (its operator Bool() will return false if something failed).

◆ EraseKey()

Bool EraseKey ( const SEARCH & key )

Erases (remove and delete) an element.

Parameters

[in] key The key that the array is searched for.

Returns: True if key was found.

◆ GetFirst() [1/2]

const TYPE* GetFirst ( ) const

Returns the first element of the array.

Returns: Pointer to the first element (nullptr if the array is empty).

◆ GetFirst() [2/2]

TYPE* GetFirst ( )

Returns the first element of the array.

Returns: Pointer to the first element (nullptr if the array is empty).

◆ GetLast() [1/2]

const TYPE* GetLast ( ) const

Returns the last element of the array.

Returns: Pointer to the last element (nullptr if the array is empty).

◆ GetLast() [2/2]

TYPE* GetLast ( )

Returns the last element of the array.

Returns: Pointer to the last element (nullptr if the array is empty).

◆ Resize()

ResultMem Resize	(	Int	newCnt,
		COLLECTION_RESIZE_FLAGS	resizeFlags = `COLLECTION_RESIZE_FLAGS::DEFAULT`
	)

Resizes the array to contain newCnt elements (BaseArray specific). If newCnt is smaller than GetCount() all extra elements are being deleted. If it is greater the array is expanded and the default constructor is called for new elements.

Parameters

[in]	newCnt	New array size.
[in]	resizeFlags	See COLLECTION_RESIZE_FLAGS (support depends on the inherited array).

Returns: False if allocation failed.

◆ Pop()

Bool Pop ( TYPE * dst = nullptr )

Deletes the last element.

Parameters

[out] dst Nullptr or pointer to return value.

Returns: True if there was at least one element.

◆ GetIndex()

Int GetIndex ( const TYPE & x ) const

Gets the index of the element. The element must be part of the array, otherwise (e.g. if x is a copy of an array element) InvalidArrayIndex will be returned.

Returns: Index of element or InvalidArrayIndex (not element of this).

◆ CopyFrom() [1/2]

Result<void> CopyFrom ( const SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > & src )

Copies an array.

Parameters

[in] src Source array.

Returns: OK on success.

◆ CopyFrom() [2/2]

Result<void> CopyFrom ( COLLECTION2 && other )

Makes this collection a copy of other. If copying doesn't succeed for all entries, the collection will be left in a valid, but intermediate state with only some entries from other added.

Parameters

[in]	other	Another collection, may be any iterable object.
[in]	resizeFlags	If ON_GROW_FIT_TO_SIZE is set, the collection will use only as much memory as needed to hold the data.

Returns: OK on success.

◆ Swap()

void Swap	(	Iterator	a,
		Iterator	b
	)

Swaps elements a and b (equivalent to global Swap(array[a], array[b]).

Parameters

[in]	a	Position of element to be swapped.
[in]	b	Position of element to be swapped.

◆ GetMemorySize()

Int GetMemorySize ( ) const

Calculates the memory usage for this array. The array element class must have a public member GetMemorySize that returns an element's size.

Returns: Memory size in bytes.

◆ Begin() [1/2]

ConstIterator Begin ( ) const

Gets an iterator for the first element. When you modify the array Begin() will change, it is not a constant value.

Returns: Iterator for the first element (equal to End() if the array is empty).

◆ Begin() [2/2]

Iterator Begin ( )

Gets an iterator for the first element. When you modify the array Begin() will change, it is not a constant value.

Returns: Iterator for the first element (equal to End() if the array is empty).

◆ End() [1/2]

ConstIterator End ( ) const

Gets an iterator for the end (End() - 1 is the last element if the array is not empty). When you modify the array End() will change, it is not a constant value.

Returns: Iterator for the array end (this is behind the last element).

◆ End() [2/2]

Iterator End ( )

Gets an iterator for the end (End() - 1 is the last element if the array is not empty). When you modify the array End() will change, it is not a constant value.

Returns: Iterator for the array end (this is behind the last element).

◆ SortChanged()

void SortChanged ( )

Marks the array as non-sorted. Sorting will happen upon the next read access.

◆ Sort()

void Sort ( )

Manually sorts the array.

◆ FindValue() [1/2]

TYPE* FindValue ( const SEARCH & key )

Finds an element in an array. The time for searching will be O(log(n)).

Parameters

[in] key The key that the array is searched for.

Returns: If an element is found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

◆ FindValue() [2/2]

const TYPE* FindValue ( const SEARCH & key ) const

Finds an element in an array. The time for searching will be O(log(n)).

Parameters

[in] key The key that the array is searched for.

Returns: If an element is found a pointer to it will be returned, otherwise the result is nullptr. If multiple elements have the same key value the first of those elements will be returned.

◆ FindIndex()

Int FindIndex ( const SEARCH & key ) const

Finds the index of an element in an array. The time for searching will be O(log(n)).

Parameters

[in] key The key that the array is searched for.

Returns: If an element is found its index will be returned, otherwise the result is the bitwise inverse of the index where key would be inserted (which is always negative). If multiple elements have the same key value the index of the first of those elements will be returned.

◆ InsertValue() [1/2]

ResultRef<TYPE> InsertValue ( const SEARCH & key )

Finds an element in an array or insert it if it was not found. The time for this operation will be O(log(n)) for searching plus O(n) for inserting. Keep in mind that the resulting pointer will only be valid right after the operation as any additional array operation might shuffle array indices. To use this routine the SortedArray class must define the following member:

static void InitInsertData(T& initme, const SEARCH& key);

key

PyObject * key

Definition: abstract.h:289

Parameters

[in] key The key that the array is searched for.

Returns: Element reference or OutOfMemoryError if the allocation failed.

◆ InsertValue() [2/2]

ResultRef<TYPE> InsertValue	(	const SEARCH &	key,
		Bool &	newElement,
		Int *	index = `nullptr`
	)

Finds an element in an array or insert it if it was not found. The time for this operation will be O(log(n)) for searching plus O(n) for inserting. Keep in mind that the resulting pointer will only be valid right after the operation as any additional array operation might shuffle array indices. The value should be filled right after the function returns. InitInsertData is not being called.

Parameters

[in]	key	The key that the array is searched for.
[out]	newElement	Specifies if the element was newly inserted (true) or if it was found in the array (false)
[out]	index	The index of the found or inserted element. May be nullptr.

Returns: Element reference or OutOfMemoryError if the allocation failed.

◆ GetUnderlyingArray() [1/2]

ARRAY& GetUnderlyingArray ( )

Returns the underlying array.

Returns: Underlying array.

◆ GetUnderlyingArray() [2/2]

const ARRAY& GetUnderlyingArray ( ) const

Returns the underlying array.

Returns: Underlying array.

◆ CheckSort()

void CheckSort ( ) const

private

Member Data Documentation

◆ _array

ARRAY _array

mutableprivate

◆ _sorted

Bool _sorted

mutableprivate

Detailed Description

template<typename MYSELF, typename ARRAY, BASESORTFLAGS FLAGS = BASESORTFLAGS::NONE, Bool PARALLEL = false> class maxon::SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Member Typedef Documentation

◆ TYPE

◆ Iterator

◆ ConstIterator

Constructor & Destructor Documentation

◆ SortedArray() [1/3]

◆ SortedArray() [2/3]

◆ ~SortedArray()

◆ SortedArray() [3/3]

Member Function Documentation

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

◆ Reset()

◆ Flush()

◆ SetCapacityHint()

◆ GetCount()

◆ GetCapacityCount()

◆ operator[]()

◆ Append()

◆ AppendPtr()

◆ PopPtr()

◆ InsertPtr()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ InsertBlock() [1/2]

◆ InsertBlock() [2/2]

◆ Erase() [1/2]

◆ ErasePtr()

◆ SwapErase() [1/2]

◆ SwapErase() [2/2]

◆ GetBlock() [1/2]

◆ GetBlock() [2/2]

◆ Erase() [2/2]

◆ EraseKey()

◆ GetFirst() [1/2]

◆ GetFirst() [2/2]

◆ GetLast() [1/2]

◆ GetLast() [2/2]

◆ Resize()

◆ Pop()

◆ GetIndex()

◆ CopyFrom() [1/2]

◆ CopyFrom() [2/2]

◆ Swap()

◆ GetMemorySize()

◆ Begin() [1/2]

◆ Begin() [2/2]

◆ End() [1/2]

◆ End() [2/2]

◆ SortChanged()

◆ Sort()

◆ FindValue() [1/2]

◆ FindValue() [2/2]

◆ FindIndex()

◆ InsertValue() [1/2]

◆ InsertValue() [2/2]

◆ GetUnderlyingArray() [1/2]

◆ GetUnderlyingArray() [2/2]

◆ CheckSort()

Member Data Documentation

◆ _array

◆ _sorted

template<typename MYSELF, typename ARRAY, BASESORTFLAGS FLAGS = BASESORTFLAGS::NONE, Bool PARALLEL = false>
class maxon::SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >