/*
  Model solution to the G52CON coursework (2008/2009), read-write lock
  version.
*/

import java.util.*;
import java.util.concurrent.locks.*;

// Records a single booking of one or more rooms.
class Booking implements Comparable<Booking> {
    String reference; 
    int[] days;
    int[] rooms;
   
    Booking(String reference, int[] days, int[] rooms) {
	Arrays.sort(days);
	Arrays.sort(rooms);

	this.reference = reference;
	this.days = days;
	this.rooms = rooms;
    }

    // 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(Booking 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<Booking>> rooms =
	new HashMap<Integer, TreeSet<Booking>>(); 

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

    /** ReadWriteLock to control access to the hotel. */

    private ReadWriteLock rwl = new ReentrantReadWriteLock();
    private Lock rl = rwl.readLock();
    private Lock wl = rwl.writeLock();

    /** 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<Booking>());
	}
    }

    /** Return the list of bookings for a particular room. */
    private TreeSet<Booking> roomBookings(int roomNum) {
	return rooms.get(roomNum);
    }

    /** Factor out the actual work of checking if a group of rooms is booked
        so that we don't need to acquire a read lock while holding a write
        lock. */

    private boolean checkBooking(int[] days, int[] roomNums) {
	Arrays.sort(days);
	for (int i = 0; i < roomNums.length; i++) {
	    // TreeSet iterator returns bookings for this room ordered by
	    // the earliest day in the booking.
	    Iterator<Booking> it = roomBookings(roomNums[i]).iterator();
	    while(it.hasNext()) {
		Booking booking = it.next();
		int[] bookedDays = booking.days;
		// If the last day of this booking is before the first day
		// of the new booking, skip it.
		if (bookedDays[bookedDays.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 (bookedDays[0] > days[days.length - 1]) 
		    break;
		else {
		    // The bookings may intersect.
		    int s = 0;
		    for (int j = 0; j < days.length; j++)
			for (int k = s;
			     k < bookedDays.length && bookedDays[k] <= days[j];
			     k++, s++) 
			    if (days[j] == bookedDays[k]) return true;
		}
	    }
	}
	return false;
    }

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

    public boolean roomBooked(int[] days, int roomNum) {
	return roomsBooked(days, new int[] { roomNum });
    }

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

    public boolean roomsBooked(int[] days, int[] roomNums) {
	Arrays.sort(days);
	rl.lock();
	try {
	    return checkBooking(days, roomNums);
	} finally {
	    rl.unlock();
	}
    }

    /** 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. */

    public boolean bookRoom(String bookingRef, int[] days, int roomNum) {
	return bookRooms(bookingRef, days, new int[] { roomNum });
    }

    /** Create a booking with reference bookingRef for the rooms in roomNums
        for each of the days specified in days. Returns true if it is
        possible to book the rooms on the given days, otherwise returns
        false. */

    public boolean bookRooms(String bookingRef, int[] days, int[] roomNums) {
	wl.lock();
	try {
	    // Check if any of the rooms are already booked on the requested
	    // days.
	    if (checkBooking(days, roomNums)) 
		return false;
	    else {
		// Add the new booking to the current bookings.
		Booking booking = new Booking(bookingRef, days, roomNums);
		bookings.put(bookingRef, booking);
		for (int i = 0; i < roomNums.length; i++) 
		    roomBookings(roomNums[i]).add(booking);
	    } 
	    return true;

	} finally {
	    wl.unlock();
	}
    }

    /** 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. */

    public boolean updateBooking(String bookingRef, int[] days, int roomNum)
      throws NoSuchBookingException {
	return updateBooking(bookingRef, days, new int[] { roomNum });
    }
    
    /** Updates the booking with reference bookingRef so that it now refers
        to the specified roomNums for each of the days specified in
        days. Returns true if it is possible to update the booking (i.e.,
        the new booking does not clash with an existing booking), otherwise
        returns false and leaves the original booking unchanged. If there is
        no booking with the specified reference throws
        NoSuchBookingException. */

    public boolean updateBooking(String bookingRef, int[] days, int[] roomNums) 
      throws NoSuchBookingException {
	wl.lock();
	try {
	    Booking booking = bookings.get(bookingRef);
	    if (booking == null) throw new NoSuchBookingException(bookingRef);
	    
	    Arrays.sort(days);
	    for (int i = 0; i < roomNums.length; i++) {
		// TreeSet iterator returns bookings for this room ordered
		// by the earliest day in the booking.
		Iterator<Booking> it = roomBookings(roomNums[i]).iterator();
		while(it.hasNext()) {
		    Booking otherBooking = it.next();
		    // If this booking is the one we are updating, skip it.
		    if (otherBooking == booking) continue;
		    int[] bookedDays = otherBooking.days;
		    // If the last day of this booking is before the first
		    // day of the new booking, skip it.
		    if (bookedDays[bookedDays.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 (bookedDays[0] > days[days.length - 1]) 
			break;
		    else {
			// The bookings may intersect.
			int s = 0;
			for (int j = 0; j < days.length; j++) 
			    for (int k = s;
				 k < bookedDays.length && bookedDays[k] <= days[j];
				 k++, s++) 
				if (days[j] == bookedDays[k]) return false;
		    }
		}
	    }
	    
	    // Remove the booking from the list of bookings for any room not
	    // booked by the new booking and add it to the list for any room
	    // which was not previously booked.
	    HashSet<Integer> oldRooms = new HashSet<Integer>();
	    for (int i = 0; i < booking.rooms.length; i++) 
		oldRooms.add(booking.rooms[i]);
	    HashSet<Integer> newRooms = new HashSet<Integer>();
	    for (int i = 0; i < roomNums.length; i++) 
		newRooms.add(roomNums[i]);

	    HashSet<Integer> unbooked = new HashSet<Integer>(oldRooms);
	    unbooked.removeAll(newRooms);
	    for (Iterator<Integer> i = unbooked.iterator(); i.hasNext(); )
		(rooms.get(i.next())).remove(booking);

	    HashSet<Integer> newbooked = new HashSet<Integer>(newRooms);
	    newbooked.removeAll(oldRooms);
	    for (Iterator<Integer> i = newbooked.iterator(); i.hasNext(); )
		(rooms.get(i.next())).add(booking);

	    // Update the booking.
	    booking.days = days;
	    booking.rooms = roomNums;
	    return true;

	} finally {
	    wl.unlock();
	}
    }
    
    /** Cancels the booking with reference bookingRef.  All the rooms booked
        under this booking reference become unbooked for the days of the
        booking. If there is no booking with the specified reference throws
        NoSuchBookingException. */

    public void cancelBooking(String bookingRef) throws NoSuchBookingException {
	wl.lock();
	try {
	    Booking booking = bookings.get(bookingRef);
	    if (booking == null) throw new NoSuchBookingException(bookingRef);

	    // Remove the booking from the bookings table and the lists of
	    // bookings for each room.
	    bookings.remove(bookingRef);
	    for (int i = 0; i < booking.rooms.length; i++)
		roomBookings(booking.rooms[i]).remove(booking);
	} finally {
	    wl.unlock();
	}
    }
}