Intervals.cpp (8632B)
1 /* GRAPHITE2 LICENSING 2 3 Copyright 2010, SIL International 4 All rights reserved. 5 6 This library is free software; you can redistribute it and/or modify 7 it under the terms of the GNU Lesser General Public License as published 8 by the Free Software Foundation; either version 2.1 of License, or 9 (at your option) any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 Lesser General Public License for more details. 15 16 You should also have received a copy of the GNU Lesser General Public 17 License along with this library in the file named "LICENSE". 18 If not, write to the Free Software Foundation, 51 Franklin Street, 19 Suite 500, Boston, MA 02110-1335, USA or visit their web page on the 20 internet at http://www.fsf.org/licenses/lgpl.html. 21 22 Alternatively, the contents of this file may be used under the terms of the 23 Mozilla Public License (http://mozilla.org/MPL) or the GNU General Public 24 License, as published by the Free Software Foundation, either version 2 25 of the License or (at your option) any later version. 26 */ 27 #include <algorithm> 28 #include <cmath> 29 #include <limits> 30 31 #include "inc/Intervals.h" 32 #include "inc/Segment.h" 33 #include "inc/Slot.h" 34 #include "inc/debug.h" 35 #include "inc/bits.h" 36 37 using namespace graphite2; 38 39 #include <cmath> 40 41 inline 42 Zones::Exclusion Zones::Exclusion::split_at(float p) { 43 Exclusion r(*this); 44 r.xm = x = p; 45 return r; 46 } 47 48 inline 49 void Zones::Exclusion::left_trim(float p) { 50 x = p; 51 } 52 53 inline 54 Zones::Exclusion & Zones::Exclusion::operator += (Exclusion const & rhs) { 55 c += rhs.c; sm += rhs.sm; smx += rhs.smx; open = false; 56 return *this; 57 } 58 59 inline 60 uint8 Zones::Exclusion::outcode(float val) const { 61 float p = val; 62 //float d = std::numeric_limits<float>::epsilon(); 63 float d = 0.; 64 return ((p - xm >= d) << 1) | (x - p > d); 65 } 66 67 void Zones::exclude_with_margins(float xmin, float xmax, int axis) { 68 remove(xmin, xmax); 69 weightedAxis(axis, xmin-_margin_len, xmin, 0, 0, _margin_weight, xmin-_margin_len, 0, 0, false); 70 weightedAxis(axis, xmax, xmax+_margin_len, 0, 0, _margin_weight, xmax+_margin_len, 0, 0, false); 71 } 72 73 namespace 74 { 75 76 inline 77 bool separated(float a, float b) { 78 return a != b; 79 //int exp; 80 //float res = frexpf(fabs(a - b), &exp); 81 //return (*(unsigned int *)(&res) > 4); 82 //return std::fabs(a-b) > std::numeric_limits<float>::epsilon(); // std::epsilon may not work. but 0.5 fails exising 64 bit tests 83 //return std::fabs(a-b) > 0.5f; 84 } 85 86 } 87 88 void Zones::insert(Exclusion e) 89 { 90 #if !defined GRAPHITE2_NTRACING 91 addDebug(&e); 92 #endif 93 e.x = max(e.x, _pos); 94 e.xm = min(e.xm, _posm); 95 if (e.x >= e.xm) return; 96 97 for (iterator i = _exclusions.begin(), ie = _exclusions.end(); i != ie && e.x < e.xm; ++i) 98 { 99 const uint8 oca = e.outcode(i->x), 100 ocb = e.outcode(i->xm); 101 if ((oca & ocb) != 0) continue; 102 103 switch (oca ^ ocb) // What kind of overlap? 104 { 105 case 0: // e completely covers i 106 // split e at i.x into e1,e2 107 // split e2 at i.mx into e2,e3 108 // drop e1 ,i+e2, e=e3 109 *i += e; 110 e.left_trim(i->xm); 111 break; 112 case 1: // e overlaps on the rhs of i 113 // split i at e->x into i1,i2 114 // split e at i.mx into e1,e2 115 // trim i1, insert i2+e1, e=e2 116 if (!separated(i->xm, e.x)) break; 117 if (separated(i->x,e.x)) { i = _exclusions.insert(i,i->split_at(e.x)); ++i; } 118 *i += e; 119 e.left_trim(i->xm); 120 break; 121 case 2: // e overlaps on the lhs of i 122 // split e at i->x into e1,e2 123 // split i at e.mx into i1,i2 124 // drop e1, insert e2+i1, trim i2 125 if (!separated(e.xm, i->x)) return; 126 if (separated(e.xm, i->xm)) i = _exclusions.insert(i,i->split_at(e.xm)); 127 *i += e; 128 return; 129 case 3: // i completely covers e 130 // split i at e.x into i1,i2 131 // split i2 at e.mx into i2,i3 132 // insert i1, insert e+i2 133 if (separated(e.xm, i->xm)) i = _exclusions.insert(i,i->split_at(e.xm)); 134 i = _exclusions.insert(i, i->split_at(e.x)); 135 *++i += e; 136 return; 137 } 138 139 ie = _exclusions.end(); 140 } 141 } 142 143 144 void Zones::remove(float x, float xm) 145 { 146 #if !defined GRAPHITE2_NTRACING 147 removeDebug(x, xm); 148 #endif 149 x = max(x, _pos); 150 xm = min(xm, _posm); 151 if (x >= xm) return; 152 153 for (iterator i = _exclusions.begin(), ie = _exclusions.end(); i != ie; ++i) 154 { 155 const uint8 oca = i->outcode(x), 156 ocb = i->outcode(xm); 157 if ((oca & ocb) != 0) continue; 158 159 switch (oca ^ ocb) // What kind of overlap? 160 { 161 case 0: // i completely covers e 162 if (separated(i->x, x)) { i = _exclusions.insert(i,i->split_at(x)); ++i; } 163 GR_FALLTHROUGH; 164 // no break 165 case 1: // i overlaps on the rhs of e 166 i->left_trim(xm); 167 return; 168 case 2: // i overlaps on the lhs of e 169 i->xm = x; 170 if (separated(i->x, i->xm)) break; 171 GR_FALLTHROUGH; 172 // no break 173 case 3: // e completely covers i 174 i = _exclusions.erase(i); 175 --i; 176 break; 177 } 178 179 ie = _exclusions.end(); 180 } 181 } 182 183 184 Zones::const_iterator Zones::find_exclusion_under(float x) const 185 { 186 size_t l = 0, h = _exclusions.size(); 187 188 while (l < h) 189 { 190 size_t const p = (l+h) >> 1; 191 switch (_exclusions[p].outcode(x)) 192 { 193 case 0 : return _exclusions.begin()+p; 194 case 1 : h = p; break; 195 case 2 : 196 case 3 : l = p+1; break; 197 } 198 } 199 200 return _exclusions.begin()+l; 201 } 202 203 204 float Zones::closest(float origin, float & cost) const 205 { 206 float best_c = std::numeric_limits<float>::max(), 207 best_x = 0; 208 209 const const_iterator start = find_exclusion_under(origin); 210 211 // Forward scan looking for lowest cost 212 for (const_iterator i = start, ie = _exclusions.end(); i != ie; ++i) 213 if (i->track_cost(best_c, best_x, origin)) break; 214 215 // Backward scan looking for lowest cost 216 // We start from the exclusion to the immediate left of start since we've 217 // already tested start with the right most scan above. 218 for (const_iterator i = start-1, ie = _exclusions.begin()-1; i != ie; --i) 219 if (i->track_cost(best_c, best_x, origin)) break; 220 221 cost = (best_c == std::numeric_limits<float>::max() ? -1 : best_c); 222 return best_x; 223 } 224 225 226 // Cost and test position functions 227 228 bool Zones::Exclusion::track_cost(float & best_cost, float & best_pos, float origin) const { 229 const float p = test_position(origin), 230 localc = cost(p - origin); 231 if (open && localc > best_cost) return true; 232 233 if (localc < best_cost) 234 { 235 best_cost = localc; 236 best_pos = p; 237 } 238 return false; 239 } 240 241 inline 242 float Zones::Exclusion::cost(float p) const { 243 return (sm * p - 2 * smx) * p + c; 244 } 245 246 247 float Zones::Exclusion::test_position(float origin) const { 248 if (sm < 0) 249 { 250 // sigh, test both ends and perhaps the middle too! 251 float res = x; 252 float cl = cost(x); 253 if (x < origin && xm > origin) 254 { 255 float co = cost(origin); 256 if (co < cl) 257 { 258 cl = co; 259 res = origin; 260 } 261 } 262 float cr = cost(xm); 263 return cl > cr ? xm : res; 264 } 265 else 266 { 267 float zerox = smx / sm + origin; 268 if (zerox < x) return x; 269 else if (zerox > xm) return xm; 270 else return zerox; 271 } 272 } 273 274 275 #if !defined GRAPHITE2_NTRACING 276 277 void Zones::jsonDbgOut(Segment *seg) const { 278 279 if (_dbg) 280 { 281 for (Zones::idebugs s = dbgs_begin(), e = dbgs_end(); s != e; ++s) 282 { 283 *_dbg << json::flat << json::array 284 << objectid(dslot(seg, (Slot *)(s->_env[0]))) 285 << reinterpret_cast<ptrdiff_t>(s->_env[1]); 286 if (s->_isdel) 287 *_dbg << "remove" << Position(s->_excl.x, s->_excl.xm); 288 else 289 *_dbg << "exclude" << json::flat << json::array 290 << s->_excl.x << s->_excl.xm 291 << s->_excl.sm << s->_excl.smx << s->_excl.c 292 << json::close; 293 *_dbg << json::close; 294 } 295 } 296 } 297 298 #endif