1 /*******************************************************************************
\r
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
\r
3 * in Industry THTH ry.
\r
4 * All rights reserved. This program and the accompanying materials
\r
5 * are made available under the terms of the Eclipse Public License v1.0
\r
6 * which accompanies this distribution, and is available at
\r
7 * http://www.eclipse.org/legal/epl-v10.html
\r
10 * VTT Technical Research Centre of Finland - initial API and implementation
\r
11 *******************************************************************************/
\r
12 package org.simantics.utils.datastructures;
\r
14 import java.util.ArrayList;
\r
15 import java.util.Arrays;
\r
16 import java.util.Collection;
\r
17 import java.util.Iterator;
\r
18 import java.util.List;
\r
21 * SegmentSet is a set of value segments.
\r
23 * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
\r
25 public class SegmentSet implements Iterable<Segment> {
\r
27 public static final SegmentSet NONE = new SegmentSet();
\r
29 /** incrementally sorted and non-intersecting, non-parallel array of segments */
\r
30 List<Segment> list = new ArrayList<Segment>();
\r
33 * Create new segment set from double value pairs
\r
35 * @param times even length array
\r
38 public static SegmentSet of(double...times)
\r
40 if (times==null || ((times.length & 1)==1))
\r
41 throw new IllegalArgumentException();
\r
42 SegmentSet result = new SegmentSet();
\r
43 for (int i=0; i<times.length/2; i++)
\r
44 result.add( Segment.of(times[i*2], times[i*2+1]) );
\r
49 * Create new set of ranges.
\r
51 public SegmentSet() {
\r
55 * Create new set of ranges.
\r
57 public SegmentSet(SegmentSet copyFrom) {
\r
58 this.list.addAll(copyFrom.list);
\r
62 * Create new set of segments.
\r
64 public SegmentSet(Collection<Segment> list) {
\r
65 for (Segment r : list)
\r
70 * Create new set of segments.
\r
72 * @param segments initial segments
\r
74 public SegmentSet(Segment...segments) {
\r
75 for (Segment r : Segment.union(segments))
\r
79 public boolean add(Segment...segments) {
\r
80 boolean result = false;
\r
81 for (Segment r : segments)
\r
87 * Add a segment set to this segment set
\r
90 * @return true if the content changed
\r
92 public boolean add(SegmentSet set) {
\r
93 boolean result = false;
\r
94 for (Segment r : set.list)
\r
100 * Get index of the segment that contains the given value.
\r
101 * If value is not included in the set, return as negative value the index
\r
102 * of the range the value is prior to.
\r
107 * @return range index
\r
109 int indexOf(double value) {
\r
110 for (int i=0; i<list.size(); i++) {
\r
111 Segment r = list.get(i);
\r
112 if (r.contains(value)) return i;
\r
113 if (r.getStart()>=value) return -i -1;
\r
115 return -list.size()-1;
\r
119 * Get the segment the value is in.
\r
122 * @return segment or null
\r
124 public Segment getSegmentOf(double value)
\r
126 int index = indexOf(value);
\r
127 if (index<0) return null;
\r
128 return list.get(index);
\r
132 * Add segment range
\r
135 * @return true if the content changed
\r
137 public boolean add(Segment range) {
\r
138 int startIndex = indexOf(range.getStart());
\r
139 int endIndex = indexOf(range.getEnd());
\r
141 // The whole segment is already included in the set
\r
142 if (startIndex>=0 && startIndex==endIndex) return false;
\r
144 // Doesn't intersect, add as is
\r
145 if (startIndex<0 && startIndex==endIndex) {
\r
146 list.add(-startIndex-1, range);
\r
150 // Intersects partially
\r
151 double start = range.getStart();
\r
152 double end = range.getEnd();
\r
154 // Extend the segment following the start position
\r
155 if (startIndex<0) {
\r
156 startIndex = -startIndex-1;
\r
158 start = list.get(startIndex).getStart();
\r
161 // Extends the segment preceding the end position
\r
163 endIndex = -endIndex-2;
\r
165 end = list.get(endIndex).getEnd();
\r
168 int segmentsToRemove = endIndex - startIndex;
\r
169 for (int j=0; j<segmentsToRemove; j++)
\r
170 list.remove(startIndex);
\r
172 if (start!=range.getStart() || end!=range.getEnd())
\r
173 range = new Segment(start, end);
\r
175 list.set( startIndex, range );
\r
179 public boolean remove(Segment...ranges) {
\r
180 boolean result = false;
\r
181 for (Segment r : ranges)
\r
182 result |= remove(r);
\r
186 public boolean remove(SegmentSet set) {
\r
187 boolean result = false;
\r
188 for (Segment r : set.list)
\r
189 result |= remove(r);
\r
193 public boolean remove(Segment range) {
\r
194 int startIndex = indexOf(range.getStart());
\r
195 int endIndex = indexOf(range.getEnd());
\r
197 // Doesn't intersect
\r
198 if (startIndex<0 && startIndex==endIndex) return false;
\r
200 // Move start to next segment
\r
202 startIndex = -startIndex-1;
\r
204 // Move end to prev segment
\r
206 endIndex = -endIndex-2;
\r
208 // Start position is in segment. Cut segment and move to next one
\r
209 if (range.getStart()>list.get(startIndex).getStart()) {
\r
210 Segment s = list.get(startIndex);
\r
211 Segment newS = new Segment(s.getStart(), range.getStart());
\r
212 list.set(startIndex, newS);
\r
215 if (s.getEnd()>range.getEnd()) {
\r
216 newS = new Segment(range.getEnd(), s.getEnd());
\r
217 list.add(startIndex, newS);
\r
222 // End position is within segment, Cut it and move to prev one
\r
223 if (range.getEnd()<list.get(endIndex).getEnd()) {
\r
224 Segment s = list.get(endIndex);
\r
225 s = new Segment(range.getEnd(), s.getEnd());
\r
226 list.set(endIndex, s);
\r
230 // Remove start if it is cut completely
\r
231 while ( startIndex<=endIndex && range.contains( list.get(startIndex) ) ) {
\r
232 list.remove(startIndex);
\r
239 * Clips SegmentSet to given segment.
\r
242 public void clip(Segment segment) {
\r
243 remove(new Segment(-Double.MAX_VALUE,segment.getStart()));
\r
244 remove(new Segment(segment.getEnd(),Double.MAX_VALUE));
\r
248 * Tests whether s intersects
\r
250 * @param s segmentset
\r
251 * @return true if s intersects with this segment set
\r
253 public boolean intersects(SegmentSet set)
\r
255 for (Segment s : set.list)
\r
256 if (intersects(s)) return true;
\r
261 * Tests whether s intersects
\r
264 * @return true if s intersects with this segment set
\r
266 public boolean intersects(Segment s)
\r
268 for (Segment localS : list)
\r
269 if (localS.intersects(s)) return true;
\r
274 * Tests whether s is fully contained in this segment set.
\r
277 * @return true if s is fully contained in this segment set
\r
279 public boolean contains(Segment s)
\r
281 for (Segment localS : list)
\r
282 if (localS.contains(s)) return true;
\r
287 * Tests whether the a values is included in the set.
\r
292 public boolean contains(double value)
\r
294 return indexOf(value)>=0;
\r
298 * Get the min and max value
\r
300 * @return boundaries or null
\r
302 public Segment getBoundaries()
\r
304 if (list.isEmpty()) return null;
\r
305 double start = list.get(0).getStart();
\r
306 double end = list.get(list.size()-1).getEnd();
\r
307 return new Segment(start, end);
\r
312 * @return lower bound or null
\r
314 public Double getLowerBound() {
\r
315 if (list.isEmpty()) return null;
\r
316 return list.get(0).getStart();
\r
321 * @return upper bound or null
\r
323 public Double getUpperBound() {
\r
324 if (list.isEmpty()) return null;
\r
325 return list.get(list.size()-1).getEnd();
\r
329 * Return incrementally sorted and non-intersecting array of segments.
\r
331 * Note this method returns an internal state, it most not be modified.
\r
335 public Segment[] toArray() {
\r
336 return list.toArray( new Segment[list.size()] );
\r
340 * Returns an iterator over the elements in this list in proper sequence.
\r
342 * @return an iterator over the elements in this list in proper sequence.
\r
344 public Iterator<Segment> iterator() {
\r
345 return list.iterator();
\r
349 public String toString() {
\r
350 return Arrays.toString( toArray() );
\r
353 public SegmentSet clone() {
\r
354 return new SegmentSet(this);
\r