Theatre.java 改
import java.util.ArrayList;
import java.util.Collection;public class Theatre {
private final String theatreName;
// private List<Seat> seats = new ArrayList<>();
private Collection<Seat> seats = new ArrayList<>();
// private Collection<Seat> seats = new LinkedList<>();
// private Collection<Seat> seats = new HashSet<>();
// private Collection<Seat> seats = new LinkedHashSet<>();
// private Collection<Seat> seats = new TreeSet<>(); // not work
public Theatre(String theatreName, int numRows, int seatsPerRow) {
this.theatreName = theatreName; int lastRow = 'A' + (numRows - 1);
for (char row = 'A'; row <= lastRow; row++) {
for (int seatNum = 1; seatNum <= seatsPerRow; seatNum++) {
Seat seat = new Seat(row + String.format("%02d", seatNum));
seats.add(seat);
}
}
} public String getTheatreName() {
return theatreName;
} public boolean reserveSeat(String seatNumber) {
Seat requestSeat = null;
int count = 0;
for (Seat seat : seats) {
System.out.print(".");
count++;
if (seat.getSeatNumber().equals(seatNumber)) {
requestSeat = seat;
break;
}
} if (requestSeat == null) {
System.out.println("There is no seat " + seatNumber);
return false;
}
System.out.println("Count: " + count );
return requestSeat.reserve();
} // for testing
public void getSeats() {
for (Seat seat : seats) {
System.out.println(seat.getSeatNumber());
}
} private class Seat {
private final String seatNumber;
private boolean reserved = false; public Seat(String seatNumber) {
this.seatNumber = seatNumber;
} public boolean reserve() {
if (!reserved) {
reserved = true;
System.out.println("Seat " + seatNumber + " reserved.");
return true;
} else {
return false;
} } public boolean cancel() {
if (reserved) {
reserved = false;
System.out.println("Reservation of seat " + seatNumber + "cancelled");
return true;
} else {
return false;
} } public String getSeatNumber() {
return seatNumber;
}
}
}
MainTheatre.java 改
public class MainTheatre {
public static void main(String[] args) {
Theatre theatre = new Theatre("Muzha Guangming", 8, 10);
// theatre.getSeats();
if (theatre.reserveSeat("E05")) {
System.out.println("Okay, this seat is yours, one seat is $1");
} else {
System.out.println("Sorry, this seat is sold out already.");
}
if (theatre.reserveSeat("E05")) {
System.out.println("Okay, this seat is yours, one seat is $1");
} else {
System.out.println("Sorry, this seat is sold out already.");
}
}}
輸出結果：
………………………………………Count: 45
Seat E05 reserved.
Okay, this seat is yours, one seat is $1
………………………………………Count: 45
Sorry, this seat is sold out already.
展示了找到位置要花幾次搜尋
Theatre.java 改
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class Theatre {
private final String theatreName;
private List<Seat> seats = new ArrayList<>();
public Theatre(String theatreName, int numRows, int seatsPerRow) {
this.theatreName = theatreName; int lastRow = 'A' + (numRows - 1);
for (char row = 'A'; row <= lastRow; row++) {
for (int seatNum = 1; seatNum <= seatsPerRow; seatNum++) {
Seat seat = new Seat(row + String.format("%02d", seatNum));
seats.add(seat);
}
}
} public String getTheatreName() {
return theatreName;
} public boolean reserveSeat(String seatNumber) {
Seat requestSeat = new Seat(seatNumber);
int foundSeat = Collections.binarySearch(seats, requestSeat, null);
if(foundSeat>=0){
return seats.get(foundSeat).reserve();
}else {
System.out.println("There is no seat " + seatNumber);
return false;
}
// int count = 0;
// for (Seat seat : seats) {
// System.out.print(".");
// count++;
// if (seat.getSeatNumber().equals(seatNumber)) {
// requestSeat = seat;
// break;
// }
// }
//
// if (requestSeat == null) {
// System.out.println("There is no seat " + seatNumber);
// return false;
// }
// System.out.println("Count: " + count);
// return requestSeat.reserve();
} // for testing
public void getSeats() {
for (Seat seat : seats) {
System.out.println(seat.getSeatNumber());
}
} private class Seat implements Comparable<Seat> {
private final String seatNumber;
private boolean reserved = false; public Seat(String seatNumber) {
this.seatNumber = seatNumber;
} @Override
public int compareTo(Seat seat) {
// if smaller return < 0, bigger return > 0, equal return 0
return this.seatNumber.compareToIgnoreCase(seat.getSeatNumber());
} public boolean reserve() {
if (!reserved) {
reserved = true;
System.out.println("Seat " + seatNumber + " reserved.");
return true;
} else {
return false;
} } public boolean cancel() {
if (reserved) {
reserved = false;
System.out.println("Reservation of seat " + seatNumber + "cancelled");
return true;
} else {
return false;
} } public String getSeatNumber() {
return seatNumber;
}
}
}
輸出結果：
Seat E05 reserved.
Okay, this seat is yours, one seat is $1
Sorry, this seat is sold out already.
使用 Binary Search 來減少搜尋次數
BinarySearch is one of the fastest algorithms developed to find an element in a collection. But there is one drawback, BinarySearch algorithm expects the Collection in which you are going to search an element in, to be sorted.
- Assume you want to search for a Seat with the seat number 716.
- You have Theatre object which has over 10.000 seats in a random order.
- For BinarySearch to find seat with the number 716 in your Theatre with 10.000 seats, your Theatre seats MUST all be sorted before hand. If you want to search by seat number, your Theatre seats should be sorted by seat number.
- Your Theatre seats may already be sorted in correct order, but BinarySearch doesn’t know that. That’s why we give it a Comparable object so it can sort it first (if not already sorted), then look for your desired element.
Theatre.java 改
import java.util.ArrayList;
import java.util.List;public class Theatre {
private final String theatreName;
private List<Seat> seats = new ArrayList<>();
public Theatre(String theatreName, int numRows, int seatsPerRow) {
this.theatreName = theatreName; int lastRow = 'A' + (numRows - 1);
for (char row = 'A'; row <= lastRow; row++) {
for (int seatNum = 1; seatNum <= seatsPerRow; seatNum++) {
Seat seat = new Seat(row + String.format("%02d", seatNum));
seats.add(seat);
}
}
} public String getTheatreName() {
return theatreName;
} public boolean reserveSeat(String seatNumber) {
int low = 0;
int high = seats.size() - 1;
int count = 0;
while (low <= high) {
System.out.print(".");
count++;
int mid = (low + high) / 2;
Seat midVal = seats.get(mid);
int cmp = midVal.getSeatNumber().compareTo(seatNumber); if (cmp < 0) {
low = mid + 1;
} else if (cmp > 0) {
high = mid - 1;
} else {
System.out.println("Count :" + count);
return seats.get(mid).reserve();
}
}
System.out.println("There is no seat " + seatNumber);
return false;
} // for testing
public void getSeats() {
for (Seat seat : seats) {
System.out.println(seat.getSeatNumber());
}
} private class Seat implements Comparable<Seat> {
private final String seatNumber;
private boolean reserved = false; public Seat(String seatNumber) {
this.seatNumber = seatNumber;
} @Override
public int compareTo(Seat seat) {
// if smaller return < 0, bigger return > 0, equal return 0
return this.seatNumber.compareToIgnoreCase(seat.getSeatNumber());
} public boolean reserve() {
if (!reserved) {
reserved = true;
System.out.println("Seat " + seatNumber + " reserved.");
return true;
} else {
return false;
} } public boolean cancel() {
if (reserved) {
reserved = false;
System.out.println("Reservation of seat " + seatNumber + "cancelled");
return true;
} else {
return false;
} } public String getSeatNumber() {
return seatNumber;
}
}
}
輸出結果：
….Count :4
Seat E05 reserved.
Okay, this seat is yours, one seat is $1
….Count :4
Sorry, this seat is sold out already.
這次不用系統預設的二分樹
造了同樣的輪子，寫了同樣的邏輯，為了用 . 展示次數
使用之後，變成只要四次就搜尋到了