gcc/ada/a-cgcaso.adb

   1 ------------------------------------------------------------------------------
   2 --                                                                          --
   3 --                         GNAT LIBRARY COMPONENTS                          --
   4 --                                                                          --
   5 --              ADA.CONTAINERS.GENERIC_CONSTRAINED_ARRAY_SORT               --
   6 --                                                                          --
   7 --                                 B o d y                                  --
   8 --                                                                          --
   9 --             Copyright (C) 2004 Free Software Foundation, Inc.            --
  10 --                                                                          --
  11 -- This specification is derived from the Ada Reference Manual for use with --
  12 -- GNAT. The copyright notice above, and the license provisions that follow --
  13 -- apply solely to the  contents of the part following the private keyword. --
  14 --                                                                          --
  15 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  16 -- terms of the  GNU General Public License as published  by the Free Soft- --
  17 -- ware  Foundation;  either version 2,  or (at your option) any later ver- --
  18 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  19 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  20 -- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
  21 -- for  more details.  You should have  received  a copy of the GNU General --
  22 -- Public License  distributed with GNAT;  see file COPYING.  If not, write --
  23 -- to  the Free Software Foundation,  59 Temple Place - Suite 330,  Boston, --
  24 -- MA 02111-1307, USA.                                                      --
  25 --                                                                          --
  26 -- As a special exception,  if other files  instantiate  generics from this --
  27 -- unit, or you link  this unit with other files  to produce an executable, --
  28 -- this  unit  does not  by itself cause  the resulting  executable  to  be --
  29 -- covered  by the  GNU  General  Public  License.  This exception does not --
  30 -- however invalidate  any other reasons why  the executable file  might be --
  31 -- covered by the  GNU Public License.                                      --
  32 --                                                                          --
  33 -- This unit has originally being developed by Matthew J Heaney.            --
  34 ------------------------------------------------------------------------------
  35
  36 procedure Ada.Containers.Generic_Constrained_Array_Sort
  37   (Container : in out Array_Type)
  38 is
  39    function Is_Less (I, J : Index_Type) return Boolean;
  40    pragma Inline (Is_Less);
  41
  42    procedure Swap (I, J : Index_Type);
  43    pragma Inline (Swap);
  44
  45    procedure Sort (First, Last : Index_Type'Base);
  46
  47    -------------
  48    -- Is_Less --
  49    -------------
  50
  51    function Is_Less (I, J : Index_Type) return Boolean is
  52    begin
  53       return Container (I) < Container (J);
  54    end Is_Less;
  55
  56    ----------
  57    -- Sort --
  58    ----------
  59
  60    procedure Sort (First, Last : Index_Type'Base) is
  61       Pivot, Lo, Mid, Hi : Index_Type;
  62
  63    begin
  64       if Last <= First then
  65          return;
  66       end if;
  67
  68       Lo := First;
  69       Hi := Last;
  70
  71       if Last = Index_Type'Succ (First) then
  72          if not Is_Less (Lo, Hi) then
  73             Swap (Lo, Hi);
  74          end if;
  75
  76          return;
  77       end if;
  78
  79       Mid := Index_Type'Val
  80                (Index_Type'Pos (Lo) +
  81                 (Index_Type'Pos (Hi) - Index_Type'Pos (Lo)) / 2);
  82
  83       --  We need to figure out which case we have:
  84       --  x < y < z
  85       --  x < z < y
  86       --  z < x < y
  87       --  y < x < z
  88       --  y < z < x
  89       --  z < y < x
  90
  91       if Is_Less (Lo, Mid) then
  92          if Is_Less (Lo, Hi) then
  93             if Is_Less (Mid, Hi) then
  94                Swap (Lo, Mid);
  95             else
  96                Swap (Lo, Hi);
  97             end if;
  98
  99          else
 100             null;  --  lo is median
 101          end if;
 102
 103       elsif Is_Less (Lo, Hi) then
 104          null; --  lo is median
 105
 106       elsif Is_Less (Mid, Hi) then
 107          Swap (Lo, Hi);
 108
 109       else
 110          Swap (Lo, Mid);
 111       end if;
 112
 113       Pivot := Lo;
 114
 115       Outer : loop
 116          loop
 117             exit Outer when not (Pivot < Hi);
 118
 119             if Is_Less (Hi, Pivot) then
 120                Swap (Hi, Pivot);
 121                Pivot := Hi;
 122                Lo := Index_Type'Succ (Lo);
 123                exit;
 124             else
 125                Hi := Index_Type'Pred (Hi);
 126             end if;
 127          end loop;
 128
 129          loop
 130             exit Outer when not (Lo < Pivot);
 131
 132             if Is_Less (Lo, Pivot) then
 133                Lo := Index_Type'Succ (Lo);
 134             else
 135                Swap (Lo, Pivot);
 136                Pivot := Lo;
 137                Hi := Index_Type'Pred (Hi);
 138                exit;
 139             end if;
 140          end loop;
 141       end loop Outer;
 142
 143       Sort (First, Index_Type'Pred (Pivot));
 144       Sort (Index_Type'Succ (Pivot), Last);
 145    end Sort;
 146
 147    ----------
 148    -- Swap --
 149    ----------
 150
 151    procedure Swap (I, J : Index_Type) is
 152       EI : constant Element_Type := Container (I);
 153    begin
 154       Container (I) := Container (J);
 155       Container (J) := EI;
 156    end Swap;
 157
 158 --  Start of processing for Generic_Constrained_Array_Sort
 159
 160 begin
 161    Sort (Container'First, Container'Last);
 162 end Ada.Containers.Generic_Constrained_Array_Sort;