#include <sortedarray.h>
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:
- 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< 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 |
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]
| SortedArray | ( | ) |
Default constructor. Creates an empty arry.
◆ SortedArray() [2/3]
|
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()
|
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] 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 | ( | 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[]()
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() [1/3]
Adds a new element at the end of the array.
- Returns
- Element pointer or OutOfMemoryError if the allocation failed.
◆ Append() [2/3]
Adds a new element at the end of the array and initializes it with a copy of x.
- Parameters
-
[in] x Value to be copied.
- Returns
- Element pointer or OutOfMemoryError if the allocation failed.
◆ Append() [3/3]
Adds a new element at the end of the array and moves the content of x to it.
- Parameters
-
[in] x Value to be moved.
- Returns
- Element pointer or OutOfMemoryError if the allocation failed.
◆ AppendPtr()
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()
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.
◆ Insert() [1/8]
Inserts a new default element at index position.
- Parameters
-
[in] position Insert 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()
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() [2/8]
| ResultMemT<Iterator> Insert | ( | Iterator | position | ) |
Inserts a new default element at iterator position.
- Parameters
-
[in] position Insert position.
- Returns
- Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).
◆ Insert() [3/8]
Inserts a new element at index position and initializes it with a copy of x.
- Parameters
-
[in] position Insert index (the array size will increase and the existing elements are moved). [in] x Value 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] position Insert position. [in] x Value to be copied.
- Returns
- Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).
◆ Insert() [5/8]
Inserts a new element at index position and moves the content of x to it.
- Parameters
-
[in] position Insert index (the array size will increase and the existing elements are moved). [in] x Value 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] position Insert position. [in] x Value to be moved.
- Returns
- Iterator for the new element or OutOfMemoryError if the allocation failed (or position is out of boundaries).
◆ Insert() [7/8]
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] values Block 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] position Insert position. [in] values Block 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]
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()
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]
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]
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]
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]
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]
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()
Deletes the last element.
- Parameters
-
[out] dst Nullptr or pointer to return value.
- Returns
- True if there was at least one element.
◆ GetIndex()
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()
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 | ( | 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 |
◆ Begin() [2/2]
| Iterator Begin | ( | ) |
◆ End() [1/2]
| ConstIterator End | ( | ) | const |
◆ End() [2/2]
| Iterator End | ( | ) |
◆ 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]
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:
- Parameters
-
[in] key The key that the array is searched for.
- Returns
- Element reference or OutOfMemoryError if the allocation failed.
◆ InsertValue() [2/2]
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()
|
private |
Member Data Documentation
◆ _array
|
mutableprivate |
◆ _sorted
|
mutableprivate |