[m-rev.] for review add ranges.search_member/4

[Julien Fischer]

For review by anyone.

The main thing I would like is feedback on is the name of the new
prediate. (Also, the test suite does not currently appear to contain
any specific tests of the ranges module; I intend to extend the test
case included in this diff to cover the rest of the ranges module in a
separate change.)

----------------------

Add ranges.search_member/4.

Add a predicate to search a ranges for a value and return the endpoints
of the range (if any) that the value is contained in.

library/ranges.m:
     Add the new predicate.

NEWS.md:
     Announce the addition.

tests/hard_coded/Mmakefile:
tests/hard_coded/test_ranges.{m,exp}:
     Add a test case.

Julien.

diff --git a/NEWS.md b/NEWS.md
index fe4211b..3eb4db8 100644
--- a/NEWS.md
+++ b/NEWS.md
@@ -686,6 +686,12 @@ Changes to the Mercury standard library
      - pred `permutation/4`
              (replacement: `random.shuffle_list/4` or `random.shuffle_list/5`)

+### Changes to the `ranges` module
+
+* The following predicate has been added:
+
+    - pred `search_member/4`
+
  ### Changes to the `rbtree` module

  * The following predicates and functions have been added:
diff --git a/library/ranges.m b/library/ranges.m
index e29ed0b..9bd92e8 100644
--- a/library/ranges.m
+++ b/library/ranges.m
@@ -3,7 +3,7 @@
  %---------------------------------------------------------------------------%
  % Copyright (C) 2006-2009 The University of Melbourne.
  % Copyright (C) 2013-2016 Opturion Pty Ltd.
-% Copyright (C) 2017-2019, 2022 The Mercury team.
+% Copyright (C) 2017-2019, 2022-2024 The Mercury team.
  % This file is distributed under the terms specified in COPYING.LIB.
  %---------------------------------------------------------------------------%
  %
@@ -109,6 +109,12 @@
      %
  :- pred nondet_member(int::out, ranges::in) is nondet.

+    % search_member(N, Set, L, H):
+    % L and H are the endpoints of the range in Set that contains N.
+    % Fails if N is not a member of Set.
+    %
+:- pred search_member(int::in, ranges::in, int::out, int::out) is semidet.
+
      % subset(A, B) is true iff every value in A is in B.
      %
  :- pred subset(ranges::in, ranges::in) is semidet.
@@ -525,12 +531,27 @@ range_member(L, U, range(A0, A1, As)) :-
          range_member(L, U, As)
      ).

+%---------------------------------------------------------------------------%
+
  nondet_member(N, As) :-
      range_member(L, U, As),
      int.nondet_int_in_range(L, U, N).

  %---------------------------------------------------------------------------%

+search_member(N, range(L0, H0, Rest), L, H) :-
+    ( if
+        N > L0,
+        N =< H0
+    then
+        L = L0 + 1,
+        H = H0
+    else
+        search_member(N, Rest, L, H)
+    ).
+
+%---------------------------------------------------------------------------%
+
  subset(A, B) :-
      % XXX Should implement this more efficiently.
      ranges.difference(A, B) = nil.
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index 2fb0b81..558ff02 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -458,6 +458,7 @@ ORDINARY_PROGS = \
  	test_one_or_more_chunk \
  	test_pretty_printer \
  	test_pretty_printer_defaults \
+	test_ranges \
  	test_semaphore \
  	test_split_switch_arms \
  	test_yield \
diff --git a/tests/hard_coded/test_ranges.exp b/tests/hard_coded/test_ranges.exp
index e69de29..1253f8c 100644
--- a/tests/hard_coded/test_ranges.exp
+++ b/tests/hard_coded/test_ranges.exp
@@ -0,0 +1,9 @@
+search_member(0, Empty) ==> FAIL
+search_member(-1, TestRanges) ==> FAIL
+search_member(0, TestRanges) ==> FAIL
+search_member(1558, TestRanges) ==> FAIL
+search_member(1560, TestRanges) ==> (1559, 8460).
+search_member(8461, TestRanges) ==> FAIL
+search_member(95586, TestRanges) ==> (93719, 100620).
+search_member(100620, TestRanges) ==> (93719, 100620).
+search_member(100621, TestRanges) ==> FAIL
diff --git a/tests/hard_coded/test_ranges.m b/tests/hard_coded/test_ranges.m
index e69de29..4b31109 100644
--- a/tests/hard_coded/test_ranges.m
+++ b/tests/hard_coded/test_ranges.m
@@ -0,0 +1,53 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 et ft=mercury
+%---------------------------------------------------------------------------%
+
+:- module test_ranges.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%---------------------------------------------------------------------------%
+%---------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module list.
+:- import_module ranges.
+:- import_module string.
+
+%---------------------------------------------------------------------------%
+
+main(!IO) :-
+    test_search_member(!IO).
+
+%---------------------------------------------------------------------------%
+
+:- pred test_search_member(io::di, io::uo) is det.
+
+test_search_member(!IO) :-
+
+    EmptyRanges = ranges.empty : ranges,
+    do_test_search_member(EmptyRanges, "Empty", 0, !IO),
+
+    TestRanges = range(1559, 8460) `union` range(43319, 48780) `union`
+        range(93719, 100620),
+    TestValues = [-1, 0, 1558, 1560, 8461, 95586, 100620, 100621],
+    list.foldl(do_test_search_member(TestRanges, "TestRanges"), TestValues, !IO).
+
+:- pred do_test_search_member(ranges::in, string::in, int::in,
+    io::di, io::uo) is det.
+
+do_test_search_member(Ranges, RangesDesc, N, !IO) :-
+    io.format("search_member(%d, %s) ==> ", [i(N), s(RangesDesc)], !IO),
+    ( if ranges.search_member(N, Ranges, Lo, Hi) then
+        io.format("(%d, %d).\n", [i(Lo), i(Hi)], !IO)
+    else
+        io.print_line("FAIL", !IO)
+    ).
+
+%---------------------------------------------------------------------------%
+:- end_module test_ranges.
+%---------------------------------------------------------------------------%