boostorg / boostorg/hana

Consider adding index retrieval functions

Open
#273 11 comments 4 reactions 0 assignees View on GitHub
feature
Dominant language
C++
Stars
1.9k
Forks
225
PR merge metrics
No merged PRs in 30d

Description

I encountered the need of functions that can give me the indices of elements matching a specific predicate in a sequence in a real development situation. I propose the addition of the following functions, whose goal is to allow users to quickly retrieve the indices of elements in sequences depending on a predicate:
- `hana::indices_of_matching`
- `hana::indices_of`
- `hana::index_of_first_matching`
- `hana::index_of`

---

`hana::indices_of_matching(xs, predicate)` returns a `Sequence` containing all the indices of the elements in `xs` that match `predicate`.

```
// pseudocode
hana::indices_of_matching = [](auto&& xs, auto&& predicate) {
return hana::make_basic_tuple(/* some hana::size_c indices ...*/);
}
```

---

`hana::indices_of(xs, key)` returns a `Sequence` containing all the indices of the elements in `xs` that are equal to `key`.

```
// pseudocode
hana::indices_of = [](auto&& xs, auto&& key) {
return hana::make_basic_tuple(/* some hana::size_c indices ...*/);
}
```

Satisfies:

`indices_of(xs, key) == indices_of_matching(xs, equal.to(key))`

---

`hana::index_of_first_matching(xs, predicate)` returns an `hana::optional` contaning:
- `hana::just`: if `xs` contains at least one element matching `predicate`, where `x` is the index of the first such element.
- `hana::none`: if `xs` does not contain any element matching `predicate`.

---

`hana::index_of(xs, key)` returns an `hana::optional` contaning:
- `hana::just`: if `xs` contains at least one element equal to `key`, where `x` is the index of the first such element.
- `hana::none`: if `xs` does not contain any element equal to `key`.

Satisfies:

`index_of(xs, key) == index_of_first_matching(xs, equal.to(key))`

---

---

In addition, I propose some functions to "select" a subsequence of elements given a sequence of indices, and functions to invert the selection:
- `hana::invert_indices`
- `hana::slice_inverse`

---

`hana::invert_indices(xs, indices)`: given a `Sequence` `xs` and a `Sequence` of indices `indices`, return the full sequence of `xs`'s indices minus `indices`. (It "filters out" indices).

Example:

```
// pseudocode
auto seq = [a, b, c, d, e, f]; // length = 6
auto indices = [0, 3, 4];
auto inv_indices = hana::invert_indices(seq, indices);
assert(inv_indices == [1, 2, 5]);
```

Satisfies:

`length(hana::invert_indices(xs, indices)) == length(xs) - length(indices)`.

---

`hana::slice_inverse(xs, indices)`: given a `Sequence` `xs` and a `Sequence` of indices `indices`, returns a subset of `xs` only containing the elements at positions not in `indices`.

Satisfies:

`hana::slice_inverse(xs, idxs) == hana::slice(xs, hana::invert_indices(xs, idxs))`.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the existing sequence, slicing, predicate-matching, equality, and optional APIs before evaluating the proposed functions. Read the discussion for decisions about naming, semantics, duplicate or invalid indices, and the scope of the feature. Done means the accepted API behavior is implemented and verified for the specified examples and equivalences.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend-api-design
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.