/*
  Model solution to the G52CON coursework (2008/2009), fine-grained
  version.

  Assumes that booking references are unique, i.e., bookRooms never
  updates a previous booking, even if the booking has been cancelled.
*/

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

// Records a list of bookings for a single room.
class BookingList {

    /** ReadersWriters to control access to the booking list. */
    protected ReadWriteLock rwl = new ReentrantReadWriteLock();
    protected Lock rl = rwl.readLock();
    protected Lock wl = rwl.writeLock();

    /** Bookings for this room. */
    protected TreeSet<Booking> bookings =  new TreeSet<Booking>();

    /** Add a booking to the list of bookings for this room. */
    protected boolean add(Booking booking) { return bookings.add(booking); }

    /** Remove a booking from the list of bookings for this room. */
    protected boolean remove(Booking booking) { return bookings.remove(booking); }

    /** Return an interator over the bookings. */
    protected Iterator<Booking> iterator() { return bookings.iterator(); }
}

public class Hotel {

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

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

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

    /** Return the list of bookings for a particular room. */
    private BookingList 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(roomNums);
	// Acquire read locks on the booking lists for all the rooms
	for (int i = 0; i < roomNums.length; i++) 
	    roomBookings(roomNums[i]).rl.lock();
	try {
	    // Check if any of the rooms are booked
	    return checkBooking(days, roomNums);
	} finally {
	    for (int i = roomNums.length - 1; i >= 0; i--)
		roomBookings(roomNums[i]).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) {
	Arrays.sort(roomNums);
	// Acquire write locks on the booking lists for all the rooms
	for (int i = 0; i < roomNums.length; i++) 
	    roomBookings(roomNums[i]).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);
		for (int i = 0; i < roomNums.length; i++) 
		    roomBookings(roomNums[i]).add(booking);
		bookings.put(bookingRef, booking);
	    } 
	    return true;

	} finally {
	    for (int i = roomNums.length - 1; i >= 0; i--) 
		roomBookings(roomNums[i]).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 {
	Booking booking = bookings.get(bookingRef);
	if (booking == null) throw new NoSuchBookingException(bookingRef);

	// Wait until any thread which already has a reference to this
	// booking and is holding the lock has finished updating or
	// cancelling the booking
	synchronized(booking) {
	    // If the booking was cancelled while we were waiting to
	    // obtain the lock, abort
	    if (booking != bookings.get(bookingRef))
		throw new NoSuchBookingException(bookingRef);

	    // Obtain write locks on both the rooms in the original
	    // booking and any additional rooms in the new booking
	    Arrays.sort(roomNums);
	    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> allRooms = new HashSet<Integer>(oldRooms);
	    allRooms.addAll(newRooms);
	    
	    for (Iterator<Integer> i = allRooms.iterator(); i.hasNext(); ) 
		roomBookings(i.next()).wl.lock();
	    try {
		// Since we can't upgrade read locks to write locks,
		// we have to check for clashes while holding write
		// locks on the rooms. Otherwise another, clashing,
		// booking could be added between checking that update
		// to the booking didn't clash and actually updating
		// it.
		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> unbooked = new HashSet<Integer>(oldRooms);
		unbooked.removeAll(newRooms);
		for (Iterator<Integer> i = unbooked.iterator(); i.hasNext(); )
		    roomBookings(i.next()).remove(booking);

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

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

	    } finally {
		Integer[] roomArray = allRooms.toArray(new Integer[0]);
		for (int i = roomArray.length - 1; i >= 0; i--) 
		    roomBookings(roomArray[i]).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 {
	// Prevent other threads obtaining a reference to this booking
	Booking booking = bookings.remove(bookingRef);
	if (booking == null) throw new NoSuchBookingException(bookingRef);

	// Wait until any thread which already has a reference to this
	// booking has finished updating it
	synchronized(booking) {
	    // Now acquire locks on the booked rooms
	    for (int i = 0; i < booking.rooms.length; i++) 
		roomBookings(booking.rooms[i]).wl.lock();
	    try {
		// Remove the booking from the lists of bookings for
		// each room
		for (int i = 0; i < booking.rooms.length; i++) 
		    roomBookings(booking.rooms[i]).remove(booking);
	    } finally {
		// Now release all room locks in reverse order
		for (int i = booking.rooms.length - 1; i >= 0; i--) 
		    roomBookings(booking.rooms[i]).wl.unlock();
	    }
	}
    }
}