Sorted Array (Container) Type
Per Nordlöw
per.nordlow at gmail.com
Tue Nov 15 21:03:24 UTC 2022
This is what I have so far.
```d
import std.algorithm.mutation : SwapStrategy;
/** Wrapper container around array (slice) or array-like
(container) `A`.
*
* See_Also: https://en.wikipedia.org/wiki/Sorted_array
*/
struct Sorted(A, alias less = "a < b", SwapStrategy ss =
SwapStrategy.unstable)
if (is(A == U[], U) || // isDynamicArray
__traits(isStaticArray, A))
{
private alias E = typeof(A.init[0]);
this(A source)
{
_source = source[];
import std.algorithm.sorting : sort;
sort!(less, ss)(_source[]);
}
auto opSlice() return scope => _source[];
static if (is(A == U[], U)) // isDynamicArray
bool insert(in E x) scope @trusted // TODO: @safe
{
import std.algorithm.sorting : completeSort;
foreach (ref e; _source)
if (e == x)
return false; // indicate no insert
const n = _source.length;
_source.reserve(n + 1); // TODO: use template parameter
`Growth`
_source.length += 1;
_source[n] = x;
// TODO: enable:
version(none) completeSort!(less, ss)(_source[0 .. n],
_source[n .. $]); // this fails
return true; // indicate insert
}
bool contains(in E x) const
{
foreach (ref e; _source)
if (e == x)
return true;
return false;
}
private A _source;
}
/// constructor from dynamic array
@safe pure nothrow unittest
{
scope int[] x = [3,2,1];
alias A = typeof(x);
auto sx = Sorted!(A)(x);
assert(sx[] == [1,2,3]);
assert(sx[].isSorted);
assert(!sx.insert(3));
// assert(sx.insert(4));
}
/// constructor from static array
@safe pure nothrow @nogc unittest
{
int[3] x = [3,2,1];
alias A = typeof(x);
auto sx = Sorted!(A)(x);
assert(sx[].isSorted);
}
version(unittest)
{
import std.algorithm.sorting : isSorted;
}
```
. But I don't understand why my call to completeSort isn't
allowed by the compiler and errors as
```
sorted.d(78): Error: none of the overloads of template
`std.algorithm.sorting.completeSort` are callable using argument
types `!("a < b", SwapStrategy.unstable)(int[], int[])`
std/algorithm/sorting.d(117): Candidate is:
`completeSort(alias less = "a < b", SwapStrategy ss =
SwapStrategy.unstable, Lhs, Rhs)(SortedRange!(Lhs, less) lhs, Rhs
rhs)`
sorted.d(98): Error: template instance `nxt.sorted.Sorted!(int[],
"a < b", SwapStrategy.unstable)` error instantiating
```
What am I missing?
More information about the Digitalmars-d-learn
mailing list