gcc/ada/a-cgaaso.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 _ A N O N Y M O U S _ 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 was originally developed by Matthew J Heaney.                  --
  35 ------------------------------------------------------------------------------
  36
  37 procedure Ada.Containers.Generic_Anonymous_Array_Sort
  38   (First, Last : Index_Type'Base)
  39 is
  40    Pivot, Lo, Mid, Hi : Index_Type;
  41
  42 begin
  43    if Last <= First then
  44       return;
  45    end if;
  46
  47    Lo := First;
  48    Hi := Last;
  49
  50    if Last = Index_Type'Succ (First) then
  51       if not Less (Lo, Hi) then
  52          Swap (Lo, Hi);
  53       end if;
  54
  55       return;
  56    end if;
  57
  58    Mid := Index_Type'Val
  59      (Index_Type'Pos (Lo) +
  60       (Index_Type'Pos (Hi) - Index_Type'Pos (Lo)) / 2);
  61
  62    --  We need to figure out which case we have:
  63    --  x < y < z
  64    --  x < z < y
  65    --  z < x < y
  66    --  y < x < z
  67    --  y < z < x
  68    --  z < y < x
  69
  70    if Less (Lo, Mid) then
  71       if Less (Lo, Hi) then
  72          if Less (Mid, Hi) then
  73             Swap (Lo, Mid);
  74
  75          else
  76             Swap (Lo, Hi);
  77
  78          end if;
  79
  80       else
  81          null;  --  lo is median
  82       end if;
  83
  84    elsif Less (Lo, Hi) then
  85       null; --  lo is median
  86
  87    elsif Less (Mid, Hi) then
  88       Swap (Lo, Hi);
  89
  90    else
  91       Swap (Lo, Mid);
  92    end if;
  93
  94    Pivot := Lo;
  95    Outer : loop
  96       loop
  97          exit Outer when not (Pivot < Hi);
  98
  99          if Less (Hi, Pivot) then
 100             Swap (Hi, Pivot);
 101             Pivot := Hi;
 102             Lo := Index_Type'Succ (Lo);
 103             exit;
 104          else
 105             Hi := Index_Type'Pred (Hi);
 106          end if;
 107       end loop;
 108
 109       loop
 110          exit Outer when not (Lo < Pivot);
 111
 112          if Less (Lo, Pivot) then
 113             Lo := Index_Type'Succ (Lo);
 114          else
 115             Swap (Lo, Pivot);
 116             Pivot := Lo;
 117             Hi := Index_Type'Pred (Hi);
 118             exit;
 119          end if;
 120       end loop;
 121    end loop Outer;
 122
 123    Generic_Anonymous_Array_Sort (First, Index_Type'Pred (Pivot));
 124    Generic_Anonymous_Array_Sort (Index_Type'Succ (Pivot), Last);
 125
 126 end Ada.Containers.Generic_Anonymous_Array_Sort;