git://gcc.gnu.org / gcc.git / blame
| Commit | Line | Data |
|---|---|---|
| 38cbfe40 RK |
1 | ------------------------------------------------------------------------------ |
| 2 | -- -- | |
| 3 | -- GNAT RUNTIME COMPONENTS -- | |
| 4 | -- -- | |
| 5 | -- G N A T . H E A P _ S O R T _ G -- | |
| 6 | -- -- | |
| 7 | -- S p e c -- | |
| 8 | -- -- | |
| fbf5a39b | 9 | -- Copyright (C) 1995-2002 Ada Core Technologies, Inc. -- |
| 38cbfe40 RK |
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 2, 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. See the GNU General Public License -- | |
| 17 | -- for more details. You should have received a copy of the GNU General -- | |
| 18 | -- Public License distributed with GNAT; see file COPYING. If not, write -- | |
| 19 | -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, -- | |
| 20 | -- MA 02111-1307, USA. -- | |
| 21 | -- -- | |
| 22 | -- As a special exception, if other files instantiate generics from this -- | |
| 23 | -- unit, or you link this unit with other files to produce an executable, -- | |
| 24 | -- this unit does not by itself cause the resulting executable to be -- | |
| 25 | -- covered by the GNU General Public License. This exception does not -- | |
| 26 | -- however invalidate any other reasons why the executable file might be -- | |
| 27 | -- covered by the GNU Public License. -- | |
| 28 | -- -- | |
| fbf5a39b AC |
29 | -- GNAT was originally developed by the GNAT team at New York University. -- |
| 30 | -- Extensive contributions were provided by Ada Core Technologies Inc. -- | |
| 38cbfe40 RK |
31 | -- -- |
| 32 | ------------------------------------------------------------------------------ | |
| 33 | ||
| 34 | -- Heapsort generic package using formal procedures | |
| 35 | ||
| 36 | -- This package provides a generic heapsort routine that can be used with | |
| fbf5a39b AC |
37 | -- different types of data. |
| 38 | ||
| 39 | -- See also GNAT.Heap_Sort, a version that works with subprogram access | |
| 40 | -- parameters, allowing code sharing. The generic version is slightly more | |
| 41 | -- efficient but does not allow code sharing and has an interface that is | |
| 42 | -- more awkward to use. The generic version is also Pure, while the access | |
| 43 | -- subprogram version can only be Preelaborate. | |
| 44 | ||
| 45 | -- There is also GNAT.Heap_Sort_A, which is now considered obsolete, but | |
| 46 | -- was an older version working with subprogram parameters. This version | |
| 47 | -- is retained for bacwards compatibility with old versions of GNAT. | |
| 48 | ||
| 49 | -- This heapsort algorithm uses approximately N*log(N) compares in the | |
| 50 | -- worst case and is in place with no additional storage required. See | |
| 51 | -- the body for exact details of the algorithm used. | |
| 38cbfe40 RK |
52 | |
| 53 | generic | |
| 54 | -- The data to be sorted is assumed to be indexed by integer values from | |
| 55 | -- 1 to N, where N is the number of items to be sorted. In addition, the | |
| 56 | -- index value zero is used for a temporary location used during the sort. | |
| 57 | ||
| 58 | with procedure Move (From : Natural; To : Natural); | |
| fbf5a39b AC |
59 | -- A procedure that moves the data item with index value From to the data |
| 60 | -- item with index value To (the old value in To being lost). An index | |
| 61 | -- value of zero is used for moves from and to a single temporary location | |
| 38cbfe40 RK |
62 | |
| 63 | with function Lt (Op1, Op2 : Natural) return Boolean; | |
| 64 | -- A function that compares two items and returns True if the item with | |
| 65 | -- index Op1 is less than the item with Index Op2, and False if the Op1 | |
| fbf5a39b AC |
66 | -- item is greater than the Op2 item. If the two items are equal, then |
| 67 | -- it does not matter whether True or False is returned (it is slightly | |
| 68 | -- more efficient to return False). | |
| 69 | ||
| 70 | -- Note on use of temporary location | |
| 71 | ||
| 72 | -- There are two ways of providing for the index value zero to represent | |
| 73 | -- a temporary value. Either an extra location can be allocated at the | |
| 74 | -- start of the array, or alternatively the Move and Lt subprograms can | |
| 75 | -- test for the case of zero and treat it specially. In any case it is | |
| 76 | -- desirable to specify the two subprograms as inlined and the tests for | |
| 77 | -- zero will in this case be resolved at instantiation time. | |
| 38cbfe40 RK |
78 | |
| 79 | package GNAT.Heap_Sort_G is | |
| 80 | pragma Pure (Heap_Sort_G); | |
| 81 | ||
| 82 | procedure Sort (N : Natural); | |
| 83 | -- This procedures sorts items in the range from 1 to N into ascending | |
| 84 | -- order making calls to Lt to do required comparisons, and Move to move | |
| 85 | -- items around. Note that, as described above, both Move and Lt use a | |
| 86 | -- single temporary location with index value zero. This sort is not | |
| 87 | -- stable, i.e. the order of equal elements in the input is not preserved. | |
| 88 | ||
| 89 | end GNAT.Heap_Sort_G; |