/*******************************************************************************
 * 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);
		    }};
			
	}
	
	
}