%%
%%  wings_dissolve.erl --
%%
%%     This module implements dissolve of faces.
%%

-module(wings_dissolve).

-export([faces/2, complement/2]).

-include("wings.hrl").

%% faces([Face], We) -> We'
%%  Dissolve the given faces.
faces([], We) -> We;
faces(Faces, #we{fs=Ftab0}=We) ->
    case gb_sets:is_empty(Faces) of
	true -> We;
	false when is_list(Faces) ->
	    Complement = ordsets:subtract(gb_trees:keys(Ftab0),
					  ordsets:from_list(Faces)),
	    dissolve_1(Faces, Complement, We);
	false ->
	    Complement = ordsets:subtract(gb_trees:keys(Ftab0),
					  gb_sets:to_list(Faces)),
	    dissolve_1(Faces, Complement, We)
    end.

faces([], _, We) -> We;
faces(Faces,Complement,We) ->
    case gb_sets:is_empty(Faces) of
        true -> We;
        false -> dissolve_1(Faces, Complement,We)
    end.

dissolve_1(Faces, Complement, We0) ->
    We1 = optimistic_dissolve(Faces,Complement,We0#we{vc=undefined}),
    NewFaces = wings_we:new_items_as_ordset(face, We0, We1),
    We2 = wings_face:delete_bad_faces(NewFaces, We1),
    We = wings_we:rebuild(We2),
    case wings_we:is_consistent(We) of
	true ->
	    We;
	false ->
	    io:format("Dissolving would cause an inconsistent object structure.")
    end.

%% complement([Face], We) -> We'
%%  Dissolve all faces BUT the given faces. Also invalidate the
%%  mirror face if it existed and was dissolved.
complement(Fs0, #we{fs=Ftab0}=We0) when is_list(Fs0) ->
    Fs = ordsets:subtract(gb_trees:keys(Ftab0), ordsets:from_list(Fs0)),
    case faces(Fs, Fs0, We0) of
        #we{mirror=none}=We -> We;
        #we{mirror=Face,fs=Ftab}=We ->
            case gb_trees:is_defined(Face, Ftab) of
                false -> We;
                true -> We#we{mirror=none}
            end
    end;
complement(Fs, We) -> complement(gb_sets:to_list(Fs), We).

optimistic_dissolve(Faces0, Compl, We0) ->
    %% Optimistically assume that we have a simple region without
    %% any holes.
    case outer_edge_loop(Faces0, We0) of
	error ->
	    %% Assumption was wrong. We need to partition the selection
	    %% and dissolve each partition in turn.
	    Parts = wings_sel:face_regions(Faces0, We0),
	    complex_dissolve(Parts, We0);
	[_|_]=Loop ->
	    %% Assumption was correct.
	    simple_dissolve(Faces0, Compl, Loop, We0)
    end.

%% simple_dissolve(Faces, Loop, We0) -> We
%%  Dissolve a region of faces with no holes and no
%%  repeated vertices in the outer edge loop.

simple_dissolve(Faces0, Compl, Loop, We0) ->
    Faces = to_gb_set(Faces0),
    OldFace = gb_sets:smallest(Faces),
    Mat = wings_facemat:face(OldFace, We0),
    We1 = fix_materials(Faces, Compl, We0),
    #we{es=Etab0,fs=Ftab0,he=Htab0} = We1,
    {Ftab1,Etab1,Htab} = simple_del(Faces, Ftab0, Etab0, Htab0, We1),
    {NewFace,We2} = wings_we:new_id(We1),
    Ftab = gb_trees:insert(NewFace, hd(Loop), Ftab1),
    Last = lists:last(Loop),
    Etab = update_outer([Last|Loop], Loop, NewFace, Ftab, Etab1),
    We = We2#we{es=Etab,fs=Ftab,he=Htab},
    wings_facemat:assign(Mat, [NewFace], We).

fix_materials(Del,Keep,We) ->
    case gb_sets:size(Del) < length(Keep) of
	true ->
	    wings_facemat:delete_faces(Del,We);
	false ->
	    wings_facemat:keep_faces(Keep,We)
    end.

to_gb_set(List) when is_list(List) ->
    gb_sets:from_list(List);
to_gb_set(S) -> S.

%% Delete faces and inner edges for a simple region.
simple_del(Faces, Ftab0, Etab0, Htab0, We) ->
    case {gb_trees:size(Ftab0),gb_sets:size(Faces)} of
	{AllSz,FaceSz} when AllSz < 2*FaceSz ->
	    %% At least half of the faces are selected.
	    %% It is faster to find the edges for the
	    %% unselected faces.
	    UnselFaces = ordsets:subtract(gb_trees:keys(Ftab0),
					  gb_sets:to_list(Faces)),

	    UnselSet = sofs:from_external(UnselFaces, [face]),
	    Ftab1 = sofs:from_external(gb_trees:to_list(Ftab0),
				       [{face,edge}]),
	    Ftab2 = sofs:restriction(Ftab1, UnselSet),
	    Ftab = gb_trees:from_orddict(sofs:to_external(Ftab2)),

	    Keep0 = wings_face:to_edges(UnselFaces, We),
	    Keep = sofs:set(Keep0, [edge]),
	    Etab1 = sofs:from_external(gb_trees:to_list(Etab0),
				       [{edge,info}]),
	    Etab2 = sofs:restriction(Etab1, Keep),
	    Etab = gb_trees:from_orddict(sofs:to_external(Etab2)),

	    Htab = simple_del_hard(Htab0, sofs:to_external(Keep), undefined),
	    {Ftab,Etab,Htab};
	{_,_} ->
	    Ftab = lists:foldl(fun(Face, Ft) ->
				       gb_trees:delete(Face, Ft)
			       end, Ftab0, gb_sets:to_list(Faces)),
	    Inner = wings_face:inner_edges(Faces, We),
	    Etab = lists:foldl(fun(Edge, Et) ->
				       gb_trees:delete(Edge, Et)
			       end, Etab0, Inner),
	    Htab = simple_del_hard(Htab0, undefined, Inner),
	    {Ftab,Etab,Htab}
    end.

simple_del_hard(Htab, Keep, Remove) ->
    case gb_sets:is_empty(Htab) of
	true -> Htab;
	false -> simple_del_hard_1(Htab, Keep, Remove)
    end.

simple_del_hard_1(Htab, Keep, undefined) ->
    gb_sets:intersection(Htab, gb_sets:from_ordset(Keep));
simple_del_hard_1(Htab, undefined, Remove) ->
    gb_sets:difference(Htab, gb_sets:from_ordset(Remove)).

%% complex([Partition], We0) -> We0
%%  The general dissolve.

complex_dissolve([Faces|T], We0) ->
    Face = gb_sets:smallest(Faces),
    Mat = wings_facemat:face(Face, We0),
    We1 = wings_facemat:delete_faces(Faces, We0),
    Parts = outer_edge_partition(Faces, We1),
    We = do_dissolve(Faces, Parts, Mat, We0, We1),
    complex_dissolve(T, We);
complex_dissolve([], We) -> We.

do_dissolve(Faces, Ess, Mat, WeOrig, We0) ->
    We1 = do_dissolve_faces(Faces, We0),
    Inner = wings_face:inner_edges(Faces, WeOrig),
    We2 = delete_inner(Inner, We1),
    #we{he=Htab0} = We = do_dissolve_1(Ess, Mat, We2),
    Htab = gb_sets:difference(Htab0, gb_sets:from_list(Inner)),
    We#we{he=Htab}.

do_dissolve_1([EdgeList|Ess], Mat, #we{es=Etab0,fs=Ftab0}=We0) ->
    {Face,We1} = wings_we:new_id(We0),
    Ftab = gb_trees:insert(Face, hd(EdgeList), Ftab0),
    Last = lists:last(EdgeList),
    Etab = update_outer([Last|EdgeList], EdgeList, Face, Ftab, Etab0),
    We2 = We1#we{es=Etab,fs=Ftab},
    We = wings_facemat:assign(Mat, [Face], We2),
    do_dissolve_1(Ess, Mat, We);
do_dissolve_1([], _Mat, We) -> We.

do_dissolve_faces(Faces, #we{fs=Ftab0}=We) ->
    Ftab = lists:foldl(fun(Face, Ft) ->
			       gb_trees:delete(Face, Ft)
		       end, Ftab0, gb_sets:to_list(Faces)),
    We#we{fs=Ftab}.

delete_inner(Inner, #we{es=Etab0}=We) ->
    Etab = lists:foldl(fun(Edge, Et) ->
			       gb_trees:delete(Edge, Et)
		       end, Etab0, Inner),
    We#we{es=Etab}.

update_outer([Pred|[Edge|Succ]=T], More, Face, Ftab, Etab0) ->
    #edge{rf=Rf} = R0 = gb_trees:get(Edge, Etab0),
    Rec = case gb_trees:is_defined(Rf, Ftab) of
	      true ->
		  ?ASSERT(false == gb_trees:is_defined(R0#edge.lf, Ftab)),
		  LS = succ(Succ, More),
		  R0#edge{lf=Face,ltpr=Pred,ltsu=LS};
	      false ->
		  ?ASSERT(true == gb_trees:is_defined(R0#edge.lf, Ftab)),
		  RS = succ(Succ, More),
		  R0#edge{rf=Face,rtpr=Pred,rtsu=RS}
	  end,
    Etab = gb_trees:update(Edge, Rec, Etab0),
    update_outer(T, More, Face, Ftab, Etab);
update_outer([_], _More, _Face, _Ftab, Etab) -> Etab.

succ([Succ|_], _More) -> Succ;
succ([], [Succ|_]) -> Succ.

%% outer_edge_loop(FaceSet,WingedEdge) -> [Edge] | error.
%%  Partition the outer edges of the FaceSet into a single closed loop.
%%  Return 'error' if the faces in FaceSet does not form a
%%  simple region without holes.
%%
%%  Equvivalent to
%%      case outer_edge_partition(FaceSet,WingedEdge) of
%%         [Loop] -> Loop;
%%         [_|_] -> error
%%      end.
%%  but faster.

outer_edge_loop(Faces, We) ->
    case lists:sort(collect_outer_edges(Faces, We)) of
	[] -> error;
	[{Key,Val}|Es0] ->
	    case any_duplicates(Es0, Key) of
		false ->
		    Es = gb_trees:from_orddict(Es0),
		    N = gb_trees:size(Es),
		    outer_edge_loop_1(Val, Es, Key, N, []);
		true -> error
	    end
    end.

outer_edge_loop_1({Edge,V}, _, V, 0, Acc) ->
    %% This edge completes the loop, and we have used all possible edges.
    [Edge|Acc];
outer_edge_loop_1({_,V}, _, V, _N, _) ->
    %% Loop is complete, but we haven't used all edges.
    error;
outer_edge_loop_1({_,_}, _, _, 0, _) ->
    %% We have used all possible edges, but somehow the loop
    %% is not complete. I can't see how this is possible.
    erlang:error(internal_error);
outer_edge_loop_1({Edge,Vb}, Es, EndV, N, Acc0) ->
    Acc = [Edge|Acc0],
    outer_edge_loop_1(gb_trees:get(Vb, Es), Es, EndV, N-1, Acc).

any_duplicates([{V,_}|_], V) -> true;
any_duplicates([_], _) -> false;
any_duplicates([{V,_}|Es], _) -> any_duplicates(Es, V).

%% outer_edge_partition(FaceSet, WingedEdge) -> [[Edge]].
%%  Partition the outer edges of the FaceSet. Each partion
%%  of edges form a closed loop with no repeated vertices.
%%    Outer edges are edges that have one face in FaceSet
%%  and one outside.
%%    It is assumed that FaceSet consists of one region returned by
%%  wings_sel:face_regions/2.

outer_edge_partition(Faces, We) ->
    F0 = collect_outer_edges(Faces, We),
    F = gb_trees:from_orddict(wings_util:rel2fam(F0)),
    partition_edges(F, []).

collect_outer_edges(Faces, We) when is_list(Faces) ->
    collect_outer_edges_1(Faces, gb_sets:from_list(Faces), We);
collect_outer_edges(Faces, We) ->
    collect_outer_edges_1(gb_sets:to_list(Faces), Faces, We).

collect_outer_edges_1(Fs0, Faces0, #we{fs=Ftab}=We) ->
    case {gb_trees:size(Ftab),gb_sets:size(Faces0)} of
	{AllSz,FaceSz} when AllSz < 2*FaceSz ->
	    Fs = ordsets:subtract(gb_trees:keys(Ftab), Fs0),
	    Faces = gb_sets:from_ordset(Fs),
	    Coll = collect_outer_edges_a(Faces),
	    wings_face:fold_faces(Coll, [], Fs, We);
	{_,_} ->
	    Coll = collect_outer_edges_b(Faces0),
	    wings_face:fold_faces(Coll, [], Fs0, We)
    end.

collect_outer_edges_a(Faces) ->
    fun(Face, _, Edge, #edge{ve=V,vs=OtherV,lf=Face,rf=Other}, Acc) ->
	    case gb_sets:is_member(Other, Faces) of
		false -> [{V,{Edge,OtherV}}|Acc];
		true -> Acc
	    end;
       (Face, _, Edge, #edge{ve=OtherV,vs=V,rf=Face,lf=Other}, Acc) ->
	    case gb_sets:is_member(Other, Faces) of
		false -> [{V,{Edge,OtherV}}|Acc];
		true -> Acc
	    end
    end.

collect_outer_edges_b(Faces) ->
    fun(Face, _, Edge, #edge{vs=V,ve=OtherV,lf=Face,rf=Other}, Acc) ->
	    case gb_sets:is_member(Other, Faces) of
		false -> [{V,{Edge,OtherV}}|Acc];
		true -> Acc
	    end;
       (Face, _, Edge, #edge{vs=OtherV,ve=V,rf=Face,lf=Other}, Acc) ->
	    case gb_sets:is_member(Other, Faces) of
		false -> [{V,{Edge,OtherV}}|Acc];
		true -> Acc
	    end
    end.

partition_edges(Es0, Acc) ->
    case gb_trees:is_empty(Es0) of
	true -> Acc;
	false ->
	    {Key,Val,Es1} = gb_trees:take_smallest(Es0),
	    {Cycle,Es} = part_collect_cycle(Key, Val, Es1, []),
	    partition_edges(Es, [Cycle|Acc])
    end.

%% part_collect_cycle(Vertex, VertexInfo, EdgeInfo, Acc0) ->
%%    none | {[Edge],EdgeInfo}
%%  Collect the cycle starting with Vertex.
%%
%%  Note: This function can only return 'none' when called
%%  recursively.

part_collect_cycle(_, repeated, _, _) ->
    %% Repeated vertex - we are not allowed to go this way.
    %% Can only happen if we were called recursively because
    %% a fork was encountered.
    none;
part_collect_cycle(_Va, [{Edge,Vb}], Es0, Acc0) ->
    %% Basic case. Only one way to go.
    Acc = [Edge|Acc0],
    case gb_trees:lookup(Vb, Es0) of
	none ->
	    {Acc,Es0};
	{value,Val} ->
	    Es = gb_trees:delete(Vb, Es0),
	    part_collect_cycle(Vb, Val, Es, Acc)
    end;
part_collect_cycle(Va, [Val|More], Es0, []) ->
    %% No cycle started yet and we have multiple choice of
    %% edges out from this vertex. It doesn't matter which
    %% edge we follow, so we'll follow the first one.
    {Cycle,Es} = part_collect_cycle(Va, [Val], Es0, []),
    {Cycle,gb_trees:insert(Va, More, Es)};
part_collect_cycle(Va, Edges, Es0, Acc) ->
    %% We have a partially collected cycle and we have a
    %% fork (multiple choice of edges). Here we must choose
    %% an edge that closes the cycle without passing Va
    %% again (because repeated vertices are not allowed).
    Es = gb_trees:insert(Va, repeated, Es0),
    part_fork(Va, Edges, Es, Acc, []).

part_fork(Va, [Val|More], Es0, Acc, Tried) ->
    %% Try to complete the cycle by following this edge.
    case part_collect_cycle(Va, [Val], Es0, Acc) of
	none ->
	    %% Failure - try the next edge.
	    part_fork(Va, More, Es0, Acc, [Val|Tried]);
	{Cycle,Es} ->
	    %% Found a cycle. Update the vertex information
	    %% with all edges remaining.
	    {Cycle,gb_trees:update(Va, lists:reverse(Tried, More), Es)}
    end;
part_fork(_, [], _, _, _) ->
    %% None of edges were possible. Can only happen if this function
    %% was called recursively (i.e. if we hit another fork while
    %% processing a fork).
    none.