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