From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!samsung!usc!elroy.jpl.nasa.gov!swrinde!mips!news.cs.indiana.edu!arizona.edu!east.pima.edu!rharwood
From: rharwood@east.pima.edu
Newsgroups: comp.lang.ada
Subject: Re: Generic Sort Package Needed
Message-ID: <1991Apr24.224403.1@east.pima.edu>
Date: 25 Apr 91 05:44:03 GMT
References: <480@platypus.uofs.edu>
List-Id: <comp.lang.ada>

In article <480@platypus.uofs.edu>, cno1@jaguar.ucs.uofs.edu 
(OHARA CHRISTOPHER N) writes:
> 
>    I am in search of a generic sort package.  It must have the ability to 
> sort integers, floats, characters, and strings.  I would appreciate
> yuor assistance in this matter.
>                                     Thanks in advance,
>                                     CN01 -  THE EAGLE -

As an instructor in Pascal and Ada, I had last semester's Ada class
"reconstruct" the Quicksort routine in Elliot Koffman's Pascal text, using
an Ada generic package.  Below are 4 files:

1) Generic package spec for SortLib
2) Generic library procedure Swap (required in SortLib package body)
3) Package body for SortLib
4) Short test procedure using array of integer.

I've used this package in several of my own programs.  I can't stress enough
just how easy it is to maintain one's own "toolkit" of routines that are simply
instantiated each time a new situation arises requiring some "generic"
programming algorithm.  I only wish I had more (paid) programming work to
justify building a larger library.

I know there must be hundreds of other sort routines out there just as good (or
better than) this one, but it was so easy (took 2-3 hours of lazy midnight
coding) to convert the Pascal code ("stolen" from another source) into really
reusable generic Ada.

------------
generic
  type element is private;
  Type index is (<>);
  Type Table is array (index range <>) of element;
  with function ">"(L,R:element) return boolean is <>;

package sortlib is
  procedure Sort (T : in out Table);
end sortlib;
------------
generic
  type element is private;
procedure swap (L,R: in out element);

procedure swap (L,R: in out element) is
  Temp : Element := L;
begin
  L := R;
  R := Temp;
end swap;
------------
With swap;
package body SortLib is

  --Design/algorithm after Koffman's Pascal 3rd Ed.
  --Section 19.8, "Quicksort".  Added generics.

  procedure exchange is new swap (element);
  
  procedure partition(T : in out table; PivIndex: out index) is
    Pivot : element := t(t'first);
	Up, Down : Index;
  begin
	
	up := T'First;
	down := t'last;
	
	loop
          -- Koffman uses "<=" in the next statment
          -- I use "not >" so that only one
          -- generic formal function is required.

	  while not (T(up) > Pivot) and then (up < t'last) loop
	    Up := index'succ(up);
	  end loop;
	  
	  while (T(down) > Pivot) loop
	    Down := index'pred(down) ;
	  end loop;
	  
	  if Up < Down then
	    exchange(T(Up), T(Down));
	  end if;
	  
	  exit when Up >= Down;
	end loop;
	
	Exchange (T(T'First),T(Down));
	PivIndex := Down;
  end partition;
  
  procedure Sort (T : in out Table) is
    PivIndex : index;
  begin
    if t'first < t'last then
	  partition(T, PivIndex);
	  Sort (T(T'first .. index'pred(PivIndex)));
	  Sort (T(index'succ(PivIndex) .. T'last));
	end if;
  end Sort;
end SortLib;
------------
with text_io; Use text_io;
with SortLib;
procedure SortTest is
  package iio is new integer_io(integer);
    use iio;

  Type Table_type is array (integer range <>) of integer;
  Int_Array : Table_Type(1..5) := (4,2,76,33,19);

  -- Note that the 4th generic formal parameter "defaults" to the
  -- visible ">" function for integers.  See later example for
  -- more complex instantiation...

  Package sort_anon is new sortlib(Integer, Integer, table_type);
    Use sort_anon;
	
  Procedure put(T : table_type) is
  begin
    for index in t'range loop
	  put(t(index));
	  new_line;
	end loop;
  end put;
  
begin
  put(int_array);
  put_line("Sorting...");
  sort(Int_array);
  put_line("Results...");
  put(int_array);
end SortTest;
----------
As an additional example, suppose I wanted to store an array of employee
records, generating one report by "last name/first name", another by
"employee number".  Here's some "code bits" for illustration:
----------
with sortlib, other_stuff;
procedure Sort_Example_2 is

  -- Lots of details left out for brevity... 
  -- but the important/relevant stuff is here:

  -- Define the "Element type"
  Type Employee_rec is record
    last_name     : string(1..20);
    first_name    : string(1..20);
    emp_number    : integer;
    other_stuff   : who_knows_what_else;
  end record;

  Max_Employees : constant Integer := 100; -- (or whatever)
  Employee_count : Integer := 0;  -- Incremented as records are "read in"

  -- Define the "Table type" as an unconstrained array; going with
  -- constrained array won't work here without major rewrite.
  -- Also, note that index type is explicitly defined here.
  Type Employee_array is array (integer range <>) of integer;

  -- Define an appropriately large object to hold enough employees for my
  -- VERY small firm (yours would be larger, I hope!):
  Employees : Employee_array(1..max_employees);

  -- Define functions (bodies would have to be appropriately defined herein)
  -- which would return TRUE if the "key field" of the "left record"
  -- is greater than the "key field" of the "right record":
  Function greater_name  (L, R : Employee_rec) return boolean;
  Function greater_empno (L, R : Employee_rec) return boolean;

  -- Now, instantiate sort routines, one for each sort key:
  Package sort_by_name is 
    new sortlib(Employee_rec, Integer, Employee_array, greater_name);
  Package sort_by_empno is 
    new sortlib(Employee_rec, Integer, Employee_array, greater_empno);

begin
  Read_all_the_records_into_the_array(employees, employee_count);
  sort_by_name(employees(1..employee_count);
  Generate_report_by_name(employees(1..employee_count));
  sort_by_empno(employees(1..employee_count);
  Generate_report_by_empno(employees(1..employee_count));
end;
---------
I know this has been a bit lengthly, but the routines were already on my Mac...
I just downloaded and annotated for clarity.  I welcome comments, but please
keep violent flames to 5 words or less per person!  (It's been a rough week.)
(Why do I have the feeling I've just done someone's homework?)  Feel free to
copy and use these routines as you desire.
-----
Ray Harwood           |Data Basix           |Associate Faculty,    
Voice: (602)721-1988  |PO Box 18324         |   Pima Community College
FAX:   (602)721-7240  |Tucson, AZ 85731     |Instructor in Ada and Pascal
CompuServe: 76645,1370|AppleLink: DATA.BASIX|Internet: rharwood@east.pima.edu