|
Enhanced C#
Language of your choice: library documentation
|
|
Enhanced C#
Language of your choice: library documentation
|
Contains static methods to help manage raw arrays with even less overhead than InternalList{T}. More...
Contains static methods to help manage raw arrays with even less overhead than InternalList{T}.
The methods of this class are used by some data structures that contain arrays but, for whatever reason, don't use InternalList{T}. These methods are also used by InternalList(T) itself.
Static Public Member Functions | |
| static InternalList< T > | AsInternalList< T > (this T[] array) |
| Converts an array to InternalList (exists to help infer type params) More... | |
| static InternalList< T > | AsInternalList< T > (this T[] array, int count) |
| static T[] | CopyToNewArray< T > (T[] _array, int _count, int newCapacity) |
| static T[] | CopyToNewArray< T > (T[] array) |
| static void | Fill< T > (T[] array, T value) |
| static void | Fill< T > (T[] array, int start, int count, T value) |
| static int | BinarySearch< T > (T[] array, int count, T k, Comparer< T > comp, bool lowerBound) |
| static int | BinarySearch< T, K > (T[] _array, int _count, K k, Func< T, K, int > compare, bool lowerBound) |
| Performs a binary search with a custom comparison function. More... | |
| static int | BinarySearchByIndex< Anything > (Anything data, int count, Func< int, Anything, int > compare, bool lowerBound) |
| A binary search function that knows nothing about the list being searched. More... | |
| static int | NextLargerSize (int than) |
| As an alternative to the typical enlarging pattern of doubling the array size when it overflows, this function proposes a 75% size increase instead (100% when the array is small), while ensuring that the array length stays even. More... | |
| static int | NextLargerSize (int than, int capacityLimit) |
| Same as NextLargerSize(int), but allows you to specify a capacity limit, to avoid wasting memory when a collection has a known maximum size. More... | |
| static T[] | Insert< T > (int index, T item, T[] array, int count) |
| static T[] | InsertRangeHelper< T > (int index, int spaceNeeded, T[] array, int count) |
| static T[] | AutoRaiseCapacity< T > (T[] array, int count, int more, int capacityLimit) |
| static int | RemoveAt< T > (int index, T[] array, int count) |
| static int | RemoveAt< T > (int index, int removeCount, T[] array, int count) |
| static void | Move< T > (T[] array, int from, int to) |
| static void | Sort< T > (T[] array, int index, int count, Comparison< T > comp) |
| Performs a quicksort using a Comparison function. More... | |
| static void | InsertionSort< T > (T[] array, int index, int count, Comparison< T > comp) |
| Performs an insertion sort. More... | |
| static bool | AllEqual< T > (this InternalList< T > a, InternalList< T > b) |
| static bool | AllEqual< T > (T[] a, T[] b, int count) |
|
inlinestatic |
Converts an array to InternalList (exists to help infer type params)
|
inlinestatic |
Performs a binary search with a custom comparison function.
| _array | Array to search |
| _count | Number of elements used in the array |
| k | A key to compare with elements of the array |
| compare | Lambda function that knows how to compare Ts with Ks (T and K can be the same). It is passed a series of elements from the array. It must return 0 if the element has the desired value, 1 if the supplied element is higher than desired, and -1 if it is lower than desired. |
| lowerBound | Whether to find the "lower bound" in case there are duplicates in the list. If duplicates exist of the search key k, the lowest index of a matching duplicate is returned. This search mode may be slightly slower when a match exists. |
// The first 6 elements are sorted. The seventh is invalid, // and must be excluded from the binary search. int[] array = new int[] { 0, 10, 20, 30, 40, 50, -1 }; // The result will be 2, because array[2] == 20. int a = InternalList.BinarySearch(array, 6, i => i.CompareTo(20)); // The result will be ~2, which equals -3, because index 2 would // be the correct place to insert 17 to preserve the sort order. int b = InternalList.BinarySearch(array, 6, i => i.CompareTo(17));
|
inlinestatic |
A binary search function that knows nothing about the list being searched.
| Anything | Any data type relevant to the caller. |
| data | State information to be passed to compare() |
| count | Number of items in the list being searched |
| compare | Comparison method that is given the current index to examine and the state parameter "data". |
| lowerBound | Whether to find the "lower bound" in case there are duplicates in the list. If duplicates exist of the search key k exist, the lowest index of a matching duplicate is returned. This search mode may be slightly slower when a match exists. |
|
inlinestatic |
Performs an insertion sort.
The insertion sort is a stable sort algorithm that is slow in general (O(N^2)). It should be used only when (a) the list to be sorted is short (less than about 20 elements) or (b) the list is very nearly sorted already.
|
inlinestatic |
As an alternative to the typical enlarging pattern of doubling the array size when it overflows, this function proposes a 75% size increase instead (100% when the array is small), while ensuring that the array length stays even.
With a seed of 0, 2, or 4: 0, 2, 4, 8, 16, 30, 54, 96, 170, 298, 522...
With a seed of 1: 1, 2, 4, 8, 16, 30, 54, 96, 170, 298, 522...
With a seed of 3: 3, 6, 12, 22, 40, 72, 128, 226, 396...
With a seed of 5: 5, 10, 18, 32, 58, 102, 180, 316, 554...
With a seed of 7: 7, 14, 26, 46, 82, 144, 254, 446, 782...
75% size increases require 23.9% more allocations than size doubling (1.75 to the 1.239th power is about 2.0), but memory utilization is increased. With size doubling, the average list uses 2/3 of its entries, but with this resizing pattern, the average list uses 72.72% of its entries. The average size of a list is 8.3% lower. Originally I used 50% size increases, but they required 71% more allocations, which seemed like too much.
|
inlinestatic |
Same as NextLargerSize(int), but allows you to specify a capacity limit, to avoid wasting memory when a collection has a known maximum size.
| than | Return value will be larger than this number. |
| capacityLimit | Maximum value to return. This parameter is ignored if it than >= capacityLimit. |
capacityLimit is returned instead. If the return value would be slightly less than capacityLimit (within 20%) then capacityLimit is returned, to ensure that another reallocation will not be required later.than). If the return value would be more than capacityLimit,
|
inlinestatic |
Performs a quicksort using a Comparison function.
Normally one uses Array.Sort for sorting arrays. This method exists because there is no Array.Sort overload that accepts both a Comparison and a range (index, count), nor does the .NET framework provide access to its internal adapter that converts Comparison to IComparer.
This quicksort algorithm uses a best-of-three pivot so that it remains performant (fast) if the input is already sorted. It is designed to perform reasonably well in case the data contains many duplicates (not verified). It is also designed to avoid using excessive stack space if a worst-case input occurs that requires O(N^2) time.
1.8.7
