gcc/ada/libgnat/g-binsea.ads

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT RUN-TIME COMPONENTS                         --
   4 --                                                                          --
   5 --                           GNAT.BINARY_SEARCH                             --
   6 --                                                                          --
   7 --                                 S p e c                                  --
   8 --                                                                          --
   9 --                        Copyright (C) 2022-2023, AdaCore                  --
  10 --                                                                          --
  11 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  12 -- terms of the  GNU General Public License as published  by the Free Soft- --
  13 -- ware  Foundation;  either version 3,  or (at your option) any later ver- --
  14 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  15 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  16 -- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
  17 --                                                                          --
  18 -- As a special exception under Section 7 of GPL version 3, you are granted --
  19 -- additional permissions described in the GCC Runtime Library Exception,   --
  20 -- version 3.1, as published by the Free Software Foundation.               --
  21 --                                                                          --
  22 -- You should have received a copy of the GNU General Public License and    --
  23 -- a copy of the GCC Runtime Library Exception along with this program;     --
  24 -- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
  25 -- <http://www.gnu.org/licenses/>.                                          --
  26 ------------------------------------------------------------------------------
  27
  28 --  Allow binary search of a sorted array (or of an array-like container;
  29 --  the generic does not reference the array directly).
  30
  31 package GNAT.Binary_Search is
  32
  33    generic
  34       type Index_Type is (<>);
  35       type Element_Type (<>) is private;
  36       with function Get (Index : Index_Type) return Element_Type;
  37       with function Before (Left, Right : Element_Type) return Boolean;
  38       Leftmost : Boolean := True;
  39    function Index
  40      (First, Last, Start : Index_Type;
  41       Element            : Element_Type) return Index_Type'Base;
  42    --  Search for element in sorted container. Function Before should return
  43    --  True when Left and Right are in the container's sort order and not
  44    --  equal. Function Get returns the container element indexed by Index;
  45    --  Index will be in the range First .. Last. If there is at least one index
  46    --  value in the range First .. Last for which Get would return Element,
  47    --  then the Leftmost generic parameter indicates whether the least (if
  48    --  Leftmost is True) or the greatest (if Leftmost is False) such index
  49    --  value is returned. If no such index value exists, then Leftmost
  50    --  determines whether to return the greater (if Leftmost is True) or the
  51    --  smaller (if Leftmost is False) of the two index values between which
  52    --  Element could be inserted. If First > Last (so that a null range is
  53    --  being searched), some Index_Type'Base value will be returned.
  54    --  Start is the index for the first probe of the binary search. It can
  55    --  improve speed of many search operations when user can guess the most
  56    --  likely values. If you do not know what value should be used there, use
  57    --  (First + Last) / 2.
  58
  59    generic
  60       type Index_Type is (<>);
  61       type Element_Type (<>) is private;
  62       with function Before
  63         (Index : Index_Type; Element : Element_Type) return Boolean;
  64    function Leftmost
  65      (First, Last, Start : Index_Type;
  66       Element            : Element_Type) return Index_Type'Base
  67      with Pre => First > Last -- Empty array
  68                  or else (Start in First .. Last
  69                           and then ( -- To prevent overflow in function result
  70                                     Index_Type'Base'Last > Last
  71                                     or else not Before (Last, Element)));
  72    --  Leftmost returns the result described for Index in the case where the
  73    --  Leftmost parameter is True, with Index_Type values mapped to
  74    --  Element_Type values via Get as needed.
  75
  76    generic
  77       type Index_Type is (<>);
  78       type Element_Type (<>) is private;
  79       with function Before
  80         (Element : Element_Type; Index : Index_Type) return Boolean;
  81    function Rightmost
  82      (First, Last, Start : Index_Type;
  83       Element            : Element_Type) return Index_Type'Base
  84      with Pre => First > Last -- Empty array
  85                  or else (Start in First .. Last
  86                           and then ( -- To prevent overflow in function result
  87                                     Index_Type'Base'First < First
  88                                     or else not Before (Element, First)));
  89    --  Rightmost returns the result described for Index in the case where the
  90    --  Leftmost parameter is False, with Index_Type values mapped to
  91    --  Element_Type values via Get as needed.
  92
  93 end GNAT.Binary_Search;