JAVA-201 · Lesson 12 of 12 · 28 min
Capstone: choosing data structures for a real system
▶ Video coming soon A video version of this lesson is on the way.
ShopBook, Hamza's booking system from the Wednesday course, was demonstrated to Odile on Saturday, April 17, 2027. It handles bookings; it does not yet know anything about the parts room, the repair rack or which day each rental bike is free. The plan for the week after the demo is the capstone of this course: from Monday, April 19 to Thursday, April 22, Hamza designs and builds StockRoom, the data layer that ties the parts room, the repair rack and the rental calendar together, and on Friday, April 23 he walks Ingrid and Kofi through his choices. The aim is not a big program. It is to choose, for each need, the right structure, and to be able to say why.
The requirements
Hamza began, as JAVA-102 taught, by writing down what the program must do, in Kofi's, Tamsin's and Odile's words, and numbering each requirement so that every design choice and every check could point back to one.
| # | Requirement | Asked for by |
|---|---|---|
| R1 | Find any part by its code instantly, out of about 600 | Kofi |
| R2 | Print the parts list in order of code for the monthly stocktake | Kofi |
| R3 | List the parts at or below their reorder level, lowest stock first, then by code | Kofi |
| R4 | Hand out repair jobs by urgency, and by arrival within the same urgency | Tamsin |
| R5 | Say whether a rental bike is free between two dates, and when it is next booked | Odile |
| R6 | Show the last ten stock changes and undo the most recent one | Kofi |
| R7 | List the shelves in use, each once, in order | Kofi |
| R8 | Never let other code change the stock room's data except through its methods | Ingrid |
Thinking about each requirement
For each requirement Hamza asked the questions from lesson 2's table: is it a lookup by key, a set of unique values, a sequence, a queue or a range? What operations happen most often, and how many elements are there? The answers lead to a structure, and the table of costs from the course says whether it is good enough.
R1 is a lookup by key, done many times a day, so a HashMap<String, Part> keyed by code gives O(1) average lookups. A TreeMap would also work at O(log n), about 10 comparisons for 612 parts, but nothing about R1 needs order, so the simpler and faster map wins. Part is a record with an immutable String key, so the hash contract from lesson 5 holds.
R2 needs the parts in code order, but only once a month. Hamza considered keeping a TreeMap alongside the HashMap and rejected it: two maps must be kept in step on every change, for a printout that happens twelve times a year. Sorting a copy of the 612 values on demand costs O(n log n), a few thousand comparisons, which is nothing at this size. That is a general lesson: the cheapest structure to maintain is often a sort when you need it.
R3 is a filter and a two-level order, again on demand. Counts change all day, and a PriorityQueue or TreeSet of low parts would have to be updated, with remove and add, on every change. Filtering and sorting when Kofi asks is O(n log n) and always correct. Ingrid agreed, with one note: if the shop ever had a hundred thousand parts, or wanted the list refreshed after every sale, a structure that is kept up to date would be worth its complexity.
R4 is a classic priority queue, exactly as in lesson 11: a PriorityQueue<Job> with a comparator on urgency, then arrival number. Jobs are added and taken one at a time, and the urgent one must always be next, so O(log n) offer and poll is the right shape.
R5 is about ranges of dates, which is what TreeMap's navigation methods are for. Each bike keeps a TreeMap<LocalDate, LocalDate> from each booking's start date to its end date. Bookings for one bike never overlap, so to check a range from one date to another, look at the booking that starts on or before the last date, using floorEntry: the range is free if there is none, or if that booking ends before the range begins. That is one O(log n) step.
R6 is a bounded history, newest first, with undo from the newest end: a stack that forgets its oldest entries. An ArrayDeque used as a stack with push and pop, plus removeLast whenever it grows past ten, does exactly that in O(1). R7 is a set of unique values in order, a TreeSet<String>. R8 is met by never returning a field directly, only unmodifiable views or copies.
The data structures chosen
| Req. | Structure | Key operations | Cost | Rejected alternative |
|---|---|---|---|---|
| R1 | HashMap<String, Part> | get, put | O(1) average | list search, O(n) |
| R2 | sort a copy when asked | values, sort | O(n log n), monthly | a second TreeMap kept in step |
| R3 | filter and sort when asked | loop, sort | O(n log n), on demand | a PriorityQueue updated on every change |
| R4 | PriorityQueue<Job> | offer, poll | O(log n) | ArrayDeque, which ignores urgency |
| R5 | TreeMap<LocalDate, LocalDate> per bike | floorEntry, ceilingEntry | O(log n) | a list of bookings, O(n) per check |
| R6 | ArrayDeque as a bounded stack | push, pop, removeLast | O(1) | java.util.Stack, ArrayList with remove(0) |
| R7 | TreeSet<String> | add, iterate | O(n log n) to build | HashSet, which has no order |
| R8 | unmodifiable views | Collections.unmodifiable* | O(1) to wrap | returning the fields directly |
The program
Hamza's StockRoom prototype keeps the three parts of the problem in three small classes, each owning its structures privately. Part is an immutable record: a change of count makes a new Part with withCount, so there is never a stale copy in the map. The main method acts as a set of checks, one line per requirement, so the output can be read against the table above.
import java.time.LocalDate;
import java.util.*;
public class Main {
public static void main(String[] args) {
StockRoom room = new StockRoom();
room.addPart(new Part("TUBE-700x25", "700x25c inner tube", "B-07", 14, 10));
room.addPart(new Part("PAD-ROAD", "brake pads, road", "B-14", 6, 8));
room.addPart(new Part("CHAIN-11", "chain, 11-speed", "C-03", 4, 4));
room.addPart(new Part("BELL", "bell, brass", "A-02", 9, 4));
room.addPart(new Part("CABLE-BRAKE", "brake cable", "C-03", 2, 6));
System.out.println("R1 lookup: " + room.find("PAD-ROAD"));
room.use("TUBE-700x25", 5);
room.use("BELL", 1);
room.receive("CABLE-BRAKE", 10);
System.out.println("R2 printout: " + room.printout());
System.out.println("R3 reorder: " + room.toReorder());
System.out.println("R6 recent: " + room.recentChanges());
System.out.println("R6 undo: " + room.undo() + " -> " + room.find("CABLE-BRAKE"));
System.out.println("R7 shelves: " + room.shelvesInUse());
RepairRack rack = new RepairRack();
rack.add("Mei Lin, tune-up", Urgency.ROUTINE);
rack.add("Ana Ruiz, flat tire", Urgency.NEEDED_TOMORROW);
rack.add("rental Cargo 1, snapped spoke", Urgency.RENTAL_DAMAGE);
rack.add("Theo Park, brake cable", Urgency.NEEDED_TOMORROW);
System.out.println("R4 next jobs: " + rack.next() + "; " + rack.next() + "; " + rack.next());
Rentals cargo = new Rentals("Cargo 1");
cargo.book(LocalDate.of(2027, 5, 1), 2, "Ana Ruiz");
cargo.book(LocalDate.of(2027, 5, 8), 3, "Theo Park");
System.out.println("R5 free May 3 to 7? " + cargo.isFree(LocalDate.of(2027, 5, 3), LocalDate.of(2027, 5, 7)));
System.out.println("R5 free May 6 to 9? " + cargo.isFree(LocalDate.of(2027, 5, 6), LocalDate.of(2027, 5, 9)));
System.out.println("R5 next after May 4: " + cargo.nextBookingAfter(LocalDate.of(2027, 5, 4)));
try {
room.printoutView().add(null);
} catch (UnsupportedOperationException e) {
System.out.println("R8 views are read-only");
}
}
}
record Part(String code, String name, String shelf, int count, int reorderAt) {
Part withCount(int c) { return new Part(code, name, shelf, c, reorderAt); }
@Override public String toString() { return code + ":" + count; }
}
class StockRoom {
private final Map<String, Part> byCode = new HashMap<>();
private final Deque<String[]> history = new ArrayDeque<>();
private static final int HISTORY = 10;
void addPart(Part p) { byCode.put(p.code(), p); }
Part find(String code) {
Part p = byCode.get(code);
if (p == null) throw new NoSuchElementException("no part " + code);
return p;
}
void use(String code, int n) { change(code, -n); }
void receive(String code, int n) { change(code, n); }
private void change(String code, int delta) {
Part p = find(code);
if (p.count() + delta < 0) throw new IllegalArgumentException("only " + p.count() + " of " + code);
byCode.put(code, p.withCount(p.count() + delta));
history.push(new String[] {code, String.valueOf(delta)});
if (history.size() > HISTORY) history.removeLast();
}
String undo() {
String[] last = history.pop();
Part p = find(last[0]);
byCode.put(last[0], p.withCount(p.count() - Integer.parseInt(last[1])));
return "undid " + last[0] + " " + last[1];
}
List<String> recentChanges() {
List<String> out = new ArrayList<>();
for (String[] h : history) out.add(h[0] + " " + h[1]);
return out;
}
List<Part> printout() {
List<Part> list = new ArrayList<>(byCode.values());
list.sort(Comparator.comparing(Part::code));
return list;
}
List<Part> printoutView() { return Collections.unmodifiableList(printout()); }
List<Part> toReorder() {
List<Part> low = new ArrayList<>();
for (Part p : byCode.values()) if (p.count() <= p.reorderAt()) low.add(p);
low.sort(Comparator.comparingInt(Part::count).thenComparing(Part::code));
return low;
}
SortedSet<String> shelvesInUse() {
TreeSet<String> s = new TreeSet<>();
for (Part p : byCode.values()) s.add(p.shelf());
return Collections.unmodifiableSortedSet(s);
}
}
enum Urgency { RENTAL_DAMAGE, NEEDED_TOMORROW, ROUTINE }
class RepairRack {
private record Job(int arrival, String what, Urgency urgency) {}
private final PriorityQueue<Job> queue = new PriorityQueue<>(
Comparator.comparing(Job::urgency).thenComparingInt(Job::arrival));
private int arrivals;
void add(String what, Urgency u) { queue.offer(new Job(++arrivals, what, u)); }
String next() { return queue.poll().what(); }
}
class Rentals {
private final String bike;
private final TreeMap<LocalDate, LocalDate> startToEnd = new TreeMap<>();
private final Map<LocalDate, String> who = new HashMap<>();
Rentals(String bike) { this.bike = bike; }
void book(LocalDate start, int days, String customer) {
LocalDate end = start.plusDays(days - 1);
if (!isFree(start, end)) throw new IllegalStateException(bike + " is booked then");
startToEnd.put(start, end);
who.put(start, customer);
}
boolean isFree(LocalDate from, LocalDate to) {
Map.Entry<LocalDate, LocalDate> before = startToEnd.floorEntry(to);
return before == null || before.getValue().isBefore(from);
}
String nextBookingAfter(LocalDate d) {
Map.Entry<LocalDate, LocalDate> e = startToEnd.ceilingEntry(d);
return e == null ? "none" : e.getKey() + " to " + e.getValue() + ", " + who.get(e.getKey());
}
}R1 lookup: PAD-ROAD:6 R2 printout: [BELL:8, CABLE-BRAKE:12, CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9] R3 reorder: [CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9] R6 recent: [CABLE-BRAKE 10, BELL -1, TUBE-700x25 -5] R6 undo: undid CABLE-BRAKE 10 -> CABLE-BRAKE:2 R7 shelves: [A-02, B-07, B-14, C-03] R4 next jobs: rental Cargo 1, snapped spoke; Ana Ruiz, flat tire; Theo Park, brake cable R5 free May 3 to 7? true R5 free May 6 to 9? false R5 next after May 4: 2027-05-08 to 2027-05-10, Theo Park R8 views are read-only
What this code does
The program builds the stock room, the repair rack and one bike's rental calendar, then exercises each requirement and prints one line labeled R1 to R8. Lookups go through the HashMap, the printout and reorder list are sorted copies, the rack is a PriorityQueue and the calendar answers range questions with floorEntry and ceilingEntry. The last line shows that a view handed out by the stock room refuses changes.
Reading the output against the requirements, every line is what was asked for. R1 finds PAD-ROAD with 6 in stock. R2 lists the parts by code, with the changed counts. R3 lists the three parts at or below their reorder level, lowest first: CHAIN-11 with 4, PAD-ROAD with 6 and the tubes, which have dropped to 9 against a reorder level of 10; the bells, down to 8, are still above their level of 4. R6 shows the three changes newest first, and the undo takes the brake cables back from 12 to 2. R4 hands out the damaged rental first, then Ana before Theo. R5 reports May 3 to 7 free, because Ana's rental ends on May 2, and May 6 to 9 not free, because Theo's starts on May 8.
Checking the choices with numbers
Ingrid asked Hamza to show, not just claim, that the HashMap matters at Second Gear's size. Counting comparisons for 1,000 lookups among 612 parts makes the point without timing anything.
import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 612, lookups = 1000;
List<String> codes = new ArrayList<>();
for (int i = 0; i < n; i++) codes.add(String.format("P-%04d", i));
long listSteps = 0;
long treeSteps = 0;
int seed = 12345;
for (int k = 0; k < lookups; k++) {
seed = (seed * 1103515245 + 12345) & 0x7fffffff;
int target = seed % n;
listSteps += target + 1;
int lo = 0, hi = n - 1;
while (lo <= hi) {
treeSteps++;
int mid = (lo + hi) / 2;
if (mid == target) break;
if (mid < target) lo = mid + 1; else hi = mid - 1;
}
}
System.out.println("comparisons for " + lookups + " lookups among " + n + " parts");
System.out.println(" scan a list: " + listSteps);
System.out.println(" balanced tree search: " + treeSteps);
System.out.println(" hash map (about 1 each): " + lookups);
}
}comparisons for 1000 lookups among 612 parts scan a list: 304224 balanced tree search: 8313 hash map (about 1 each): 1000
What this code does
A simple fixed-seed generator picks the same 1,000 part codes to look up on every run, so the counts are repeatable. Scanning a list costs hundreds of thousands of comparisons, a balanced search tree about eight per lookup, and a hash map about one. At 612 parts the list is already hundreds of times more work than the map.
The same habit of counting answered Kofi's question about R2. Sorting 612 parts takes at most about 612 × log₂ 612, roughly 5,700 comparisons, once a month. Keeping a second sorted map in step would cost a little on every one of the thousands of stock changes in that month, and add a whole class of bugs where the two maps disagree. Doing less work all month to do slightly more work once is the better trade.
A bug found at the review
At the Friday review Kofi tried to break the rental calendar by booking Cargo 1 from May 2 for two days, overlapping Ana's rental, which ends on May 2. The booking was refused, as it should be. He then asked what happens if two bookings start on the same date. Because the TreeMap's key is the start date, a second put with the same date would replace the first booking silently. book is safe because it checks isFree first, but Ingrid pointed out that any future method that calls put directly would reintroduce the bug. Hamza added a comment and a check, and noted it for the ShopBook integration.
import java.time.LocalDate;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
TreeMap<LocalDate, String> byStart = new TreeMap<>();
LocalDate may1 = LocalDate.of(2027, 5, 1);
byStart.put(may1, "Ana Ruiz");
String lost = byStart.put(may1, "Kofi, testing");
System.out.println("put replaced: " + lost + ", map now " + byStart);
byStart.put(may1, "Ana Ruiz");
String existing = byStart.putIfAbsent(may1, "Kofi, testing");
System.out.println("putIfAbsent kept: " + existing + ", map now " + byStart);
}
}put replaced: Ana Ruiz, map now {2027-05-01=Kofi, testing}
putIfAbsent kept: Ana Ruiz, map now {2027-05-01=Ana Ruiz}What this code does
put returns the value it replaced, so the first call shows that Ana's booking was silently overwritten by Kofi's test. putIfAbsent leaves an existing entry alone and returns it, so the second attempt keeps Ana's booking. A key that two entries could share needs this kind of check, or a different key.
import java.time.LocalDate;
import java.util.*;
public class Main {
public static void main(String[] args) {
StockRoom room = new StockRoom();
room.addPart(new Part("TUBE-700x25", "700x25c inner tube", "B-07", 14, 10));
room.addPart(new Part("PAD-ROAD", "brake pads, road", "B-14", 6, 8));
room.addPart(new Part("CHAIN-11", "chain, 11-speed", "C-03", 4, 4));
room.addPart(new Part("BELL", "bell, brass", "A-02", 9, 4));
room.addPart(new Part("CABLE-BRAKE", "brake cable", "C-03", 2, 6));
System.out.println("R1 lookup: " + room.find("PAD-ROAD"));
room.use("TUBE-700x25", 5);
room.use("BELL", 1);
room.receive("CABLE-BRAKE", 10);
System.out.println("R2 printout: " + room.printout());
System.out.println("R3 reorder: " + room.toReorder());
System.out.println("R6 recent: " + room.recentChanges());
System.out.println("R6 undo: " + room.undo() + " -> " + room.find("CABLE-BRAKE"));
System.out.println("R7 shelves: " + room.shelvesInUse());
RepairRack rack = new RepairRack();
rack.add("Mei Lin, tune-up", Urgency.ROUTINE);
rack.add("Ana Ruiz, flat tire", Urgency.NEEDED_TOMORROW);
rack.add("rental Cargo 1, snapped spoke", Urgency.RENTAL_DAMAGE);
rack.add("Theo Park, brake cable", Urgency.NEEDED_TOMORROW);
System.out.println("R4 next jobs: " + rack.next() + "; " + rack.next() + "; " + rack.next());
Rentals cargo = new Rentals("Cargo 1");
cargo.book(LocalDate.of(2027, 5, 1), 2, "Ana Ruiz");
cargo.book(LocalDate.of(2027, 5, 8), 3, "Theo Park");
System.out.println("R5 free May 3 to 7? " + cargo.isFree(LocalDate.of(2027, 5, 3), LocalDate.of(2027, 5, 7)));
System.out.println("R5 free May 6 to 9? " + cargo.isFree(LocalDate.of(2027, 5, 6), LocalDate.of(2027, 5, 9)));
System.out.println("R5 next after May 4: " + cargo.nextBookingAfter(LocalDate.of(2027, 5, 4)));
cargo.book(LocalDate.of(2027, 5, 2), 2, "Kofi, testing");
try {
room.printoutView().add(null);
} catch (UnsupportedOperationException e) {
System.out.println("R8 views are read-only");
}
}
}
record Part(String code, String name, String shelf, int count, int reorderAt) {
Part withCount(int c) { return new Part(code, name, shelf, c, reorderAt); }
@Override public String toString() { return code + ":" + count; }
}
class StockRoom {
private final Map<String, Part> byCode = new HashMap<>();
private final Deque<String[]> history = new ArrayDeque<>();
private static final int HISTORY = 10;
void addPart(Part p) { byCode.put(p.code(), p); }
Part find(String code) {
Part p = byCode.get(code);
if (p == null) throw new NoSuchElementException("no part " + code);
return p;
}
void use(String code, int n) { change(code, -n); }
void receive(String code, int n) { change(code, n); }
private void change(String code, int delta) {
Part p = find(code);
if (p.count() + delta < 0) throw new IllegalArgumentException("only " + p.count() + " of " + code);
byCode.put(code, p.withCount(p.count() + delta));
history.push(new String[] {code, String.valueOf(delta)});
if (history.size() > HISTORY) history.removeLast();
}
String undo() {
String[] last = history.pop();
Part p = find(last[0]);
byCode.put(last[0], p.withCount(p.count() - Integer.parseInt(last[1])));
return "undid " + last[0] + " " + last[1];
}
List<String> recentChanges() {
List<String> out = new ArrayList<>();
for (String[] h : history) out.add(h[0] + " " + h[1]);
return out;
}
List<Part> printout() {
List<Part> list = new ArrayList<>(byCode.values());
list.sort(Comparator.comparing(Part::code));
return list;
}
List<Part> printoutView() { return Collections.unmodifiableList(printout()); }
List<Part> toReorder() {
List<Part> low = new ArrayList<>();
for (Part p : byCode.values()) if (p.count() <= p.reorderAt()) low.add(p);
low.sort(Comparator.comparingInt(Part::count).thenComparing(Part::code));
return low;
}
SortedSet<String> shelvesInUse() {
TreeSet<String> s = new TreeSet<>();
for (Part p : byCode.values()) s.add(p.shelf());
return Collections.unmodifiableSortedSet(s);
}
}
enum Urgency { RENTAL_DAMAGE, NEEDED_TOMORROW, ROUTINE }
class RepairRack {
private record Job(int arrival, String what, Urgency urgency) {}
private final PriorityQueue<Job> queue = new PriorityQueue<>(
Comparator.comparing(Job::urgency).thenComparingInt(Job::arrival));
private int arrivals;
void add(String what, Urgency u) { queue.offer(new Job(++arrivals, what, u)); }
String next() { return queue.poll().what(); }
}
class Rentals {
private final String bike;
private final TreeMap<LocalDate, LocalDate> startToEnd = new TreeMap<>();
private final Map<LocalDate, String> who = new HashMap<>();
Rentals(String bike) { this.bike = bike; }
void book(LocalDate start, int days, String customer) {
LocalDate end = start.plusDays(days - 1);
if (!isFree(start, end)) throw new IllegalStateException(bike + " is booked then");
startToEnd.put(start, end);
who.put(start, customer);
}
boolean isFree(LocalDate from, LocalDate to) {
Map.Entry<LocalDate, LocalDate> before = startToEnd.floorEntry(to);
return before == null || before.getValue().isBefore(from);
}
String nextBookingAfter(LocalDate d) {
Map.Entry<LocalDate, LocalDate> e = startToEnd.ceilingEntry(d);
return e == null ? "none" : e.getKey() + " to " + e.getValue() + ", " + who.get(e.getKey());
}
}What this code does
Kofi's test booking for May 2 overlaps the end of Ana's rental, so isFree finds her booking with floorEntry and book refuses it with IllegalStateException. The run prints every requirement line up to R5 and then stops at the refused booking. That is the right behavior, and the test belongs in the program's checks.
$ javac Main.java
$ java Main
R1 lookup: PAD-ROAD:6
R2 printout: [BELL:8, CABLE-BRAKE:12, CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9]
R3 reorder: [CHAIN-11:4, PAD-ROAD:6, TUBE-700x25:9]
R6 recent: [CABLE-BRAKE 10, BELL -1, TUBE-700x25 -5]
R6 undo: undid CABLE-BRAKE 10 -> CABLE-BRAKE:2
R7 shelves: [A-02, B-07, B-14, C-03]
R4 next jobs: rental Cargo 1, snapped spoke; Ana Ruiz, flat tire; Theo Park, brake cable
R5 free May 3 to 7? true
R5 free May 6 to 9? false
R5 next after May 4: 2027-05-08 to 2027-05-10, Theo Park
Exception in thread "main" java.lang.IllegalStateException: Cargo 1 is booked then
at Rentals.book(Main.java:130)
at Main.main(Main.java:36)What the course added up to
Every structure in StockRoom came from a lesson in this course: generics from lesson 1 make the containers type-safe; the framework's interfaces from lesson 2 let fields be declared as Map and Deque; ArrayList, ArrayDeque, HashMap and TreeMap each won because of the costs measured in lessons 3 to 6; the comparators from lesson 7 order the reorder list and the repair rack; iterators from lesson 8 walk the history safely; and lessons 9 to 11 explain what is happening inside each of them. The skill that ties them together is the one this capstone practiced: state the need, count the operations, choose the simplest structure whose costs fit, and check the result against the requirements.
| Question to ask | If the answer is yes | Structure |
|---|---|---|
| Do I look things up by a key? | and order does not matter | HashMap |
| and I need sorted keys or ranges | TreeMap | |
| Must each value appear once? | and order does not matter | HashSet |
| and I need them sorted | TreeSet | |
| Do I always want the smallest or most urgent next? | PriorityQueue | |
| Do I add and remove only at the ends? | ArrayDeque, as a queue or stack | |
| Otherwise, a sequence? | ArrayList | |
| Is the need rare, such as a monthly report? | compute it on demand, for example by sorting a copy |
Try it yourself
A bounded change history
Complete record so the history keeps only the newest three entries: push the new entry onto the ArrayDeque, and if it then holds more than max entries, remove the oldest with removeLast.
The program should print [chain -1, pads -2, tube +10].
import java.util.*;
public class Main {
public static void main(String[] args) {
History h = new History(3);
for (String change : new String[] {"bell -1", "cable +6", "tube +10", "pads -2", "chain -1"}) h.record(change);
System.out.println(h.newestFirst());
}
}
class History {
private final Deque<String> entries = new ArrayDeque<>();
private final int max;
History(int max) { this.max = max; }
void record(String change) {
entries.push(change);
}
List<String> newestFirst() { return new ArrayList<>(entries); }
}Try it yourself
Is the bike free?
Complete isFree for a bike whose bookings never overlap. Find the booking that starts on or before to with floorEntry(to); the range is free if there is none, or if that booking's end date is before from.
The program should print May 3-7 free: true, May 6-9 free: false and April 28-30 free: true.
import java.time.LocalDate;
import java.util.*;
public class Main {
public static void main(String[] args) {
TreeMap<LocalDate, LocalDate> bookings = new TreeMap<>();
bookings.put(LocalDate.of(2027, 5, 1), LocalDate.of(2027, 5, 2));
bookings.put(LocalDate.of(2027, 5, 8), LocalDate.of(2027, 5, 10));
System.out.println("May 3-7 free: " + isFree(bookings, LocalDate.of(2027, 5, 3), LocalDate.of(2027, 5, 7)));
System.out.println("May 6-9 free: " + isFree(bookings, LocalDate.of(2027, 5, 6), LocalDate.of(2027, 5, 9)));
System.out.println("April 28-30 free: " + isFree(bookings, LocalDate.of(2027, 4, 28), LocalDate.of(2027, 4, 30)));
}
static boolean isFree(TreeMap<LocalDate, LocalDate> bookings, LocalDate from, LocalDate to) {
return !bookings.containsKey(from);
}
}Common mistakes
MistakeChoosing a structure before writing down what the program must do.
InsteadList the requirements first, then choose a structure for each one.
MistakeKeeping two structures in step for a report that is rarely needed.
InsteadCompute rare results on demand, for example by sorting a copy.
MistakeUsing a key that two entries can share, such as a start date, and calling put directly.
InsteadCheck for an existing key first, or choose a key that is unique.
MistakeReturning a private collection from a getter.
InsteadReturn an unmodifiable view or a copy.
MistakeClaiming a structure is faster without evidence.
InsteadCount the operations for realistic sizes, as the lookup comparison did.
Summary and key terms
- A good data layer starts from numbered requirements and chooses one structure per need by asking whether it is a lookup by key, a set, a sequence, a queue or a range, how often each operation happens and how many elements there are.
- StockRoom uses a HashMap for lookup by code, an on-demand sort for the monthly printout and the reorder list, a PriorityQueue for the repair rack, a TreeMap from start to end date for each rental bike, an ArrayDeque as a bounded undo stack, a TreeSet for shelves and unmodifiable views to protect its data.
- Rare needs are often best met by computing them when asked, rather than by keeping an extra structure in step.
- Counting comparisons shows the difference between a list scan, a tree search and a hash lookup at real sizes.
- Reviews and deliberate attempts to break the design, such as overlapping bookings, find the bugs the requirements did not mention.
- Requirement
- A numbered statement of something the program must do.
- Data layer
- The part of a program that holds and organizes its data.
- On-demand computation
- Producing a result when it is asked for instead of keeping it up to date all the time.
- Bounded history
- A record that keeps only the newest entries, up to a fixed number.
- Design review
- A meeting in which others question a design to find weaknesses.
- Trade-off
- Accepting a cost in one place for a benefit in another.
- Invariant check
- Code that confirms a rule still holds, such as bookings not overlapping.
- Unmodifiable view
- A read-only wrapper that lets callers see a collection without changing it.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Why did Hamza use a HashMap rather than a TreeMap for R1?
Show answer
Lookups by code need no order, and a HashMap gives O(1) average lookups.
Why is the monthly printout sorted on demand instead of kept in a second sorted map?
Show answer
Sorting once a month is cheap, while keeping two maps in step costs work on every change and risks bugs.
How does Rentals.isFree check a date range in O(log n)?
Show answer
It finds the booking that starts on or before the end date with floorEntry and checks whether it ends before the start date.
What structure suits a history that keeps only the last ten changes, newest first?
Show answer
An ArrayDeque used as a stack, with removeLast when it grows past ten.
What bug did the review find in the rental calendar?
Show answer
Two bookings with the same start date would replace each other in the TreeMap if put were called without checking.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.