/*  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 <cmath>

#include <limits>

#include "inc/Intervals.h"

#include "inc/Segment.h"

#include "inc/Slot.h"

#include "inc/debug.h"

#include "inc/bits.h"

using namespace graphite2;

#include <cmath>

inline

Zones::Exclusion  Zones::Exclusion::split_at(float p) {

    Exclusion r(*this);

    r.xm = x = p;

    return r;

}

inline

void Zones::Exclusion::left_trim(float p) {

    x = p;

}

inline

Zones::Exclusion & Zones::Exclusion::operator += (Exclusion const & rhs) {

    c += rhs.c; sm += rhs.sm; smx += rhs.smx; open = false;

    return *this;

}

inline

uint8 Zones::Exclusion::outcode(float val) const {

    float p = val;

    //float d = std::numeric_limits<float>::epsilon();

    float d = 0.;

    return ((p - xm >= d) << 1) | (x - p > d);

}

void Zones::exclude_with_margins(float xmin, float xmax, int axis) {

    remove(xmin, xmax);

    weightedAxis(axis, xmin-_margin_len, xmin, 0, 0, _margin_weight, xmin-_margin_len, 0, 0, false);

    weightedAxis(axis, xmax, xmax+_margin_len, 0, 0, _margin_weight, xmax+_margin_len, 0, 0, false);

}

namespace

{

inline

bool separated(float a, float b) {

    return a != b;

    //int exp;

    //float res = frexpf(fabs(a - b), &exp);

    //return (*(unsigned int *)(&res) > 4);

    //return std::fabs(a-b) > std::numeric_limits<float>::epsilon(); // std::epsilon may not work. but 0.5 fails exising 64 bit tests

    //return std::fabs(a-b) > 0.5f;

}

}

void Zones::insert(Exclusion e)

{

#if !defined GRAPHITE2_NTRACING

    addDebug(&e);

#endif

    e.x = max(e.x, _pos);

    e.xm = min(e.xm, _posm);

    if (e.x >= e.xm) return;

    for (iterator i = _exclusions.begin(), ie = _exclusions.end(); i != ie && e.x < e.xm; ++i)

    {

        const uint8 oca = e.outcode(i->x),

                    ocb = e.outcode(i->xm);

        if ((oca & ocb) != 0) continue;

        switch (oca ^ ocb)  // What kind of overlap?

        {

        case 0:     // e completely covers i

            // split e at i.x into e1,e2

            // split e2 at i.mx into e2,e3

            // drop e1 ,i+e2, e=e3

            *i += e;

            e.left_trim(i->xm);

            break;

        case 1:     // e overlaps on the rhs of i

            // split i at e->x into i1,i2

            // split e at i.mx into e1,e2

            // trim i1, insert i2+e1, e=e2

            if (!separated(i->xm, e.x)) break;

            if (separated(i->x,e.x))   { i = _exclusions.insert(i,i->split_at(e.x)); ++i; }

            *i += e;

            e.left_trim(i->xm);

            break;

        case 2:     // e overlaps on the lhs of i

            // split e at i->x into e1,e2

            // split i at e.mx into i1,i2

            // drop e1, insert e2+i1, trim i2

            if (!separated(e.xm, i->x)) return;

            if (separated(e.xm, i->xm)) i = _exclusions.insert(i,i->split_at(e.xm));

            *i += e;

            return;

        case 3:     // i completely covers e

            // split i at e.x into i1,i2

            // split i2 at e.mx into i2,i3

            // insert i1, insert e+i2

            if (separated(e.xm, i->xm)) i = _exclusions.insert(i,i->split_at(e.xm));

            i = _exclusions.insert(i, i->split_at(e.x));

            *++i += e;

            return;

        }

        ie = _exclusions.end();

    }

}

void Zones::remove(float x, float xm)

{

#if !defined GRAPHITE2_NTRACING

    removeDebug(x, xm);

#endif

    x = max(x, _pos);

    xm = min(xm, _posm);

    if (x >= xm) return;

    for (iterator i = _exclusions.begin(), ie = _exclusions.end(); i != ie; ++i)

    {

        const uint8 oca = i->outcode(x),

                    ocb = i->outcode(xm);

        if ((oca & ocb) != 0)   continue;

        switch (oca ^ ocb)  // What kind of overlap?

        {

        case 0:     // i completely covers e

            if (separated(i->x, x))  { i = _exclusions.insert(i,i->split_at(x)); ++i; }

            GR_FALLTHROUGH;

            // no break

        case 1:     // i overlaps on the rhs of e

            i->left_trim(xm);

            return;

        case 2:     // i overlaps on the lhs of e

            i->xm = x;

            if (separated(i->x, i->xm)) break;

            GR_FALLTHROUGH;

            // no break

        case 3:     // e completely covers i

            i = _exclusions.erase(i);

            --i;

            break;

        }

        ie = _exclusions.end();

    }

}

Zones::const_iterator Zones::find_exclusion_under(float x) const

{

    size_t l = 0, h = _exclusions.size();

    while (l < h)

    {

        size_t const p = (l+h) >> 1;

        switch (_exclusions[p].outcode(x))

        {

        case 0 : return _exclusions.begin()+p;

        case 1 : h = p; break;

        case 2 :

        case 3 : l = p+1; break;

        }

    }

    return _exclusions.begin()+l;

}

float Zones::closest(float origin, float & cost) const

{

    float best_c = std::numeric_limits<float>::max(),

          best_x = 0;

    const const_iterator start = find_exclusion_under(origin);

    // Forward scan looking for lowest cost

    for (const_iterator i = start, ie = _exclusions.end(); i != ie; ++i)

        if (i->track_cost(best_c, best_x, origin)) break;

    // Backward scan looking for lowest cost

    //  We start from the exclusion to the immediate left of start since we've

    //  already tested start with the right most scan above.

    for (const_iterator i = start-1, ie = _exclusions.begin()-1; i != ie; --i)

        if (i->track_cost(best_c, best_x, origin)) break;

    cost = (best_c == std::numeric_limits<float>::max() ? -1 : best_c);

    return best_x;

}

// Cost and test position functions

bool Zones::Exclusion::track_cost(float & best_cost, float & best_pos, float origin) const {

    const float p = test_position(origin),

                localc = cost(p - origin);

    if (open && localc > best_cost) return true;

    if (localc < best_cost)

    {

        best_cost = localc;

        best_pos = p;

    }

    return false;

}

inline

float Zones::Exclusion::cost(float p) const {

    return (sm * p - 2 * smx) * p + c;

}

float Zones::Exclusion::test_position(float origin) const {

    if (sm < 0)

    {

        // sigh, test both ends and perhaps the middle too!

        float res = x;

        float cl = cost(x);

        if (x < origin && xm > origin)

        {

            float co = cost(origin);

            if (co < cl)

            {

                cl = co;

                res = origin;

            }

        }

        float cr = cost(xm);

        return cl > cr ? xm : res;

    }

    else

    {

        float zerox = smx / sm + origin;

        if (zerox < x) return x;

        else if (zerox > xm) return xm;

        else return zerox;

    }

}

#if !defined GRAPHITE2_NTRACING

void Zones::jsonDbgOut(Segment *seg) const {

    if (_dbg)

    {

        for (Zones::idebugs s = dbgs_begin(), e = dbgs_end(); s != e; ++s)

        {

            *_dbg << json::flat << json::array

                << objectid(dslot(seg, (Slot *)(s->_env[0])))

                << reinterpret_cast<ptrdiff_t>(s->_env[1]);

            if (s->_isdel)

                *_dbg << "remove" << Position(s->_excl.x, s->_excl.xm);

            else

                *_dbg << "exclude" << json::flat << json::array

                    << s->_excl.x << s->_excl.xm

                    << s->_excl.sm << s->_excl.smx << s->_excl.c

                    << json::close;

            *_dbg << json::close;

        }

    }

}

#endif