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