Recently I stumbled upon a small issue in dlang's docs.
I wanted to look up uniq in std.algorithm. Started from https://dlang.org/phobos/std_algorithm.html and clicked uniq, no
problem, all good. But my code did not work. After some debugging
I saw, that for some inputs uniq just did not work. I clicked around
some more in the online docs and finally arrived at https://dlang.org
/phobos/std_algorithm_iteration.html which also lists uniq at the
beginning of the page and mentions (only there) that the input needs to
be sorted.
With that all was back to good :)

Would it make sense to mention this prerequisite also at the main documentation of uniq (https://dlang.org/phobos/std_algorithm_iteration.html#uniq)

Kind regards,
Christian

On Thu, Dec 08, 2022 at 09:15:45PM +0100, Christian Köstlin via Digitalmars-d-learn wrote:
> Recently I stumbled upon a small issue in dlang's docs.
> I wanted to look up uniq in std.algorithm. Started from
> https://dlang.org/phobos/std_algorithm.html and clicked uniq, no
> problem, all good. But my code did not work. After some debugging
> I saw, that for some inputs uniq just did not work. I clicked around
> some more in the online docs and finally arrived at https://dlang.org
> /phobos/std_algorithm_iteration.html which also lists uniq at the
> beginning of the page and mentions (only there) that the input needs to
> be sorted.
> With that all was back to good :)
> 
> Would it make sense to mention this prerequisite also at the main documentation of uniq (https://dlang.org/phobos/std_algorithm_iteration.html#uniq)
[...]

Technically, .uniq can be used with a custom predicate for collapsing adjacent equivalent items, which can be useful on non-sorted ranges sometimes.

OTOH, it's true that the most common use case for .uniq is on sorted ranges.  The docs do say that it iterates "unique *consecutive* elements" (emphasis mine), but I guess this is easy to miss.  I'll see if I can reword this to be more explicit.


T

-- 
Spaghetti code may be tangly, but lasagna code is just cheesy.

On Thu, Dec 08, 2022 at 05:21:52PM -0800, H. S. Teoh via Digitalmars-d-learn wrote: [...]
> I'll see if I can reword this to be more explicit.
[...]

https://github.com/dlang/phobos/pull/8646


T

-- 
Don't modify spaghetti code unless you can eat the consequences.

On 09.12.22 02:27, H. S. Teoh wrote:
> On Thu, Dec 08, 2022 at 05:21:52PM -0800, H. S. Teoh via Digitalmars-d-learn wrote:
> [...]
>> I'll see if I can reword this to be more explicit.
> [...]
> 
> https://github.com/dlang/phobos/pull/8646
> 
> 
> T
> 
Thanks a lot ...
that was fast.

Is there also an implementation that works on non sorted ranges?


Kind regards,
Christian

On Fri, Dec 09, 2022 at 12:51:27PM +0100, Christian Köstlin via Digitalmars-d-learn wrote:
> On 09.12.22 02:27, H. S. Teoh wrote:
[...]
> > https://github.com/dlang/phobos/pull/8646
[...]
> Thanks a lot ...
> that was fast.

It only took a minute to fix. :-D


> Is there also an implementation that works on non sorted ranges?
[...]

Not as far as I know, because on a non-sorted range you'd have a much higher time/space complexity.  You could sort the range first, but that's O(n log n) time and possibly O(n) space if you want to preserve the original range.

Alternatively, you could use an AA to keep track of items already seen, but that's also O(n) space in the worst case.  Ostensibly it'd be O(n) time as well, but that depends on your data set (some pathological cases may trigger poorer AA performance). It will also trigger GC allocations. Something along these lines:

	auto noDuplicates(R)(R range)
		if (isInputRange!R)
	{
		bool[ElementType!R] aa;
		return range.filter!((e) {
			if (e in aa)
				return false;
			aa[e] = true;
			return true;
		});
	}


T

-- 
Fact is stranger than fiction.

On 09.12.22 19:55, H. S. Teoh wrote:
> On Fri, Dec 09, 2022 at 12:51:27PM +0100, Christian Köstlin via Digitalmars-d-learn wrote:
>> On 09.12.22 02:27, H. S. Teoh wrote:
> [...]
>>> https://github.com/dlang/phobos/pull/8646
> [...]
>> Thanks a lot ...
>> that was fast.
> 
> It only took a minute to fix. :-D
> 
> 
>> Is there also an implementation that works on non sorted ranges?
> [...]
> 
> Not as far as I know, because on a non-sorted range you'd have a much
> higher time/space complexity.  You could sort the range first, but
> that's O(n log n) time and possibly O(n) space if you want to preserve
> the original range.
> 
> Alternatively, you could use an AA to keep track of items already seen,
> but that's also O(n) space in the worst case.  Ostensibly it'd be O(n)
> time as well, but that depends on your data set (some pathological cases
> may trigger poorer AA performance). It will also trigger GC allocations.
> Something along these lines:
> 
> 	auto noDuplicates(R)(R range)
> 		if (isInputRange!R)
> 	{
> 		bool[ElementType!R] aa;
> 		return range.filter!((e) {
> 			if (e in aa)
> 				return false;
> 			aa[e] = true;
> 			return true;
> 		});
> 	}
> 
> 
> T
> 
Thanks for the sketch ... sure ... for pathological cases all hope is lost :).

Kind regards,
Christian