entity buf is
  generic ( Tpd : time := 1 ns );
  port ( a : in bit;  y : out bit );
end buf;

----------------------------------------------------------------

architecture behaviour of buf is
begin

  y <= a after Tpd;

end behaviour;

----------------------------------------------------------------

entity fanout_tree is
  generic ( h : natural;  d : positive );
  port ( input : in bit;  output : out bit_vector (0 to d**h - 1) );
end fanout_tree;

----------------------------------------------------------------

architecture recursive of fanout_tree is

  component buf
    port ( a : in bit;  y : out bit );
  end component;

  component fanout_tree
    generic ( h : natural;  d : positive );
    port ( input : in bit;  output : out bit_vector(0 to d**h - 1) );
  end component;

  signal buffered_input : bit_vector(0 to d - 1);

begin

  degenerate_tree : if h = 0 generate
    output(0) <= input;
  end generate degenerate_tree;

  compound_tree : if h > 0 generate

    subtree_array : for i in 0 to d - 1 generate

      the_buffer : buf
        port map ( a => input, y => buffered_input(i) );

      the_subtree : fanout_tree
        generic map ( h => h - 1, d => d )
        port map ( input => buffered_input(i),
                   output => output(i * d**(h-1) to (i+1) * d**(h-1) -1) );

    end generate subtree_array;

  end generate compound_tree;

end recursive;

----------------------------------------------------------------

configuration recursive_fanout_tree of fanout_tree is

  for recursive

    for compound_tree
      for subtree_array
        for the_buffer : buf
          use entity work.buf(behaviour);
        end for;
        for the_subtree : fanout_tree
          use configuration recursive_fanout_tree;
        end for;
      end for;
    end for;

  end for;

end recursive_fanout_tree;

----------------------------------------------------------------

architecture repetitive of fanout_tree is

  component buf
    port ( a : in bit;  y : out bit );
  end component;

  signal buffered_input : bit_vector(0 to (d**(h + 1) - 1) / (d - 1) - 1 );

begin

  buffered_input(0) <= input;

  levels : for k in 1 to h generate

    buf_array_array : for i in 0 to d**(k - 1) - 1 generate

      buf_array : for j in 0 to d - 1 generate
        the_buf : buf
          port map ( a => buffered_input( (d**(k - 1) - 1) / (d - 1) + i ),
                     y => buffered_input( (d**k - 1) / (d - 1) + d * i + j ) );
      end generate buf_array;

    end generate buf_array_array;

  end generate levels;

  output <= buffered_input( (d**h - 1) / (d - 1)
                               to (d**(h + 1) - 1) / (d - 1) - 1 );

end repetitive;

----------------------------------------------------------------

configuration repetitive_fanout_tree of fanout_tree is

  for repetitive

    for levels
      for buf_array_array
        for buf_array
          for the_buf : buf
            use entity work.buf(behaviour);
          end for;
        end for;
      end for;
    end for;

  end for;

end repetitive_fanout_tree;

----------------------------------------------------------------

entity tree_test is
  
end tree_test;

----------------------------------------------------------------

architecture bench of tree_test is

  constant test_height : positive := 3;
  constant test_degree : positive := 2;

  signal clock : bit;
  signal recursive_result,
         repetitive_result : bit_vector(0 to test_degree**test_height - 1);

  component fanout_tree
    generic ( h : natural;  d : positive );
    port ( input : in bit;  output : out bit_vector(0 to d**h - 1) );
  end component;

  for recursive_dut : fanout_tree
    use configuration work.recursive_fanout_tree;

  for repetitive_dut : fanout_tree
    use configuration work.repetitive_fanout_tree;

begin

  recursive_dut : fanout_tree
    generic map ( h => test_height, d => test_degree )
    port map ( input => clock, output => recursive_result );

  repetitive_dut : fanout_tree
    generic map ( h => test_height, d => test_degree )
    port map ( input => clock, output => repetitive_result );

  clock_gen : process
  begin
    clock <= '1' after 10 ns, '0' after 20 ns;
    wait for 20 ns;
  end process clock_gen;

  compare_results :
    assert recursive_result = repetitive_result
      report "Results differ";

end bench;