aboutsummaryrefslogtreecommitdiffstats
path: root/lib/gs/src/gs_packer.erl
diff options
context:
space:
mode:
Diffstat (limited to 'lib/gs/src/gs_packer.erl')
-rw-r--r--lib/gs/src/gs_packer.erl275
1 files changed, 275 insertions, 0 deletions
diff --git a/lib/gs/src/gs_packer.erl b/lib/gs/src/gs_packer.erl
new file mode 100644
index 0000000000..a06ec37e5b
--- /dev/null
+++ b/lib/gs/src/gs_packer.erl
@@ -0,0 +1,275 @@
+%%
+%% %CopyrightBegin%
+%%
+%% Copyright Ericsson AB 1997-2009. All Rights Reserved.
+%%
+%% The contents of this file are subject to the Erlang Public License,
+%% Version 1.1, (the "License"); you may not use this file except in
+%% compliance with the License. You should have received a copy of the
+%% Erlang Public License along with this software. If not, it can be
+%% retrieved online at http://www.erlang.org/.
+%%
+%% Software distributed under the License is distributed on an "AS IS"
+%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+%% the License for the specific language governing rights and limitations
+%% under the License.
+%%
+%% %CopyrightEnd%
+%%
+
+%%
+%% ------------------------------------------------------------
+%% Erlang Graphics Interface geometry manager caclulator
+%% ------------------------------------------------------------
+
+
+-module(gs_packer).
+
+-export([pack/2]).
+%-compile(export_all).
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%
+%%%% This is a simple packer that take a specification in the format
+%%%%
+%%%% Spec -> [WidthSpec, WidthSpec....]
+%%%% WidthSpec -> {fixed,Size} | {stretch,Weight} |
+%%%% {stretch,Weight,Min} | {stretch,Weight,Min,Max}
+%%%%
+%%%% and a given total size it produces a list of sizes of the
+%%%% individual elements. Simple heuristics are used to make the code
+%%%% fast and simple.
+%%%%
+%%%% The Weight is simply a number that is the relative size to the
+%%%% other elements that has weights. If for example the weights
+%%%% for a frame that has three columns are 40 20 100 it means that
+%%%% column 1 has 40/160'th of the space, column 2 20/160'th of
+%%%% the space and column 3 100/160'th of the space.
+%%%%
+%%%% The program try to solve the equation with the constraints given.
+%%%% We have tree cases
+%%%%
+%%%% o We can fullfil the request in the space given
+%%%% o We have less space than needed
+%%%% o We have more space than allowed
+%%%%
+%%%% The algorithm is as follows:
+%%%%
+%%%% 1. Subtract the fixed size, nothing to do about that.
+%%%%
+%%%% 2. Calculate the Unit (or whatever it should be called), the
+%%%% given space minus the fixed sise divided by the Weights.
+%%%%
+%%%% 3. If we in total can fullfill the request we try to
+%%%% fullfill the individual constraints. See remove_failure/2.
+%%%%
+%%%% 4. If we have too little or too much pixels we take our
+%%%% specification and create a new more relaxed one. See
+%%%% cnvt_to_min/1 and cnvt_to_max/1.
+%%%%
+%%%% In general we adjust the specification and redo the whole process
+%%%% until we have a specification that meet the total constraints
+%%%% and individual constraints. When we know that the constraints
+%%%% are satisfied we finally call distribute_space/2 to set the
+%%%% resulting size values for the individual elements.
+%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+pack(Size, SpecSizes) when Size < 0 ->
+ pack(0, SpecSizes);
+pack(Size, SpecSizes) ->
+ {Weights,_Stretched,Fixed,Min,Max} = get_size_info(SpecSizes),
+ Left = Size - Fixed,
+ Unit = if Weights == 0 -> 0; true -> Left / Weights end,
+ if
+ Left < Min ->
+ NewSpecs = cnvt_to_min(SpecSizes),
+ pack(Size,NewSpecs);
+ is_integer(Max), Max =/= 0, Left > Max ->
+ NewSpecs = cnvt_to_max(SpecSizes),
+ pack(Size,NewSpecs);
+ true ->
+ case remove_failure(SpecSizes, Unit) of
+ {no,NewSpecs} ->
+ distribute_space(NewSpecs,Unit);
+ {yes,NewSpecs} ->
+ pack(Size, NewSpecs)
+ end
+ end.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%
+%%%% remove_failure(Specs, Unit)
+%%%%
+%%%% We know that we in total have enough space to fit within the total
+%%%% maximum and minimum requirements. But we have to take care of
+%%%% individual minimum and maximum requirements.
+%%%%
+%%%% This is done with a simple heuristic. We pick the element that
+%%%% has the largest diff from the required min or max, change this
+%%%% {stretch,W,Mi,Ma} to a {fixed,Mi} or {fixed,Ma} and redo the
+%%%% whole process again.
+%%%%
+%%%% **** BUGS ****
+%%%% No known. But try to understand this function and you get a medal ;-)
+%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+remove_failure(Specs, Unit) ->
+ case remove_failure(Specs, Unit, 0) of
+ {done,NewSpecs} ->
+ {yes,NewSpecs};
+ {_,_NewSpecs} ->
+ {no,Specs} % NewSpecs == Specs but
+ end. % we choose the old one
+
+remove_failure([], _Unit, MaxFailure) ->
+ {MaxFailure,[]};
+remove_failure([{stretch,W,Mi} | Specs], Unit, MaxFailure) ->
+ {MinMax,NewMaxFailure} = max_failure(MaxFailure, Mi-W*Unit, 0),
+ case {MinMax,remove_failure(Specs, Unit, NewMaxFailure)} of
+ {min,{NewMaxFailure,Rest}} ->
+ {done,[{fixed,Mi} | Rest]};
+ {_,{OtherMaxFailure, Rest}} ->
+ {OtherMaxFailure,[{stretch,W,Mi} | Rest]}
+ end;
+remove_failure([{stretch,W,Mi,Ma} | Specs], Unit, MaxFailure) ->
+ {MinMax,NewMaxFailure} = max_failure(MaxFailure, Mi-W*Unit, W*Unit-Ma),
+ case {MinMax,remove_failure(Specs, Unit, NewMaxFailure)} of
+ {min,{NewMaxFailure,Rest}} ->
+ {done,[{fixed,Mi} | Rest]};
+ {max,{NewMaxFailure,Rest}} ->
+ {done,[{fixed,Ma} | Rest]};
+ {_,{OtherMaxFailure, Rest}} ->
+ {OtherMaxFailure,[{stretch,W,Mi,Ma} | Rest]}
+ end;
+remove_failure([Spec | Specs], Unit, MaxFailure) ->
+ {NewMaxFailure,NewSpecs} = remove_failure(Specs, Unit, MaxFailure),
+ {NewMaxFailure, [Spec | NewSpecs]}.
+
+max_failure(LastDiff, DMi, DMa)
+ when DMi > LastDiff, DMi > DMa ->
+ {min,DMi};
+max_failure(LastDiff, _DMi, DMa)
+ when DMa > LastDiff ->
+ {max,DMa};
+max_failure(MaxFailure, _DMi, _DMa) ->
+ {other,MaxFailure}.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%
+%%%% distribute_space(Spec,Unit)
+%%%%
+%%%% We now know that we can distribute the space to the elements in
+%%%% the list.
+%%%%
+%%%% **** BUGS ****
+%%%% No known bugs. It try hard to distribute the pixels so that
+%%%% there should eb no pixels left when done but there is no proof
+%%%% that this is the case. The distribution of pixels may also
+%%%% not be optimal. The rounding error from giving one element some
+%%%% pixels is added to the next even if it would be better to add
+%%%% it to an element later in the list (for example the weights
+%%%% 1000, 2, 1000). But this should be good enough.
+%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+distribute_space(Specs, Unit) ->
+ distribute_space(Specs, Unit, 0.0).
+
+distribute_space([], _Unit, _Err) ->
+ [];
+distribute_space([Spec | Specs], Unit, Err) ->
+ distribute_space(Spec, Specs, Unit, Err).
+
+distribute_space({fixed,P}, Specs, Unit, Err) ->
+ [P | distribute_space(Specs, Unit, Err)];
+distribute_space({stretch,Weight}, Specs, Unit, Err) ->
+ Size = Weight * Unit + Err,
+ Pixels = round(Size),
+ NewErr = Size - Pixels,
+ [Pixels | distribute_space(Specs, Unit, NewErr)];
+distribute_space({stretch,W,_Mi}, Specs, Unit, Err) ->
+ distribute_space({stretch,W}, Specs, Unit, Err);
+distribute_space({stretch,W,_Mi,_Ma}, Specs, Unit, Err) ->
+ distribute_space({stretch,W}, Specs, Unit, Err).
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%
+%%%% cnvt_to_min(Spec)
+%%%% cnvt_to_max(Spec)
+%%%%
+%%%% If the space we got isn't enough for the total minimal or maximal
+%%%% requirements then we convert the specification to a more relaxed
+%%%% one that we always can satisfy.
+%%%%
+%%%% This is fun! We do a simple transformation from one specification
+%%%% to a new one. The min, max and fixed size are our new weights!
+%%%% This way the step from a specification we can satisfy and one
+%%%% close that we can't is only a few pixels away, i.e. the transition
+%%%% from within the constraints and outside will be smooth.
+%%%%
+%%%% **** BUGS ****
+%%%% No known bugs.
+%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+cnvt_to_min([]) ->
+ [];
+cnvt_to_min([Spec | Specs]) ->
+ cnvt_to_min(Spec, Specs).
+
+cnvt_to_max([]) ->
+ [];
+cnvt_to_max([Spec | Specs]) ->
+ cnvt_to_max(Spec, Specs).
+
+cnvt_to_min({fixed,P}, Specs) ->
+ [{stretch,P} | cnvt_to_min(Specs)];
+cnvt_to_min({stretch,_W}, Specs) ->
+ [{fixed,0} | cnvt_to_min(Specs)];
+cnvt_to_min({stretch,_W,Mi}, Specs) ->
+ [{stretch,Mi} | cnvt_to_min(Specs)];
+cnvt_to_min({stretch,_W,Mi,_Ma}, Specs) ->
+ [{stretch,Mi} | cnvt_to_min(Specs)].
+
+%% We know that there can only be {fixed,P} and {stretch,W,Mi,Ma}
+%% in this list.
+
+cnvt_to_max({fixed,P}, Specs) ->
+ [{stretch,P} | cnvt_to_max(Specs)];
+cnvt_to_max({stretch,_W,_Mi,Ma}, Specs) ->
+ [{stretch,Ma} | cnvt_to_max(Specs)].
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%
+%%%% Sum the Weights, Min and Max etc
+%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+get_size_info(Specs) ->
+ get_size_info(Specs, 0, 0, 0, 0, 0).
+
+get_size_info([], TotW, NumW, TotFixed, TotMin, TotMax) ->
+ {TotW, NumW, TotFixed, TotMin, TotMax};
+get_size_info([Spec | Specs], TotW, NumW, TotFixed, TotMin, TotMax) ->
+ get_size_info(Spec, TotW, NumW, TotFixed, TotMin, TotMax, Specs).
+
+get_size_info({fixed,P}, TotW, NumW, TotFixed, TotMin, TotMax, Specs) ->
+ get_size_info(Specs, TotW, NumW, TotFixed+P, TotMin, TotMax);
+get_size_info({stretch,W}, TotW, NumW, TotFixed, TotMin, _TotMax, Specs) ->
+ get_size_info(Specs, TotW+W, NumW+1, TotFixed, TotMin, infinity);
+get_size_info({stretch,W,Mi}, TotW, NumW, TotFixed, TotMin, _TotMax, Specs) ->
+ get_size_info(Specs, TotW+W, NumW+1, TotFixed, TotMin+Mi, infinity);
+get_size_info({stretch,W,Mi,_Ma}, TotW, NumW, TotFixed, TotMin, infinity, Specs) ->
+ get_size_info(Specs, TotW+W, NumW+1, TotFixed, TotMin+Mi, infinity);
+get_size_info({stretch,W,Mi,Ma}, TotW, NumW, TotFixed, TotMin, TotMax, Specs) ->
+ get_size_info(Specs, TotW+W, NumW+1, TotFixed, TotMin+Mi, TotMax+Ma).