-/*******************************************************************************\r
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
- * in Industry THTH ry.\r
- * All rights reserved. This program and the accompanying materials\r
- * are made available under the terms of the Eclipse Public License v1.0\r
- * which accompanies this distribution, and is available at\r
- * http://www.eclipse.org/legal/epl-v10.html\r
- *\r
- * Contributors:\r
- * VTT Technical Research Centre of Finland - initial API and implementation\r
- *******************************************************************************/\r
-package org.simantics.utils.datastructures;\r
-\r
-import java.util.ArrayList;\r
-import java.util.Arrays;\r
-import java.util.Collection;\r
-import java.util.Iterator;\r
-import java.util.List;\r
-\r
-/**\r
- * SegmentSet is a set of value segments.\r
- * \r
- * @author Toni Kalajainen <toni.kalajainen@vtt.fi>\r
- */\r
-public class SegmentSet implements Iterable<Segment> {\r
-\r
- public static final SegmentSet NONE = new SegmentSet();\r
- \r
- /** incrementally sorted and non-intersecting, non-parallel array of segments */\r
- List<Segment> list = new ArrayList<Segment>();\r
- \r
- /**\r
- * Create new segment set from double value pairs \r
- * \r
- * @param times even length array\r
- * @return\r
- */\r
- public static SegmentSet of(double...times)\r
- {\r
- if (times==null || ((times.length & 1)==1))\r
- throw new IllegalArgumentException();\r
- SegmentSet result = new SegmentSet();\r
- for (int i=0; i<times.length/2; i++)\r
- result.add( Segment.of(times[i*2], times[i*2+1]) );\r
- return result;\r
- }\r
- \r
- /**\r
- * Create new set of ranges.\r
- */\r
- public SegmentSet() { \r
- }\r
-\r
- /**\r
- * Create new set of ranges.\r
- */\r
- public SegmentSet(SegmentSet copyFrom) {\r
- this.list.addAll(copyFrom.list);\r
- }\r
- \r
- /**\r
- * Create new set of segments.\r
- */\r
- public SegmentSet(Collection<Segment> list) {\r
- for (Segment r : list)\r
- add(r);\r
- }\r
- \r
- /**\r
- * Create new set of segments.\r
- * \r
- * @param segments initial segments\r
- */\r
- public SegmentSet(Segment...segments) {\r
- for (Segment r : Segment.union(segments))\r
- list.add(r);\r
- }\r
- \r
- public boolean add(Segment...segments) {\r
- boolean result = false;\r
- for (Segment r : segments) \r
- result |= add(r);\r
- return result;\r
- }\r
- \r
- /**\r
- * Add a segment set to this segment set\r
- * \r
- * @param set \r
- * @return true if the content changed\r
- */\r
- public boolean add(SegmentSet set) {\r
- boolean result = false;\r
- for (Segment r : set.list)\r
- result |= add(r);\r
- return result;\r
- }\r
- \r
- /**\r
- * Get index of the segment that contains the given value.\r
- * If value is not included in the set, return as negative value the index\r
- * of the range the value is prior to.\r
- * e.g. \r
- * -1 before 0\r
- * -2 before 1\r
- * \r
- * @return range index\r
- */\r
- int indexOf(double value) {\r
- for (int i=0; i<list.size(); i++) {\r
- Segment r = list.get(i);\r
- if (r.contains(value)) return i;\r
- if (r.getStart()>=value) return -i -1;\r
- }\r
- return -list.size()-1;\r
- }\r
- \r
- /**\r
- * Get the segment the value is in.\r
- * \r
- * @param value \r
- * @return segment or null\r
- */\r
- public Segment getSegmentOf(double value)\r
- {\r
- int index = indexOf(value);\r
- if (index<0) return null;\r
- return list.get(index);\r
- }\r
- \r
- /**\r
- * Add segment range\r
- * \r
- * @param range\r
- * @return true if the content changed\r
- */\r
- public boolean add(Segment range) {\r
- int startIndex = indexOf(range.getStart());\r
- int endIndex = indexOf(range.getEnd());\r
- \r
- // The whole segment is already included in the set\r
- if (startIndex>=0 && startIndex==endIndex) return false;\r
- \r
- // Doesn't intersect, add as is\r
- if (startIndex<0 && startIndex==endIndex) {\r
- list.add(-startIndex-1, range);\r
- return true;\r
- }\r
-\r
- // Intersects partially\r
- double start = range.getStart();\r
- double end = range.getEnd();\r
-\r
- // Extend the segment following the start position \r
- if (startIndex<0) {\r
- startIndex = -startIndex-1;\r
- } else {\r
- start = list.get(startIndex).getStart();\r
- }\r
- \r
- // Extends the segment preceding the end position \r
- if (endIndex<0) {\r
- endIndex = -endIndex-2;\r
- } else {\r
- end = list.get(endIndex).getEnd();\r
- }\r
- \r
- int segmentsToRemove = endIndex - startIndex;\r
- for (int j=0; j<segmentsToRemove; j++)\r
- list.remove(startIndex);\r
- \r
- if (start!=range.getStart() || end!=range.getEnd())\r
- range = new Segment(start, end);\r
- \r
- list.set( startIndex, range ); \r
- return true;\r
- }\r
- \r
- public boolean remove(Segment...ranges) {\r
- boolean result = false;\r
- for (Segment r : ranges)\r
- result |= remove(r);\r
- return result;\r
- }\r
- \r
- public boolean remove(SegmentSet set) {\r
- boolean result = false;\r
- for (Segment r : set.list)\r
- result |= remove(r);\r
- return result;\r
- }\r
- \r
- public boolean remove(Segment range) {\r
- int startIndex = indexOf(range.getStart());\r
- int endIndex = indexOf(range.getEnd());\r
-\r
- // Doesn't intersect\r
- if (startIndex<0 && startIndex==endIndex) return false;\r
-\r
- // Move start to next segment\r
- if (startIndex<0) \r
- startIndex = -startIndex-1;\r
- \r
- // Move end to prev segment\r
- if (endIndex<0) \r
- endIndex = -endIndex-2;\r
-\r
- // Start position is in segment. Cut segment and move to next one\r
- if (range.getStart()>list.get(startIndex).getStart()) {\r
- Segment s = list.get(startIndex);\r
- Segment newS = new Segment(s.getStart(), range.getStart());\r
- list.set(startIndex, newS);\r
- startIndex++;\r
- \r
- if (s.getEnd()>range.getEnd()) {\r
- newS = new Segment(range.getEnd(), s.getEnd());\r
- list.add(startIndex, newS);\r
- startIndex++;\r
- } \r
- }\r
- \r
- // End position is within segment, Cut it and move to prev one\r
- if (range.getEnd()<list.get(endIndex).getEnd()) {\r
- Segment s = list.get(endIndex);\r
- s = new Segment(range.getEnd(), s.getEnd());\r
- list.set(endIndex, s);\r
- endIndex--;\r
- }\r
- \r
- // Remove start if it is cut completely\r
- while ( startIndex<=endIndex && range.contains( list.get(startIndex) ) ) {\r
- list.remove(startIndex);\r
- endIndex--;\r
- }\r
- return true;\r
- }\r
- \r
- /**\r
- * Clips SegmentSet to given segment.\r
- * @param segment\r
- */\r
- public void clip(Segment segment) {\r
- remove(new Segment(-Double.MAX_VALUE,segment.getStart()));\r
- remove(new Segment(segment.getEnd(),Double.MAX_VALUE));\r
- }\r
-\r
- /**\r
- * Tests whether s intersects \r
- * \r
- * @param s segmentset\r
- * @return true if s intersects with this segment set \r
- */\r
- public boolean intersects(SegmentSet set)\r
- {\r
- for (Segment s : set.list)\r
- if (intersects(s)) return true;\r
- return false;\r
- }\r
- \r
- /**\r
- * Tests whether s intersects \r
- * \r
- * @param s segment\r
- * @return true if s intersects with this segment set \r
- */\r
- public boolean intersects(Segment s)\r
- {\r
- for (Segment localS : list)\r
- if (localS.intersects(s)) return true;\r
- return false;\r
- }\r
- \r
- /**\r
- * Tests whether s is fully contained in this segment set. \r
- * \r
- * @param s segment\r
- * @return true if s is fully contained in this segment set\r
- */\r
- public boolean contains(Segment s) \r
- {\r
- for (Segment localS : list)\r
- if (localS.contains(s)) return true;\r
- return false;\r
- }\r
- \r
- /**\r
- * Tests whether the a values is included in the set.\r
- *\r
- * @param value\r
- * @return\r
- */\r
- public boolean contains(double value)\r
- {\r
- return indexOf(value)>=0;\r
- }\r
- \r
- /**\r
- * Get the min and max value\r
- * \r
- * @return boundaries or null\r
- */\r
- public Segment getBoundaries()\r
- {\r
- if (list.isEmpty()) return null;\r
- double start = list.get(0).getStart();\r
- double end = list.get(list.size()-1).getEnd();\r
- return new Segment(start, end);\r
- }\r
- \r
- /**\r
- * \r
- * @return lower bound or null\r
- */\r
- public Double getLowerBound() {\r
- if (list.isEmpty()) return null;\r
- return list.get(0).getStart();\r
- }\r
- \r
- /**\r
- * \r
- * @return upper bound or null\r
- */\r
- public Double getUpperBound() {\r
- if (list.isEmpty()) return null;\r
- return list.get(list.size()-1).getEnd();\r
- }\r
- \r
- /**\r
- * Return incrementally sorted and non-intersecting array of segments.\r
- * \r
- * Note this method returns an internal state, it most not be modified.\r
- * \r
- * @return array\r
- */\r
- public Segment[] toArray() {\r
- return list.toArray( new Segment[list.size()] );\r
- }\r
- \r
- /**\r
- * Returns an iterator over the elements in this list in proper sequence.\r
- *\r
- * @return an iterator over the elements in this list in proper sequence.\r
- */\r
- public Iterator<Segment> iterator() {\r
- return list.iterator();\r
- } \r
- \r
- @Override\r
- public String toString() {\r
- return Arrays.toString( toArray() );\r
- }\r
- \r
- public SegmentSet clone() {\r
- return new SegmentSet(this);\r
- }\r
- \r
-}\r
-\r
+/*******************************************************************************
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management
+ * in Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VTT Technical Research Centre of Finland - initial API and implementation
+ *******************************************************************************/
+package org.simantics.utils.datastructures;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+
+/**
+ * SegmentSet is a set of value segments.
+ *
+ * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
+ */
+public class SegmentSet implements Iterable<Segment> {
+
+ public static final SegmentSet NONE = new SegmentSet();
+
+ /** incrementally sorted and non-intersecting, non-parallel array of segments */
+ List<Segment> list = new ArrayList<Segment>();
+
+ /**
+ * Create new segment set from double value pairs
+ *
+ * @param times even length array
+ * @return
+ */
+ public static SegmentSet of(double...times)
+ {
+ if (times==null || ((times.length & 1)==1))
+ throw new IllegalArgumentException();
+ SegmentSet result = new SegmentSet();
+ for (int i=0; i<times.length/2; i++)
+ result.add( Segment.of(times[i*2], times[i*2+1]) );
+ return result;
+ }
+
+ /**
+ * Create new set of ranges.
+ */
+ public SegmentSet() {
+ }
+
+ /**
+ * Create new set of ranges.
+ */
+ public SegmentSet(SegmentSet copyFrom) {
+ this.list.addAll(copyFrom.list);
+ }
+
+ /**
+ * Create new set of segments.
+ */
+ public SegmentSet(Collection<Segment> list) {
+ for (Segment r : list)
+ add(r);
+ }
+
+ /**
+ * Create new set of segments.
+ *
+ * @param segments initial segments
+ */
+ public SegmentSet(Segment...segments) {
+ for (Segment r : Segment.union(segments))
+ list.add(r);
+ }
+
+ public boolean add(Segment...segments) {
+ boolean result = false;
+ for (Segment r : segments)
+ result |= add(r);
+ return result;
+ }
+
+ /**
+ * Add a segment set to this segment set
+ *
+ * @param set
+ * @return true if the content changed
+ */
+ public boolean add(SegmentSet set) {
+ boolean result = false;
+ for (Segment r : set.list)
+ result |= add(r);
+ return result;
+ }
+
+ /**
+ * Get index of the segment that contains the given value.
+ * If value is not included in the set, return as negative value the index
+ * of the range the value is prior to.
+ * e.g.
+ * -1 before 0
+ * -2 before 1
+ *
+ * @return range index
+ */
+ int indexOf(double value) {
+ for (int i=0; i<list.size(); i++) {
+ Segment r = list.get(i);
+ if (r.contains(value)) return i;
+ if (r.getStart()>=value) return -i -1;
+ }
+ return -list.size()-1;
+ }
+
+ /**
+ * Get the segment the value is in.
+ *
+ * @param value
+ * @return segment or null
+ */
+ public Segment getSegmentOf(double value)
+ {
+ int index = indexOf(value);
+ if (index<0) return null;
+ return list.get(index);
+ }
+
+ /**
+ * Add segment range
+ *
+ * @param range
+ * @return true if the content changed
+ */
+ public boolean add(Segment range) {
+ int startIndex = indexOf(range.getStart());
+ int endIndex = indexOf(range.getEnd());
+
+ // The whole segment is already included in the set
+ if (startIndex>=0 && startIndex==endIndex) return false;
+
+ // Doesn't intersect, add as is
+ if (startIndex<0 && startIndex==endIndex) {
+ list.add(-startIndex-1, range);
+ return true;
+ }
+
+ // Intersects partially
+ double start = range.getStart();
+ double end = range.getEnd();
+
+ // Extend the segment following the start position
+ if (startIndex<0) {
+ startIndex = -startIndex-1;
+ } else {
+ start = list.get(startIndex).getStart();
+ }
+
+ // Extends the segment preceding the end position
+ if (endIndex<0) {
+ endIndex = -endIndex-2;
+ } else {
+ end = list.get(endIndex).getEnd();
+ }
+
+ int segmentsToRemove = endIndex - startIndex;
+ for (int j=0; j<segmentsToRemove; j++)
+ list.remove(startIndex);
+
+ if (start!=range.getStart() || end!=range.getEnd())
+ range = new Segment(start, end);
+
+ list.set( startIndex, range );
+ return true;
+ }
+
+ public boolean remove(Segment...ranges) {
+ boolean result = false;
+ for (Segment r : ranges)
+ result |= remove(r);
+ return result;
+ }
+
+ public boolean remove(SegmentSet set) {
+ boolean result = false;
+ for (Segment r : set.list)
+ result |= remove(r);
+ return result;
+ }
+
+ public boolean remove(Segment range) {
+ int startIndex = indexOf(range.getStart());
+ int endIndex = indexOf(range.getEnd());
+
+ // Doesn't intersect
+ if (startIndex<0 && startIndex==endIndex) return false;
+
+ // Move start to next segment
+ if (startIndex<0)
+ startIndex = -startIndex-1;
+
+ // Move end to prev segment
+ if (endIndex<0)
+ endIndex = -endIndex-2;
+
+ // Start position is in segment. Cut segment and move to next one
+ if (range.getStart()>list.get(startIndex).getStart()) {
+ Segment s = list.get(startIndex);
+ Segment newS = new Segment(s.getStart(), range.getStart());
+ list.set(startIndex, newS);
+ startIndex++;
+
+ if (s.getEnd()>range.getEnd()) {
+ newS = new Segment(range.getEnd(), s.getEnd());
+ list.add(startIndex, newS);
+ startIndex++;
+ }
+ }
+
+ // End position is within segment, Cut it and move to prev one
+ if (range.getEnd()<list.get(endIndex).getEnd()) {
+ Segment s = list.get(endIndex);
+ s = new Segment(range.getEnd(), s.getEnd());
+ list.set(endIndex, s);
+ endIndex--;
+ }
+
+ // Remove start if it is cut completely
+ while ( startIndex<=endIndex && range.contains( list.get(startIndex) ) ) {
+ list.remove(startIndex);
+ endIndex--;
+ }
+ return true;
+ }
+
+ /**
+ * Clips SegmentSet to given segment.
+ * @param segment
+ */
+ public void clip(Segment segment) {
+ remove(new Segment(-Double.MAX_VALUE,segment.getStart()));
+ remove(new Segment(segment.getEnd(),Double.MAX_VALUE));
+ }
+
+ /**
+ * Tests whether s intersects
+ *
+ * @param s segmentset
+ * @return true if s intersects with this segment set
+ */
+ public boolean intersects(SegmentSet set)
+ {
+ for (Segment s : set.list)
+ if (intersects(s)) return true;
+ return false;
+ }
+
+ /**
+ * Tests whether s intersects
+ *
+ * @param s segment
+ * @return true if s intersects with this segment set
+ */
+ public boolean intersects(Segment s)
+ {
+ for (Segment localS : list)
+ if (localS.intersects(s)) return true;
+ return false;
+ }
+
+ /**
+ * Tests whether s is fully contained in this segment set.
+ *
+ * @param s segment
+ * @return true if s is fully contained in this segment set
+ */
+ public boolean contains(Segment s)
+ {
+ for (Segment localS : list)
+ if (localS.contains(s)) return true;
+ return false;
+ }
+
+ /**
+ * Tests whether the a values is included in the set.
+ *
+ * @param value
+ * @return
+ */
+ public boolean contains(double value)
+ {
+ return indexOf(value)>=0;
+ }
+
+ /**
+ * Get the min and max value
+ *
+ * @return boundaries or null
+ */
+ public Segment getBoundaries()
+ {
+ if (list.isEmpty()) return null;
+ double start = list.get(0).getStart();
+ double end = list.get(list.size()-1).getEnd();
+ return new Segment(start, end);
+ }
+
+ /**
+ *
+ * @return lower bound or null
+ */
+ public Double getLowerBound() {
+ if (list.isEmpty()) return null;
+ return list.get(0).getStart();
+ }
+
+ /**
+ *
+ * @return upper bound or null
+ */
+ public Double getUpperBound() {
+ if (list.isEmpty()) return null;
+ return list.get(list.size()-1).getEnd();
+ }
+
+ /**
+ * Return incrementally sorted and non-intersecting array of segments.
+ *
+ * Note this method returns an internal state, it most not be modified.
+ *
+ * @return array
+ */
+ public Segment[] toArray() {
+ return list.toArray( new Segment[list.size()] );
+ }
+
+ /**
+ * Returns an iterator over the elements in this list in proper sequence.
+ *
+ * @return an iterator over the elements in this list in proper sequence.
+ */
+ public Iterator<Segment> iterator() {
+ return list.iterator();
+ }
+
+ @Override
+ public String toString() {
+ return Arrays.toString( toArray() );
+ }
+
+ public SegmentSet clone() {
+ return new SegmentSet(this);
+ }
+
+}
+
Code Review / simantics / platform.git / blobdiff