package body Frequency_Graph is

-- CREATORS :

  function Occurrences ( i : natural; l : List ) return natural is

    res : natural := 0;
    tmp : List := l;
    pt : Link_to_Vector;

  begin
    while not Is_Null(tmp) loop
      pt := Head_Of(tmp);
      if pt(i) /= 0
       then res := res + 1;
      end if;
      tmp := Tail_Of(tmp);
    end loop;
    return res;
  end Occurrences;

  function Graph ( n : natural; supports : Array_of_Lists ) return Matrix is

    res : Matrix(1..n,supports'range);

  begin
    for i in 1..n loop
      for j in supports'range loop
        res(i,j) := Occurrences(i,supports(j));
      end loop;
    end loop;
    return res;
  end Graph;

-- MODIFIER :

  procedure Ignore ( m : in out Matrix; point : in Vector ) is
  begin
    for i in point'range loop
      if point(i) /= 0
       then for j in m'range(2) loop
              m(i,j) := 1;
            end loop;
      end if;
    end loop;
  end Ignore;

-- SELECTORS :

  function Occurrence ( i : natural; m : Matrix ) return natural is

    res : natural := 0;

  begin
    for j in m'range(2) loop
      if m(i,j) /= 0
       then res := res + 1;
      end if;
    end loop;
    return res;
  end Occurrence;

  function Occurrence ( i : natural; m : Matrix; col : natural; perm : Vector )
                      return natural is

    res : natural := 0;

  begin
    for j in col+1..m'last(2) loop
      if m(i,perm(j)) /= 0
       then res := res + 1;
      end if;
    end loop;
    return res;
  end Occurrence;

  function Occurrence ( v : Vector; m : Matrix ) return natural is

    min : natural := 1000000;
    occ : natural;

  begin
    for i in v'range loop
      if v(i) /= 0
       then occ := Occurrence(i,m);
            if occ < min
             then min := occ;
            end if;
      end if;
    end loop;
    return min;
  end Occurrence;

  function Occurrence ( v : Vector; m : Matrix; col : natural; perm : Vector )
                      return natural is

    min : natural := 1000000;
    occ : natural;

  begin
    for i in v'range loop
      if v(i) /= 0
       then occ := Occurrence(i,m,col,perm);
            if occ < min
             then min := occ;
            end if;
      end if;
    end loop;
    return min;
  end Occurrence;

  function Lowest_Occurrence
               ( Vec : VecVec; start : natural; m : Matrix ) return natural is

    res : natural := start;
    min : natural := Occurrence(vec(start).all,m);
    occ : natural;

  begin
    for i in start+1..vec'last loop
      occ := Occurrence(vec(i).all,m);
      if occ < min
       then min := occ; res := i;
      end if;
    end loop;
    return res;
  end Lowest_Occurrence;

  function Lowest_Occurrence
               ( vec : VecVec; start : natural; m : Matrix;
                 col : natural; perm : Vector ) return natural is

    res : natural := start;
    min : natural := Occurrence(vec(start).all,m,col,perm);
    occ : natural;

  begin
    for i in start+1..vec'last loop
      occ := Occurrence(vec(i).all,m,col,perm);
      if occ < min
       then min := occ; res := i;
      end if;
    end loop;
    return res;
  end Lowest_Occurrence;

-- CONSTRUCTORS :

  function Sort ( l : List; m : Matrix ) return List is

    res : List;
    vec : VecVec(1..Length_Of(l))
           := Deep_Create(l);
    tmp : Link_to_Vector;
    low : natural;

  begin
    if Length_Of(l) <= 1
     then Copy(l,res);
     else for i in vec'first..vec'last-1 loop
            low := Lowest_Occurrence(vec,i,m);
            if low /= i
             then tmp := vec(i);
                  vec(i) := vec(low);
                  vec(low) := tmp;
            end if;
          end loop;
          res := Deep_Create(vec);
          Clear(vec);
    end if;
    return res;
  end Sort;

  procedure Sort ( l : in out List; m : in Matrix ) is

    res : List := Sort(l,m);

  begin
    Copy(res,l); Deep_Clear(res);
  end Sort;

  function Sort ( l : List; m : Matrix; col : natural; perm : Vector )
                return List is

    res : List;
    vec : VecVec(1..Length_Of(l)) := Deep_Create(l);
    tmp : Link_to_Vector;
    low : natural;

  begin
    if Length_Of(l) <= 1
     then Copy(l,res);
     else for i in vec'first..vec'last-1 loop
            low := Lowest_Occurrence(vec,i,m,col,perm);
            if low /= i
             then tmp := vec(i);
                  vec(i) := vec(low);
                  vec(low) := tmp;
            end if;
          end loop;
          res := Deep_Create(vec);
          Clear(vec);
    end if;
    return res;
  end Sort;

  procedure Sort ( l : in out List; m : in Matrix;
                   col : in natural; perm : in Vector ) is

    res : List := Sort(l,m,col,perm);

  begin
    Copy(res,l); Deep_Clear(res);
  end Sort;

end Frequency_Graph;