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