The R13B03 release.OTP_R13B03

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).