%%
%%  wings_we.erl --
%%
%%     This module contains functions to build and manipulate
%%     we records (winged-edged records, the central data structure
%%     in Wings 3D).

-module(wings_we).

-export([rebuild/1, is_consistent/1, is_face_consistent/2, new_id/1,
	 new_items_as_ordset/3, validate_mirror/1, visible/1, visible_edges/1]).
 
-include("wings.hrl").

%%%
%%% API.
%%%

validate_mirror(#we{mirror=none}=We) -> We;
validate_mirror(#we{fs=Ftab,mirror=Face}=We) ->
    case gb_trees:is_defined(Face, Ftab) of
        false -> We#we{mirror=none};
        true -> We
    end.

%% rebuild(We) -> We'
%%  Rebuild any missing 'vc' and 'fs' tables. If there are
%%  fewer elements in the 'vc' table than in the 'vp' table,
%%  remove redundant entries in the 'vp' table. Updated id
%%  bounds.
rebuild(#we{vc=undefined,fs=undefined,es=Etab0}=We0) ->
    Etab = gb_trees:to_list(Etab0),
    Ftab = rebuild_ftab(Etab),
    VctList = rebuild_vct(Etab),
    We = We0#we{vc=gb_trees:from_orddict(VctList),fs=Ftab},
    rebuild_1(VctList, We);
rebuild(#we{vc=undefined,es=Etab}=We) ->
    VctList = rebuild_vct(gb_trees:to_list(Etab), []),
    rebuild_1(VctList, We#we{vc=gb_trees:from_orddict(VctList)});
rebuild(#we{fs=undefined,es=Etab}=We) ->
    Ftab = rebuild_ftab(gb_trees:to_list(Etab)),
    rebuild(We#we{fs=Ftab});
rebuild(We) -> update_id_bounds(We).

%%% Utilities for allocating IDs.

new_id(#we{next_id=Id}=We) ->
    {Id,We#we{next_id=Id+1}}.

%%% Returns sets of newly created items.

new_items_as_ordset(vertex, #we{next_id=Wid}, #we{next_id=NewWid,vp=Tab}) ->
    new_items_as_ordset_1(Tab, Wid, NewWid);
new_items_as_ordset(edge, #we{next_id=Wid}, #we{next_id=NewWid,es=Tab}) ->
    new_items_as_ordset_1(Tab, Wid, NewWid);
new_items_as_ordset(face, #we{next_id=Wid}, #we{next_id=NewWid,fs=Tab}) ->
    new_items_as_ordset_1(Tab, Wid, NewWid).

any_hidden(#we{fs=Ftab}) ->
    not gb_trees:is_empty(Ftab) andalso
	wings_util:gb_trees_smallest_key(Ftab) < 0.

%%%
%%% Local functions.
%%%

rebuild_1(VctList, #we{vc=Vct,vp=Vtab0}=We) ->
    case {gb_trees:size(Vct),gb_trees:size(Vtab0)} of
	{Same,Same} -> rebuild(We);
	{Sz1,Sz2} when Sz1 < Sz2 ->
	    Vtab = vertex_gc_1(VctList, gb_trees:to_list(Vtab0), []),
	    rebuild(We#we{vp=Vtab})
    end.

rebuild_vct(Es) ->
    rebuild_vct(Es, []).

rebuild_vct([{Edge,#edge{vs=Va,ve=Vb}}|Es], Acc0) ->
    Acc = rebuild_maybe_add(Va, Vb, Edge, Acc0),
    rebuild_vct(Es, Acc);
rebuild_vct([], VtoE) ->
    build_incident_tab(VtoE).

rebuild_ftab(Es) ->
    rebuild_ftab_1(Es, []).

rebuild_ftab_1([{Edge,#edge{lf=Lf,rf=Rf}}|Es], Acc0) ->
    Acc = rebuild_maybe_add(Lf, Rf, Edge, Acc0),
    rebuild_ftab_1(Es, Acc);
rebuild_ftab_1([], FtoE) ->
    gb_trees:from_orddict(build_incident_tab(FtoE)).

rebuild_maybe_add(Ka, Kb, E, [_,{Ka,_}|_]=Acc) ->
    [{Kb,E}|Acc];
rebuild_maybe_add(Ka, Kb, E, [_,{Kb,_}|_]=Acc) ->
    [{Ka,E}|Acc];
rebuild_maybe_add(Ka, Kb, E, [{Ka,_}|_]=Acc) ->
    [{Kb,E}|Acc];
rebuild_maybe_add(Ka, Kb, E, [{Kb,_}|_]=Acc) ->
    [{Ka,E}|Acc];
rebuild_maybe_add(Ka, Kb, E, Acc) ->
    [{Ka,E},{Kb,E}|Acc].

vertex_gc_1([{V,_}|Vct], [{V,_}=Vtx|Vpos], Acc) ->
    vertex_gc_1(Vct, Vpos, [Vtx|Acc]);
vertex_gc_1([_|_]=Vct, [_|Vpos], Acc) ->
    vertex_gc_1(Vct, Vpos, Acc);
vertex_gc_1([], _, Acc) ->
    gb_trees:from_orddict(lists:reverse(Acc)).

%%%
%%% Handling of hidden faces.
%%%

visible(#we{mirror=none,fs=Ftab}) ->
    visible_2(gb_trees:keys(Ftab));
visible(#we{mirror=Face,fs=Ftab}) ->
    visible_2(gb_trees:keys(gb_trees:delete(Face, Ftab))).

visible_2([F|Fs]) when F < 0 -> visible_2(Fs);
visible_2(Fs) -> Fs.

visible_edges(#we{es=Etab,mirror=Face}=We) ->
    case any_hidden(We) of
	false -> gb_trees:keys(Etab);
	true -> visible_es_1(gb_trees:to_list(Etab), Face, [])
    end.

visible_es_1([{E,#edge{lf=Lf,rf=Rf}}|Es], Face, Acc) ->
    if
	Lf < 0 ->
	    %% Left face hidden.
	    if
		Rf < 0; Rf =:= Face ->
		    %% Both faces invisible (in some way).
		    visible_es_1(Es, Face, Acc);
		true ->
		    %% Right face is visible.
		    visible_es_1(Es, Face, [E|Acc])
	    end;
	Lf =:= Face, Rf < 0 ->
	    %% Left face mirror, right face hidden.
	    visible_es_1(Es, Face, Acc);
	true ->
	    %% At least one face visible.
	    visible_es_1(Es, Face, [E|Acc])
    end;
visible_es_1([], _, Acc) -> ordsets:from_list(Acc).

update_id_bounds(#we{vp=Vtab,es=Etab,fs=Ftab}=We) ->
    case gb_trees:is_empty(Etab) of
	true -> We#we{next_id=0};
	false ->
	    LastId = lists:max([wings_util:gb_trees_largest_key(Vtab),
				wings_util:gb_trees_largest_key(Etab),
				wings_util:gb_trees_largest_key(Ftab)]),
	    We#we{next_id=LastId+1}
    end.

%% build_incident_tab([{Elem,Edge}]) -> [{Elem,Edge}]
%%      Elem = Face or Vertex
%%  Build the table of incident edges for either faces or vertices.
%%  Returns an ordered list where each Elem is unique.

build_incident_tab(ElemToEdgeRel) ->
    T = ets:new(?MODULE, [ordered_set]),
    ets:insert(T, ElemToEdgeRel),
    R = ets:tab2list(T),
    ets:delete(T),
    R.

%%%
%%% Calculate normals.
%%%

new_items_as_ordset_1(Tab, Wid, NewWid) when NewWid-Wid < 32 ->
    new_items_as_ordset_2(Wid, NewWid, Tab, []);
new_items_as_ordset_1(Tab, Wid, _NewWid) ->
    [Item || Item <- gb_trees:keys(Tab), Item >= Wid].

new_items_as_ordset_2(Wid, NewWid, Tab, Acc) when Wid < NewWid ->
    case gb_trees:is_defined(Wid, Tab) of
	true -> new_items_as_ordset_2(Wid+1, NewWid, Tab, [Wid|Acc]);
	false -> new_items_as_ordset_2(Wid+1, NewWid, Tab, Acc)
    end;
new_items_as_ordset_2(_Wid, _NewWid, _Tab, Acc) -> lists:reverse(Acc).

%%%
%%% Test the consistency of a #we{}.
%%%

is_consistent(#we{}=We) ->
    try
	validate_vertex_tab(We),
	validate_faces(We)
    catch error:_ -> false
    end.

is_face_consistent(Face, #we{fs=Ftab,es=Etab}) ->
    Edge = gb_trees:get(Face, Ftab),
    try validate_face(Face, Edge, Etab)
    catch error:_ -> false
    end.

validate_faces(#we{fs=Ftab,es=Etab}) ->
    validate_faces_1(gb_trees:to_list(Ftab), Etab).

validate_faces_1([{Face,Edge}|Fs], Etab) ->
    validate_face(Face, Edge, Etab),
    validate_faces_1(Fs, Etab);
validate_faces_1([], _) -> true.

validate_face(Face, Edge, Etab) ->
    Ccw = walk_face_ccw(Edge, Etab, Face, Edge, []),
    Edge = walk_face_cw(Edge, Etab, Face, Ccw),
    [V|Vs] = lists:sort(Ccw),
    validate_face_vertices(Vs, V).

validate_face_vertices([V|_], V) ->
    erlang:error(repeated_vertex);
validate_face_vertices([_], _) ->
    true;
validate_face_vertices([V|Vs], _) ->
    validate_face_vertices(Vs, V).

walk_face_ccw(LastEdge, _, _, LastEdge, [_|_]=Acc) -> Acc;
walk_face_ccw(Edge, Etab, Face, LastEdge, Acc) ->
    case gb_trees:get(Edge, Etab) of
	#edge{ve=V,lf=Face,ltpr=Next} ->
	    walk_face_ccw(Next, Etab, Face, LastEdge, [V|Acc]);
	#edge{vs=V,rf=Face,rtpr=Next} ->
	    walk_face_ccw(Next, Etab, Face, LastEdge, [V|Acc])
    end.

walk_face_cw(Edge, _, _, []) -> Edge;
walk_face_cw(Edge, Etab, Face, [V|Vs]) ->
    case gb_trees:get(Edge, Etab) of
	#edge{vs=V,lf=Face,ltsu=Next} ->
	    walk_face_cw(Next, Etab, Face, Vs);
	#edge{ve=V,rf=Face,rtsu=Next} ->
	    walk_face_cw(Next, Etab, Face, Vs)
    end.

validate_vertex_tab(#we{es=Etab,vc=Vct}) ->
    lists:foreach(fun({V,Edge}) ->
			  case gb_trees:get(Edge, Etab) of
			      #edge{vs=V} -> ok;
			      #edge{ve=V} -> ok
			  end
		  end, gb_trees:to_list(Vct)).