// SPDX-License-Identifier: MIT OR MPL-2.0 OR LGPL-2.1-or-later OR GPL-2.0-or-later

// Copyright 2010, SIL International, All rights reserved.

#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();

    _slotNear.insert(_slotNear.begin(), numSlices, NULL);

    _nearEdges.clear();

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

#endif

    // Determine the trailing edge of each slice (ie, left edge for a RTL glyph).

    for (s = base; s; s = s->nextInCluster(s))

    {

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

        if (!gc.check(s->gid()))

            return false;

        const BBox &bs = gc.getBoundingBBox(s->gid());

        float x = s->origin().x + c->shift().x + ((dir & 1) ? bs.xi : bs.xa);

        // Loop over slices.

        // Note smin might not be zero if glyph s is not at the bottom of the cluster; similarly for smax.

        float toffset = c->shift().y - _miny + 1 + s->origin().y;

        int smin = max(0, int((bs.yi + toffset) / _sliceWidth));

        int smax = min(numSlices - 1, int((bs.ya + toffset) / _sliceWidth + 1));