new iterator for TREE index: NP (NextPrefix)

[unera]

example table contains PRIMARY KEY

- foo
- foo bar
- foo bar baz
- g
- g abc
- g cde
- g cde def

for _, tuple in space:pairs('foo', { iterator = 'GE' }) do
   print(tuple)
end

- foo
- foo bar
...

for _, tuple in space:pairs('foo', { iterator = 'NP' }) do
  print(tuple)
end

- g
- g abc

the iterator works like GT but for the first key it can receive a string that can be part of the field (prefix substring).
the first iteration must return value which prefix is more than noticed in key.

[unera]

We need the iterator for S3 that operates by triplets

- bucket_id
- key
- version

for _, file in space:pairs({bucket, name}, {iterator = 'NP'}) do
   print('next name is ', file.name)
   break
end

[alyapunov]

I would define it more formally.

Let's define tuple_key as an array of values of a tuple that correspond to index parts. For example if a space has format
{{'a', 'string'}, {'b', 'string'}, {'c', 'map'}} and its index has parts {{'b'}, {'c.e', 'string'}} then tuple {'u', 'v', {d = 'x', e = 'y', f = 'z'}} will have tuple_key as {'v', 'y'}.
Let search_key be the array of values that passed to pairs or select as the first argument.

For example usual definition that a tuple_key {t₁, t₂,... t_n} is greater than a search_key {s₁, s₂,... s_m} is that there is such k: 1 <= k <= m that t_i == s_i for i = 1, k - 1 AND t_k > s_k (keep in mind that in case of descending part '>' must be replaced with '<').

It seems that 'np' aka 'NextPrefix' iterator is only meaningful if the last part of search key and the corresponding tuple key part are strings. If it is not so, let's define behavior of 'np' iterator to be the same as 'gt' iterator. The following definition is for strings.

Let's define a property that a value is greater than a search_value in terms or prefix:

return string.sub(value, 1, #search_value) > search_value
-- keep in mind that in case of descending part '>' must be replaced with '<'.

Let's define a property that a tuple_key {t₁, t₂,... t_n} is greater than a search_key {s₁, s₂,... s_m} in terms or prefix if the tuple_key is greater that search_subkey {s₁, s₂,... s_m-1} OR tuple_key is equal to search_subkey {s₁, s₂,... s_m-1} while the last part t_m is greater than s_m in terms of prefix.

A tuple is greater than a search_key in terms of prefix if its tuple_key in that index s greater than the search_key in terms of prefix.

So the 'np' iterator must start from the first tuple in the index that is greater than the search_key in terms of prefix, and the continue normally as any forward iterator ('gt' for example) would continue.

[unera]

@alyapunov Yes, You are right.

The iterator selects the first tuple by rule:

string.sub(value, 1, #search_value) > search_value

all the following tuples select as in 'GT/GE' iterators.