Confirming a sort or partition

Continuing the discussion from A new binary-search attempt:

I was thinking of some extension from the binary search on collections that can work for sequences. Then I came up with checking if a sequence matches a given partition (with a partitioning predicate) or sort (with a comparison predicate and monotonic flag). These match the std::is_partitioned, std::is_sorted, and std::is_sorted_until functions from C++.

The code is in a gist. Sequence.partitionFailure(by:) and Sequence.sortFailure(monotonic: by:) return the two elements surrounding where a partition or sorting predicate fails. The Sequence.isPartitioned(by:) and Sequence.isSorted(monotonically: by:) are the Boolean-return variants. The sort checking methods have a flag whether consecutive elements being equal is an error or not.

1 Like

I'm retiring the gist I listed in the OP for an updated one as part of the type it supports, an always-sorted set.

Terms of Service

Privacy Policy

Cookie Policy