some updates

[iv.d.git] / flexlay2.d

/* Invisible Vector Library
 * simple FlexBox-based layouting engine
 *
 * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
 * Understanding is not required. Only obedience.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3 of the License ONLY.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */
/// this engine can layout any boxset (if it is valid)
module iv.flexlay2 /*is aliced*/;

/*
the idea of flexbox layout is very simple:

the size of a box is equal to the size of its parent multiplied by the
value of the its `flex` property, and divided by the sum of all the
`flex` properties of all boxes included in its parent.
*/

/*
the algorithm is multipass, and it also does separate layouting for
horizontal and vertical containers.

each box has the following basic properties:
  minSize
  maxSize
  prefSize (preferred, initial size)
also, there is runtime property
  size (real box size)
  finalSize (expanded box size; see below)

let's see how horizontal container is layouted.

first pass: set initial sizes.
recursively calls `setInitSizes()` for all children.
each child sets its initial size to `prefsize`, and calls
`setInitSizes()` for all its children.

second pass: calculate bounding size.
recursively calls `fitToSize()` for all children.
on this pass, we simply sum sizes of all children, and check if
they fit in our maxsize. if they aren't, calculate the extra,
and ask each children to shrink itself with `shrinkBy()`.
we can check child `size` property to see if a shrink succeeded.
loop over all children until either there is no more extra, or
all children refuse to shrink. if we have some extra left,
add it to our size (because this is everything we can do now).

third pass: set real sizes.
recursively calls `calcFinalSize()` for all children.
on this pass, we have correct sizes set, so we simply process
flexbox expanding, as described above.

the same thing is done for vertical containers then.

note that horizontal second pass can perform wrapping too. if we hit a hard
limit, we can try to wrap some children before distributing extra. i didn't
implemented it yet, tho, because i never need to wrap anything, and i prefer
to keep the code clean (haha) and small.
*/

//version = flexlay_debug;


// ////////////////////////////////////////////////////////////////////////// //
/**
Flexbox Layouter

BoxIdT should be lightweight and copyable; also, BoxIdT.init should mean "no box".

the layouter will never allocate anything by itself (but it is highly recursive).
*/
struct FuiFlexLayouter(BoxIdT) {
public:
  bool delegate (BoxIdT id) isValidBoxId;

  // the following delegates will never receive invalid box id from the layouter
  BoxIdT delegate (BoxIdT id) firstChild;
  BoxIdT delegate (BoxIdT id) nextSibling;

  // make sure that returned sizes are never negative (zero is allowed)
  // also, make sure that max size is bigger than min size
  // max size can return `int.max` for "unlimited"

  int delegate (BoxIdT id, in bool horiz) getMinSize;
  int delegate (BoxIdT id, in bool horiz) getMaxSize;
  int delegate (BoxIdT id, in bool horiz) getPrefSize;

  // is this box a horizontal container?
  bool delegate (BoxIdT id) isHorizBox;

  // flex value for this box; <=0 means "not flexible"
  int delegate (BoxIdT id) getFlex;

  // unexpanded box size; never bigger than final size
  // this can be used to align the box inside the expanded (final) rectangle
  // the layouter will never try to get this size before setting it
  int delegate (BoxIdT id, in bool horiz) getSize;
  void delegate (BoxIdT id, in bool horiz, int val) setSize;

  // final expanded box size
  // the layouter will never try to get this size before setting it
  int delegate (BoxIdT id, in bool horiz) getFinalSize;
  void delegate (BoxIdT id, in bool horiz, int val) setFinalSize;

  // final expanded box coordinates inside the parent (i.e. relative to the parent origin)
  void delegate (BoxIdT id, in bool horiz, int val) setFinalPos;

public:
  // the only interesting method here ;-)
  void layout (BoxIdT rootId) {
    if (!isValidBoxId(rootId)) return;
    // phase 0
    setInitSizes(rootId);
    //version(flexlay_debug) dumpLayout();
    // phase 1
    version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "=== fit-to-size: horiz ===\n"); }
    fitToSize(rootId, true, getMaxSize(rootId, true));
    version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "=== fit-to-size: vert ===\n"); }
    fitToSize(rootId, false, getMaxSize(rootId, false));
    //version(flexlay_debug) dumpLayout();
    // phase 2
    version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "=== calc-final: horiz ===\n"); }
    calcFinalSize(rootId, true, true);
    version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "=== calc-final: vert ===\n"); }
    calcFinalSize(rootId, false, true);
    //version(flexlay_debug) dumpLayout();
  }

private:
  void forEachChild (BoxIdT id, scope void delegate (BoxIdT id) dg) {
    assert(dg !is null);
    if (!isValidBoxId(id)) return;
    for (id = firstChild(id); isValidBoxId(id); id = nextSibling(id)) dg(id);
  }

  int calcChildrenSize (BoxIdT id, in bool horiz) {
    if (!isValidBoxId(id)) return 0;
    immutable bool mainDir = (horiz == isHorizBox(id));
    int res = (mainDir ? 0 : int.min);
    for (id = firstChild(id); isValidBoxId(id); id = nextSibling(id)) {
      immutable int sz = getSize(id, horiz);
      if (mainDir) res += sz; else { if (res < sz) res = sz; }
    }
    return res;
  }

private:
  static T min2(T) (in T a, in T b) pure nothrow @safe @nogc { pragma(inline, true); return (a < b ? a : b); }
  static T max2(T) (in T a, in T b) pure nothrow @safe @nogc { pragma(inline, true); return (a > b ? a : b); }
  static T clampval(T) (in T val, in T min, in T max) pure nothrow @safe @nogc { pragma(inline, true); return (val < min ? min : val > max ? max : val); }

  // setup initial size from preferred size
  void setInitSizes (BoxIdT id) {
    if (!isValidBoxId(id)) return;
    // horiz size
    setSize(id, true, clampval(getPrefSize(id, true), getMinSize(id, true), getMaxSize(id, true)));
    // vert size
    setSize(id, false, clampval(getPrefSize(id, false), getMinSize(id, false), getMaxSize(id, false)));
    version(flexlay_debug) {
      import core.stdc.stdio : stderr, fprintf;
      fprintf(stderr, "setInitSizes for %08x; min=(%d,%d); max=(%d,%d); pref=(%d,%d); size=(%d,%d)\n", cast(uint)cast(void*)id,
        getMinSize(id, true), getMinSize(id, false),
        getMaxSize(id, true), getMaxSize(id, false),
        getPrefSize(id, true), getPrefSize(id, false),
        getSize(id, true), getSize(id, false));
    }
    // process children
    forEachChild(id, &setInitSizes);
  }

  void shrinkBy (BoxIdT id, in bool horiz, int delta) {
    assert(delta >= 0);
    if (delta < 1) return;
    immutable int sz = getSize(id, horiz);
    immutable int minsz = getMinSize(id, horiz);
    if (sz <= minsz) return;
    immutable int maxShrink = sz-minsz;
    assert(maxShrink > 0);
    if (delta > maxShrink) delta = maxShrink;
    immutable int nsz = sz-delta;
    fitToSize(id, horiz, nsz);
  }

  // fit into the given size
  // recursively calls `fitToSize()` for all children.
  // on this pass, we simply sum sizes of all children, and check if
  // they fit in our maxsize. if they aren't, calculate the extra,
  // and ask each children to shrink itself with `shrinkBy()`.
  // we can check child `size` property to see if a shrink succeeded.
  // loop over all children until either there is no more extra, or
  // all children refuse to shrink. if we have some extra left,
  // add it to our size (because this is everything we can do now).
  // this also expands box size to accomodate all children.
  void fitToSize (BoxIdT id, in bool horiz, int maxsz) {
    if (!isValidBoxId(id)) return;

    maxsz = max2(0, clampval(maxsz, getMinSize(id, horiz), getMaxSize(id, horiz)));
    version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "fitToSize for %08x: maxsz=%d; size=(%d,%d)\n", cast(uint)cast(void*)id, maxsz, getSize(id, true), getSize(id, false)); }

    int ccount = 0; // number of visible children
    // recursively calls `fitToSize()` for all children
    forEachChild(id, (box) { fitToSize(box, horiz, maxsz); ++ccount; });
    if (ccount == 0) {
      if (getSize(id, horiz) > maxsz) setSize(id, horiz, maxsz);
      return;
    }

    // shrink (fit) loop
    bool wasShrink = true;
    while (wasShrink) {
      // check if our size fits in max
      immutable int csz = calcChildrenSize(id, horiz);
      version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, " csz for %08x=%d; maxsz=%d\n", cast(uint)cast(void*)id, csz, maxsz); }
      if (csz <= maxsz) break; // we're done
      // can't fit, need to shrink children
      int extra = csz-maxsz;
      int shrinkStep = extra/ccount;
      shrinkStep += !shrinkStep;
      wasShrink = false;
      forEachChild(id, (box) {
        if (!extra) return;
        immutable int osz = getSize(box, horiz);
        immutable int sk = (shrinkStep < extra ? shrinkStep : extra);
        shrinkBy(box, horiz, sk);
        immutable int nsz = getSize(box, horiz);
        if (nsz < osz) {
          wasShrink = true;
          extra = max2(0, extra-(osz-nsz));
        }
      });
    }

    // expand this box (up to max size) to fit all children
    immutable int fcsz = min2(maxsz, calcChildrenSize(id, horiz));
    if (getSize(id, horiz) < fcsz) setSize(id, horiz, fcsz);
  }

  void calcFinalSize (BoxIdT id, in bool horiz, in bool isRoot) {
    if (!isValidBoxId(id)) return;

    // degenerate case?
    if (getSize(id, horiz) <= 0) {
      setSize(id, horiz, 0);
      setFinalPos(id, horiz, 0);
      setFinalSize(id, horiz, 0);
      forEachChild(id, (box) {
        setSize(box, horiz, 0);
        setFinalPos(box, horiz, 0);
        calcFinalSize(box, horiz, false);
      });
      return;
    }

    // top level?
    if (isRoot) {
      setFinalPos(id, horiz, 0);
      setFinalSize(id, horiz, getSize(id, horiz));
    }

    // expand all flexboxes
    // the size of a box is equal to the size of its parent multiplied by the
    // value of the its `flex` property, and divided by the sum of all the
    // `flex` properties of all boxes included in its parent.
    //
    // actually, calculate the remaining free space, and distribute it
    int ccount = 0;
    int flextotal = 0;
    forEachChild(id, (box) {
      ++ccount;
      immutable int flex = getFlex(box);
      if (flex > 0) flextotal += flex;
      // also, set initial final size
      setFinalSize(box, horiz, getSize(box, horiz));
    });

    // flexbox processing
    if (flextotal) {
      immutable int csz = calcChildrenSize(id, horiz);
      int left = getSize(id, horiz);
      version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "flex for %08x; csz=%d; left=%d\n", cast(uint)cast(void*)id, csz, left); }
      if (csz < left) {
        left -= csz;
        // grow flexboxes
        while (left) {
          bool wasChange = false;
          immutable int totalsz = left;
          version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "flexpass for %08x: left=%d; flextotal=%d\n", cast(uint)cast(void*)id, left, flextotal); }
          forEachChild(id, (box) {
            if (!left) return;
            immutable int flex = getFlex(box);
            if (flex <= 0) return;
            immutable int finsz = getFinalSize(box, horiz);
            immutable int maxsz = getMaxSize(box, horiz);
            if (finsz >= maxsz) return;
            int addsp = totalsz*flex/flextotal;
            addsp += !addsp;
            version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "  %08x: left=%d; flextotal=%d; flex=%d; addsp=%d\n", cast(uint)cast(void*)box, left, flextotal, getFlex(box), addsp); }
            if (addsp > left) addsp = left;
            immutable int maxgrow = maxsz-finsz;
            if (addsp > maxgrow) addsp = maxgrow;
            version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "  %08x: left=%d; flextotal=%d; flex=%d; addsp=%d (maxgrow=%d)\n", cast(uint)cast(void*)box, left, flextotal, getFlex(box), addsp, maxgrow); }
            setFinalSize(box, horiz, finsz+addsp);
            left -= addsp;
            wasChange = true;
          });
          if (!wasChange) break;
        }
      }
    }

    // setup coords
    immutable bool mainDir = (horiz == isHorizBox(id));
    immutable int fsz = getFinalSize(id, horiz);

    int coord = 0;
    BoxIdT last; // save last child, we may need it later
    forEachChild(id, (box) {
      last = box;
      setFinalPos(box, horiz, coord);
      if (mainDir) {
        coord += getFinalSize(box, horiz);
      } else {
        // expand each box
        immutable int bsz = getSize(box, horiz);
        version(flexlay_debug) { import core.stdc.stdio : stderr, fprintf; fprintf(stderr, "  %08x: expand; bsz=%d; fsz=%d\n", cast(uint)cast(void*)box, bsz, fsz); }
        if (bsz < fsz) {
          // respect max size
          immutable int mxsz = getMaxSize(box, horiz);
          if (bsz < mxsz) setFinalSize(box, horiz, min2(fsz, mxsz));
        }
      }
    });

    // expand last box
    if (mainDir && coord < fsz && isValidBoxId(last)) {
      coord = fsz-coord;
      immutable int lmxsz = getMaxSize(last, horiz);
      immutable int finsz = getFinalSize(last, horiz);
      if (finsz < lmxsz) {
        setFinalSize(last, horiz, min2(finsz+coord, lmxsz));
      }
    }

    // now do the same for all visible children
    // this is done as the last step, because children has their sizes set now
    // we will temporarily set box size property to calculated size, so
    // the box will correctly redistribute everything
    forEachChild(id, (box) {
      //HACK!
      immutable int osz = getSize(box, horiz);
      setSize(box, horiz, getFinalSize(box, horiz));
      calcFinalSize(box, horiz, false);
      setSize(box, horiz, osz);
    });
  }
}