(1)　生徒が席を使用するときは受付で申請し，割り当てられた席を使用する。 使用終了時には，受付に届ける。

(2)　空席がないときに使用希望者がある場合は， １時間を超えて最も長く使用している者が使用希望者のために席を空けなければならない。 空席がなく，１時間を超えて使用している者がいない場合，使用希望者は席を使用できない。

(3)　１人で同時に複数の席を使用することはできない。

この運用規則に従った自習席管理を支援するためのプログラムを，次のように設計した。

(1)　図に示す双方向リストを実装するためのクラス ListElement を定義する。 双方向リストは環状にし，要素の挿入・削除処理で終端を特別扱いしないようにする。 ListElement は，リストのヘッド（先頭）と要素の両方を表現する。 ListElement では，次のメソッドを実装する。

SnextElement

　　この ListElement インスタンスの次の要素を返す。

SpreviousElement

　　この ListElement インスタンスの前の要素を返す。

SinsertBefore

　　この ListElement インスタンスを，引数で指定された要素の前に挿入する。

Sremove

　　この ListElement インスタンスをリストから削除する。

　　図　空のときと要素があるときの双方向リストの状態

(2)　席は，ListElement を拡張したクラス Seat で表す。 各席に座席番号が割り振られる。

(3)　クラス SeatManager で，運用規則を実現するためのメソッドを実装する。

(4)　空席，使用中の席のリストを，それぞれ freeSeats，occupiedSeats とする。 Seat のインスタンスが各リストの要素となる。

(5)　使用中の席は，occupiedSeats に登録する。 リストは使用時間が短いものから長いものへと並ぶように管理する。

(6)　SeatManager では，次の public メソッドを実装する。

Scheckin

　　引数で指定された使用希望者が既に席を使用中でないことを確認する。 freeSeats（空席リスト）に空きがあればその席を， なければ１時間を超えて使われている席を使用希望者に割り当てる。 割り当てられた席を occupiedSeats（使用中リスト）の最初の要素として登録し， その Seat インスタンスを返す。 使用できる席がなければ null を返す。

Scheckout

　　引数で指定された使用者が使っていた席を occupiedSeats から削除して freeSeats へ戻し， true を返す。 指定された使用者が occupiedSeats に見つからないときは false を返す。

最初に，クラス ListElement 及びクラス Seat を実装して単体テストを行い， 正しく動作することを確認した。 次に，クラス SeatManager を実装してテストしたところ， １人で同時に複数の席が使用できるという不具合が見つかった。 それ以外は，正常に動作することを確認した。

〔プログラム 1〕

public class ListElement {
    private ListElement prev, next;
    public ListElement() {
        prev = next = this;
    }
    public ListElement nextElement() { return next; }
    public ListElement previousElement() { return prev; }
    public void insertBefore(ListElement element) {
        next = element;
        prev = element.prev;
        next.prev = prev.next = ;
    }
    public void remove() {
         = next;
         = prev;
        prev = next = this;
    }
}

〔プログラム 2〕

public class Seat extends ListElement {
    private String userID;     // 使用者
    private long checkinTime;  // 使用開始時刻
    private int seatNumber;    // 座席番号
    public Seat(int seatNumber) {
        this.seatNumber = seatNumber;
    }
    public int getSeatNumber() {
        return seatNumber;
    }
    public String getUserID() {
        return userID;
    }
    public void setUserID(String userID) {
        this.userID = userID;
    }
    public boolean isUsedBy(String userID) {
        return this.userID.equals(userID);
    }
    public long getCheckinTime() {
        return checkinTime;
    }
    public void setCheckinTime(long time) {
        checkinTime = time;
    }
}

〔プログラム 3〕

public class SeatManager {
    private static final int NSEATS = 30;  // 席数
    // 最大使用時間〔ミリ秒〕
    private static final int MAXTIME = 60 * 60 * 1000;
    // 空席リスト
    private ListElement freeSeats = new ListElement();
    // 使用中リスト
    private ListElement occupiedSeats = new ListElement();
    public SeatManager() {
        for (int i = 1; i <= NSEATS; i++) {
            Seat seat = new Seat(i);
            seat.insertBefore(freeSeats);
        }
    }
    // 空席リストに空席があればその Seat インスタンスを空席リストから
    // 削除し，そのインスタンスを返す。空きがなければ null を返す。
    private Seat getFreeSeat() {
        ListElement le = freeSeats.nextElement();
        if (le != freeSeats) {
            le.remove();
            return (Seat) le;
        }
        return null;
    }
    // 使用中リストを調べ，最大使用時間を超えて席を使用している
    // 使用者がいれば，その旨出力し，checkout を呼ぶ。
    private void vacateExpiredSeat(long time) {
        ListElement le = ;
        if (le != occupiedSeats) {
            Seat seat = (Seat) le;
            if ((seat.getCheckinTime() + MAXTIME) < time) {
               System.out.println("Seat#" + 
                                  seat.getSeatNumber() + " " +
                                  seat.getUserID() + 
                                  " must check out.");
               checkout(seat.getUserID());
            }
        }
    }
    // 使用中リストから指定された使用者が使っている席を探し，見つかれば
    // その席を，見つからなければ null を返す。
    private Seat findUser(String userID) {
        ListElement le = ;
        while (le != occupiedSeats) {
            Seat seat = (Seat) le;
            if (seat.isUsedBy(userID)) {
                return seat;
            }
            le = le.nextElement();
        }
        return null;
    }
    public Seat checkin(String userID) {
        long now = System.currentTimeMillis();
        Seat seat = getFreeSeat();
        if (seat == null) {
            vacateExpiredSeat(now);
            seat = getFreeSeat();
        }
        if (seat != null) {
            seat.setCheckinTime(now);
            seat.setUserID(userID);
            seat.insertBefore(occupiedSeats.nextElement());
        }
        return seat;
    }
    public boolean checkout(String userID) {
        Seat seat = findUser(userID);
        if (seat != null) {
            seat.remove();
            seat.setUserID(null);
            seat.insertBefore(freeSeats);
            return true;
        }
        return false;
    }
}

ア　element　　　　　　イ　element.next　　　　　　ウ　element.prev

エ　new ListElement()　　　　オ　next　　　　　　カ　next.prev

キ　null　　　　　　　ク　prev　　　　　　ケ　prev.next

コ　this

ア　freeSeats

イ　freeSeats.nextElement()

ウ　freeSeats.previousElement()

エ　occupiedSeats

オ　occupiedSeats.nextElement()

カ　occupiedSeats.previousElement()

ア　メソッド checkin で，席の割当て処理をする前に occupiedSeats を調べ， もしこの使用希望者が既に他の席を使用中であればエラーとし，席の割当て処理を行わない。

イ　メソッド checkout で，使用を終了した席が occupiedSeats から 正しく削除されていないので，occupiedSeats から使用を終了した席を正しく削除する。

ウ　メソッド vacateExpiredSeat で，最大使用時間（MAXTIME）を超えて席を 使用している者を強制的にチェックアウトさせるために，メソッド checkout を呼び出している。 その直後に，その使用者の使っていた席を occupiedSeats から削除する処理を追加する。