SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > Class Template Reference

#include <sortedarray.h>

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

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
MYSELFThe class itself.
ARRAYThe used array, e.g. BaseArray, BlockArray or PointerArray.
FLAGSSee BASESORTFLAGS, normally can be left at default.
PARALLELUse 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< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, ARRAY::ValueType, EmptyClass >
using Super = BaseCollection< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, EmptyClass >
 
using ValueType = ARRAY::ValueType
 
- Public Types inherited from BaseCollection< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, EmptyClass >
using IsCollection = std::true_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 TYPEoperator[] (Int idx) const
 
ResultRef< TYPEAppend ()
 
ResultRef< TYPEAppend (const TYPE &x)
 
ResultRef< TYPEAppend (TYPE &&x)
 
ResultPtr< TYPEAppendPtr (TYPE *x)
 
Bool PopPtr (TYPE **dst)
 
ResultRef< TYPEInsert (Int position)
 
ResultPtr< TYPEInsertPtr (Int position, TYPE *x)
 
ResultMemT< IteratorInsert (Iterator position)
 
ResultRef< TYPEInsert (Int position, const TYPE &x)
 
ResultMemT< IteratorInsert (Iterator position, const TYPE &x)
 
ResultRef< TYPEInsert (Int position, TYPE &&x)
 
ResultMemT< IteratorInsert (Iterator position, TYPE &&x)
 
ResultPtr< TYPEInsert (Int position, const Block< const TYPE > &values)
 
ResultMemT< IteratorInsert (Iterator position, const Block< const TYPE > &values)
 
ResultPtr< TYPEErase (Int position, Int eraseCnt=1)
 
ResultPtr< TYPEErasePtr (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 TYPEGetFirst () const
 
TYPEGetFirst ()
 
const TYPEGetLast () const
 
TYPEGetLast ()
 
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_same<typename std::decay<COLLECTION2>::type, SortedArray>::value>::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 >
TYPEFindValue (const SEARCH &key)
 
template<typename SEARCH >
const TYPEFindValue (const SEARCH &key) const
 
template<typename SEARCH >
Int FindIndex (const SEARCH &key) const
 
template<typename SEARCH >
ResultRef< TYPEInsertValue (const SEARCH &key)
 
template<typename SEARCH >
ResultRef< TYPEInsertValue (const SEARCH &key, Bool &newElement, Int *index=nullptr)
 
ARRAYGetUnderlyingArray ()
 
const ARRAYGetUnderlyingArray () const
 
- Public Member Functions inherited from ArrayBase< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, ARRAY::ValueType, EmptyClass, MYSELF >
MAXON_ATTRIBUTE_FORCE_INLINE ArrayBase (ARGS &&... args)
 
ArrayImpl< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > &> ToArray ()
 
ArrayImpl< const SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > &> ToArray () const
 
MAXON_ATTRIBUTE_FORCE_INLINE operator ArrayImpl< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > &> ()
 
MAXON_ATTRIBUTE_FORCE_INLINE operator ArrayImpl< const SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > &> () const
 
- Public Member Functions inherited from ArrayBase0< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, ARRAY::ValueType, EmptyClass, MYSELF >
MAXON_ATTRIBUTE_FORCE_INLINE ArrayBase0 (ARGS &&... args)
 
Bool IsValidIndex (Int index) const
 
Result< void > CheckValidIndex (Int index) const
 
Int FindIndex (typename ByValueParam< ARRAY::ValueType >::type v, Int start) const
 
Int FindLastIndex (typename ByValueParam< ARRAY::ValueType >::type v) const
 
Int FindLastIndex (typename ByValueParam< ARRAY::ValueType >::type v, Int start) const
 
Bool EraseFirst (typename ByValueParam< ARRAY::ValueType >::type v)
 
Int EraseAll (typename ByValueParam< ARRAY::ValueType >::type v)
 
Result< void > AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)
 
Result< void > InsertAll (Int index, COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
Result< void > Add (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
Result< void > SubtractImpl (COLLECTION2 &&other, OverloadRank0)
 
Bool IsEqualImpl (const COLLECTION2 &other, COMPARE &&cmp, OverloadRank0) const
 
UInt GetHashCode () const
 
MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > > Slice (Int start)
 
MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< const SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > > Slice (Int start) const
 
MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > > Slice (Int start, Int end)
 
MAXON_ATTRIBUTE_FORCE_INLINE AutoIterator< const SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL > > Slice (Int start, Int end) const
 
BlockIterator< false, false > GetBlocks ()
 
BlockIterator< true, false > GetBlocks () const
 
BlockIterator< false, true > GetStridedBlocks ()
 
BlockIterator< true, true > GetStridedBlocks () const
 
- Public Member Functions inherited from Collection< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, ARRAY::ValueType, EmptyClass >
MAXON_ATTRIBUTE_FORCE_INLINE Collection (ARGS &&... args)
 
ResultOk< void > VariadicAppend ()
 
Result< void > VariadicAppend (V &&value, VALUES &&... rest)
 
 operator ValueReceiver< const ARRAY::ValueType &> ()
 
 operator ValueReceiver< ARRAY::ValueType &&> ()
 
 operator ValueReceiver< typename std::conditional< std::is_scalar< ARRAY::ValueType >::value, ARRAY::ValueType, DummyParamType &>::type > ()
 
Result< BoolForEach (FN &&callback)
 
H::Iterator Find (typename ByValueParam< ARRAY::ValueType >::type v)
 
H::ConstIterator Find (typename ByValueParam< ARRAY::ValueType >::type v) const
 
Int FindIndex (typename ByValueParam< ARRAY::ValueType >::type v) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Bool Contains (typename ByValueParam< ARRAY::ValueType >::type v) const
 
- Public Member Functions inherited from BaseCollection< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, EmptyClass >
MAXON_ATTRIBUTE_FORCE_INLINE BaseCollection (ARGS &&... args)
 
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type operator== (const COLLECTION2 &other) const
 
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value, Bool >::type operator!= (const COLLECTION2 &other) const
 
MAXON_ATTRIBUTE_FORCE_INLINE std::enable_if< maxon::IsCollection< COLLECTION2 >::value &&!std::is_same< typename std::decay< COMPARE >::type, EQUALITY >::value, Bool >::type IsEqual (const COLLECTION2 &other, COMPARE &&cmp=COMPARE()) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > AppendAll (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::ON_GROW_RESERVE_CAPACITY)
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > CopyFrom (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags=COLLECTION_RESIZE_FLAGS::FIT_TO_SIZE)
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > Subtract (COLLECTION2 &&other)
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > Intersect (const COLLECTION2 &other)
 
Bool Intersects (const COLLECTION2 &other) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Result< void > CopyFromImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, OverloadRank0)
 
Result< void > AppendAllImpl (COLLECTION2 &&other, COLLECTION_RESIZE_FLAGS resizeFlags, Bool overwrite, OverloadRank0)
 
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) const
 
MAXON_ATTRIBUTE_FORCE_INLINE Bool ContainsAll (COLLECTION2 &&other) const
 
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< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, ARRAY::ValueType, EmptyClass >
static const ARRAY::ValueType & GetMapKey (const ARRAY::ValueType &key)
 
- Static Public Attributes inherited from ArrayBase0< SortedArray< MYSELF, ARRAY, FLAGS, PARALLEL >, ARRAY::ValueType, EmptyClass, MYSELF >
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]

Default constructor. Creates an empty arry.

◆ 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()

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 ( void  )

Deletes all elements (calls destructors and frees memory).

◆ Flush()

void Flush ( void  )

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]requestedCapacityThe desired internal capacity.
[in]resizeFlagsIf 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 ( void  ) 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]idxElement index (if it's out of bounds you will get an error in debug code only, otherwise it will crash).
Returns
Array element.

◆ Append() [1/3]

ResultRef<TYPE> Append ( )

Adds a new element at the end of the array.

Returns
Element pointer or OutOfMemoryError if the allocation failed.

◆ Append() [2/3]

ResultRef<TYPE> Append ( const TYPE x)

Adds a new element at the end of the array and initializes it with a copy of x.

Parameters
[in]xValue to be copied.
Returns
Element pointer or OutOfMemoryError if the allocation failed.

◆ Append() [3/3]

ResultRef<TYPE> Append ( TYPE &&  x)

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

Parameters
[in]xValue to be moved.
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]xPointer 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]dstUsed to return pointer to the last element (must not be null), the caller will take ownership of the element.
Returns
True if successful.

◆ Insert() [1/8]

ResultRef<TYPE> Insert ( Int  position)

Inserts a new default element at index position.

Parameters
[in]positionInsert index (the array size will increase and the existing elements are moved).
Returns
Element reference or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ InsertPtr()

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

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

Parameters
[in]positionInsert index (the array size will increase and the existing elements are moved).
[in]xPointer 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() [2/8]

ResultMemT<Iterator> Insert ( Iterator  position)

Inserts a new default element at iterator position.

Parameters
[in]positionInsert position.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [3/8]

ResultRef<TYPE> Insert ( Int  position,
const TYPE x 
)

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

Parameters
[in]positionInsert index (the array size will increase and the existing elements are moved).
[in]xValue to be copied.
Returns
Element reference or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [4/8]

ResultMemT<Iterator> Insert ( Iterator  position,
const TYPE x 
)

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

Parameters
[in]positionInsert position.
[in]xValue to be copied.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [5/8]

ResultRef<TYPE> Insert ( Int  position,
TYPE &&  x 
)

Inserts a new element at index position and moves the content of x to it.

Parameters
[in]positionInsert index (the array size will increase and the existing elements are moved).
[in]xValue to be moved.
Returns
Element reference or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [6/8]

ResultMemT<Iterator> Insert ( Iterator  position,
TYPE &&  x 
)

Inserts a new element at iterator position and moves the content of x to it.

Parameters
[in]positionInsert position.
[in]xValue to be moved.
Returns
Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).

◆ Insert() [7/8]

ResultPtr<TYPE> Insert ( Int  position,
const Block< const TYPE > &  values 
)

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

Parameters
[in]positionInsert index (the array size will increase and the existing elements are moved).
[in]valuesBlock with values to be copied. 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).

◆ Insert() [8/8]

ResultMemT<Iterator> Insert ( Iterator  position,
const Block< const TYPE > &  values 
)

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

Parameters
[in]positionInsert position.
[in]valuesBlock with values to be copied. 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]positionErase index (Erase() will fail if out of bounds and return nullptr).
[in]eraseCntNumber 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]positionErase index (Erase() will fail if out of bounds and return nullptr).
[in,out]dstUsed 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]positionErase position.
[in]eraseCntNumber 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]positionErase position.
[in]eraseCntNumber 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]positionElement index.
[out]blockBlock 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]positionElement index.
[out]blockBlock 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]positionErase position.
[in]eraseCntNumber 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]keyThe 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()

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]newCntNew array size.
[in]resizeFlagsSee 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]dstNullptr 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]srcSource 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]otherAnother collection, may be any iterable object.
[in]resizeFlagsIf 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]aPosition of element to be swapped.
[in]bPosition of element to be swapped.

◆ GetMemorySize()

Int GetMemorySize ( void  ) 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]keyThe 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]keyThe 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]keyThe 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);
Parameters
[in]keyThe 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]keyThe key that the array is searched for.
[out]newElementSpecifies if the element was newly inserted (true) or if it was found in the array (false)
[out]indexThe 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