/*
  Model solution to the G52CON coursework (2008/2009), unsynchronized version.
*/

import java.util.*;

// Records the information for a single booking of a particular room.
class SimpleBooking implements Comparable<SimpleBooking> {
    String reference; 
    int[] days;
    int room;
   
    SimpleBooking(String reference, int[] days, int room) {
	Arrays.sort(days);

	this.reference = reference;
	this.days = days;
	this.room = room;
    }

    // We assume that the days for each booking are in ascending order, and
    // order bookings by the earliest (i.e. first) day in the booking
    public int compareTo(SimpleBooking otherBooking) {
        if (this.days[0] < otherBooking.days[0]) return -1;
        if (otherBooking.days[0] < this.days[0]) return 1;
	// Ensure the order is consistent with equals.  This isn't strictly
	// necessary, since we should never have two bookings for the same
	// room which have the same start date (or any date).
        return this.reference.compareTo(otherBooking.reference);
    }

}

public class Hotel {

    // Mapping from room number to a list of bookings for this room.
    protected HashMap<Integer, TreeSet<SimpleBooking>> rooms =
	new HashMap<Integer, TreeSet<SimpleBooking>>(); 

    // Mapping from booking reference to booking object for this booking.
    protected HashMap<String, SimpleBooking> bookings =
	new HashMap<String, SimpleBooking>();

    /** Constructs a hotel with room numbers as specified in roomNums.  
	The rooms are initially unbooked. */

    public Hotel(int[] roomNums) {
	// Initialise the rooms map.
	for (int i = 0; i < roomNums.length; i++) {
	    rooms.put(roomNums[i], new TreeSet<SimpleBooking>());
	}
    }

    /** Returns true if the room roomNum is booked on any of the days 
	specified in days, otherwise returns false. */

    boolean roomBooked(int[] days, int roomNum) {
	Arrays.sort(days);
	// TreeSet iterator returns bookings for this room ordered by the
	// earliest day in the booking.
	Iterator<SimpleBooking> it = (rooms.get(roomNum)).iterator();
        while(it.hasNext()) {
	    SimpleBooking booking = it.next();
	    int[] when = booking.days;
	    // If the last day of this booking is before the first day of
	    // the new booking, skip it.
	    if (when[when.length - 1] < days[0]) continue;
	    // If the first day of this booking is after the last day of the
	    // new booking, the room is free.
	    if (when[0] > days[days.length - 1]) {
		return false;
	    } else {
		// The bookings may intersect.
		for (int j = 0; j < days.length; j++) {
		    for (int k = 0; k < when.length; k++) {
			if (days[j] == when[k]) {
			    return true;
			}
		    }
		}
	    }
        }
	return false;
    }

    /** Create a booking with reference bookingRef for the room roomNum 
	for each of the days specified in days. Returns true if it is possible
	to book the room on the given days, otherwise (if the room is booked
	on any of the specified days) returns false. */

    boolean bookRoom(String bookingRef, int[] days, int roomNum) {
	// Check if the room is already booked on the requested days.
	if (roomBooked(days, roomNum)) {
	    return false;
	} else {
	    // Add the new booking to the current bookings.
	    SimpleBooking booking = new SimpleBooking(bookingRef, days, roomNum);
	    bookings.put(bookingRef, booking);
	    (rooms.get(roomNum)).add(booking);
	} 
	return true;
    }

    /** Updates the booking with reference bookingRef so that it now refers
        to the specified roomNum for each of the days specified in days.
        The previous booking under this booking reference is cancelled. If
        there is no booking with the specified reference throws
        NoSuchBookingException. */

    boolean updateBooking(String bookingRef, int[] days, int roomNum) throws
	NoSuchBookingException {
	SimpleBooking booking = bookings.get(bookingRef);
	if (booking == null) throw new NoSuchBookingException(bookingRef);

	Arrays.sort(days);
	// TreeSet iterator returns bookings for this room ordered by the
	// earliest day in the booking.
	Iterator<SimpleBooking> it = (rooms.get(roomNum)).iterator();
	while(it.hasNext()) {
	    SimpleBooking otherBooking = it.next();
	    // If this booking is the one we are updating, skip it.
	    if (otherBooking == booking) continue;
	    int[] when = otherBooking.days;
	    // If the last day of this booking is before the first day of
	    // the new booking, skip it.
	    if (when[when.length - 1] < days[0]) continue;
	    // If the first day of this booking is after the last day of the
	    // new booking, the room is free.
	    if (when[0] > days[days.length - 1]) {
		break;
	    } else {
		// The bookings may intersect.
		for (int j = 0; j < days.length; j++) {
		    for (int k = 0; k < when.length; k++) {
			if (days[j] == when[k]) {
			    return false;
			}
		    }
		}
	    }
	}

	// If the new booking is for a different room, remove the booking
	// from the list of bookings for the previous room and add it to the
	// list for this room.
	if (booking.room != roomNum) {
	    (rooms.get(booking.room)).remove(booking); 
	    (rooms.get(roomNum)).add(booking); 
	}	    

	// Update the booking.
	booking.days = days;
	booking.room = roomNum;
	return true;
    }
    
    /** Cancel the booking with reference bookingRef. The room booked under
	this booking reference becomes unbooked for the days of the
	booking. If there is no booking with the specified reference throws
	NoSuchBookingException. */

    void cancelBooking(String bookingRef) throws NoSuchBookingException {
	SimpleBooking booking = bookings.get(bookingRef);
	if (booking == null) throw new NoSuchBookingException(bookingRef);

	// Remove the booking from the bookings table and the list of
	// bookings for this room.
	bookings.remove(bookingRef);
	(rooms.get(booking.room)).remove(booking); 
    }
}