-- combinations.adb  instantiate with Item_Type and Vector_Type
--
-- type Vector_Type is array(integer range <>) of Item_Type;
-- procedure My_Combinations is new Combinations(Item_Type, Vector_Type);
--
-- usage:
-- package My_Comb is new Combinations(max_size, item_type, vector_type);
--
-- First := True;
-- Last  := False;
-- while not last loop
--    My_Comb.Comb(N, M, Vn, Vm, First, Last);
--    -- use the generated Vm array
-- end loop;
--
-- N is for n things     n! / ((n-m)! m!) combinations
-- M is for m at a time
-- Vn must be the N items of Vector_Type, unchanged by combinations
-- Vm must be of size M items of Vector_type,
--                      the returned combination each call
-- First must be true the first call, then set to false internally
-- Last is false if more combinations to come.
-- Last is True for the final combination

with Ada.Text_Io;
use  Ada.Text_Io;
package body Combinations is

  procedure Comb(N : Integer; M: Integer; Vn : in Vector_Type;
                 Vm : in out Vector_Type; First : in out Boolean;
                 Last : in out Boolean) is
    J : Integer;
    Debug : Boolean := False;
    Empty : Integer := -1;
  begin
    -- Vm(Vm'First+I) := Vn(Vn'First+I);

    if M<1 or M>N then
      Put_Line("bad parameters to combination, N:="&Integer'Image(N)&
               ", M:="&Integer'Image(M));
      Last := True;
      return;
    end if;

    if First then
      First := False;
      for I in 0..N-1 loop
        if I<M then
          C(i) := i;
          Vm(Vm'First+I) := Vn(Vn'First+I); -- first combination
        else
          C(i) := empty;
        end if;
      end loop;
      Pos := M-1;
      Var := 0;
      Mov := 0;
      if M=N then
        Last := True; -- only one combination
      else
        Last := False;
      end if;
      return;
    end if; -- First

    -- non first case
    if Pos<N-1 then -- simple position, increment last, m-1, item
      if C(Pos+1) /= Empty then
        Put_Line("combinations internal pos error Pos:="&Integer'Image(Pos)&
                 ", Var:="&Integer'Image(Var)&
                 ", Mov:="&Integer'Image(Mov)&
                 ", C(Pos):="&Integer'Image(C(Pos))&
                 ", C(Pos+1):="&Integer'Image(C(Pos+1)));
        Last := True;
        return;
      end if; -- /= Empty
      C(Pos+1) := C(Pos);
      C(Pos) := Empty; -- mark empty space
      Pos := Pos + 1;
      Vm(Vm'First+m-1) := Vn(Vn'First+Pos); -- set new combination
      if M=1 and Pos=N-1 then
        Last := True; -- finished
      else
        Last := False;
      end if;
      return;
    end if; -- pos<N-1

    -- must back up case
    C(N-1) := Empty;
    Mov := N;
    J := 0;
    for I in reverse 0..N-2 loop -- ???
      if C(I) /= Empty then
        C(I) := Empty;
      else
        J := I;
        exit;
      end if;
    end loop;
    for I in reverse 0..J loop -- n-1 last used if we get here
      if C(I) /= Empty then
        Var  := C(I);
        C(I) := Empty;
        Mov  := I+1;   -- start new sequence
        Pos  := Mov+1;
        exit;
      else
        C(I) := Empty;
      end if;
    end loop;
    if Mov=N then
        Put_Line("combinations internal pos error Pos:="&Integer'Image(Pos)&
                 ", Var:="&Integer'Image(Var)&
                 ", Mov:="&Integer'Image(Mov)&
                 ", C(Pos):="&Integer'Image(C(Pos))&
                 ", C(Pos+1):="&Integer'Image(C(Pos+1)));
      Last := True;
      return;
    end if;
    for I in Mov..N-1 loop
      C(I) := Var;
      Vm(Vm'First+Var) := Vn(Vn'First+I);
      Var := Var + 1;
      Pos := I;
      if Var=M then
        exit;
      end if;
    end loop;
    if Debug then
      Put_line("check Pos:="&Integer'Image(Pos)&
               ", Var:="&Integer'Image(Var)&
               ", Mov:="&Integer'Image(Mov));
      for J in 0..N-1 loop
        Put_Line("C("&Integer'Image(J)&")="&Integer'Image(c(j)));
      end loop;
      New_Line;
    end if; -- debug
    if c(mov)=0 and mov>=N-M then
      Last := True; -- last combination
    else
      Last := False;
    end if;
    return;
  end Comb;
end Combinations;