-- HeapSortParallel
--
-- +-----------------------------+
-- |    Copyright 1996 DOULOS    |
-- |        Library: Sort        |
-- |    designer : Mike Smith    |
-- +-----------------------------+
 
-- This design contains VHDL’93 code that is incompatible with VHDL’87

library IEEE;
use IEEE.Std_logic_1164.all;

package HeapType is

  subtype Key is Integer;
  type ListIndex is range 0 to Integer'High;
  type List is array (ListIndex range <>) of Key;

end package HeapType;

use Work.HeapType.all;

entity HeapSortParallel is
  port (Input: in List;
        Output: out List);
end entity HeapSortParallel;

architecture Algorithm of HeapSortParallel is

  -- A pure algorithm to input a list of numbers in parallel and output 
  -- the same values sorted.

  procedure Heapify (Heap: inout List; Start: ListIndex) is

    -- Percolate item in Start position down into the heap
    -- Assumes that the 2 sub-heaps are already valid heaps
    -- A heap is a binary tree with Parent > max(Children) at each level

    variable Parent: ListIndex := Start;
    variable Child: ListIndex := 2*Parent;
    variable NewComer: Key := Heap(Start);
  begin

    while Child <= Heap'Right loop
      if Child < Heap'Right then
        -- Pick the biggest child...
        if Heap(Child + 1) > Heap(Child) then
          Child := Child + 1;
        end if;
      end if;
      if Heap(Child) > NewComer then
        -- Percolate NewComer down heap
        Heap(Parent) := Heap(Child);
        Parent := Child;
        Child := 2*Parent;
      else
        exit;
      end if;
    end loop;
    -- Newby has reached his final resting place
    Heap(Parent) := NewComer;
  end procedure Heapify;

begin

  process (Input)

    -- Re-define the index constraint so we know for convenience that the 
    -- first element is numbered 1, and the range is ascending...

    variable Heap: List(1 to Input'Length);
    variable Biggest: Key;
  begin
    assert Input'Length = Output'Length 
      report "HeapSort input and output must be the same length";
    Heap := Input;

    -- Transform the list into a heap, bottom up...
    for J in Heap'Right / 2 downto 1 loop
      Heapify(Heap, J);
    end loop;

    -- Sort the heap into an ascending linear sequence
    for J in Heap'Right downto 2 loop
      -- Swap the item on the top (the biggest) to the "done" pile...
      Biggest := Heap(1);
      Heap(1) := Heap(J);
      Heap(J) := Biggest;
      -- Percolate the promoted item to re-form a valid heap...
      Heapify(Heap(1 to J-1), 1);
    end loop;

    -- Output the heap
    Output <= Heap;    
  end process;

end architecture Algorithm;