package sorting_pkg is
    -- elements indices for comparison
    type elements is (l, r) ;

    -- the indices that need to be compared
    type tuple_t is array(elements) of integer ;
    constant IGNORE : tuple_t := tuple_t'(-1, -1) ;

    -- the array of comparisons that need to happen based on the number of stages and the number of elements
    -- an array entry with both indices the same natural index, pass-through
    -- an array entry with both indices -1, ignore
    type comparisons_t is array(natural range <>, natural range <>) of tuple_t ;

    -- get the comparisons
    function get_comparisons(constant num_elements : in positive) return comparisons_t ;

    -- invalid entries
    constant NULL_COMPARISONS : comparisons_t(0 to -1, 0 to -1) := (others => (others => IGNORE)) ;

end package ;

package body sorting_pkg is

    function init_comparisons(constant num_elements, num_stages : in positive) return comparisons_t is
        variable rv : comparisons_t(0 to num_stages-1, 0 to num_elements-1) := (others => (others => IGNORE));
    begin
        return rv ;
    end function ;

    -- TODO: Create a function to make these entries for all possible networks
    function comparisons_8 return comparisons_t is
        variable rv : comparisons_t := init_comparisons(num_elements => 8, num_stages => 6) ;
    begin
        rv(0,0) := (0,2); rv(0,1) := (1,3); rv(0,2) := (4,6); rv(0,3) := (5,7);                                     -- stage 0: 4 comparisons
        rv(1,0) := (0,4); rv(1,1) := (1,5); rv(1,2) := (2,6); rv(1,3) := (3,7);                                     -- stage 1: 4 comparisons
        rv(2,0) := (0,1); rv(2,1) := (2,3); rv(2,2) := (4,5); rv(2,3) := (6,7);                                     -- stage 2: 4 comparisons
        rv(3,0) := (2,4); rv(3,1) := (3,5); rv(3,2) := (0,0); rv(3,3) := (1,1); rv(3,4) := (6,6); rv(3,5) := (7,7); -- stage 3: 2 comparisons, 4 pass-through
        rv(4,0) := (1,4); rv(4,1) := (3,6); rv(4,2) := (0,0); rv(4,3) := (2,2); rv(4,4) := (5,5); rv(4,5) := (7,7); -- stage 4: 2 comparisons, 4 pass-through
        rv(5,0) := (1,2); rv(5,1) := (3,4); rv(5,2) := (5,6); rv(5,3) := (0,0); rv(5,4) := (7,7);                   -- stage 5: 3 comparisons, 2 pass-through
        return rv ;
    end function ;

    function get_comparisons(constant num_elements : in positive) return comparisons_t is
    begin
        case num_elements is
            when 8      => return comparisons_8 ;
            when others => return NULL_COMPARISONS ;
        end case ;
    end function ;

end package body ;

library ieee;
use ieee.std_logic_1164.all;

use work.sorting_pkg.all ;

entity sorting_network is
  generic (
    type a is array(natural range <>) of type is private;
    function "<"(l, r : in a'element) return boolean is <>;
    comparisons : comparisons_t
  );
  port(
    clock       : in    std_logic;
    unsorted    : in    a ;
    sorted      : out   a
  );
end entity;

architecture arch of sorting_network is

    constant NUM_ELEMENTS   : natural := a'length ;
    constant NUM_STAGES     : natural := comparisons'length(1) ;

    -- Riviera PRO doesn't like this
    --subtype STAGES is comparisons'range(1) ;
    --subtype ELEMENTS is a'range ;

    subtype STAGES is natural range 0 to comparisons'length(1)-1 ;
    subtype ELEMENTS is natural range 0 to a'length(1)-1 ;

    type data_array is array (natural range <>, natural range <>) of a'element ;
    signal data : data_array(STAGES, ELEMENTS) ;

begin

    -- Input assignments
    stage0 : for element in 0 to NUM_ELEMENTS-1 generate
        data(0, element) <= unsorted(element) ;
    end generate ;

    -- Sorting network
    gen_stages : for stage in 0 to NUM_STAGES-1 generate
        process(clock) begin
            if( rising_edge(clock) ) then
                for element in 0 to NUM_ELEMENTS-1 loop
                    if comparisons(stage,element)(l) = -1 then
                        -- Ignore the entry
                        null ;
                    elsif comparisons(stage, element)(l) = comparisons(stage, element)(r) then
                        -- Pass through
                        -- Note: Evaluation of this constant should not turn into logic
                        data(stage+1, element) <= data(stage, element) ;
                    else
                        -- Only logic generated here for this comparison
                        if data(stage, comparisons(stage, element)(l)) < data(stage, comparisons(stage, element)(r)) then
                            -- Swap
                            data(stage+1, comparisons(stage, element)(l)) <= data(stage, comparisons(stage, element)(r)) ;
                            data(stage+1, comparisons(stage, element)(r)) <= data(stage, comparisons(stage, element)(l)) ;
                        else
                            -- No Swap, pass-through
                            data(stage+1, comparisons(stage, element)(l)) <= data(stage, comparisons(stage, element)(l)) ;
                            data(stage+1, comparisons(stage, element)(r)) <= data(stage, comparisons(stage, element)(r)) ;
                        end if ;
                    end if ;
                end loop ;
            end if ;
        end process ;
    end generate ;

    -- Output assignments
    gen_output : for element in 0 to NUM_ELEMENTS-1 generate
        sorted(element) <= data(NUM_STAGES, element) ;
    end generate ;

end architecture ;

library ieee ;
use ieee.std_logic_1164.all ;
use work.sorting_pkg.all ;

entity sorting_tb is
end entity ;

architecture arch of sorting_tb is

    constant NUM_ELEMENTS : positive := 8 ;

    -- Get the sorting network based on the number of elements
    constant comparisons : comparisons_t := get_comparisons(num_elements => NUM_ELEMENTS) ;

    -- A couple of input data types
    type data_t is array(comparisons'range(2)) of natural ;
    type data2_t is array(comparisons'range(2)) of real ;

    -- Common clock
    signal clock    : std_ulogic ;

    -- Natural data type
    signal data     : data_t ;
    signal sorted   : data_t ;

    -- Real data type
    signal data2    : data2_t ;
    signal sorted2  : data2_t ;

begin

    -- Make sure we have a valid network
    assert comparisons'length(1) > 0 report "NULL sorting network" severity failure ;

    U_natural_network : entity work.sorting_network
      generic map (
        a           => data'subtype,
        comparisons => comparisons
      ) port map (
        clock       => clock,
        unsorted    => data,
        sorted      => sorted
      ) ;

    U_real_network : entity work.sorting_network
      generic map (
        a           => data2'subtype,
        comparisons => comparisons
      ) port map (
        clock       => clock,
        unsorted    => data2,
        sorted      => sorted2
      ) ;

end architecture ;