gcc/ada/a-cgcaso.adb

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