X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=bundles%2Forg.simantics.history%2Fsrc%2Forg%2Fsimantics%2Fhistory%2Futil%2FMedian.java;fp=bundles%2Forg.simantics.history%2Fsrc%2Forg%2Fsimantics%2Fhistory%2Futil%2FMedian.java;h=f250b780224edb33fc096a306ad1a8873ad44e85;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

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
index 000000000..f250b7802
--- /dev/null
+++ b/bundles/org.simantics.history/src/org/simantics/history/util/Median.java
@@ -0,0 +1,102 @@
+/*******************************************************************************
+ * 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