--- /dev/null
+/*******************************************************************************\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
Code Review / simantics / platform.git / blobdiff