www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorted Array (Container) Type

reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
Have anybody created a wrapper container

```d
struct Sorted(ArrayLike, alias lessThanPred)
```


that wraps an array-like type `ArrayLike` so that it's always 
sorted according to the binary predicate `lessThanPred`?
Nov 12 2022
next sibling parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Saturday, 12 November 2022 at 14:07:46 UTC, Per Nordlöw wrote:

 Have anybody created a wrapper container

 ```d
 struct Sorted(ArrayLike, alias lessThanPred)
 ```


 that wraps an array-like type `ArrayLike` so that it's always 
 sorted according to the binary predicate `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 ?
Nov 13 2022
parent reply Tejas <notrealemail gmail.com> writes:
On Sunday, 13 November 2022 at 18:51:09 UTC, Siarhei Siamashka 
wrote:

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

 Have anybody created a wrapper container

 ```d
 struct Sorted(ArrayLike, alias lessThanPred)
 ```


 that wraps an array-like type `ArrayLike` so that it's always 
 sorted according to the binary predicate `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 ?


He said on Discord he want contiguous data structure, rbtree 
allocates too much
Nov 13 2022
next sibling parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Monday, 14 November 2022 at 00:29:40 UTC, Tejas wrote:

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


OK, I guess this person got their question answered on Discord 
and does not need any further assistance.
Nov 14 2022
prev sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Monday, 14 November 2022 at 00:29:40 UTC, Tejas wrote:

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


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.
Nov 15 2022
parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Tuesday, 15 November 2022 at 20:09:40 UTC, Per Nordlöw wrote:

 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.


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

```D
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
}
```
Nov 15 2022
parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Tuesday, 15 November 2022 at 23:27:07 UTC, Siarhei Siamashka 
wrote:

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

 ```D
 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
 }
 ```


Actually the comparison needs to be done using the provided 
predicate too:

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

unittest {
   auto less = function bool(ref Tuple!(int, int) a,
                             ref Tuple!(int, int) b) { return a[0] 
< b[0]; };
   auto a = [tuple(0, 1), tuple(0, 2)];
   a.sort!less;

   assert(a.fast_insert_in_a_sorted_array!less(tuple(0, 2)) == 
false);
   assert(a == [tuple(0, 1), tuple(0, 2)]);

   assert(a.fast_insert_in_a_sorted_array!less(tuple(0, 3)) == 
true);
   assert(a == [tuple(0, 1), tuple(0, 2), tuple(0, 3)]);

   assert(a.fast_insert_in_a_sorted_array!less(tuple(-1, 0)) == 
true);
   assert(a == [tuple(-1, 0), tuple(0, 1), tuple(0, 2), tuple(0, 
3)]);
}
```
Nov 15 2022
prev sibling parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
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?
Nov 15 2022
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Tuesday, 15 November 2022 at 21:03:24 UTC, Per Nordlöw wrote:

 This is what I have so far.


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

```d
// TODO: completeSort!(less, ss)(_source[0 .. 
n].assumeSorted!(less), _source[n .. $]);
```
Nov 15 2022
parent reply Per =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Tuesday, 15 November 2022 at 22:15:36 UTC, Per Nordlöw wrote:

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

 This is what I have so far.


 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

 ```d
 // 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```
Nov 15 2022
parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Tuesday, 15 November 2022 at 22:32:56 UTC, Per Nordlöw wrote:

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


Maybe add two typeof arguments?
```D
   completeSort!(less, ss, typeof(_source), 
typeof(_raw))(_source[0 .. n], _raw[n .. $]);
```
Nov 15 2022