/*
 *  File: DefaultOverlapStrategy.java
 *  Copyright (c) 2004-2007  Peter Kliem (Peter.Kliem@jaret.de)
 *  A commercial license is available, see http://www.jaret.de.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */
package brn.gui.editors.timebar;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

import de.jaret.util.date.Interval;
import de.jaret.util.date.IntervalImpl;
import de.jaret.util.ui.timebars.TimeBarViewerDelegate;
import de.jaret.util.ui.timebars.model.TimeBarRow;

import de.jaret.util.ui.timebars.strategy.DefaultOverlapStrategy;
import de.jaret.util.ui.timebars.strategy.IOverlapStrategy;
import de.jaret.util.ui.timebars.strategy.OverlapInfo;

/**
 * Default implementation of an overlap strategy that does a complete check on overlaps between intervals including
 * transitive overlaps. This can be VERY time consuming when dealing with a lot of intervals.
 *
 * @author kliem
 * @version $Id: $
 */
public class OverlapStrategy extends DefaultOverlapStrategy {

    /**
     * Construct a default strategy for a specific delegate.
     *
     * @param delegate the delegate the strategy works for
     */
    public OverlapStrategy(TimeBarViewerDelegate delegate) {
      super (delegate);
    }

    /**
     * {@inheritDoc} Assumes sorted Intervals.
     */
    public Map<Interval, OverlapInfo> updateOICache(TimeBarRow row) {
        List<Interval> intervals = _delegate.filterIntervals(row.getIntervals());
        Map<Interval, OverlapInfo> result = new HashMap<Interval, OverlapInfo>();

        // build a array of indices, sorted according to the start time
        Integer[] sortedStartTime = new Integer[intervals.size()];
        for (int i = 0; i < intervals.size(); i++)
          sortedStartTime[i] = i;
        final List<Interval> finalIntervals = intervals;
        Arrays.sort(sortedStartTime, new Comparator<Integer>() {
          public int compare(Integer o1, Integer o2) {
            return finalIntervals.get(o1).getBegin().compareTo(finalIntervals.get(o2).getBegin());
          }
        });

        // map max end time of the list so far on index in sortedStartTime
        NavigableMap<Long, Integer> mapEndTime = new TreeMap<Long,Integer>();
        long maxEndTime = Long.MIN_VALUE;
        for (int i = 0; i < sortedStartTime.length; i++) {
          Interval interval1 = intervals.get(sortedStartTime[i]);
          maxEndTime = Math.max(maxEndTime, interval1.getEnd().getDate().getTime());
          mapEndTime.put(maxEndTime, i);
        }

        List<OverlapInfo> oList = new ArrayList<OverlapInfo>();
        for (int i = 0; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            OverlapInfo oi = new OverlapInfo();
            oi.interval = interval;
            result.put(interval, oi);
            oList.add(oi);

            Map.Entry<Long, Integer> first =
              mapEndTime.floorEntry(interval.getBegin().getDate().getTime()-1);
            int startIdx = (null == first? 0 : first.getValue());
            for (int y = startIdx; y < sortedStartTime.length; y++) {
              int x = sortedStartTime[y];
              if (i == x)
                continue;
              Interval cmp = intervals.get(x);
              if (0 < cmp.getBegin().compareTo(interval.getEnd()))
                break;
              if (IntervalImpl.intersectNonIncluding(interval, cmp)) {
                oi.overlapping.add(cmp);
              }
            }

            // verify maxOverlapping
            int max = 0;
            int cur = 0;
            for (Interval check : oi.overlapping) {
                if (check.contains(interval.getBegin())) {
                    cur++;
                }
            }
            if (cur > max) {
                max = cur;
            }
            cur = 0;
            for (Interval check : oi.overlapping) {
                if (check.contains(interval.getEnd())) {
                    cur++;
                }
            }
            if (cur > max) {
                max = cur;
            }

            for (Interval check : oi.overlapping) {
                if (interval.contains(check.getBegin())) {
                    cur = 1;
                    for (Interval check2 : oi.overlapping) {
                        if (!check.equals(check2)) {
                            if (IntervalImpl.containsNonIncluding(check2, check.getBegin())) {
                                cur++;
                            }
                        }
                    }
                    if (cur > max) {
                        max = cur;
                    }
                }
            }
            for (Interval check : oi.overlapping) {
                if (interval.contains(check.getEnd())) {
                    cur = 1;
                    for (Interval check2 : oi.overlapping) {
                        if (!check.equals(check2)) {
                            if (IntervalImpl.containsNonIncluding(check2, check.getEnd())) {
                                cur++;
                            }
                        }
                    }
                    if (cur > max) {
                        max = cur;
                    }
                }
            }

            oi.maxOverlapping = max;
            oi.overlappingCount = max;

        }

        // sort oList by overlap count
        Collections.sort(oList, new Comparator<OverlapInfo>() {
            public int compare(OverlapInfo arg0, OverlapInfo arg1) {
                return arg1.overlappingCount - arg0.overlappingCount;
            }
        });

        boolean change = true;
        while (change) {
            change = false;
            for (int i = 0; i < oList.size(); i++) {
                OverlapInfo oi = oList.get(i);
                int max = getMaxOverlapping(oi, result);
                if (max != oi.maxOverlapping) {
                    oi.maxOverlapping = max;
                    change = true;
                }
            }
        }

        // positions
        for (int i = 0; i < oList.size(); i++) {
            OverlapInfo oi = oList.get(i);
            int[] positions = new int[oi.maxOverlapping + 1];
            for (int p = 0; p < oi.maxOverlapping + 1; p++) {
                positions[p] = -1;
            }
            for (Interval interval : oi.overlapping) {
                OverlapInfo o = result.get(interval);
                if (o.pos != -1) {
                    positions[o.pos] = o.pos;
                }
            }
            if (oi.pos == -1) {
                for (int p = 0; p < oi.maxOverlapping + 1; p++) {
                    if (positions[p] == -1) {
                        oi.pos = p;
                        positions[p] = p;
                        break;
                    }
                }
            }

        }
        // put to cache
        _oiRowCache.put(row, result);
        // dump(result);
        return result;
    }

    /**
     * Retrieve the maximum count of overlapping intervals for all overlapping intervals regsitered in an oInfo.
     *
     * @param oi OverlapInfo
     * @param map map containing the oois of all intervals
     * @return the maximum overlap count of all overlapping intervals
     */
    private int getMaxOverlapping(OverlapInfo oi, Map<Interval, OverlapInfo> map) {
        int max = oi.overlappingCount;
        for (Interval interval : oi.overlapping) {
            OverlapInfo o = map.get(interval);
            if (o.maxOverlapping > max) {
                max = o.maxOverlapping;
            }
        }
        return max;
    }
}
