Source code
Revision control
Copy as Markdown
Other Tools
/* 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
Alternatively, the contents of this file may be used under the terms of the
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