source: xssim/trunk/src/schedframe/scheduling/ReservationList.java @ 104

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; 
                }
                
        }
}