import util.
%import cp.
%module unknown.

/* DWG field packing problem, the solver in picat-lang.org
   See https://www.gnu.org/software/libredwg/ examples/unknown

   At first fix all positions for unique finds: BL93,H330,BL92.
   Skip conflicts, i.e. duplicate fields.

   Then check for all multiple finds if the number of finds is the same as the
   number of equal values: BL90,BL96,BL97. Distribute it then.

   TODO Then pack the possible others optimally: smallest amount of
   missing holes, and keep the original order, with backtracking.

   Print the final layout of fixed and open ranges in dwg.spec syntax.

   Compare to all examples of the same class.
*/

bits(S) = S[1]. % TODO filter out " " and "\n"
value(S) = S[2].
poslist(S) = S[3].
fieldname(S) = cond(S.length >= 4, S[4],
                    [C: C in S.name.atom_chars, ord(C) > ord('9')].to_lowercase).
dxfcode(S) = cond(S.length >= 5, S[5],
                    [C: C in S.name.atom_chars, ord(C) >= ord('0'), ord(C) <= ord('9')]).
bitslen(S) = S[1].length.

go(Data) =>
  [S,Fields,Class,Dxf,Version,Offsets] = Data,
  Found = [],
  println(S), nl,
  print("[hdloff, strsize, commonsize, bitsize, hdlsize]="),println(Offsets),
  S := S.delete_all(" "),
  S := S.delete_all("\n"),
  foreach(Sub in Fields)
    print(Sub.name), print(" "), print(Sub[2]), print(": "++Sub[1]),
    PosList = findall([Start,End], find(S,Sub[1],Start,End)),
    Sub[3] := PosList,
    if PosList.length = 1 then
      Found := add_found(PosList[1],Found,[Sub],Fields), % checks overlap
      print(" "),println(fixed=first(Sub[3]))
    else
      print(" "),print(PosList.length),println(" positions"), % println(positions=PosList),
      % check for matching number of multiple values
      N := same_values(Fields, Sub), % all Subs with same values
      if N.length = PosList.length then
        print("distribute positions: "),
        I = 1,
        foreach(X in N, X[3].length >= I)
          print(X.name),print(" "),
          nth(I,X[3],T1),
          Found := add_found(T1,Found,N,Fields),
          % nth(I,PosList,T),
          X[3] := [PosList[I]], % collapse to single entry
          I := I + 1
        end,
        nl
      end
    end,
    %println(fixed=Found),
  end,

  % At first fix all positions for one finds: BL93,H330,BL92.
  % TODO Error if there's a conflict already.
  % Then check for all multiple finds if the number of finds is the same as the number of
  % equal values: BL90,BL96,BL97. Distribute it then.
  % TODO Then pack the possible others optimally (smallest amount of missing holes),
  % with backtracking.

  % Print the layout of all fixed ranges and holes (yet unconstraint)
  nl,println(fixed=Found),
  Holes = [],
  Sorted := [F: F in Fields, F[3].length == 1],
  Sorted := field_sort(Sorted),
  println(sortd=Sorted.map(poslist).map(first)), % just for control
  % here maybe filter out all all fixed from Fields again
  foreach (F in Found)
    delete_found(F, [], Fields)
  end,
  nl,
  FoundSize = sum(map(bitslen,Sorted)),
  print("Definite result: "),print(FoundSize),print("/"),print(S.length),
  print("\t"),println(Dxf.slice(length("test/test-data/")+1)),
  println("----------------"),
  % create holes by looking at all adjacent pos's
  foreach (I in 1 .. Sorted.length)
    Sub = Sorted[I],
    Pos = first(poslist(Sub)),
    if I == 1 then
      if Pos[1] != 1 then
        %println(pos=Pos),
        H = [1, Pos[1]-1], %println(h=H),
        R = S.slice(1,Pos[1]-1),
        Hole = new_struct('HOLE', [H, R]),
        print(Hole),print(" "),println(len=H[2]+1-H[1]),
        Holes := [Hole]
      end
    else
      Prev := Sorted[I-1],
      PrevPos = first(poslist(Prev)),
      %println(prevpos=PrevPos),
      %println(pos=Pos),
      if Pos[1] > PrevPos[2]+1 then
        H = [PrevPos[2]+1, Pos[1]-1], %println(h=H),
        R = S.slice(PrevPos[2]+1, Pos[1]-1), %println(r=R),
        Hole = new_struct('HOLE', [H, R]),
        print(Hole),print(" "),println(len=H[2]+1-H[1]),
        append(Holes, [Hole], T), Holes := T
      end
    end,
    print_field(Sub,false)
  end,
  % maybe one last hole
  if Sorted.length > 1 then
    Sub = last(Sorted), Pos = first(poslist(Sub)),
    if Pos[2] < S.length then
      H = [Pos[2]+1, S.length], %println(h=H),
      R = S.slice(Pos[2]+1, S.length), %println(r=R),
      Hole = new_struct('HOLE', [H, R]),
      print(Hole),print(" "),println(len=H[2]+1-H[1]),
      append(Holes, [Hole], T), Holes := T
    end
  end,
  println("----------------"),
  NotFoundSize = sum(map(bitslen,[F: F in Fields, F[3].length > 1])),
  BothFoundSizes = FoundSize+NotFoundSize,
  print("Todo: "),print(NotFoundSize),print(" + "),print(FoundSize),
    print(" = "),print(BothFoundSizes),
    print(", Missing: "),println(S.length-BothFoundSizes),
  foreach (F in Fields, F[3].length > 1)
    print_field(F,true)
  end,
  nl,
  println("Most probable result: (TODO)"),
  % TODO: fill holes by probable types (cp or sat?)
  % e.g. if the Hole length is 66 it is most likely a BD, 64 RD, ...
  % check for the nan range then.
  nl.

% H330(01100000,2E4,[[192,199]],reactors,330) =>
% FIELD_H (reactors, 330); // 2E4 01100000 191-198
print_field(Sub,ShowBits) =>
  % split name into type and dxf
  Name = name(Sub), L = poslist(Sub),
  Type = [C: C in Name.atom_chars, ord(C) > ord('9')],
  DXF = Sub.dxfcode,
  print("FIELD_"),print(Type),print(" ("),
  print(Sub.fieldname),
  print(", "),print(DXF),print(");\t// "),
  print(Sub.value),print(" "),
  if ShowBits then print(Sub.bits),print(" ") end,
  if L.length > 10 then
    print(L.slice(1,10)),
    print("...)")
  else
    if L.length == 1 then
      print(L[1])
    else
      print(L)
    end
  end,
  nl.

% list of same values and number of solutions of Sub in Fields
same_values(Fields, Sub) =
  % && or , for /\ here: "compound condition". ; would be or
  [X : X in Fields, X[3].length == Sub[3].length && X[1] = Sub[1]].

% delete found pos from all other fields. changes Fields destructively
delete_found(Pos, Subs, Fields) =>
  %print("delete_found "),print(pos=Pos),print(" "),println(sub=Sub),
  foreach(S in Fields, S[3].length > 1, not member(S, Subs))
    P = S[3], %print(P),
    Before = [P1: P1 in P, P1[1] < Pos[1]],
    After  = [P2: P2 in P, P2[1] > Pos[2]],
    append(Before, After, T),
    %if T.length != P.length then print("=>"), println(T) end,
    S[3] := T
  end.

% add found pos if not already in.
% check valid ranges, change Found inline, keep Found sorted.
add_found(Pos, [], Subs, Fields) = List =>
  List = [Pos],
  delete_found(Pos, Subs, Fields).
% backtracking not needed yet
add_found(Pos, Found, Subs, Fields) = List =>
  %print("add_found "),print(pos=Pos),print(" "),println(found=Found),
  % sort Pos into Found: pos = [33,42] found = [[192,199]]
  Before = [X1: X1 in Found, Pos[1] > X1[1], Pos[2] > X1[1]],
  append(Before, [Pos], T1),
  % and the remaining elems behind. pos = [43,52] found = [[33,42],[192,199]]
  Behind = [X2: X2 in Found, Pos[1] < X2[1], Pos[2] < X2[1]],
  append(T1, Behind, T2),
  if Found.length != T2.length-1 then
    print(" Ignored overlap "), List = Found
  else
    List = T2,
    delete_found(Pos, Subs, Fields)
  end.

% sort Field struct by first pos (simple bubble sort)
field_sort(T) = Ret =>
  T2 = copy_term(T),
  Len = T.length,
  Check = true,
  while(Check = true)
    Swapped = false,
    foreach(I in 2..Len)
      P = T2[I-1], C = T2[I],
      if first(first(P[3])) > first(first(C[3])) then
        T2 := swap(T2,I-1,I),
        Swapped := true % interchange the items.
      end
    end,
    if Swapped = false then
      Check := false
    end
  end,
  Ret = T2.

swap(L,I,J) = L2, list(L) =>
  L2 = copy_term(L),
  T = L2[I],
  L2[I] := L2[J],
  L2[J] := T.

%nth(I,List) = Elem =>
%  K = 0,
%  while (K<I) do
%    L := List.head
%  end,
%  Elem = L.