/*  GRAPHITE2 LICENSING

    Copyright 2010, SIL International

    All rights reserved.

    This library is free software; you can redistribute it and/or modify

    it under the terms of the GNU Lesser General Public License as published

    by the Free Software Foundation; either version 2.1 of License, or

    (at your option) any later version.

    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

    Lesser General Public License for more details.

    You should also have received a copy of the GNU Lesser General Public

    License along with this library in the file named "LICENSE".

    If not, write to the Free Software Foundation, 51 Franklin Street,

    Suite 500, Boston, MA 02110-1335, USA or visit their web page on the

    internet at http://www.fsf.org/licenses/lgpl.html.

Alternatively, the contents of this file may be used under the terms of the

Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public

License, as published by the Free Software Foundation, either version 2

of the License or (at your option) any later version.

*/

#include <algorithm>

#include <limits>

#include <cmath>

#include <string>

#include <functional>

#include "inc/Collider.h"

#include "inc/Segment.h"

#include "inc/Slot.h"

#include "inc/GlyphCache.h"

#include "inc/Sparse.h"

#define ISQRT2 0.707106781f

// Possible rounding error for subbox boundaries: 0.016 = 1/64 = 1/256 * 4

// (values in font range from 0..256)

// #define SUBBOX_RND_ERR 0.016

using namespace graphite2;

////    SHIFT-COLLIDER    ////

// Initialize the Collider to hold the basic movement limits for the

// target slot, the one we are focusing on fixing.

bool ShiftCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin, float marginWeight,

    const Position &currShift, const Position &currOffset, int dir, GR_MAYBE_UNUSED json * const dbgout)

{

    int i;

    float mx, mn;

    float a, shift;

    const GlyphCache &gc = seg->getFace()->glyphs();

    unsigned short gid = aSlot->gid();

    if (!gc.check(gid))

        return false;

    const BBox &bb = gc.getBoundingBBox(gid);

    const SlantBox &sb = gc.getBoundingSlantBox(gid);

    //float sx = aSlot->origin().x + currShift.x;

    //float sy = aSlot->origin().y + currShift.y;

    if (currOffset.x != 0.f || currOffset.y != 0.f)

        _limit = Rect(limit.bl - currOffset, limit.tr - currOffset);

    else

        _limit = limit;

    // For a ShiftCollider, these indices indicate which vector we are moving by:

    // each _ranges represents absolute space with respect to the origin of the slot. Thus take into account true origins but subtract the vmin for the slot

    for (i = 0; i < 4; ++i)

    {

        switch (i) {

            case 0 :  // x direction

                mn = _limit.bl.x + currOffset.x;

                mx = _limit.tr.x + currOffset.x;

                _len[i] = bb.xa - bb.xi;

                a = currOffset.y + currShift.y;

                _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a);

                break;

            case 1 :  // y direction

                mn = _limit.bl.y + currOffset.y;

                mx = _limit.tr.y + currOffset.y;

                _len[i] = bb.ya - bb.yi;

                a = currOffset.x + currShift.x;

                _ranges[i].initialise<XY>(mn, mx, margin, marginWeight, a);

                break;

            case 2 :  // sum (negatively sloped diagonal boundaries)

                // pick closest x,y limit boundaries in s direction

                shift = currOffset.x + currOffset.y + currShift.x + currShift.y;

                mn = -2 * min(currShift.x - _limit.bl.x, currShift.y - _limit.bl.y) + shift;

                mx = 2 * min(_limit.tr.x - currShift.x, _limit.tr.y - currShift.y) + shift;

                _len[i] = sb.sa - sb.si;

                a = currOffset.x - currOffset.y + currShift.x - currShift.y;

                _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a);

                break;

            case 3 :  // diff (positively sloped diagonal boundaries)

                // pick closest x,y limit boundaries in d direction

                shift = currOffset.x - currOffset.y + currShift.x - currShift.y;

                mn = -2 * min(currShift.x - _limit.bl.x, _limit.tr.y - currShift.y) + shift;

                mx = 2 * min(_limit.tr.x - currShift.x, currShift.y - _limit.bl.y) + shift;

                _len[i] = sb.da - sb.di;

                a = currOffset.x + currOffset.y + currShift.x + currShift.y;

                _ranges[i].initialise<SD>(mn, mx, margin / ISQRT2, marginWeight, a);

                break;

        }

    }

  _target = aSlot;

    if ((dir & 1) == 0)

    {

        // For LTR, switch and negate x limits.

        _limit.bl.x = -1 * limit.tr.x;

        //_limit.tr.x = -1 * limit.bl.x;

    }

    _currOffset = currOffset;

    _currShift = currShift;

    _origin = aSlot->origin() - currOffset;     // the original anchor position of the glyph

  _margin = margin;

  _marginWt = marginWeight;

    SlotCollision *c = seg->collisionInfo(aSlot);

    _seqClass = c->seqClass();

  _seqProxClass = c->seqProxClass();

    _seqOrder = c->seqOrder();

    return true;

}

template <class O>

float sdm(float vi, float va, float mx, float my, O op)

{

    float res = 2 * mx - vi;

    if (op(res, vi + 2 * my))

    {

        res = va + 2 * my;

        if (op(res, 2 * mx - va))

            res = mx + my;

    }

    return res;

}

Unexecuted instantiation: float sdm<std::__1::greater<float> >(float, float, float, float, std::__1::greater<float>)

Unexecuted instantiation: float sdm<std::__1::less<float> >(float, float, float, float, std::__1::less<float>)

// Mark an area with a cost that can vary along the x or y axis. The region is expressed in terms of the centre of the target glyph in each axis

void ShiftCollider::addBox_slope(bool isx, const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, float weight, float m, bool minright, int axis)

{

    float a, c;

    switch (axis) {

        case 0 :

             if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0)

            {

                a = org.y + 0.5f * (bb.yi + bb.ya);

                c = 0.5f * (bb.xi + bb.xa);

                if (isx)

                    _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, m,

                                                (minright ? box.tr.x : box.bl.x) - c, a, 0, false);

                else

                    _ranges[axis].weighted<XY>(box.bl.x - c, box.tr.x - c, weight, a, 0, 0, org.y,

                                                m * (a * a + sqr((minright ? box.tr.y : box.bl.y) - 0.5f * (bb.yi + bb.ya))), false);

            }

            break;

        case 1 :

            if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0)

            {

                a = org.x + 0.5f * (bb.xi + bb.xa);

                c = 0.5f * (bb.yi + bb.ya);

                if (isx)

                    _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, 0, 0, org.x,

                                                m * (a * a + sqr((minright ? box.tr.x : box.bl.x) - 0.5f * (bb.xi + bb.xa))), false);

                else

                    _ranges[axis].weighted<XY>(box.bl.y - c, box.tr.y - c, weight, a, m,

                                                (minright ? box.tr.y : box.bl.y) - c, a, 0, false);

            }

            break;

        case 2 :

            if (box.bl.x - box.tr.y < org.x - org.y + sb.da && box.tr.x - box.bl.y > org.x - org.y + sb.di)

            {

                float d = org.x - org.y + 0.5f * (sb.di + sb.da);

                c = 0.5f * (sb.si + sb.sa);

                float smax = min(2 * box.tr.x - d, 2 * box.tr.y + d);

                float smin = max(2 * box.bl.x - d, 2 * box.bl.y + d);

                if (smin > smax) return;

                float si;

                a = d;

                if (isx)

                    si = 2 * (minright ? box.tr.x : box.bl.x) - a;

                else

                    si = 2 * (minright ? box.tr.y : box.bl.y) + a;

                _ranges[axis].weighted<SD>(smin - c, smax - c, weight / 2, a, m / 2, si, 0, 0, isx);

            }

            break;

        case 3 :

            if (box.bl.x + box.bl.y < org.x + org.y + sb.sa && box.tr.x + box.tr.y > org.x + org.y + sb.si)

            {

                float s = org.x + org.y + 0.5f * (sb.si + sb.sa);

                c = 0.5f * (sb.di + sb.da);

                float dmax = min(2 * box.tr.x - s, s - 2 * box.bl.y);

                float dmin = max(2 * box.bl.x - s, s - 2 * box.tr.y);

                if (dmin > dmax) return;

                float di;

                a = s;

                if (isx)

                    di = 2 * (minright ? box.tr.x : box.bl.x) - a;

                else

                    di = 2 * (minright ? box.tr.y : box.bl.y) + a;

                _ranges[axis].weighted<SD>(dmin - c, dmax - c, weight / 2, a, m / 2, di, 0, 0, !isx);

            }

            break;

        default :

            break;

    }

    return;

}

// Mark an area with an absolute cost, making it completely inaccessible.

inline void ShiftCollider::removeBox(const Rect &box, const BBox &bb, const SlantBox &sb, const Position &org, int axis)

{

    float c;

    switch (axis) {

        case 0 :

            if (box.bl.y < org.y + bb.ya && box.tr.y > org.y + bb.yi && box.width() > 0)

            {

                c = 0.5f * (bb.xi + bb.xa);

                _ranges[axis].exclude(box.bl.x - c, box.tr.x - c);

            }

            break;

        case 1 :

            if (box.bl.x < org.x + bb.xa && box.tr.x > org.x + bb.xi && box.height() > 0)

            {

                c = 0.5f * (bb.yi + bb.ya);

                _ranges[axis].exclude(box.bl.y - c, box.tr.y - c);

            }

            break;

        case 2 :

            if (box.bl.x - box.tr.y < org.x - org.y + sb.da && box.tr.x - box.bl.y > org.x - org.y + sb.di

                && box.width() > 0 && box.height() > 0)

            {

                float di = org.x - org.y + sb.di;

                float da = org.x - org.y + sb.da;

                float smax = sdm(di, da, box.tr.x, box.tr.y, std::greater<float>());

                float smin = sdm(da, di, box.bl.x, box.bl.y, std::less<float>());

                c = 0.5f * (sb.si + sb.sa);

                _ranges[axis].exclude(smin - c, smax - c);

            }

            break;

        case 3 :

            if (box.bl.x + box.bl.y < org.x + org.y + sb.sa && box.tr.x + box.tr.y > org.x + org.y + sb.si

                && box.width() > 0 && box.height() > 0)

            {

                float si = org.x + org.y + sb.si;

                float sa = org.x + org.y + sb.sa;

                float dmax = sdm(si, sa, box.tr.x, -box.bl.y, std::greater<float>());

                float dmin = sdm(sa, si, box.bl.x, -box.tr.y, std::less<float>());

                c = 0.5f * (sb.di + sb.da);

                _ranges[axis].exclude(dmin - c, dmax - c);

            }

            break;

        default :

            break;

    }

    return;

}

// Adjust the movement limits for the target to avoid having it collide

// with the given neighbor slot. Also determine if there is in fact a collision

// between the target and the given slot.

bool ShiftCollider::mergeSlot(Segment *seg, Slot *slot, const SlotCollision *cslot, const Position &currShift,

    bool isAfter,  // slot is logically after _target

    bool sameCluster, bool &hasCol, bool isExclusion,

        GR_MAYBE_UNUSED json * const dbgout )

{

    bool isCol = false;

    const float sx = slot->origin().x - _origin.x + currShift.x;

    const float sy = slot->origin().y - _origin.y + currShift.y;

    const float sd = sx - sy;

    const float ss = sx + sy;

    float vmin, vmax;

    float omin, omax, otmin, otmax;

    float cmin, cmax;   // target limits

    float torg;

    const GlyphCache &gc = seg->getFace()->glyphs();

    const unsigned short gid = slot->gid();

    if (!gc.check(gid))

        return false;

    const BBox &bb = gc.getBoundingBBox(gid);

    // SlotCollision * cslot = seg->collisionInfo(slot);

    int orderFlags = 0;

    bool sameClass = _seqProxClass == 0 && cslot->seqClass() == _seqClass;

    if (sameCluster && _seqClass

        && (sameClass || (_seqProxClass != 0 && cslot->seqClass() == _seqProxClass)))

    // Force the target glyph to be in the specified direction from the slot we're testing.

        orderFlags = _seqOrder;

    // short circuit if only interested in direct collision and we are out of range

    if (orderFlags || (sx + bb.xa + _margin >= _limit.bl.x && sx + bb.xi - _margin <= _limit.tr.x)

                    || (sy + bb.ya + _margin >= _limit.bl.y && sy + bb.yi - _margin <= _limit.tr.y))

    {

        const float tx = _currOffset.x + _currShift.x;

        const float ty = _currOffset.y + _currShift.y;

        const float td = tx - ty;

        const float ts = tx + ty;

        const SlantBox &sb = gc.getBoundingSlantBox(gid);

        const unsigned short tgid = _target->gid();

        const BBox &tbb = gc.getBoundingBBox(tgid);

        const SlantBox &tsb = gc.getBoundingSlantBox(tgid);

        float seq_above_wt = cslot->seqAboveWt();

        float seq_below_wt = cslot->seqBelowWt();

        float seq_valign_wt = cslot->seqValignWt();

        float lmargin;

        // if isAfter, invert orderFlags for diagonal orders.

        if (isAfter)

        {

            // invert appropriate bits

            orderFlags ^= (sameClass ? 0x3F : 0x3);

            // consider 2 bits at a time, non overlapping. If both bits set, clear them

            orderFlags = orderFlags ^ ((((orderFlags >> 1) & orderFlags) & 0x15) * 3);

        }

#if !defined GRAPHITE2_NTRACING

        if (dbgout)

            dbgout->setenv(0, slot);

#endif

        // Process main bounding octabox.

        for (int i = 0; i < 4; ++i)

        {

            switch (i) {

                case 0 :  // x direction

                    vmin = max(max(bb.xi - tbb.xa + sx, sb.di - tsb.da + ty + sd), sb.si - tsb.sa - ty + ss);

                    vmax = min(min(bb.xa - tbb.xi + sx, sb.da - tsb.di + ty + sd), sb.sa - tsb.si - ty + ss);

                    otmin = tbb.yi + ty;

                    otmax = tbb.ya + ty;

                    omin = bb.yi + sy;

                    omax = bb.ya + sy;

                    torg = _currOffset.x;

                    cmin = _limit.bl.x + torg;

                    cmax = _limit.tr.x - tbb.xi + tbb.xa + torg;

                    lmargin = _margin;

                    break;

                case 1 :  // y direction

                    vmin = max(max(bb.yi - tbb.ya + sy, tsb.di - sb.da + tx - sd), sb.si - tsb.sa - tx + ss);

                    vmax = min(min(bb.ya - tbb.yi + sy, tsb.da - sb.di + tx - sd), sb.sa - tsb.si - tx + ss);

                    otmin = tbb.xi + tx;

                    otmax = tbb.xa + tx;

                    omin = bb.xi + sx;

                    omax = bb.xa + sx;

                    torg = _currOffset.y;

                    cmin = _limit.bl.y + torg;

                    cmax = _limit.tr.y - tbb.yi + tbb.ya + torg;

                    lmargin = _margin;

                    break;

                case 2 :    // sum - moving along the positively-sloped vector, so the boundaries are the

                            // negatively-sloped boundaries.

                    vmin = max(max(sb.si - tsb.sa + ss, 2 * (bb.yi - tbb.ya + sy) + td), 2 * (bb.xi - tbb.xa + sx) - td);

                    vmax = min(min(sb.sa - tsb.si + ss, 2 * (bb.ya - tbb.yi + sy) + td), 2 * (bb.xa - tbb.xi + sx) - td);

                    otmin = tsb.di + td;

                    otmax = tsb.da + td;

                    omin = sb.di + sd;

                    omax = sb.da + sd;

                    torg = _currOffset.x + _currOffset.y;

                    cmin = _limit.bl.x + _limit.bl.y + torg;

                    cmax = _limit.tr.x + _limit.tr.y - tsb.si + tsb.sa + torg;

                    lmargin = _margin / ISQRT2;

                    break;

                case 3 :    // diff - moving along the negatively-sloped vector, so the boundaries are the

                            // positively-sloped boundaries.

                    vmin = max(max(sb.di - tsb.da + sd, 2 * (bb.xi - tbb.xa + sx) - ts), -2 * (bb.ya - tbb.yi + sy) + ts);

                    vmax = min(min(sb.da - tsb.di + sd, 2 * (bb.xa - tbb.xi + sx) - ts), -2 * (bb.yi - tbb.ya + sy) + ts);

                    otmin = tsb.si + ts;

                    otmax = tsb.sa + ts;

                    omin = sb.si + ss;

                    omax = sb.sa + ss;

                    torg = _currOffset.x - _currOffset.y;

                    cmin = _limit.bl.x - _limit.tr.y + torg;

                    cmax = _limit.tr.x - _limit.bl.y - tsb.di + tsb.da + torg;

                    lmargin = _margin / ISQRT2;

                    break;

                default :

                    continue;

            }

#if !defined GRAPHITE2_NTRACING

            if (dbgout)

                dbgout->setenv(1, reinterpret_cast<void *>(-1));

#define DBGTAG(x) if (dbgout) dbgout->setenv(1, reinterpret_cast<void *>(-x));

#else

#define DBGTAG(x)

#endif

            if (orderFlags)

            {

                Position org(tx, ty);

                float xminf = _limit.bl.x + _currOffset.x + tbb.xi;

                float xpinf = _limit.tr.x + _currOffset.x + tbb.xa;

                float ypinf = _limit.tr.y + _currOffset.y + tbb.ya;

                float yminf = _limit.bl.y + _currOffset.y + tbb.yi;

                switch (orderFlags) {

                    case SlotCollision::SEQ_ORDER_RIGHTUP :

                    {

                        float r1Xedge = cslot->seqAboveXoff() + 0.5f * (bb.xi + bb.xa) + sx;

                        float r3Xedge = cslot->seqBelowXlim() + bb.xa + sx + 0.5f * (tbb.xa - tbb.xi);

                        float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy;

                        // DBGTAG(1x) means the regions are up and right

                        // region 1

                        DBGTAG(11)

                        addBox_slope(true, Rect(Position(xminf, r2Yedge), Position(r1Xedge, ypinf)),

                                        tbb, tsb, org, 0, seq_above_wt, true, i);

                        // region 2

                        DBGTAG(12)

                        removeBox(Rect(Position(xminf, yminf), Position(r3Xedge, r2Yedge)), tbb, tsb, org, i);

                        // region 3, which end is zero is irrelevant since m weight is 0

                        DBGTAG(13)

                        addBox_slope(true, Rect(Position(r3Xedge, yminf), Position(xpinf, r2Yedge - cslot->seqValignHt())),

                                        tbb, tsb, org, seq_below_wt, 0, true, i);

                        // region 4

                        DBGTAG(14)

                        addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge), Position(xpinf, r2Yedge + cslot->seqValignHt())),

                                        tbb, tsb, org, 0, seq_valign_wt, true, i);

                        // region 5

                        DBGTAG(15)

                        addBox_slope(false, Rect(Position(sx + bb.xi, r2Yedge - cslot->seqValignHt()), Position(xpinf, r2Yedge)),

                                        tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i);

                        break;

                    }

                    case SlotCollision::SEQ_ORDER_LEFTDOWN :

                    {

                        float r1Xedge = 0.5f * (bb.xi + bb.xa) + cslot->seqAboveXoff() + sx;

                        float r3Xedge = bb.xi - cslot->seqBelowXlim() + sx - 0.5f * (tbb.xa - tbb.xi);

                        float r2Yedge = 0.5f * (bb.yi + bb.ya) + sy;

                        // DBGTAG(2x) means the regions are up and right

                        // region 1

                        DBGTAG(21)

                        addBox_slope(true, Rect(Position(r1Xedge, yminf), Position(xpinf, r2Yedge)),

                                        tbb, tsb, org, 0, seq_above_wt, false, i);

                        // region 2

                        DBGTAG(22)

                        removeBox(Rect(Position(r3Xedge, r2Yedge), Position(xpinf, ypinf)), tbb, tsb, org, i);

                        // region 3

                        DBGTAG(23)

                        addBox_slope(true, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()), Position(r3Xedge, ypinf)),

                                        tbb, tsb, org, seq_below_wt, 0, false, i);

                        // region 4

                        DBGTAG(24)

                        addBox_slope(false, Rect(Position(xminf, r2Yedge), Position(sx + bb.xa, r2Yedge + cslot->seqValignHt())),

                                        tbb, tsb, org, 0, seq_valign_wt, true, i);

                        // region 5

                        DBGTAG(25)

                        addBox_slope(false, Rect(Position(xminf, r2Yedge - cslot->seqValignHt()),

                                        Position(sx + bb.xa, r2Yedge)), tbb, tsb, org, seq_below_wt, seq_valign_wt, false, i);

                        break;

                    }

                    case SlotCollision::SEQ_ORDER_NOABOVE : // enforce neighboring glyph being above

                        DBGTAG(31);

                        removeBox(Rect(Position(bb.xi - tbb.xa + sx, sy + bb.ya),

                                        Position(bb.xa - tbb.xi + sx, ypinf)), tbb, tsb, org, i);

                        break;

                    case SlotCollision::SEQ_ORDER_NOBELOW : // enforce neighboring glyph being below

                        DBGTAG(32);

                        removeBox(Rect(Position(bb.xi - tbb.xa + sx, yminf),

                                        Position(bb.xa - tbb.xi + sx, sy + bb.yi)), tbb, tsb, org, i);

                        break;

                    case SlotCollision::SEQ_ORDER_NOLEFT :  // enforce neighboring glyph being to the left

                        DBGTAG(33)

                        removeBox(Rect(Position(xminf, bb.yi - tbb.ya + sy),

                                        Position(bb.xi - tbb.xa + sx, bb.ya - tbb.yi + sy)), tbb, tsb, org, i);

                        break;

                    case SlotCollision::SEQ_ORDER_NORIGHT : // enforce neighboring glyph being to the right

                        DBGTAG(34)

                        removeBox(Rect(Position(bb.xa - tbb.xi + sx, bb.yi - tbb.ya + sy),

                                        Position(xpinf, bb.ya - tbb.yi + sy)), tbb, tsb, org, i);

                        break;

                    default :

                        break;

                }

            }

            if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin)

                continue;

            // Process sub-boxes that are defined for this glyph.

            // We only need to do this if there was in fact a collision with the main octabox.

            uint8 numsub = gc.numSubBounds(gid);

            if (numsub > 0)

            {

                bool anyhits = false;

                for (int j = 0; j < numsub; ++j)

                {

                    const BBox &sbb = gc.getSubBoundingBBox(gid, j);

                    const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, j);

                    switch (i) {

                        case 0 :    // x

                            vmin = max(max(sbb.xi-tbb.xa+sx, ssb.di-tsb.da+sd+ty), ssb.si-tsb.sa+ss-ty);

                            vmax = min(min(sbb.xa-tbb.xi+sx, ssb.da-tsb.di+sd+ty), ssb.sa-tsb.si+ss-ty);

                            omin = sbb.yi + sy;

                            omax = sbb.ya + sy;

                            break;

                        case 1 :    // y

                            vmin = max(max(sbb.yi-tbb.ya+sy, tsb.di-ssb.da-sd+tx), ssb.si-tsb.sa+ss-tx);

                            vmax = min(min(sbb.ya-tbb.yi+sy, tsb.da-ssb.di-sd+tx), ssb.sa-tsb.si+ss-tx);

                            omin = sbb.xi + sx;

                            omax = sbb.xa + sx;

                            break;

                        case 2 :    // sum

                            vmin = max(max(ssb.si-tsb.sa+ss, 2*(sbb.yi-tbb.ya+sy)+td), 2*(sbb.xi-tbb.xa+sx)-td);

                            vmax = min(min(ssb.sa-tsb.si+ss, 2*(sbb.ya-tbb.yi+sy)+td), 2*(sbb.xa-tbb.xi+sx)-td);

                            omin = ssb.di + sd;

                            omax = ssb.da + sd;

                            break;

                        case 3 :    // diff

                            vmin = max(max(ssb.di-tsb.da+sd, 2*(sbb.xi-tbb.xa+sx)-ts), -2*(sbb.ya-tbb.yi+sy)+ts);

                            vmax = min(min(ssb.da-tsb.di+sd, 2*(sbb.xa-tbb.xi+sx)-ts), -2*(sbb.yi-tbb.ya+sy)+ts);

                            omin = ssb.si + ss;

                            omax = ssb.sa + ss;

                            break;

                    }

                    if (vmax < cmin - lmargin || vmin > cmax + lmargin || omax < otmin - lmargin || omin > otmax + lmargin)

                        continue;

#if !defined GRAPHITE2_NTRACING

                    if (dbgout)

                        dbgout->setenv(1, reinterpret_cast<void *>(j));

#endif

                    if (omin > otmax)

                        _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,

                                                sqr(lmargin - omin + otmax) * _marginWt, false);

                    else if (omax < otmin)

                        _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,

                                                sqr(lmargin - otmin + omax) * _marginWt, false);

                    else

                        _ranges[i].exclude_with_margins(vmin, vmax, i);

                    anyhits = true;

                }

                if (anyhits)

                    isCol = true;

            }

            else // no sub-boxes

            {

#if !defined GRAPHITE2_NTRACING

                    if (dbgout)

                        dbgout->setenv(1, reinterpret_cast<void *>(-1));

#endif

                isCol = true;

                if (omin > otmax)

                    _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,

                                            sqr(lmargin - omin + otmax) * _marginWt, false);

                else if (omax < otmin)

                    _ranges[i].weightedAxis(i, vmin - lmargin, vmax + lmargin, 0, 0, 0, 0, 0,

                                            sqr(lmargin - otmin + omax) * _marginWt, false);

                else

                    _ranges[i].exclude_with_margins(vmin, vmax, i);

            }

        }

    }

    bool res = true;

    if (cslot->exclGlyph() > 0 && gc.check(cslot->exclGlyph()) && !isExclusion)

    {

        // Set up the bogus slot representing the exclusion glyph.

        Slot *exclSlot = seg->newSlot();

        if (!exclSlot)

            return res;

        exclSlot->setGlyph(seg, cslot->exclGlyph());

        Position exclOrigin(slot->origin() + cslot->exclOffset());

        exclSlot->origin(exclOrigin);

        SlotCollision exclInfo(seg, exclSlot);

        res &= mergeSlot(seg, exclSlot, &exclInfo, currShift, isAfter, sameCluster, isCol, true, dbgout );

        seg->freeSlot(exclSlot);

    }

    hasCol |= isCol;

    return res;

}   // end of ShiftCollider::mergeSlot

// Figure out where to move the target glyph to, and return the amount to shift by.

Position ShiftCollider::resolve(GR_MAYBE_UNUSED Segment *seg, bool &isCol, GR_MAYBE_UNUSED json * const dbgout)

{

    float tbase;

    float totalCost = (float)(std::numeric_limits<float>::max() / 2);

    Position resultPos = Position(0, 0);

#if !defined GRAPHITE2_NTRACING

  int bestAxis = -1;

    if (dbgout)

    {

    outputJsonDbgStartSlot(dbgout, seg);

        *dbgout << "vectors" << json::array;

    }

#endif

    isCol = true;

    for (int i = 0; i < 4; ++i)

    {

        float bestCost = -1;

        float bestPos;

        // Calculate the margin depending on whether we are moving diagonally or not:

        switch (i) {

            case 0 :  // x direction

                tbase = _currOffset.x;

                break;

            case 1 :  // y direction

                tbase = _currOffset.y;

                break;

            case 2 :  // sum (negatively-sloped diagonals)

                tbase = _currOffset.x + _currOffset.y;

                break;

            case 3 :  // diff (positively-sloped diagonals)

                tbase = _currOffset.x - _currOffset.y;

                break;

        }

        Position testp;

        bestPos = _ranges[i].closest(0, bestCost) - tbase;     // Get the best relative position

#if !defined GRAPHITE2_NTRACING

        if (dbgout)

            outputJsonDbgOneVector(dbgout, seg, i, tbase, bestCost, bestPos) ;

#endif

        if (bestCost >= 0.0f)

        {

            isCol = false;

            switch (i) {

                case 0 : testp = Position(bestPos, _currShift.y); break;

                case 1 : testp = Position(_currShift.x, bestPos); break;

                case 2 : testp = Position(0.5f * (_currShift.x - _currShift.y + bestPos), 0.5f * (_currShift.y - _currShift.x + bestPos)); break;

                case 3 : testp = Position(0.5f * (_currShift.x + _currShift.y + bestPos), 0.5f * (_currShift.x + _currShift.y - bestPos)); break;

            }

            if (bestCost < totalCost - 0.01f)

            {

                totalCost = bestCost;

                resultPos = testp;

#if !defined GRAPHITE2_NTRACING

                bestAxis = i;

#endif

            }

        }

    }  // end of loop over 4 directions

#if !defined GRAPHITE2_NTRACING

    if (dbgout)

        outputJsonDbgEndSlot(dbgout, resultPos, bestAxis, isCol);

#endif

    return resultPos;

}   // end of ShiftCollider::resolve

#if !defined GRAPHITE2_NTRACING

void ShiftCollider::outputJsonDbg(json * const dbgout, Segment *seg, int axis)

{

    int axisMax = axis;

    if (axis < 0) // output all axes

    {

        *dbgout << "gid" << _target->gid()

            << "limit" << _limit

            << "target" << json::object

                << "origin" << _target->origin()

                << "margin" << _margin

                << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())

                << "slantbox" << seg->getFace()->glyphs().slant(_target->gid())

                << json::close; // target object

        *dbgout << "ranges" << json::array;

        axis = 0;

        axisMax = 3;

    }

    for (int iAxis = axis; iAxis <= axisMax; ++iAxis)

    {

        *dbgout << json::flat << json::array << _ranges[iAxis].position();

        for (Zones::const_iterator s = _ranges[iAxis].begin(), e = _ranges[iAxis].end(); s != e; ++s)

            *dbgout << json::flat << json::array

                        << Position(s->x, s->xm) << s->sm << s->smx << s->c

                    << json::close;

        *dbgout << json::close;

    }

    if (axis < axisMax) // looped through the _ranges array for all axes

        *dbgout << json::close; // ranges array

}

void ShiftCollider::outputJsonDbgStartSlot(json * const dbgout, Segment *seg)

{

        *dbgout << json::object // slot - not closed till the end of the caller method

                << "slot" << objectid(dslot(seg, _target))

        << "gid" << _target->gid()

                << "limit" << _limit

                << "target" << json::object

                    << "origin" << _origin

                    << "currShift" << _currShift

                    << "currOffset" << seg->collisionInfo(_target)->offset()

                    << "bbox" << seg->theGlyphBBoxTemporary(_target->gid())

                    << "slantBox" << seg->getFace()->glyphs().slant(_target->gid())

                    << "fix" << "shift";

        *dbgout     << json::close; // target object

}

void ShiftCollider::outputJsonDbgEndSlot(GR_MAYBE_UNUSED json * const dbgout,

   Position resultPos, int bestAxis, bool isCol)

{

    *dbgout << json::close // vectors array

    << "result" << resultPos

  //<< "scraping" << _scraping[bestAxis]

  << "bestAxis" << bestAxis

    << "stillBad" << isCol

    << json::close; // slot object

}

void ShiftCollider::outputJsonDbgOneVector(json * const dbgout, Segment *seg, int axis,

  float tleft, float bestCost, float bestVal)

{

  const char * label;

  switch (axis)

  {

    case 0: label = "x";      break;

    case 1: label = "y";      break;

    case 2: label = "sum (NE-SW)";  break;

    case 3: label = "diff (NW-SE)"; break;

    default: label = "???";     break;

  }

  *dbgout << json::object // vector

    << "direction" << label

    << "targetMin" << tleft;

  outputJsonDbgRemovals(dbgout, axis, seg);

    *dbgout << "ranges";

    outputJsonDbg(dbgout, seg, axis);

    *dbgout << "bestCost" << bestCost

        << "bestVal" << bestVal + tleft

        << json::close; // vectors object

}

void ShiftCollider::outputJsonDbgRemovals(json * const dbgout, int axis, Segment *seg)

{

    *dbgout << "removals" << json::array;

    _ranges[axis].jsonDbgOut(seg);

    *dbgout << json::close; // removals array

}

#endif // !defined GRAPHITE2_NTRACING

////    KERN-COLLIDER    ////

inline

static float localmax (float al, float au, float bl, float bu, float x)

{

    if (al < bl)

    { if (au < bu) return au < x ? au : x; }

    else if (au > bu) return bl < x ? bl : x;

    return x;

}

inline

static float localmin(float al, float au, float bl, float bu, float x)

{

    if (bl > al)

    { if (bu > au) return bl > x ? bl : x; }

    else if (au > bu) return al > x ? al : x;

    return x;

}

// Return the given edge of the glyph at height y, taking any slant box into account.

static float get_edge(Segment *seg, const Slot *s, const Position &shift, float y, float width, float margin, bool isRight)

{

    const GlyphCache &gc = seg->getFace()->glyphs();

    unsigned short gid = s->gid();

    float sx = s->origin().x + shift.x;

    float sy = s->origin().y + shift.y;

    uint8 numsub = gc.numSubBounds(gid);

    float res = isRight ? (float)-1e38 : (float)1e38;

    if (numsub > 0)

    {

        for (int i = 0; i < numsub; ++i)

        {

            const BBox &sbb = gc.getSubBoundingBBox(gid, i);

            const SlantBox &ssb = gc.getSubBoundingSlantBox(gid, i);

            if (sy + sbb.yi - margin > y + width / 2 || sy + sbb.ya + margin < y - width / 2)

                continue;

            if (isRight)

            {

                float x = sx + sbb.xa + margin;

                if (x > res)

                {

                    float td = sx - sy + ssb.da + margin + y;

                    float ts = sx + sy + ssb.sa + margin - y;

                    x = localmax(td - width / 2, td + width / 2,  ts - width / 2, ts + width / 2, x);

                    if (x > res)

                        res = x;

                }

            }

            else

            {

                float x = sx + sbb.xi - margin;

                if (x < res)

                {

                    float td = sx - sy + ssb.di - margin + y;

                    float ts = sx + sy + ssb.si - margin - y;

                    x = localmin(td - width / 2, td + width / 2, ts - width / 2, ts + width / 2, x);

                    if (x < res)

                        res = x;

                }

            }

        }

    }

    else

    {

        const BBox &bb = gc.getBoundingBBox(gid);

        const SlantBox &sb = gc.getBoundingSlantBox(gid);

        if (sy + bb.yi - margin > y + width / 2 || sy + bb.ya + margin < y - width / 2)

            return res;

        float td = sx - sy + y;

        float ts = sx + sy - y;

        if (isRight)

            res = localmax(td + sb.da - width / 2, td + sb.da + width / 2, ts + sb.sa - width / 2, ts + sb.sa + width / 2, sx + bb.xa) + margin;

        else

            res = localmin(td + sb.di - width / 2, td + sb.di + width / 2, ts + sb.si - width / 2, ts + sb.si + width / 2, sx + bb.xi) - margin;

    }

    return res;

}

bool KernCollider::initSlot(Segment *seg, Slot *aSlot, const Rect &limit, float margin,

    const Position &currShift, const Position &offsetPrev, int dir,

    float ymin, float ymax, GR_MAYBE_UNUSED json * const dbgout)

{

    const GlyphCache &gc = seg->getFace()->glyphs();

    const Slot *base = aSlot;

    // const Slot *last = aSlot;

    const Slot *s;

    int numSlices;

    while (base->attachedTo())

        base = base->attachedTo();

    if (margin < 10) margin = 10;

    _limit = limit;

    _offsetPrev = offsetPrev; // kern from a previous pass

    // Calculate the height of the glyph and how many horizontal slices to use.

    if (_maxy >= 1e37f)

    {

        _sliceWidth = margin / 1.5f;

        _maxy = ymax + margin;

        _miny = ymin - margin;

        numSlices = int((_maxy - _miny + 2) / (_sliceWidth / 1.5f) + 1.f);  // +2 helps with rounding errors

        _edges.clear();

        _edges.insert(_edges.begin(), numSlices, (dir & 1) ? 1e38f : -1e38f);

        _xbound = (dir & 1) ? (float)1e38f : (float)-1e38f;

    }

    else if (_maxy != ymax || _miny != ymin)

    {

        if (_miny != ymin)

        {

            numSlices = int((ymin - margin - _miny) / _sliceWidth - 1);

            _miny += numSlices * _sliceWidth;

            if (numSlices < 0)

                _edges.insert(_edges.begin(), -numSlices, (dir & 1) ? 1e38f : -1e38f);

            else if ((unsigned)numSlices < _edges.size())    // this shouldn't fire since we always grow the range

            {

                Vector<float>::iterator e = _edges.begin();

                while (numSlices--)

                    ++e;

                _edges.erase(_edges.begin(), e);

            }

        }

        if (_maxy != ymax)

        {

            numSlices = int((ymax + margin - _miny) / _sliceWidth + 1);

            _maxy = numSlices * _sliceWidth + _miny;

            if (numSlices > (int)_edges.size())

                _edges.insert(_edges.end(), numSlices - _edges.size(), (dir & 1) ? 1e38f : -1e38f);

            else if (numSlices < (int)_edges.size())   // this shouldn't fire since we always grow the range

            {

                while ((int)_edges.size() > numSlices)

                    _edges.pop_back();

            }

        }

        goto done;

    }

    numSlices = int(_edges.size());

#if !defined GRAPHITE2_NTRACING

    // Debugging

    _seg = seg;

    _slotNear.clear();