X-Git-Url: https://gerrit.simantics.org/r/gitweb?p=simantics%2Fplatform.git;a=blobdiff_plain;f=bundles%2Forg.simantics.history%2Fsrc%2Forg%2Fsimantics%2Fhistory%2Futil%2FWeightedMedianApprox.java;h=6f2c3f804f22400a22bf821c289ba1ab2b6fb8a9;hp=376e6f8d62bb3df317faa623a936e291c26bcba2;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hpb=24e2b34260f219f0d1644ca7a138894980e25b14

diff --git a/bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedianApprox.java b/bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedianApprox.java
index 376e6f8d6..6f2c3f804 100644
--- a/bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedianApprox.java
+++ b/bundles/org.simantics.history/src/org/simantics/history/util/WeightedMedianApprox.java
@@ -1,274 +1,274 @@
-/*******************************************************************************
- * 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.Arrays;
-import java.util.Comparator;
-import java.util.Iterator;
-import java.util.PriorityQueue;
-import java.util.TreeMap;
-
-import org.simantics.databoard.annotations.Referable;
-
-/**
- * Weighted median approximation
- * 
- * @author toni.kalajainen
- */
-public class WeightedMedianApprox {
-
-	static final Comparator<Item> valueComparator;
-	static final Comparator<Double> double_comparator, reverse_double_comparator;
-	
-    public Item median;
-    public TreeMap<Double, Item> lower;
-    public TreeMap<Double, Item> upper;
-    public int maxSize = Integer.MAX_VALUE;
-    public double rpos;
-
-    public WeightedMedianApprox() {
-        lower = new TreeMap<Double, Item>( reverse_double_comparator );
-        upper = new TreeMap<Double, Item>( double_comparator );
-    }
-    
-    public WeightedMedianApprox(int maxSize) {
-    	this();
-        this.maxSize = maxSize;
-    }
-
-    public void clear() {
-    	lower.clear();
-    	upper.clear();
-    	median = null;
-    	rpos = 0.;
-    }
-
-    public void add(double weight, double value) {
-                
-    	System.out.println("Adding (value="+value+", weight="+weight+")");
-        if (median == null) {
-            median = new Item(weight, value);
-			rpos = weight / 2;
-            return;
-        }
-        
-        if ( value == median.value ) {
-        	median.weight += weight;
-        	return;
-        }
-
-        TreeMap<Double, Item> map = value>median.value ? upper : lower;
-        Item i = map.get( value );
-        if ( i != null ) {
-        	i.weight += weight;
-        } else {
-        	map.put(value, new Item(weight, value));
-        }
-
-		rpos += (value<median.value?-1:1) * weight / 2;
-        balance();
-
-        int count = size();
-        if (count>maxSize) {
-        	coalesce((count+1)/2); 
-        }
-    }
-    
-    void balance() {
-        // Relative Pos - Balance
-		while (rpos<0) {
-			upper.put(median.value, median);
-			median = lower.remove( lower.firstKey() );
-			rpos += median.weight;
-		}
-		while (rpos>=median.weight) {
-			rpos -= median.weight;
-			lower.put(median.value, median);
-			median = upper.remove( upper.firstKey() );
-		}        
-    	
-    }
-
-    public double getMedian() {
-    	if (median==null) return Double.NaN;
-        return median.value;
-    }
-
-	public int size() {
-		return upper.size() + lower.size() + (median==null?0:1);
-	}
-	
-	@Override
-	public String toString() {
-		StringBuilder sb = new StringBuilder();
-		sb.append( "Median="+getMedian()+" ");
-		
-		PriorityQueue<Item> q = new PriorityQueue<Item>( size(), valueComparator );
-		q.addAll(lower.values());
-		if (median!=null) q.add(median);
-		q.addAll(upper.values());
-		
-		while ( !q.isEmpty() ) {
-			Item i = q.remove();
-			sb.append("(value=");
-			sb.append(i.value);
-			sb.append(", w=");
-			sb.append(i.weight);
-			if (i == median) sb.append(", pos="+rpos);
-			sb.append(")");
-		}
-		
-		return sb.toString();
-	}	
-	
-	/**
-	 * Halves sample count.
-	 * Combines items whose combination causes smallest error.
-	 */
-	public void coalesce(int targetCount) {
-		int count = size();
-		if (count<3) return;
-		
-		ErrorStack err = new ErrorStack();
-		err.start();
-		Iterator<Item> itr = lower.values().iterator();
-		while (itr.hasNext()) {
-			Item item = itr.next();
-			err.addItem( item );
-		}
-		err.addItem( median );
-		itr = upper.values().iterator();
-		while (itr.hasNext()) {
-			Item item = itr.next();
-			err.addItem( item );
-		}
-		MergeAction[] errs = err.finish();
-		for (int i=targetCount-1; i>=0; i--) {
-			MergeAction e = errs[i];
-			System.out.println("  Merging "+e.itemToMerge+" to "+e.mergeToItem+", err="+e.error);
-			e.mergeToItem.weight += e.itemToMerge.weight;
-			if (e.itemToMerge == median) {
-				median = e.mergeToItem;
-				TreeMap<Double, Item> map = e.mergeToItem.value < median.value ? lower : upper;
-				map.remove(e.mergeToItem.value);
-				if (e.itemToMerge.value<e.mergeToItem.value) {
-					rpos += e.itemToMerge.weight;
-					balance();
-				}
-			} else {
-				TreeMap<Double, Item> map = e.itemToMerge.value < median.value ? lower : upper; 
-				map.remove(e.mergeToItem.value);
-			}
-		}
-	}
-
-	@Referable
-	static public class Item {
-		public double weight;
-		public double value;
-		public Item() {}
-		public Item(double weight, double value) {
-			this.weight = weight;
-			this.value = value;
-		}
-		@Override
-		public String toString() {
-			return "(value="+value+", w="+weight+")";
-		}				
-	}	
-
-	class ErrorStack {
-		MergeAction[] errs;
-		int count;
-		int i;
-		Item prev;
-		void start() {
-			count = size();
-			errs = new MergeAction[ count - 1 ];
-			i = 0;
-			prev = null;
-		}
-		void addItem(Item item) {
-			if (prev!=null) {
-				MergeAction e = new MergeAction();
-				e.mergeToItem = prev;
-				e.itemToMerge = item;
-				double valueDiff = Math.abs(e.itemToMerge.value - e.mergeToItem.value);
-				double mergeError = valueDiff * e.itemToMerge.weight;
-				e.error = mergeError;
-				errs[i++] = e;
-			}
-			prev = item;
-		}
-		MergeAction[] finish() {
-			MergeErrorComparator c = new MergeErrorComparator();
-			c.median = median!=null?median.value:0;
-			Arrays.sort(errs, c);
-			return errs;
-		}
-	}
-	
-	static class MergeAction {
-		public double error;
-		public Item mergeToItem, itemToMerge;
-	}	
-	
-	/**
-	 * This comparator minimizes error, then maximizes distance to median
-	 */
-	static class MergeErrorComparator implements Comparator<MergeAction> {
-		double median;
-		@Override
-		public int compare(MergeAction o1, MergeAction o2) {
-			double diff = o1.error - o2.error;
-			if (diff==0) {
-				double distToMedian1 = o1.mergeToItem.value - median;
-				double distToMedian2 = o2.mergeToItem.value - median;
-				diff = distToMedian1 - distToMedian2;
-				return diff>0?-1:1;
-			} else return diff<0?-1:1; 
-		}
-	};
-
-	
-	static {
-		
-		valueComparator = new Comparator<Item>() {
-			@Override
-			public int compare(Item o1, Item o2) {
-				double diff = o1.value - o2.value;
-				return diff==0.0 ? 0 : ( diff<0?-1:1);
-			}
-		};
-		
-		reverse_double_comparator = new Comparator<Double>() {
-			@Override
-			public int compare(Double o1, Double o2) {
-		    	Double d1 = (Double) o1;
-		    	Double d2 = (Double) o2;
-		    	double d = d2-d1;
-		    	return d == 0.0 ? 0 : (d<0?-1:1);
-		    }};
-		
-		double_comparator = new Comparator<Double>() {
-			@Override
-			public int compare(Double o1, Double o2) {
-		    	Double d1 = (Double) o1;
-		    	Double d2 = (Double) o2;
-		    	double d = d1-d2;
-		    	return d == 0.0 ? 0 : (d<0?-1:1);
-		    }};
-			
-	}
-	
-	
-}
+/*******************************************************************************
+ * 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.Arrays;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.PriorityQueue;
+import java.util.TreeMap;
+
+import org.simantics.databoard.annotations.Referable;
+
+/**
+ * Weighted median approximation
+ * 
+ * @author toni.kalajainen
+ */
+public class WeightedMedianApprox {
+
+	static final Comparator<Item> valueComparator;
+	static final Comparator<Double> double_comparator, reverse_double_comparator;
+	
+    public Item median;
+    public TreeMap<Double, Item> lower;
+    public TreeMap<Double, Item> upper;
+    public int maxSize = Integer.MAX_VALUE;
+    public double rpos;
+
+    public WeightedMedianApprox() {
+        lower = new TreeMap<Double, Item>( reverse_double_comparator );
+        upper = new TreeMap<Double, Item>( double_comparator );
+    }
+    
+    public WeightedMedianApprox(int maxSize) {
+    	this();
+        this.maxSize = maxSize;
+    }
+
+    public void clear() {
+    	lower.clear();
+    	upper.clear();
+    	median = null;
+    	rpos = 0.;
+    }
+
+    public void add(double weight, double value) {
+                
+    	System.out.println("Adding (value="+value+", weight="+weight+")");
+        if (median == null) {
+            median = new Item(weight, value);
+			rpos = weight / 2;
+            return;
+        }
+        
+        if ( value == median.value ) {
+        	median.weight += weight;
+        	return;
+        }
+
+        TreeMap<Double, Item> map = value>median.value ? upper : lower;
+        Item i = map.get( value );
+        if ( i != null ) {
+        	i.weight += weight;
+        } else {
+        	map.put(value, new Item(weight, value));
+        }
+
+		rpos += (value<median.value?-1:1) * weight / 2;
+        balance();
+
+        int count = size();
+        if (count>maxSize) {
+        	coalesce((count+1)/2); 
+        }
+    }
+    
+    void balance() {
+        // Relative Pos - Balance
+		while (rpos<0) {
+			upper.put(median.value, median);
+			median = lower.remove( lower.firstKey() );
+			rpos += median.weight;
+		}
+		while (rpos>=median.weight) {
+			rpos -= median.weight;
+			lower.put(median.value, median);
+			median = upper.remove( upper.firstKey() );
+		}        
+    	
+    }
+
+    public double getMedian() {
+    	if (median==null) return Double.NaN;
+        return median.value;
+    }
+
+	public int size() {
+		return upper.size() + lower.size() + (median==null?0:1);
+	}
+	
+	@Override
+	public String toString() {
+		StringBuilder sb = new StringBuilder();
+		sb.append( "Median="+getMedian()+" ");
+		
+		PriorityQueue<Item> q = new PriorityQueue<Item>( size(), valueComparator );
+		q.addAll(lower.values());
+		if (median!=null) q.add(median);
+		q.addAll(upper.values());
+		
+		while ( !q.isEmpty() ) {
+			Item i = q.remove();
+			sb.append("(value=");
+			sb.append(i.value);
+			sb.append(", w=");
+			sb.append(i.weight);
+			if (i == median) sb.append(", pos="+rpos);
+			sb.append(")");
+		}
+		
+		return sb.toString();
+	}	
+	
+	/**
+	 * Halves sample count.
+	 * Combines items whose combination causes smallest error.
+	 */
+	public void coalesce(int targetCount) {
+		int count = size();
+		if (count<3) return;
+		
+		ErrorStack err = new ErrorStack();
+		err.start();
+		Iterator<Item> itr = lower.values().iterator();
+		while (itr.hasNext()) {
+			Item item = itr.next();
+			err.addItem( item );
+		}
+		err.addItem( median );
+		itr = upper.values().iterator();
+		while (itr.hasNext()) {
+			Item item = itr.next();
+			err.addItem( item );
+		}
+		MergeAction[] errs = err.finish();
+		for (int i=targetCount-1; i>=0; i--) {
+			MergeAction e = errs[i];
+			System.out.println("  Merging "+e.itemToMerge+" to "+e.mergeToItem+", err="+e.error);
+			e.mergeToItem.weight += e.itemToMerge.weight;
+			if (e.itemToMerge == median) {
+				median = e.mergeToItem;
+				TreeMap<Double, Item> map = e.mergeToItem.value < median.value ? lower : upper;
+				map.remove(e.mergeToItem.value);
+				if (e.itemToMerge.value<e.mergeToItem.value) {
+					rpos += e.itemToMerge.weight;
+					balance();
+				}
+			} else {
+				TreeMap<Double, Item> map = e.itemToMerge.value < median.value ? lower : upper; 
+				map.remove(e.mergeToItem.value);
+			}
+		}
+	}
+
+	@Referable
+	static public class Item {
+		public double weight;
+		public double value;
+		public Item() {}
+		public Item(double weight, double value) {
+			this.weight = weight;
+			this.value = value;
+		}
+		@Override
+		public String toString() {
+			return "(value="+value+", w="+weight+")";
+		}				
+	}	
+
+	class ErrorStack {
+		MergeAction[] errs;
+		int count;
+		int i;
+		Item prev;
+		void start() {
+			count = size();
+			errs = new MergeAction[ count - 1 ];
+			i = 0;
+			prev = null;
+		}
+		void addItem(Item item) {
+			if (prev!=null) {
+				MergeAction e = new MergeAction();
+				e.mergeToItem = prev;
+				e.itemToMerge = item;
+				double valueDiff = Math.abs(e.itemToMerge.value - e.mergeToItem.value);
+				double mergeError = valueDiff * e.itemToMerge.weight;
+				e.error = mergeError;
+				errs[i++] = e;
+			}
+			prev = item;
+		}
+		MergeAction[] finish() {
+			MergeErrorComparator c = new MergeErrorComparator();
+			c.median = median!=null?median.value:0;
+			Arrays.sort(errs, c);
+			return errs;
+		}
+	}
+	
+	static class MergeAction {
+		public double error;
+		public Item mergeToItem, itemToMerge;
+	}	
+	
+	/**
+	 * This comparator minimizes error, then maximizes distance to median
+	 */
+	static class MergeErrorComparator implements Comparator<MergeAction> {
+		double median;
+		@Override
+		public int compare(MergeAction o1, MergeAction o2) {
+			double diff = o1.error - o2.error;
+			if (diff==0) {
+				double distToMedian1 = o1.mergeToItem.value - median;
+				double distToMedian2 = o2.mergeToItem.value - median;
+				diff = distToMedian1 - distToMedian2;
+				return diff>0?-1:1;
+			} else return diff<0?-1:1; 
+		}
+	};
+
+	
+	static {
+		
+		valueComparator = new Comparator<Item>() {
+			@Override
+			public int compare(Item o1, Item o2) {
+				double diff = o1.value - o2.value;
+				return diff==0.0 ? 0 : ( diff<0?-1:1);
+			}
+		};
+		
+		reverse_double_comparator = new Comparator<Double>() {
+			@Override
+			public int compare(Double o1, Double o2) {
+		    	Double d1 = (Double) o1;
+		    	Double d2 = (Double) o2;
+		    	double d = d2-d1;
+		    	return d == 0.0 ? 0 : (d<0?-1:1);
+		    }};
+		
+		double_comparator = new Comparator<Double>() {
+			@Override
+			public int compare(Double o1, Double o2) {
+		    	Double d1 = (Double) o1;
+		    	Double d2 = (Double) o2;
+		    	double d = d1-d2;
+		    	return d == 0.0 ? 0 : (d<0?-1:1);
+		    }};
+			
+	}
+	
+	
+}