Have anybody created a wrapper container

struct Sorted(ArrayLike, alias lessThanPred)

that wraps an array-like type ArrayLike so that it's always sorted according to the binary predicate lessThanPred?

On Saturday, 12 November 2022 at 14:07:46 UTC, Per Nordlöw wrote:

struct Sorted(ArrayLike, alias lessThanPred)

I'm not sure if these are a good fit for what you need, but have you checked https://dlang.org/phobos/std_container_rbtree.html and https://dlang.org/phobos/std_container_binaryheap.html ?

On Sunday, 13 November 2022 at 18:51:09 UTC, Siarhei Siamashka wrote:

struct Sorted(ArrayLike, alias lessThanPred)

He said on Discord he want contiguous data structure, rbtree allocates too much

On Monday, 14 November 2022 at 00:29:40 UTC, Tejas wrote:

OK, I guess this person got their question answered on Discord and does not need any further assistance.

On Monday, 14 November 2022 at 00:29:40 UTC, Tejas wrote:

rbtree has it's uses cases. I wanted a sorted array because I want to include it in a benchmark suite and study it's time and space complexity. No application yet.

This is what I have so far.

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?

On Tuesday, 15 November 2022 at 21:03:24 UTC, Per Nordlöw wrote:

Found some issues but still cannot instantiate my solution at

https://github.com/nordlow/phobos-next/blob/master/src/nxt/sorted.d#L15

when I uncomment the line containing

// TODO: completeSort!(less, ss)(_source[0 .. n].assumeSorted!(less), _source[n .. $]);

On Tuesday, 15 November 2022 at 22:15:36 UTC, Per Nordlöw wrote:

// TODO: completeSort!(less, ss)(_source[0 .. n].assumeSorted!(less), _source[n .. $]);

I made an adjustment to make better use of existing member functions of SortedRange.

Still, does anybody understand why the line https://github.com/nordlow/phobos-next/blob/master/src/nxt/sorted.d#L52 fails to compile as

sorted.d(52): Error: none of the overloads of template `std.algorithm.sorting.completeSort` are callable using argument types `!("a < b", SwapStrategy.unstable)(SortedRange!(int[], "a < b", SortedRangeOptions.assumeSorted), int[])` /home/per/.local/dlang/linux/bin64/src/phobos/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(74): Error: template instance `nxt.sorted.Sorted!(int[], "a < b", SwapStrategy.unstable).Sorted.insert!int` error instantiating

On Tuesday, 15 November 2022 at 22:32:56 UTC, Per Nordlöw wrote:

Maybe add two typeof arguments?

  completeSort!(less, ss, typeof(_source), typeof(_raw))(_source[0 .. n], _raw[n .. $]);

On Tuesday, 15 November 2022 at 20:09:40 UTC, Per Nordlöw wrote:

For doing a fast insert into an already sorted array (and avoiding duplicated values) it's probably better to do something like this:

bool fast_insert_into_a_sorted_array(alias less = "a < b", T)(ref T[] a, T value)
{
  auto pos = a.assumeSorted!(less).lowerBound(value).length;
  if (pos < a.length && a[pos] == value)
    return false; // indicate no insert
  a.insertInPlace(pos, value);
  return true; // indicate insert
}