Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.history / src / org / simantics / history / util / Median.java

diff --git a/bundles/org.simantics.history/src/org/simantics/history/util/Median.java b/bundles/org.simantics.history/src/org/simantics/history/util/Median.java
new file mode 100644 (file)
index 0000000..f250b78
--- /dev/null
+++ b/bundles/org.simantics.history/src/org/simantics/history/util/Median.java
@@ -0,0 +1,102 @@
+/*******************************************************************************\r
+ * Copyright (c) 2007, 2011 Association for Decentralized Information Management in\r
+ * 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.history.util;\r
+\r
+import java.util.Collections;\r
+import java.util.Comparator;\r
+import java.util.PriorityQueue;\r
+\r
+public class Median<T> {\r
+       \r
+    PriorityQueue<T> upper;\r
+    PriorityQueue<T> lower;\r
+    T median;\r
+\r
+    public Median(Comparator<? super T> comparator) {\r
+        lower = new PriorityQueue<T>(11, comparator);\r
+        upper = new PriorityQueue<T>(11, Collections.reverseOrder(comparator));\r
+    }\r
+\r
+    public Median(int length, Comparator<? super T> comparator) {\r
+       int c = length/2;\r
+       if (c<3) c = 3;\r
+        lower = new PriorityQueue<T>( c, comparator);\r
+        upper = new PriorityQueue<T>( c, Collections.reverseOrder(comparator));\r
+    }\r
+    \r
+    public void clear() {\r
+       lower.clear();\r
+       upper.clear();\r
+       median = null;\r
+    }\r
+\r
+    public void add(T e) {\r
+        if (median == null) {\r
+            median = e;\r
+            return;\r
+        }\r
+        \r
+        int cmp = lower.comparator().compare(e, median);\r
+        if (cmp < 0) {\r
+            upper.add(e);\r
+        } else {\r
+            lower.add(e);\r
+        }\r
+\r
+        int diff = upper.size() - lower.size();\r
+        if (diff >= 1) {\r
+            lower.add(median);\r
+            median = upper.remove();\r
+        } else if (diff < -1) {\r
+            upper.add(median);\r
+            median = lower.remove();\r
+        }\r
+    }\r
+\r
+    public T getMedian() {\r
+        return median;\r
+    }\r
+\r
+       public int size() {\r
+               return upper.size() + lower.size();\r
+       }\r
+       \r
+       /**\r
+        * Shrinkages the median by removing from highest and lowest ends\r
+        * \r
+        * @param newSize\r
+        */\r
+       public void setSize(int newSize) {\r
+               int x = newSize/2;\r
+               if (upper.size()<x) {\r
+                       upper.clear();\r
+               } else {\r
+                       int y = upper.size() - x;\r
+                       for (int i=0; i<y; i++) {\r
+                               upper.remove();\r
+                       }\r
+               }\r
+               \r
+               if (lower.size()<x) {\r
+                       lower.clear();\r
+               } else {\r
+                       int y = lower.size() - x;\r
+                       for (int i=0; i<y; i++) {\r
+                               lower.remove();\r
+                       }\r
+               }\r
+       }\r
+       \r
+       \r
+       \r
+    \r
+}
\ No newline at end of file