/*******************************************************************************
 * Copyright (c) 2007, 2010 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.utils.datastructures;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

/**
 * SegmentSet is a set of value segments.
 * 
 * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
 */
public class SegmentSet implements Iterable<Segment> {

	public static final SegmentSet NONE = new SegmentSet();
	
	/** incrementally sorted and non-intersecting, non-parallel array of segments */
	List<Segment> list = new ArrayList<Segment>();
	
	/**
	 * Create new segment set from double value pairs 
	 * 
	 * @param times even length array
	 * @return
	 */
	public static SegmentSet of(double...times)
	{
		if (times==null || ((times.length & 1)==1))
			throw new IllegalArgumentException();
		SegmentSet result = new SegmentSet();
		for (int i=0; i<times.length/2; i++)
			result.add( Segment.of(times[i*2], times[i*2+1]) );
		return result;
	}
	
	/**
	 * Create new set of ranges.
	 */
	public SegmentSet() {		
	}

	/**
	 * Create new set of ranges.
	 */
	public SegmentSet(SegmentSet copyFrom) {
		this.list.addAll(copyFrom.list);
	}
	
	/**
	 * Create new set of segments.
	 */
	public SegmentSet(Collection<Segment> list) {
		for (Segment r : list)
			add(r);
	}
	
	/**
	 * Create new set of segments.
	 * 
	 * @param segments initial segments
	 */
	public SegmentSet(Segment...segments) {
		for (Segment r : Segment.union(segments))
			list.add(r);
	}
	
	public boolean add(Segment...segments) {
		boolean result = false;
		for (Segment r : segments) 
			result |= add(r);
		return result;
	}
	
	/**
	 * Add a segment set to this segment set
	 *  
	 * @param set 
	 * @return true if the content changed
	 */
	public boolean add(SegmentSet set) {
		boolean result = false;
		for (Segment r : set.list)
			result |= add(r);
		return result;
	}
	
	/**
	 * Get index of the segment that contains the given value.
	 * If value is not included in the set, return as negative value the index
	 * of the range the value is prior to.
	 *  e.g. 
	 *    -1 before 0
	 *    -2 before 1
	 * 
	 * @return range index
	 */
	int indexOf(double value) {
		for (int i=0; i<list.size(); i++) {
			Segment r = list.get(i);
			if (r.contains(value)) return i;
			if (r.getStart()>=value) return -i -1;
		}
		return -list.size()-1;
	}
	
	/**
	 * Get the segment the value is in.
	 * 
	 * @param value 
	 * @return segment or null
	 */
	public Segment getSegmentOf(double value)
	{
		int index = indexOf(value);
		if (index<0) return null;
		return list.get(index);
	}
	
	/**
	 * Add segment range
	 * 
	 * @param range
	 * @return true if the content changed
	 */
	public boolean add(Segment range) {
		int startIndex = indexOf(range.getStart());
		int endIndex = indexOf(range.getEnd());
				
		// The whole segment is already included in the set
		if (startIndex>=0 && startIndex==endIndex) return false;
		
		// Doesn't intersect, add as is
		if (startIndex<0 && startIndex==endIndex) {
			list.add(-startIndex-1, range);
			return true;
		}

		// Intersects partially
		double start = range.getStart();
		double end = range.getEnd();

		// Extend the segment following the start position 
		if (startIndex<0) {
			startIndex = -startIndex-1;
		} else {
			start = list.get(startIndex).getStart();
		}
		
		// Extends the segment preceding the end position 
		if (endIndex<0) {
			endIndex = -endIndex-2;
		} else {
			end = list.get(endIndex).getEnd();
		}
				
		int segmentsToRemove = endIndex - startIndex;
		for (int j=0; j<segmentsToRemove; j++)
			list.remove(startIndex);
		
		if (start!=range.getStart() || end!=range.getEnd())
			range = new Segment(start, end);
		
		list.set( startIndex, range );		
		return true;
	}
	
	public boolean remove(Segment...ranges) {
		boolean result = false;
		for (Segment r : ranges)
			result |= remove(r);
		return result;
	}
	
	public boolean remove(SegmentSet set) {
		boolean result = false;
		for (Segment r : set.list)
			result |= remove(r);
		return result;
	}
	
	public boolean remove(Segment range) {
		int startIndex = indexOf(range.getStart());
		int endIndex = indexOf(range.getEnd());

		// Doesn't intersect
		if (startIndex<0 && startIndex==endIndex) return false;

		// Move start to next segment
		if (startIndex<0) 
			startIndex = -startIndex-1;
		
		// Move end to prev segment
		if (endIndex<0) 
			endIndex = -endIndex-2;

		// Start position is in segment. Cut segment and move to next one
		if (range.getStart()>list.get(startIndex).getStart()) {
			Segment s = list.get(startIndex);
			Segment newS = new Segment(s.getStart(), range.getStart());
			list.set(startIndex, newS);
			startIndex++;
			
			if (s.getEnd()>range.getEnd()) {
				newS = new Segment(range.getEnd(), s.getEnd());
				list.add(startIndex, newS);
				startIndex++;
			}			
		}
		
		// End position is within segment, Cut it and move to prev one
		if (range.getEnd()<list.get(endIndex).getEnd()) {
			Segment s = list.get(endIndex);
			s = new Segment(range.getEnd(), s.getEnd());
			list.set(endIndex, s);
			endIndex--;
		}
		
		// Remove start if it is cut completely
		while ( startIndex<=endIndex && range.contains( list.get(startIndex) ) ) {
			list.remove(startIndex);
			endIndex--;
		}
		return true;
	}
	
	/**
	 * Clips SegmentSet to given segment.
	 * @param segment
	 */
	public void clip(Segment segment) {
		remove(new Segment(-Double.MAX_VALUE,segment.getStart()));
		remove(new Segment(segment.getEnd(),Double.MAX_VALUE));
	}

	/**
	 * Tests whether s intersects 
	 * 
	 * @param s segmentset
	 * @return true if s intersects with this segment set 
	 */
	public boolean intersects(SegmentSet set)
	{
		for (Segment s : set.list)
			if (intersects(s)) return true;
		return false;
	}
	
	/**
	 * Tests whether s intersects 
	 * 
	 * @param s segment
	 * @return true if s intersects with this segment set 
	 */
	public boolean intersects(Segment s)
	{
		for (Segment localS : list)
			if (localS.intersects(s)) return true;
		return false;
	}
	
	/**
	 * Tests whether s is fully contained in this segment set. 
	 * 
	 * @param s segment
	 * @return true if s is fully contained in this segment set
	 */
	public boolean contains(Segment s) 
	{
		for (Segment localS : list)
			if (localS.contains(s)) return true;
		return false;
	}
	
	/**
	 * Tests whether the a values is included in the set.
	 *
	 * @param value
	 * @return
	 */
	public boolean contains(double value)
	{
		return indexOf(value)>=0;
	}
	
	/**
	 * Get the min and max value
	 * 
	 * @return boundaries or null
	 */
	public Segment getBoundaries()
	{
		if (list.isEmpty()) return null;
		double start = list.get(0).getStart();
		double end = list.get(list.size()-1).getEnd();
		return new Segment(start, end);
	}
	
	/**
	 * 
	 * @return lower bound or null
	 */
	public Double getLowerBound() {
		if (list.isEmpty()) return null;
		return list.get(0).getStart();
	}
	
	/**
	 * 
	 * @return upper bound or null
	 */
	public Double getUpperBound() {
		if (list.isEmpty()) return null;
		return list.get(list.size()-1).getEnd();
	}
	
	/**
	 * Return incrementally sorted and non-intersecting array of segments.
	 * 
	 * Note this method returns an internal state, it most not be modified.
	 * 
	 * @return array
	 */
	public Segment[] toArray() {
		return list.toArray( new Segment[list.size()] );
	}
	
    /**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * @return an iterator over the elements in this list in proper sequence.
     */
    public Iterator<Segment> iterator() {
    	return list.iterator();
    }	
	
	@Override
	public String toString() {
		return Arrays.toString( toArray() );
	}
	
	public SegmentSet clone() {
		return new SegmentSet(this);
	}
	
}