LEFT | RIGHT |
(no file at all) | |
1 /* | 1 /* |
2 This file is part of LilyPond, the GNU music typesetter. | 2 This file is part of LilyPond, the GNU music typesetter. |
3 | 3 |
4 Copyright (C) 2004--2012 Han-Wen Nienhuys <hanwen@xs4all.nl> | 4 Copyright (C) 2004--2012 Han-Wen Nienhuys <hanwen@xs4all.nl> |
5 | 5 |
6 LilyPond is free software: you can redistribute it and/or modify | 6 LilyPond is free software: you can redistribute it and/or modify |
7 it under the terms of the GNU General Public License as published by | 7 it under the terms of the GNU General Public License as published by |
8 the Free Software Foundation, either version 3 of the License, or | 8 the Free Software Foundation, either version 3 of the License, or |
9 (at your option) any later version. | 9 (at your option) any later version. |
10 | 10 |
11 LilyPond is distributed in the hope that it will be useful, | 11 LilyPond is distributed in the hope that it will be useful, |
12 but WITHOUT ANY WARRANTY; without even the implied warranty of | 12 but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 GNU General Public License for more details. | 14 GNU General Public License for more details. |
15 | 15 |
16 You should have received a copy of the GNU General Public License | 16 You should have received a copy of the GNU General Public License |
17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>. | 17 along with LilyPond. If not, see <http://www.gnu.org/licenses/>. |
18 */ | 18 */ |
19 | 19 |
20 #include "interval-set.hh" | 20 #include "interval-set.hh" |
21 | 21 |
22 /* | 22 /* |
23 A union of intervals in the real line. | 23 A union of intervals in the real line. |
24 | 24 |
25 Abysmal performance (quadratic) for large N, hopefully we don't have | 25 This class gives good performance for finding the union of |
26 that large N. In any case, this should probably be rewritten to use | 26 a collection of intervals (n log n) and for testing if a point |
27 a balanced tree. | 27 belongs to the union (log n). It does not give an efficient way to |
| 28 update the set (ie. by adding more intervals); to do this |
| 29 efficiently would require a self-balancing tree, and it would not |
| 30 be currently useful in lilypond anyway. |
28 */ | 31 */ |
29 | 32 |
30 Interval_set::Interval_set () | 33 Interval_set::Interval_set () |
31 { | 34 { |
32 set_full (); | |
33 } | 35 } |
34 | 36 |
35 void | 37 Interval_set |
36 Interval_set::set_full () | 38 Interval_set::interval_union (vector<Interval> ivs) |
37 { | 39 { |
38 allowed_regions_.clear (); | 40 vector_sort (ivs, Interval::left_less); |
39 Interval s; | 41 |
40 s.set_full (); | 42 Interval_set ret; |
41 allowed_regions_.push_back (s); | 43 |
| 44 if (ivs.empty ()) |
| 45 return ret; |
| 46 |
| 47 ret.intervals_.push_back (ivs.front ()); |
| 48 |
| 49 // Go over the intervals from left to right. If the current interval |
| 50 // overlaps with the last one, merge them. Otherwise, append the |
| 51 // current interval to the list. |
| 52 for (vsize i = 1; i < ivs.size (); ++i) |
| 53 { |
| 54 Interval iv = ivs[i]; |
| 55 Interval &last = ret.intervals_.back (); |
| 56 |
| 57 if (last[RIGHT] >= iv[LEFT]) |
| 58 // overlapping intervals: merge them |
| 59 last[RIGHT] = max (last[RIGHT], iv[RIGHT]); |
| 60 else if (!iv.is_empty ()) |
| 61 ret.intervals_.push_back (iv); |
| 62 } |
| 63 |
| 64 return ret; |
42 } | 65 } |
43 | 66 |
44 void | 67 // Returns an iterator pointing to the first interval whose left |
45 Interval_set::remove_interval (Interval rm) | 68 // endpoint is at least x. That interval may or may not contain x. |
| 69 vector<Interval>::const_iterator |
| 70 Interval_set::upper_bound (Real x) const |
46 { | 71 { |
47 for (vsize i = 0; i < allowed_regions_.size ();) | 72 Interval xx (x, x); |
| 73 return std::upper_bound (intervals_.begin (), intervals_.end (), xx, Interval:
:left_less); |
| 74 } |
| 75 |
| 76 Real |
| 77 Interval_set::nearest_point (Real x, Direction d) const |
| 78 { |
| 79 Real left = -infinity_f; // The closest point to the left of x. |
| 80 Real right = infinity_f; // The closest point to the right of x. |
| 81 |
| 82 vector<Interval>::const_iterator i = upper_bound (x); |
| 83 if (i != intervals_.end ()) |
| 84 right = (*i)[LEFT]; |
| 85 |
| 86 if (i != intervals_.begin ()) |
48 { | 87 { |
49 Interval s = rm; | 88 Interval left_iv = *(i - 1); |
| 89 // left_iv[LEFT] is guaranteed to be less than x. So if |
| 90 // left_iv[RIGHT] >= x then left_iv contains x, which must then |
| 91 // be the nearest point to x. |
| 92 if (left_iv[RIGHT] >= x) |
| 93 return x; |
50 | 94 |
51 s.intersect (allowed_regions_[i]); | 95 left = left_iv[RIGHT]; |
| 96 } |
52 | 97 |
53 if (!s.is_empty ()) | 98 if (d == RIGHT) |
54 { | 99 return right; |
55 Interval before = allowed_regions_[i]; | 100 if (d == LEFT) |
56 Interval after = allowed_regions_[i]; | 101 return left; |
| 102 else |
| 103 return (right - x) < (x - left) ? right : left; |
| 104 } |
57 | 105 |
58 before[RIGHT] = s[LEFT]; | 106 Interval_set |
59 after[LEFT] = s[RIGHT]; | 107 Interval_set::complement () const |
| 108 { |
| 109 Interval_set ret; |
60 | 110 |
61 if (!before.is_empty () && before.length () > 0.0) | 111 if (intervals_.empty ()) |
62 { | 112 { |
63 allowed_regions_.insert (allowed_regions_.begin () + (long)i, befo
re); | 113 ret.intervals_.push_back (Interval (-infinity_f, infinity_f)); |
64 i++; | 114 return ret; |
65 } | |
66 allowed_regions_.erase (allowed_regions_.begin () + (long)i); | |
67 if (!after.is_empty () && after.length () > 0.0) | |
68 { | |
69 allowed_regions_.insert (allowed_regions_.begin () + (long)i, afte
r); | |
70 i++; | |
71 } | |
72 } | |
73 else | |
74 i++; | |
75 } | 115 } |
| 116 |
| 117 if (intervals_[0][LEFT] > -infinity_f) |
| 118 ret.intervals_.push_back (Interval (-infinity_f, intervals_[0][LEFT])); |
| 119 |
| 120 for (vsize i = 1; i < intervals_.size (); ++i) |
| 121 ret.intervals_.push_back (Interval (intervals_[i - 1][RIGHT], intervals_[i][
LEFT])); |
| 122 |
| 123 if (intervals_.back ()[RIGHT] < infinity_f) |
| 124 ret.intervals_.push_back (Interval (intervals_.back ()[RIGHT], infinity_f)); |
| 125 |
| 126 return ret; |
76 } | 127 } |
LEFT | RIGHT |