diff options
Diffstat (limited to 'lib/gs/src/gs_packer.erl')
| -rw-r--r-- | lib/gs/src/gs_packer.erl | 275 |
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). |