summaryrefslogtreecommitdiff
path: root/Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp')
-rw-r--r--Build/source/libs/graphite2/graphite2-src/src/Intervals.cpp298
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