package schedframe.scheduling;


import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

import schedframe.scheduling.Reservation.Status;


/**
 * A wrapper class used to store reservations.
 * Reservations on this list are ordered based on their start time
 * 
 * @author Marcin Krystek
 *
 */
public class ReservationList extends ArrayList<Reservation> {
	
	protected static Log log = LogFactory.getLog(ReservationList.class);

	private static final long serialVersionUID = -7805575807997748584L;

	protected Comparator<Reservation> comparator;
	
	/**
	 * Default constructor 
	 *
	 */
	public ReservationList() {
		super();
		this.comparator = new ReservationComparator();
	}

	public boolean add(Reservation r){
		int i = findPositionFor(r);
		super.add(i, r);
		return true;
	}

	public Reservation get(Reservation r){
		int size = size();

		// find location estimation of the reservation r
		int idx = bisection(r.getStartMillis(), 0, size - 1);
		int i = idx;

		// go left and check if desired reservation is there
		Reservation res = get(i);
			// check only these reservations which start time is later
			// or equal to r start time
		while(i >= 0 && comparator.compare(res, r) >= 0){
			if(res.equals(r))
				return res;
			i--;
			res = get(i);
		}
		
		// if it is not there, then go to the right
		i = idx + 1;
		res = get(i);
			// check only these reservations which start time is earlier
			// or equal to r start time
		while(i < size && comparator.compare(res, r) <= 0){
			if(res.equals(r))
				return res;
			i++;
			res = get(i);
		}
		
		throw new IllegalArgumentException("There is no reservation " + r + " on the list");
	}
	
	private int bisection(long startTime, int leftIdx, int rightIdx){

		// 4 elements can be iterated by for loop
		if((rightIdx - leftIdx) < 4)
			return leftIdx;
		
		long first_startTime = get(leftIdx).getStartMillis();
		long last_startTime = get(rightIdx).getStartMillis();
		
		if(startTime < first_startTime){
			int idx = leftIdx;
			while(idx > 0 && startTime < get(idx).getStartMillis())
				idx--;
			return idx;
		}
		
		/* measure distance between new reservation start time and 
		 * both ends of the reservations list
		 */
		long delta_f = startTime - first_startTime;
		long delta_l = last_startTime - startTime;

		int middleIdx = leftIdx + ((rightIdx - leftIdx)/2);
		
		/* choose the correct half of the reservation list,
		 * where "correct" means this one, which end is closer
		 * to the new reservation start time
		 */
		if(delta_f < delta_l){
			return bisection(startTime, leftIdx, middleIdx + 1);
		} else {
			return bisection(startTime, middleIdx - 1, rightIdx);
		}
		
	}
	
	protected int findPositionFor(Reservation r){
		long startTime = r.getStartMillis();
		boolean trace = false;
		
		int size = size();
		int i = bisection(startTime, 0, size - 1);
		if(trace)
			log.debug("asdfgh: " + r.getStart() + " " + r.getId() + " " + i);
		while(i < size && comparator.compare(get(i), r) < 1){
			i++;
		}
		
		if(trace) {
			log.debug("asdfgh: " + r.getId() + " " + i);
			for(int j = 0; j < size(); j++){
				Reservation lr = get(j);
				log.debug("asdfgh: "+ j +".\t" + lr.getStart() + " id=" + lr.getId() + " jobId="+ lr.getJobId());
			}
		}
		
		return i;
	}
	
	/**
	 * Creates reservation for requested time resource allocation 
	 * @param key
	 * @param resourceUsage
	 * @return reservation
	 */
	public Reservation add(TimeResourceAllocation resourceUsage, Status status){
		throw new RuntimeException("This method is not implemented");
	}
	
	public void add(int i, Reservation r){
		super.add(i, r);
		log.warn("Using this method may violate order of the reservations.");
	}
	
	public boolean addAll(Collection<? extends Reservation> c){
		Iterator<? extends Reservation> itr = c.iterator();
		while(itr.hasNext()){
			this.add(itr.next());
		}
		return true;
	}
	
	public boolean addAll(int i, Collection<? extends Reservation> c){
		boolean ret = super.addAll(c);
		log.warn("Using this method may violate order of the reservations.");
		return ret;
	}
	
	
	public TimeResourceAllocation findInterval(TimeResourceAllocation timeSlot, long interval, int size) {
		throw new RuntimeException("Not implemented");
		/*if (timeSlot.getEndTimeInMillis() <= timeSlot.getStartTimeInMillis()
				|| interval == 0 || timeSlot.getDurationInMillis() < interval)
			return null;
		LinkedHashSet<Long> timestampsSet = createTimestampsSet();
		TreeMap<Long, Integer> calendar = createCalendar(timestampsSet);
		if(calendar.size()==0){
			return new TimeSlot(timeSlot.getStartTimeInMillis(), timeSlot.getStartTimeInMillis() + interval);
		}
		Date availableStartDate = getAvailableStartDate(calendar, timeSlot
				.getStartTime().getTime(), timeSlot.getEndTime().getTime(),
				interval, size);
		if (availableStartDate == null)
			return null;
		TimeSlot availableTimeSlot = new TimeSlot(availableStartDate.getTime(),
				availableStartDate.getTime() + interval);
		return availableTimeSlot;
		*/
	}
	
	protected class ReservationComparator implements Comparator<Reservation>{

		public int compare(Reservation o1, Reservation o2) {
			long start1 = o1.getStart().getMillis();
			long start2 = o2.getStart().getMillis();

			if(start1 < start2)
				return -1;
			
			if(start1 > start2)
				return 1;
			
			return 0; 
		}
		
	}
}