diff options
Diffstat (limited to 'Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp')
-rw-r--r-- | Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp | 298 |
1 files changed, 0 insertions, 298 deletions
diff --git a/Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp b/Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp deleted file mode 100644 index 0fe99a127a8..00000000000 --- a/Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp +++ /dev/null @@ -1,298 +0,0 @@ -/* 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 |