URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [ada/] [a-cgaaso.adb] - Blame information for rev 847

Go to most recent revision | Details | Compare with Previous | View Log


------------------------------------------------------------------------------
--                                                                          --
--                         GNAT LIBRARY COMPONENTS                          --
--                                                                          --
--              ADA.CONTAINERS.GENERIC_ANONYMOUS_ARRAY_SORT                 --
--                                                                          --
--                                 B o d y                                  --
--                                                                          --
--          Copyright (C) 2004-2009, Free Software Foundation, Inc.         --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
--                                                                          --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception,   --
-- version 3.1, as published by the Free Software Foundation.               --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
-- This unit was originally developed by Matthew J Heaney.                  --
------------------------------------------------------------------------------
 
--  This algorithm was adapted from GNAT.Heap_Sort (see g-heasor.ad[sb])
 
with System;
 
procedure Ada.Containers.Generic_Anonymous_Array_Sort
  (First, Last : Index_Type'Base)
is
   type T is range System.Min_Int .. System.Max_Int;
 
   function To_Index (J : T) return Index_Type;
   pragma Inline (To_Index);
 
   function Lt (J, K : T) return Boolean;
   pragma Inline (Lt);
 
   procedure Xchg (J, K : T);
   pragma Inline (Xchg);
 
   procedure Sift (S : T);
 
   --------------
   -- To_Index --
   --------------
 
   function To_Index (J : T) return Index_Type is
      K : constant T'Base := Index_Type'Pos (First) + J - T'(1);
   begin
      return Index_Type'Val (K);
   end To_Index;
 
   --------
   -- Lt --
   --------
 
   function Lt (J, K : T) return Boolean is
   begin
      return Less (To_Index (J), To_Index (K));
   end Lt;
 
   ----------
   -- Xchg --
   ----------
 
   procedure Xchg (J, K : T) is
   begin
      Swap (To_Index (J), To_Index (K));
   end Xchg;
 
   Max : T := Index_Type'Pos (Last) - Index_Type'Pos (First) + T'(1);
 
   ----------
   -- Sift --
   ----------
 
   procedure Sift (S : T) is
      C      : T := S;
      Son    : T;
      Father : T;
 
   begin
      loop
         Son := C + C;
 
         if Son < Max then
            if Lt (Son, Son + 1) then
               Son := Son + 1;
            end if;
         elsif Son > Max then
            exit;
         end if;
 
         Xchg (Son, C);
         C := Son;
      end loop;
 
      while C /= S loop
         Father := C / 2;
 
         if Lt (Father, C) then
            Xchg (Father, C);
            C := Father;
         else
            exit;
         end if;
      end loop;
   end Sift;
 
--  Start of processing for Generic_Anonymous_Array_Sort
 
begin
   for J in reverse 1 .. Max / 2 loop
      Sift (J);
   end loop;
 
   while Max > 1 loop
      Xchg (1, Max);
      Max := Max - 1;
      Sift (1);
   end loop;
end Ada.Containers.Generic_Anonymous_Array_Sort;

Line No.	Rev	Author	Line
1	281	jeremybenn	`------------------------------------------------------------------------------`
2			`-- --`
3			`-- GNAT LIBRARY COMPONENTS --`
4			`-- --`
5			`-- ADA.CONTAINERS.GENERIC_ANONYMOUS_ARRAY_SORT --`
6			`-- --`
7			`-- B o d y --`
8			`-- --`
9			`-- Copyright (C) 2004-2009, Free Software Foundation, Inc. --`
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			`-- This unit was originally developed by Matthew J Heaney. --`
28			`------------------------------------------------------------------------------`
29
30			`-- This algorithm was adapted from GNAT.Heap_Sort (see g-heasor.ad[sb])`
31
32			`with System;`
33
34			`procedure Ada.Containers.Generic_Anonymous_Array_Sort`
35			`(First, Last : Index_Type'Base)`
36			`is`
37			`type T is range System.Min_Int .. System.Max_Int;`
38
39			`function To_Index (J : T) return Index_Type;`
40			`pragma Inline (To_Index);`
41
42			`function Lt (J, K : T) return Boolean;`
43			`pragma Inline (Lt);`
44
45			`procedure Xchg (J, K : T);`
46			`pragma Inline (Xchg);`
47
48			`procedure Sift (S : T);`
49
50			`--------------`
51			`-- To_Index --`
52			`--------------`
53
54			`function To_Index (J : T) return Index_Type is`
55			`K : constant T'Base := Index_Type'Pos (First) + J - T'(1);`
56			`begin`
57			`return Index_Type'Val (K);`
58			`end To_Index;`
59
60			`--------`
61			`-- Lt --`
62			`--------`
63
64			`function Lt (J, K : T) return Boolean is`
65			`begin`
66			`return Less (To_Index (J), To_Index (K));`
67			`end Lt;`
68
69			`----------`
70			`-- Xchg --`
71			`----------`
72
73			`procedure Xchg (J, K : T) is`
74			`begin`
75			`Swap (To_Index (J), To_Index (K));`
76			`end Xchg;`
77
78			`Max : T := Index_Type'Pos (Last) - Index_Type'Pos (First) + T'(1);`
79
80			`----------`
81			`-- Sift --`
82			`----------`
83
84			`procedure Sift (S : T) is`
85			`C : T := S;`
86			`Son : T;`
87			`Father : T;`
88
89			`begin`
90			`loop`
91			`Son := C + C;`
92
93			`if Son < Max then`
94			`if Lt (Son, Son + 1) then`
95			`Son := Son + 1;`
96			`end if;`
97			`elsif Son > Max then`
98			`exit;`
99			`end if;`
100
101			`Xchg (Son, C);`
102			`C := Son;`
103			`end loop;`
104
105			`while C /= S loop`
106			`Father := C / 2;`
107
108			`if Lt (Father, C) then`
109			`Xchg (Father, C);`
110			`C := Father;`
111			`else`
112			`exit;`
113			`end if;`
114			`end loop;`
115			`end Sift;`
116
117			`-- Start of processing for Generic_Anonymous_Array_Sort`
118
119			`begin`
120			`for J in reverse 1 .. Max / 2 loop`
121			`Sift (J);`
122			`end loop;`
123
124			`while Max > 1 loop`
125			`Xchg (1, Max);`
126			`Max := Max - 1;`
127			`Sift (1);`
128			`end loop;`
129			`end Ada.Containers.Generic_Anonymous_Array_Sort;`

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [ada/] [a-cgaaso.adb] - Blame information for rev 847