Java Bridge · J8
Generics vs templates — erasure, wildcards, and no List<int>
The idea
One class, and the types are gone
corpus/shopping-cart/reference/src/ holds the same registry twice. Catalog maps a code to a Sku, CouponBook maps a code to a Promotion, and both are a map plus a require(code) that throws for an unknown code. One type parameter collapses them into one file:
public final class CodeIndex<T> {
private final Map<String, T> byCode;
public T require(String code) { ... }
}A template would hand you two classes here, CodeIndex<Sku> and CodeIndex<Promotion>, each generated separately and each knowing its own T. Java hands you one. javap -s on what it compiled:
public T require(java.lang.String);
descriptor: (Ljava/lang/String;)Ljava/lang/Object;T became Object. The caller got a cast nobody wrote:
3: invokevirtual #9 // Method CodeIndex.require:(Ljava/lang/String;)Ljava/lang/Object;
6: checkcast #15 // class SkuThat is erasure, and it is the whole lesson: one class with Object in it, and a cast at every call site.
The first thing it costs is smaller than that machinery suggests. Catalog.require says no such sku: NOPE, CouponBook.require says no such coupon: SAVE99, and the grader asserts both. So CodeIndex.require needs the name of T — which the descriptor above no longer carries. There is nowhere to read it from. It has to arrive as data:
new CodeIndex<>("sku", byCode)That missing string is the shape of everything else on this page. No new T(). No new T[n]. A static field shared by every parameterisation, because there is one class holding it. And no List<int>, so a quantity in a map is an Integer, and an Integer can be null.
Coming from C++
From C++ — the same syntax over a completely different mechanism
You know templates, including specialisation and SFINAE. None of that is the risk here. The risk is that CodeIndex<Sku> is spelled the same way in both languages while meaning two unrelated things. The syntax transfers and the mental model does not.
Names in the compiler output below: CodeIndex, Discounts and Erasure are in worked/src/. E4 to E7 are four-line probes that exist to fail, so they are quoted here rather than shipped — every .java file under lessons/ has to compile.
A template is a code generator. CodeIndex<Sku> and CodeIndex<Promotion> are two classes, generated at each instantiation, type-checked against the arguments you actually used, and each holding its own static members. Two .o sections, deduplicated by the linker if you are lucky.
A Java generic is one class with the types deleted. javac checks the type arguments, then throws them away and writes Object in the bytecode. One .class file, whatever you parameterise it with. That deletion is called erasure, and every surprise below is a consequence of it rather than a separate rule to memorise.
Here is the deletion, from javap -s -p on the CodeIndex in worked/:
public T require(java.lang.String);
descriptor: (Ljava/lang/String;)Ljava/lang/Object;
public T[] toArray(java.util.function.IntFunction<T[]>);
descriptor: (Ljava/util/function/IntFunction;)[Ljava/lang/Object;Two signatures per method. The one javap prints first comes from a Signature attribute that javac writes for the benefit of other compilers; the descriptor is what the JVM dispatches on, and it says Object. Now the caller, javap -c:
static Sku firstSku(CodeIndex<Sku>);
Code:
0: aload_0
1: ldc #7 // String TEA
3: invokevirtual #9 // Method CodeIndex.require:(Ljava/lang/String;)Ljava/lang/Object;
6: checkcast #15 // class Sku
9: areturncheckcast Sku at offset 6. Nobody wrote that cast. Generics in Java are a compile-time check plus inserted casts, and the run time sees a registry of Object.
The delta table
| C++ | Java | What differs, and where it bites |
|---|---|---|
template<class T> class CodeIndex | class CodeIndex<T> | One class, not one per instantiation |
| implicit constraints from the body | <T extends Promotion> | With no bound, T has only Object's methods. There is no duck typing |
template<> class CodeIndex<Sku> | nothing | No specialisation, full or partial. This is the biggest single loss |
std::array<T, N> | nothing | No non-type parameters. Sizes are constructor arguments, checked at run time |
if constexpr, constexpr, tag dispatch | nothing | No metaprogramming. A type parameter cannot compute |
T x; as a member | T x; fine | Same, because it is a reference to Object underneath |
new T(), T() | nothing | error: unexpected type. Pass a Supplier<T> |
new T[n] | nothing | error: generic array creation. Pass an IntFunction<T[]> |
static T cache; in a template | nothing | error: non-static type variable T .... One class, so one field for everybody |
typeid(T).name() | nothing | The name is gone at run time. Pass a label, or a Class<T> token |
std::is_same_v<T, Sku> | nothing | instanceof List<Promotion> will not compile |
std::vector<int> | List<Integer> | No primitive type arguments, ever. Boxing, and null becomes possible |
std::vector<Dog> is unrelated to std::vector<Animal> | same | Generics are invariant, as templates are |
Dog*[] converts to Animal*[] | Dog[] is an Animal[] | Java arrays are covariant. The asymmetry with generics is the trap |
| a throwing template | class E<T> extends Throwable | error: a generic class may not extend java.lang.Throwable |
| errors at the instantiation | errors at the declaration | An error in a generic method is found even if nobody calls it |
| header-only, source required | a .class is enough | Separate compilation. The caller never sees the generic's source |
const T& to avoid a copy | irrelevant | Everything is already a reference. There is nothing to copy |
The five things you can no longer write
Every message below is the real javac output, triggered against worked/'s CodeIndex.
new T(). Catalog has no reason to build a blank Sku, but a generic pool or a generic default would. There is no constructor to call, because T is Object by the time anything runs:
CodeIndex.java:92: error: unexpected type
return new T();
^
required: class
found: type parameter T
where T is a type-variable:
T extends Object declared in class CodeIndexThe fix is to make the caller supply the construction: a Supplier<T> parameter, or a Class<T> token and getDeclaredConstructor().newInstance(). The first is better in every case that is not a framework.
new T[n]. Same reason, blunter message:
CodeIndex.java:75: error: generic array creation
T[] out = new T[byCode.size()];
^CodeIndex.toArray in worked/ takes an IntFunction<T[]> so the caller writes Sku[]::new. The version that looks right compiles and is wrong:
return (T[]) byCode.values().toArray();CodeIndex.java:86: warning: [unchecked] unchecked cast
return (T[]) byCode.values().toArray();
^
required: T[]
found: Object[]A warning, not an error, and the method returns normally. The failure lands elsewhere:
toArrayTheWayItLooks() : java.lang.ClassCastException
message : class [Ljava.lang.Object; cannot be cast to class [LSku;
thrown at: Erasure.whereTheCastActuallyIs(Erasure.java:84)Erasure.java:84 is the caller's assignment, not the cast on line 86. The checkcast you saw in the bytecode above is where the failure surfaces, and no frame in the trace names the class that lied. Recognise this one: an unchecked-cast warning you dismissed becomes a ClassCastException in somebody else's file.
instanceof on a parameterised type. Asking what is in a list is asking a question the run time threw away:
E5.java:6: error: Object cannot be safely cast to List<Promotion>
return handedIn instanceof List<Promotion>;
^handedIn instanceof List<?> does compile, and a List<Sku> answers true to it. worked/ prints that:
a List<Sku> answers `o instanceof List<?>` : true
first element's real class : SkuSo the elements can be checked one at a time and the list cannot be checked at all. That is the whole of run-time type inspection for generics.
Two overloads differing only by type argument. This is the C++ move, one total per coupon kind, and it is the error you will hit first. The code looks fine:
public static long total(List<PercentageCoupon> coupons, long owedMinor) { ... }
public static long total(List<FixedAmountCoupon> coupons, long owedMinor) { ... }E4.java:10: error: name clash: total(List<FixedAmountCoupon>,long) and total(List<PercentageCoupon>,long) have the same erasure
public static long total(List<FixedAmountCoupon> coupons, long owedMinor) {
^"have the same erasure" is the phrase to learn. Both methods erase to total(List, long), and a class file cannot hold two methods with one descriptor. Rename one, or take List<? extends Promotion> once and let the promotion decide, which is what the corpus does with DiscountStage.
A static field mentioning T.
CodeIndex.java:27: error: non-static type variable T cannot be referenced from a static context
private static T fallback;
^One class means one static field. A static long counter is legal, and it counts every parameterisation together. worked/ block 4, after two lookups on the catalogue and two on the coupon book:
catalogue.lookups() : 2
coupons.lookups() : 2
CodeIndex.lookupsAcrossAllIndexes() : 4 <- both, added upIn C++ that field is per-instantiation and the two numbers stay apart. This is the one on the list that produces no compile error and no exception. It shows up as a metric that is silently double, or a lazily built cache that hands Sku-shaped answers to code asking about coupons.
Invariance, and the asymmetry with arrays
List<PercentageCoupon> is not a List<Promotion>, for the reason it is not a vector<Promotion>: if it were, you could add a FixedAmountCoupon to it. Totals.price in the reference declares List<Promotion>, and here is what that refuses:
E6.java:8: error: incompatible types: List<PercentageCoupon> cannot be converted to List<Promotion>
Discounts.totalNarrow(percentages, List.of(), 5899);
^Nothing surprising so far. The surprise is that Java arrays do not follow the same rule:
Sku[] catalogue = { new Sku("TEA", "Loose leaf tea", 450), ... };
Object[] anything = catalogue; // legal: arrays are covariant
anything[0] = "TEA"; // compiles Sku[] assigned to Object[] : compiles, runs
storing a String in it : java.lang.ArrayStoreException: java.lang.StringSku[] is an Object[], so the assignment is legal and the store is checked at run time instead. Every array store in Java carries that check. C++ has the same hole through Dog** and gives you no diagnostic either, so the array half is familiar. What is new is that two features of one language disagree. Generics chose compile-time safety; arrays predate generics and could not.
The practical consequence: prefer a List<T> to a T[] for anything held in a field. You get the error at the line that is wrong, and you lose the run-time store check you were never using.
Wildcards, and the rule that settles them in ten seconds
Invariance is strict enough to be inconvenient, and wildcards are the release valve. There are two, and one question tells you which.
Look at the parameter and ask which way the values travel.
- Out of it, never in →
? extends. It produces values, and you read them. - In to it, never out →
? super. It consumes values, and you write them. - Both → no wildcard. Name the type.
- A return type → no wildcard, always. Wildcards belong in parameters, so that a caller reading your signature never has to reason about a capture.
That is PECS: producer extends, consumer super. The JDK is the proof it holds. Collection.addAll(Collection<? extends E>) reads its argument, and List.sort(Comparator<? super E>) is handed something that consumes E.
Here is the corpus signature that should have it. Totals.price takes the promotions, sorts them by stage, and takes money off. It never adds one:
public static long total(List<? extends Promotion> promotions, List<LineItem> lines, long subtotalMinor) {The reference gets away with List<Promotion> because Cart.activePromotions() happens to build exactly that. Any other caller pays: a factory holding List<PercentageCoupon>, a test with List.of(new MultiBuyPromotion("MUG", 4)), a per-tier cart that keeps its offers typed. Each one gets the E6 error above. Each one is then "fixed" with a copy into a new ArrayList<Promotion>, which is a line of code that exists to work around a signature.
? super is the other half, and it is rarer, so here is where it earns its place. Cart.activePromotions() builds a list and returns it. Written to fill a list the caller owns:
public static void collectInto(List<? super Promotion> sink,
List<? extends Promotion> standing,
CodeIndex<? extends Promotion> couponBook) {
sink.addAll(standing);
sink.addAll(couponBook.all());
} collectInto(List<Object>, ...) : accepted, 3 promotions writtenA List<Object> is accepted, because anything that can hold an Object can hold a Promotion. With List<Promotion> as the parameter type, a caller keeping a List<Object> of everything it has built cannot use the method.
Two limits worth knowing before you reach for ? extends everywhere.
A ? extends list refuses every write, including putting back what you took out:
E7.java:6: error: incompatible types: PercentageCoupon cannot be converted to CAP#1
promotions.add(new PercentageCoupon(10));
^
where CAP#1 is a fresh type-variable:
CAP#1 extends Promotion from capture of ? extends Promotion
E7.java:10: error: incompatible types: Promotion cannot be converted to CAP#1
promotions.set(0, promotions.get(0));
^CAP#1 is the compiler naming the unknown subtype for you. Learn the word "capture": it appears in every wildcard error, and it means "there is one specific type here and I do not know which".
Sorting is not a write, as far as the compiler is concerned. promotions.sort(...) on a List<? extends Promotion> compiles, because sort wants a Comparator<? super E> and Comparator<Promotion> satisfies it. So ? extends does not protect the caller's list from being reordered. Discounts.inStageOrder copies for that reason, not because of the wildcard:
the mixed list as it was wired up : [FIXED_AMOUNT_COUPON, PERCENTAGE_COUPON, ITEM_PROMOTION]
inStageOrder(...) hands back : [ITEM_PROMOTION, PERCENTAGE_COUPON, FIXED_AMOUNT_COUPON]
the caller's list afterwards : [FIXED_AMOUNT_COUPON, PERCENTAGE_COUPON, ITEM_PROMOTION]No primitive type arguments, and what boxing actually costs
List<int> does not exist and never will. A type argument is a reference type, because erasure writes Object and an int is not one. So a cart's quantities are Map<String, Integer> and its line totals, if they live in a collection, are a List<Long>.
The performance question comes up in interviews, so here is the measurement instead of an opinion. worked/ block 8, medians of eleven timed repetitions, four runs of the whole program:
read 5 long[] 1.8 ns List<Long> 5.3 ns LongStream 10.2 ns x2.9
read 50 long[] 8.5 ns List<Long> 51.0 ns LongStream 14.5 ns x6.0
read 1000 long[] 235.4 ns List<Long> 355.9 ns LongStream 248.3 ns x1.5
read 1000000 long[] 246540.0 ns List<Long> 1122910.0 ns LongStream 259560.0 ns x4.6
build 5 long[] 7.1 ns List<Long> 24.4 ns x3.4
build 50 long[] 48.4 ns List<Long> 176.7 ns x3.7
build 1000 long[] 1007.1 ns List<Long> 3357.7 ns x3.3
heap 1000000 long[] 8.2 bytes/number List<Long> 28.2 bytes/number x3.4The absolute numbers move by a fifth between runs and the ratios hold. Over five runs of the whole program the boxed-to-raw ratio stayed between 6.0 and 6.7 on the 50-line read, and between 3.7 and 4.2 on the 50-line build. The heap ratio never left 3.4 to 3.5.
Now the honest reading of that, which matters more than the numbers. A shopping cart has five to fifty lines. Summing fifty boxed line totals takes 51 nanoseconds against 8.5 for the array, so boxing the subtotal costs 35 to 43 nanoseconds per total() call across the five runs. A cart page that renders in one millisecond has a budget of 1,000,000 nanoseconds. This is 0.004% of it. At LLD scale, in an interview, in production for a cart: it does not matter, and saying it does is the mistake.
Three things in that table do matter.
The memory ratio, at scale. 8.2 bytes against 28.2 per number — a long is 8 bytes, a Long is a 16-byte object plus a reference plus the ArrayList slot. If you ever hold ten million of something, that is the row to quote.
LongStream is not free either. At five and fifty elements it is slower than the plain loop, 10.2 ns and 14.5 ns against 1.8 and 8.5, because a stream pipeline has setup to pay for. It matches the array loop from about a thousand elements. So "use IntStream" is right about boxing and wrong about speed at small sizes. int[], long[] and IntStream/LongStream are the escape hatches when a measurement says you need one, and a measurement rarely does at this scale.
Integer can be null, and that is the real cost. There is no int that is absent. This compiles and reads as if it were safe:
public int quantityOf(String skuCode) {
return byCode.get(skuCode);
}java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return
value of "java.util.Map.get(Object)" is nullThe unboxing is invisible in the source, so the throw names a method you did not call. getOrDefault(skuCode, 0) is the fix. Helpful NPE messages, on by default since Java 15, are why that text names the map call at all.
There is a second edge with the same root. Integer.valueOf caches −128 to 127, so == on two boxes is true for small numbers and false for large ones:
quantity 100, boxed twice, compared with == : true
quantity 200, boxed twice, compared with == : false
line total 450 as Long, compared with == : falseJ6 is the lesson on == against .equals. The new part here is that no new appears on the line: the compiler created the object, so nothing in the source looks like an allocation. A quantity comparison written this way passes every test with a quantity under 128.
What you lose, and what you get for it
The loss is real and it is worth naming plainly, because dismissing it is the fastest way to look like you have not used the other language.
No specialisation. template<> class CodeIndex<Sku> giving the sku index an extra method or a different require has no Java form, full or partial. If CodeIndex<Sku> needs to behave differently, it is a different class or a subclass, and you have re-introduced the duplication the type parameter removed.
No non-type parameters. std::array<long, 5> and a Matrix<3, 4> whose dimensions are checked by the compiler cannot be expressed. Sizes are constructor arguments and mistakes are exceptions.
No compile-time computation. No constexpr, no if constexpr, no tag dispatch, no SFINAE and no concepts. Bounded type parameters are the entire constraint language: <T extends Promotion & Comparable<T>>. A generic Java method cannot decide anything at compile time; it can only require that T has an interface.
No duck typing. A template body compiles against whatever the instantiation happens to support, which is why templates work with types nobody planned for. A Java <T> with no bound gives you only the methods on Object. Every capability has to be written into the bound first.
What you get, and each of these is checkable:
One class file. CodeIndex.class is compiled once for every parameterisation there will ever be. Two hundred instantiations of a C++ template are two hundred bodies for the linker to fold. Here there is one, so getClass() == getClass() is true for CodeIndex<Sku> and CodeIndex<Promotion> — nothing else could be returned.
Error messages you can read. Every message quoted on this page is at most six lines and names your file, your line and your type. CAP#1 is the worst of them, and it is explained by the two lines under it.
Separate compilation. The caller of a generic needs a .class file and nothing else. No header-only libraries, no source shipped, no recompiling the world when a template body changes.
Errors at the declaration, not the instantiation. A generic method with a type error in it fails to compile even if nothing calls it. A template with the same error compiles fine until someone instantiates it, which is why C++ template bugs arrive from a caller you have never read.
Interoperation with pre-generic code. This is the historical reason for erasure, and worth knowing because it explains why the design is what it is. Java 5 added generics to a language with millions of lines of List-using code, and erasure is what let List and List<String> be the same class at run time. The alternative was a language break, and the cost of avoiding it is everything on this page.
When a type parameter earns its place, and when an interviewer reads it as over-engineering
STANDARD v1.0 grades design at D3, and level 3 requires that "the seam set is minimal — no speculative interface with a single implementation and no foreseeable second one". Level 3 penalises over-abstraction exactly as level 0 penalises none, and the failure tag is over-engineered (premature interface). A type parameter is a seam, and it counts.
The threshold, in two conditions that both have to hold.
- Two parameterisations exist in the code you are writing, or the requirements name the second.
CodeIndex<Sku>andCodeIndex<Promotion>are both constructed inCartFactory, so this one clears it.Cart<T extends Sku>has one parameterisation and no second in sight, so it fails. - The body never asks what
Tis.CodeIndex.requiredoes a map lookup and a throw, and works the same for both. The moment a method needsif (t instanceof Sku), the type parameter is modelling something a subclass or an interface should model, and it cannot do it anyway — see theinstanceoferror above.
Miss either and the concrete type is the honest answer. Catalog and CouponBook with the sku and coupon types written out are shorter to read, and they are what a reviewer expects.
Which is worth applying to this lesson's own example. CodeIndex<T> replaces two 30-line classes with one 40-line class plus a "sku" string that exists only to replace a type name. It clears both conditions and is still arguably the wrong call at this size. The reference solution ships Catalog and CouponBook as two files, with different javadoc, different error messages and no shared abstraction. That choice is defensible and it is the one the corpus made. Extract the generic when the third registry arrives, or when the duplicated body is long enough that two copies will drift.
Worked walkthrough
NOTES — thirteen files, and six lines that only exist because of erasure
Compile and run from the directory holding the sources:
..\..\..\.toolchain\jdk-21\bin\javac.exe -d out *.java
..\..\..\.toolchain\jdk-21\bin\java.exe -cp out Mainjavac -Xlint:all prints nothing and exits 0. Main takes about eight seconds, almost all of it in block 8's warm-up. Seven of the thirteen files are the corpus unchanged: Sku and LineItem from contract/, DiscountStage, Promotion and PercentageCoupon from reference/src/, FixedAmountCoupon and MultiBuyPromotion from the two curveball patches. The six that are this lesson's are CodeIndex, Discounts, CartQuantities, Boxing, Erasure and Main.
Real output, from exactly this code:
== 1 - Catalog and CouponBook are one class here, and the label is why ==
require("TEA") Sku[code=TEA, name=Loose leaf tea, unitPriceMinor=450]
require("SAVE10") PERCENTAGE_COUPON
catalogue.require("NOPE"): IllegalArgumentException: no such sku: NOPE
coupons.require("SAVE99"): IllegalArgumentException: no such coupon: SAVE99
the two messages differ only because "sku" and "coupon" were passed in
== 2 - one class, not two ==
catalogue.getClass() == couponBook.getClass() : true
both report : CodeIndex
List<Sku> and List<String> share a Class too : true
Map<String,Sku> and Map<String,Promotion> : true, both MapN
Object require(String)
Object[] toArray(IntFunction)
T became Object, and the caller got a cast it did not write
== 3 - new T[n] does not exist, so the caller makes the array ==
toArray(Sku[]::new) : 5 skus, first TEA
toArrayTheWayItLooks() : java.lang.ClassCastException
message : class [Ljava.lang.Object; cannot be cast to class [LSku;
thrown at: Erasure.whereTheCastActuallyIs(Erasure.java:84)
== 4 - static is shared, because there is one class to hold it ==
catalogue.lookups() : 2
coupons.lookups() : 2
CodeIndex.lookupsAcrossAllIndexes() : 4 <- both, added up
== 5 - generics are invariant, arrays are covariant ==
Sku[] assigned to Object[] : compiles, runs
storing a String in it : java.lang.ArrayStoreException: java.lang.String
the same mistake through a List<Sku> is a compile error, which is the point
a List<Sku> answers `o instanceof List<?>` : true
first element's real class : Sku
so the elements can be checked, the list cannot
== 6 - PECS on Totals.price's second parameter ==
subtotal : 5899
total(List<PercentageCoupon>, ...) : 590
total(List<Promotion>, ...) : 2215
the mixed list as it was wired up : [FIXED_AMOUNT_COUPON, PERCENTAGE_COUPON, ITEM_PROMOTION]
inStageOrder(...) hands back : [ITEM_PROMOTION, PERCENTAGE_COUPON, FIXED_AMOUNT_COUPON]
the caller's list afterwards : [FIXED_AMOUNT_COUPON, PERCENTAGE_COUPON, ITEM_PROMOTION]
the last two lines differ, so the copy is doing real work
collectInto(List<Object>, ...) : accepted, 3 promotions written
== 7 - there is no Map<String, int>, so absent is null ==
quantityOf("TEA") : 4
quantityOf("LAMP"), never added : 0
itemCount() : 104
holdsExactly("MUG", 100) : true
holdsExactlyByReference("MUG", 100) : true <- passes, by luck
holdsExactly("MUG", 200) : true
holdsExactlyByReference("MUG", 200) : false <- same code, 200 instead of 100
== 8 - what boxing costs, measured on this JVM ==
read 5 long[] 1.8 ns List<Long> 5.3 ns LongStream 10.2 ns x2.9
read 50 long[] 8.5 ns List<Long> 51.0 ns LongStream 14.5 ns x6.0
read 1000 long[] 235.4 ns List<Long> 355.9 ns LongStream 248.3 ns x1.5
read 1000000 long[] 246540.0 ns List<Long> 1122910.0 ns LongStream 259560.0 ns x4.6
build 5 long[] 7.1 ns List<Long> 24.4 ns x3.4
build 50 long[] 48.4 ns List<Long> 176.7 ns x3.7
build 1000 long[] 1007.1 ns List<Long> 3357.7 ns x3.3
heap 1000000 long[] 8.2 bytes/number List<Long> 28.2 bytes/number x3.4
both still reachable here: 1000000 and 1000000
quantity 100, boxed twice, compared with == : true
quantity 200, boxed twice, compared with == : false
line total 450 as Long, compared with == : false
Integer.valueOf caches -128..127, so the first line is true by luckBlocks 1 to 7 reproduce byte for byte. Block 8 will not: the timings move by roughly a fifth between runs on the same machine, and by more on a different one. What holds is the shape: the boxed column is 3 to 7 times the array column, and from-cpp.md gives the ranges over five runs.
Four lines in there are the lesson. no such sku: NOPE next to no such coupon: SAVE99, from one method. 4 where two 2s were expected. java.lang.ArrayStoreException where a compile error would have been. And true then false from the same comparison at 100 and at 200.
CodeIndex.java — the class that replaces Catalog and CouponBook
private final String what;This field exists only because T's name does not survive compilation. Catalog.require's message is no such sku: NOPE and CouponBook.require's is no such coupon: SAVE99, and the grader asserts both. A template would take the word from T; typeid(T).name() has no Java equivalent. Drop the field and there is no way to write either message from inside require. Block 2 shows why: the JVM holds Object require(String) and nothing else.
The alternative is a Class<T> token, which is what a framework passes. Class<Sku> would give you "Sku", so the messages would read no such Sku: NOPE. That is a different string from the one the contract asserts, so the label wins here. Reach for the token when you also need reflection.
private static long lookupsAcrossAllIndexes;static on a generic class is one field, shared by every parameterisation. The catalogue and the coupon book each answered two lookups, and block 4 prints 4 for this field. A C++ template gives you one counter per instantiation, so the equivalent code there prints 2 and 2. Nothing in the Java source hints at the difference.
This is the consequence with no compile error and no exception, which is what makes it the dangerous one. It shows up as a metric that is silently the sum of two things, or as a lazily built static cache that hands Sku-shaped entries to a caller asking about coupons. If a generic class has static mutable state, it is shared, and there is no per-parameterisation form of it.
private long lookups;Kept next to the static one for exactly that contrast. Same type, same increment, different scope, and only the modifier says so. faded/ makes this line a gap for that reason.
this.byCode = new LinkedHashMap<>(Objects.requireNonNull(byCode, "byCode"));A copy, so the index cannot be edited after the cart is built — CouponBook's own reasoning, unchanged. LinkedHashMap rather than HashMap because all() hands the values back and the catalogue's declaration order is the order Catalog.skus() promises. J7 is the lesson on that choice; the generic changes nothing about it.
if (found == null) {
throw new IllegalArgumentException("no such " + what + ": " + code);
}The null check is the erasure boundary in this method. byCode.get(code) returns T, which is Object in the bytecode, and absent is null. There is no optional<T> and no std::map::at throwing for you. Remove the check and require hands back null, the caller's inserted checkcast accepts it, and the failure lands wherever the Sku is first dereferenced.
public T[] toArray(IntFunction<T[]> newArray) {
return byCode.values().toArray(newArray);
}The IntFunction is the caller supplying what new T[n] cannot. new T[byCode.size()] is error: generic array creation, so the only code that can make a Sku[] is code that knows the word Sku, and that is the caller writing Sku[]::new. The parameter is not ceremony; it is the component type arriving at run time by the only route left.
Collection.toArray(IntFunction) exists for this, added in Java 11. The older spelling is toArray(new Sku[0]), which does the same thing and reads worse.
@SuppressWarnings("unchecked")
public T[] toArrayTheWayItLooks() {
return (T[]) byCode.values().toArray();
}Kept in the file so it can be run. Without the suppression javac -Xlint:unchecked reports warning: [unchecked] unchecked cast / required: T[] / found: Object[], and with or without it the method returns an Object[] successfully. Block 3 shows where the failure appears:
thrown at: Erasure.whereTheCastActuallyIs(Erasure.java:84)Line 84 is the caller's assignment, not the cast. The cast on this line compiles to nothing at all; the checkcast is at the call site. So the stack trace names a file that did nothing wrong, and no frame mentions CodeIndex. That is the cost of dismissing an unchecked-cast warning, and it is the reason toArray takes the IntFunction instead.
Discounts.java — the two wildcards, on a real signature
public static long total(List<? extends Promotion> promotions, List<LineItem> lines, long subtotalMinor) {? extends Promotion because every value moves out of that list and none moves in. The corpus declares List<Promotion> here, and block 6 prices a List<PercentageCoupon> through this one. Narrow it and that call is error: incompatible types: List<PercentageCoupon> cannot be converted to List<Promotion>, and the usual repair is a copy into a fresh ArrayList<Promotion> at every call site.
lines keeps its exact type on purpose. List<LineItem> is not List<? extends LineItem>, because LineItem is a record with no subtypes and none possible. A wildcard there would be noise that a reader has to check for meaning. Wildcards where a hierarchy exists; exact types where one cannot.
for (Promotion promotion : inStageOrder(promotions)) {Reading out of a ? extends Promotion list as a Promotion is always allowed, and this is the half of PECS that has no cost. Every element is some subtype of Promotion, so Promotion is a safe static type for it. The direction that fails is the other one: promotions.add(...) is error: incompatible types: PercentageCoupon cannot be converted to CAP#1.
List<Promotion> ordered = new ArrayList<>(promotions);
ordered.sort(Comparator.comparing(Promotion::stage));The copy is what stops the sort reaching the caller's list, and the wildcard does not do that job. promotions.sort(...) compiles against a List<? extends Promotion>, because sort wants a Comparator<? super E> and Comparator<Promotion> is one. So ? extends bought read-only element access and not an immutable list. Block 6 is the proof: the caller's list comes back in the order it was wired up.
Delete the copy and Totals.price silently reorders its argument. A factory that wired promotions up in a chosen order finds them rearranged, by a method whose name mentions no sort. The copy costs one allocation per total() call, which block 8 puts at tens of nanoseconds.
Comparator.comparing(Promotion::stage) works because DiscountStage is an enum, so its compareTo is declaration order, and DiscountStage declares the requirement's order. List.sort is stable, so promotions within a stage keep the order they arrived in.
public static void collectInto(List<? super Promotion> sink,
List<? extends Promotion> standing,
CodeIndex<? extends Promotion> couponBook) {? super Promotion on sink because every value moves into it. Block 6 passes a List<Object> and it is accepted: anything that can hold an Object can hold a Promotion. Declare it List<Promotion> and a caller keeping a wider list of everything it has assembled cannot call this.
Both wildcards in one signature is the normal case, not a clever one. sink is written, so super; standing and couponBook are read, so extends. Collection.addAll(Collection<? extends E>) in the JDK is the same split for the same reason.
CartQuantities.java — what Map<String, int> would have prevented
private final Map<String, Integer> byCode = new LinkedHashMap<>();Integer, because a type argument cannot be a primitive. Erasure writes Object and an int is not one, so Map<String, int> does not exist and never will. The substitution brings two properties an int never had: the value can be null, and two of them can be separate objects holding one number. Both of the gaps below are one of those two.
public int quantityOf(String skuCode) {
return byCode.getOrDefault(skuCode, 0);
}getOrDefault is the whole of "a sku the cart does not hold has quantity zero". Write return byCode.get(skuCode) and it still compiles, because javac inserts the unboxing to match the int return type. The first sku nobody has added gives:
java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return
value of "java.util.Map.get(Object)" is nullThe unboxing is invisible in the source, so the message names intValue(), a method that does not appear on the line. Helpful NPE messages, on by default since Java 15, are why that sentence names the map call at all.
public boolean holdsExactly(String skuCode, int quantity) {
return quantityOf(skuCode) == quantity;
}Both sides are int here, so == compares numbers. That is what makes this line answer the same way for 4 socks and for 400.
public boolean holdsExactlyByReference(String skuCode, int quantity) {
Integer held = byCode.get(skuCode);
return held == Integer.valueOf(quantity);
}Kept so it can be run, because reading it is not enough to distrust it. Block 7:
holdsExactlyByReference("MUG", 100) : true <- passes, by luck
holdsExactlyByReference("MUG", 200) : false <- same code, 200 instead of 100Integer.valueOf caches −128 to 127, so the two boxes are one object below 128 and two objects above it. ShoppingCartApi accepts any positive quantity, so both branches are reachable from a legal call. J6 is the lesson on == against .equals; the new fact here is that no new appears in the source, because the compiler allocated the object.
Erasure.java — the demonstrations that need a running JVM
System.out.println(" catalogue.getClass() == couponBook.getClass() : "
+ (catalogue.getClass() == couponBook.getClass()));true, and this is erasure observed rather than described. Two parameterisations, one Class object, because there is one class file. List<Sku> and List<String> answer the same way. Nothing can be built on those differing: not a per-type registry keyed on Class, and not a switch over parameterisations.
Arrays.stream(CodeIndex.class.getDeclaredMethods())Reflection reports the erased signatures, which is why block 2 prints Object require(String). The unerased form is in a Signature attribute and reachable through getGenericReturnType(), and it is metadata for compilers rather than something dispatch uses. javap -s shows both side by side.
Object[] anything = catalogue; // legal: arrays are covariant
anything[0] = "TEA"; // a String into a Sku[]Two lines that compile and should not. Sku[] is an Object[], so the assignment is legal, and the store is checked at run time instead: java.lang.ArrayStoreException: java.lang.String. Every array store in Java carries that check, which is a cost paid on all of them for a rule that predates generics.
The same mistake through a List<Sku> does not compile at all. That is the asymmetry: generics chose the compile error, arrays could not, and the two features disagree inside one language.
System.out.println(" a List<Sku> answers `o instanceof List<?>` : " + (o instanceof List<?>));List<?> is the only list shape instanceof accepts, and it tells you nothing about the elements. o instanceof List<Promotion> is error: Object cannot be safely cast to List<Promotion>. So a List<Sku> answers true to "is this a list", and the only way further is to pull an element out and check that.
Worked source
The 13 files of the worked design
Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.
worked/src/Boxing.java205 linesworked/src/CartQuantities.java59 linesworked/src/CodeIndex.java97 linesworked/src/DiscountStage.java25 linesworked/src/Discounts.java60 linesworked/src/Erasure.java104 linesworked/src/FixedAmountCoupon.java37 linesworked/src/LineItem.java36 linesworked/src/MultiBuyPromotion.java55 linesworked/src/PercentageCoupon.java38 linesworked/src/Promotion.java31 linesworked/src/Sku.java33 linesworked/src/Main.java144 lines
worked/src/Boxing.java205 lines
// Boxing.java — what List<Long> costs against long[], measured on a cart-sized subtotal.
//
// A cart's line totals are minor units in a long. There is no List<long>, so a design that keeps
// them in a collection keeps a List<Long>: one heap object per number, one pointer chase per read.
// This file measures the difference instead of asserting it.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public final class Boxing {
/** The subtotal of a cart whose line totals live in a primitive array. */
static long subtotalOf(long[] lineTotals) {
long subtotal = 0;
for (long lineTotal : lineTotals) {
subtotal += lineTotal;
}
return subtotal;
}
/** The same subtotal, with the same numbers, boxed. Every read is an unboxing. */
static long subtotalOf(List<Long> lineTotals) {
long subtotal = 0;
for (Long lineTotal : lineTotals) {
subtotal += lineTotal;
}
return subtotal;
}
/** The escape hatch: a primitive stream, so nothing is ever boxed. */
static long subtotalStreamed(long[] lineTotals) {
return Arrays.stream(lineTotals).sum();
}
static long[] rawLineTotals(int lines) {
long[] out = new long[lines];
for (int i = 0; i < lines; i++) {
out[i] = 450L + (i * 37L) % 4600L;
}
return out;
}
static List<Long> boxedLineTotals(int lines) {
List<Long> out = new ArrayList<>(lines);
for (int i = 0; i < lines; i++) {
out.add(450L + (i * 37L) % 4600L);
}
return out;
}
private static long median(long[] samples) {
long[] sorted = samples.clone();
Arrays.sort(sorted);
return sorted[sorted.length / 2];
}
private static boolean warmed;
/**
* Gets all five methods compiled before anything is timed, on a small cart so it is quick.
*
* Without this the first row measures the interpreter and reports the boxed version as hundreds
* of times slower than it is. Warming up at each measured size instead would spend minutes on
* the million-element row for no extra accuracy: the JIT compiles methods, not array lengths.
* The guard is what keeps that cost paid once rather than once per row.
*/
static long warmUp() {
if (warmed) {
return 0;
}
long[] raw = rawLineTotals(100);
List<Long> boxed = boxedLineTotals(100);
long sink = 0;
for (int i = 0; i < 2_000_000; i++) {
sink += subtotalOf(raw) + subtotalOf(boxed) + subtotalStreamed(raw);
sink += rawLineTotals(100).length + boxedLineTotals(100).size();
}
warmed = true;
return sink;
}
/** One row of the table: read the subtotal `inner` times, `reps` times over, report the median. */
static void readRow(int lines, int reps, int inner) {
long sink = warmUp();
long[] raw = rawLineTotals(lines);
List<Long> boxed = boxedLineTotals(lines);
// Collect once, after the lists exist and before anything is timed. Without it the boxed row
// moves by a factor of two between runs, because the Long objects are left wherever the
// warm-up's garbage happened to leave room. This is the collection the boxed version needs
// and the array version does not, which is itself part of the cost being measured.
collect();
long[] rawTimes = new long[reps];
long[] boxedTimes = new long[reps];
long[] streamTimes = new long[reps];
for (int rep = 0; rep < reps; rep++) {
long t0 = System.nanoTime();
for (int i = 0; i < inner; i++) {
sink += subtotalOf(raw);
}
long t1 = System.nanoTime();
for (int i = 0; i < inner; i++) {
sink += subtotalOf(boxed);
}
long t2 = System.nanoTime();
for (int i = 0; i < inner; i++) {
sink += subtotalStreamed(raw);
}
long t3 = System.nanoTime();
rawTimes[rep] = t1 - t0;
boxedTimes[rep] = t2 - t1;
streamTimes[rep] = t3 - t2;
}
double perRaw = median(rawTimes) / (double) inner;
double perBoxed = median(boxedTimes) / (double) inner;
double perStream = median(streamTimes) / (double) inner;
System.out.printf(" read %-9d long[] %9.1f ns List<Long> %9.1f ns LongStream %9.1f ns x%.1f%n",
lines, perRaw, perBoxed, perStream, perBoxed / perRaw);
if (sink == 42) {
System.out.println(" (the sink is here so nothing above is dead code)");
}
}
/** The other half of the cost: making the boxes in the first place. */
static void buildRow(int lines, int reps, int inner) {
long sink = warmUp();
long[] rawTimes = new long[reps];
long[] boxedTimes = new long[reps];
for (int rep = 0; rep < reps; rep++) {
long t0 = System.nanoTime();
for (int i = 0; i < inner; i++) {
sink += rawLineTotals(lines).length;
}
long t1 = System.nanoTime();
for (int i = 0; i < inner; i++) {
sink += boxedLineTotals(lines).size();
}
long t2 = System.nanoTime();
rawTimes[rep] = t1 - t0;
boxedTimes[rep] = t2 - t1;
}
double perRaw = median(rawTimes) / (double) inner;
double perBoxed = median(boxedTimes) / (double) inner;
System.out.printf(" build %-9d long[] %9.1f ns List<Long> %9.1f ns %22s x%.1f%n",
lines, perRaw, perBoxed, "", perBoxed / perRaw);
if (sink == 42) {
System.out.println(" (sink)");
}
}
/** Bytes of heap per number, held live. Approximate, and the ratio is the useful part. */
static void heapRow(int lines) {
long before = usedHeap();
long[] raw = rawLineTotals(lines);
long afterRaw = usedHeap();
List<Long> boxed = boxedLineTotals(lines);
long afterBoxed = usedHeap();
System.out.printf(" heap %-9d long[] %9.1f bytes/number List<Long> %6.1f bytes/number x%.1f%n",
lines, (afterRaw - before) / (double) lines, (afterBoxed - afterRaw) / (double) lines,
(afterBoxed - afterRaw) / (double) (afterRaw - before));
System.out.println(" both still reachable here: " + raw.length + " and " + boxed.size());
}
private static void collect() {
for (int attempt = 0; attempt < 4; attempt++) {
System.gc();
try {
Thread.sleep(60);
} catch (InterruptedException interrupted) {
Thread.currentThread().interrupt();
}
}
}
private static long usedHeap() {
collect();
Runtime runtime = Runtime.getRuntime();
return runtime.totalMemory() - runtime.freeMemory();
}
/**
* The Integer cache, which is why a boxing bug passes its first test.
*
* Integer.valueOf caches -128..127, so == on two boxes of the same small number is true. A cart
* quantity of 100 and a cart quantity of 200 take different branches through the same line of
* code. Long has the same cache and the same trap. J6 is the lesson on ==; the new fact here is
* that the box is created by the compiler, so there is no `new` on the line to warn you.
*/
static void integerCache() {
int small = 100;
int large = 200;
System.out.println(" quantity 100, boxed twice, compared with == : "
+ (Integer.valueOf(small) == Integer.valueOf(small)));
System.out.println(" quantity 200, boxed twice, compared with == : "
+ (Integer.valueOf(large) == Integer.valueOf(large)));
System.out.println(" line total 450 as Long, compared with == : "
+ (Long.valueOf(450) == Long.valueOf(450)));
System.out.println(" Integer.valueOf caches -128..127, so the first line is true by luck");
}
private Boxing() {}
}worked/src/CartQuantities.java59 lines
// CartQuantities.java — the sku-to-quantity map CartLines would keep if it kept counts, not lines.
//
// A quantity is an int. There is no Map<String, int>, so this is a Map<String, Integer>, and that
// substitution brings two things an int never had: it can be null, and two of them can be different
// objects holding the same number.
import java.util.LinkedHashMap;
import java.util.Map;
public final class CartQuantities {
private final Map<String, Integer> byCode = new LinkedHashMap<>();
/** Sets a sku's quantity outright. Zero removes the line, as ShoppingCartApi.setQuantity does. */
public void set(String skuCode, int quantity) {
if (quantity < 0) {
throw new IllegalArgumentException("a quantity cannot be negative: " + quantity);
}
if (quantity == 0) {
byCode.remove(skuCode);
} else {
byCode.put(skuCode, quantity);
}
}
/**
* How many of this sku the cart holds, or 0 for a sku it does not hold.
*
* getOrDefault, not get. `return byCode.get(skuCode)` compiles, because javac unboxes it for
* you, and throws NullPointerException on the first sku the cart does not hold.
*/
public int quantityOf(String skuCode) {
return byCode.getOrDefault(skuCode, 0);
}
/**
* Whether the cart holds exactly this many of a sku.
*
* The int comparison is deliberate. Comparing the boxes with == is true for quantities up to 127
* and false from 128 up, because Integer.valueOf caches the small ones.
*/
public boolean holdsExactly(String skuCode, int quantity) {
return quantityOf(skuCode) == quantity;
}
/** The same question asked wrongly, kept so it can be run. Boxes both sides and compares them. */
public boolean holdsExactlyByReference(String skuCode, int quantity) {
Integer held = byCode.get(skuCode);
return held == Integer.valueOf(quantity);
}
/** Quantities added up — ShoppingCartApi.itemCount. */
public int itemCount() {
int items = 0;
for (int quantity : byCode.values()) {
items += quantity;
}
return items;
}
}worked/src/CodeIndex.java97 lines
// CodeIndex.java — the one class that Catalog and CouponBook both are.
//
// corpus/shopping-cart/reference/src/ holds two classes with the same shape: a read-only map from
// a String code to a value, and a require(code) that throws IllegalArgumentException when the code
// is unknown. Catalog does it for Sku, CouponBook does it for Promotion. In C++ that duplication is
// one template and two instantiations. In Java it is one type parameter and ONE compiled class.
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.function.IntFunction;
public final class CodeIndex<T> {
/**
* How many lookups every CodeIndex in this JVM has answered, added together.
*
* Static, and there is exactly one of it, because there is exactly one CodeIndex class. A C++
* template would give this field once per instantiation: one counter for Sku, another for
* Promotion. Main block 4 prints the difference.
*/
private static long lookupsAcrossAllIndexes;
/** This index's own count. An instance field, so a catalogue and a coupon book count apart. */
private long lookups;
/**
* What kind of thing this indexes: "sku", "coupon". Carried as data because erasure removed the
* only other way to find out.
*
* Catalog.require says "no such sku: " and CouponBook.require says "no such coupon: ", and both
* messages are asserted by the grader. A template gets that name for free from T. Here the
* bytecode holds Object where T was written, so at run time this object cannot answer "what am I
* an index of". If the label is not passed in, it does not exist.
*/
private final String what;
private final Map<String, T> byCode;
public CodeIndex(String what, Map<String, T> byCode) {
this.what = Objects.requireNonNull(what, "what");
this.byCode = new LinkedHashMap<>(Objects.requireNonNull(byCode, "byCode"));
}
/**
* The value this code names.
*
* @throws IllegalArgumentException if there is no such code. An unknown code is a caller's
* mistake, not an expected absence — Catalog.require's own
* reasoning, unchanged.
*/
public T require(String code) {
Objects.requireNonNull(code, "code");
lookups++;
lookupsAcrossAllIndexes++;
T found = byCode.get(code);
if (found == null) {
throw new IllegalArgumentException("no such " + what + ": " + code);
}
return found;
}
/** Everything indexed, in the order it was written. Immutable, so handing it out is safe. */
public List<T> all() {
return List.copyOf(byCode.values());
}
/**
* The same values as a T[], for a caller that wants an array.
*
* The IntFunction is not ceremony. `new T[n]` does not compile, so the array has to be made
* somewhere that knows the real type, and the only such place is the caller: Sku[]::new.
*/
public T[] toArray(IntFunction<T[]> newArray) {
return byCode.values().toArray(newArray);
}
/**
* The same thing done the way it looks like it should be done, and it is wrong.
*
* The cast compiles with an unchecked warning and this method returns normally. What it returns
* is an Object[], and the ClassCastException lands on the CALLER's line, because that is where
* javac put the checkcast. Main block 3 catches it and prints the frame.
*/
@SuppressWarnings("unchecked")
public T[] toArrayTheWayItLooks() {
return (T[]) byCode.values().toArray();
}
public long lookups() {
return lookups;
}
public static long lookupsAcrossAllIndexes() {
return lookupsAcrossAllIndexes;
}
}worked/src/DiscountStage.java25 lines
// Copied unchanged from corpus/shopping-cart/reference/src/DiscountStage.java.
/**
* When a discount is worked out, relative to the other discounts.
*
* The requirement fixes this order and says so in the contract: item promotions, then percentage
* coupons, then fixed amounts, each computed on what is still owed after the earlier ones. So the
* order is <b>not</b> a design invention — it is the requirement, written down once, in
* declaration order, where {@link Totals} can sort by it.
*
* <p>The alternative is to rely on the order things happen to be wired up in. That works right up
* until someone adds a promotion to the wrong line of the factory and every price in the shop
* moves by a few cents, silently, with no test to catch it. A stage is the promotion's own
* property, so it cannot be got wrong from the outside.
*/
public enum DiscountStage {
/** "Buy two get one free" and friends: worked out from the lines themselves. */
ITEM_PROMOTION,
/** A percentage off what is owed. */
PERCENTAGE_COUPON,
/** A flat amount off what is owed. Last, so a percentage never discounts a discount. */
FIXED_AMOUNT_COUPON
}worked/src/Discounts.java60 lines
// Discounts.java — Totals.price's discount stage, with the wildcards the reference does not have.
//
// corpus/shopping-cart/reference/src/Totals.java declares price(List<LineItem>, List<Promotion>).
// That second parameter is read and never written, so it should be List<? extends Promotion>. The
// reference gets away with List<Promotion> because Cart.activePromotions() happens to build exactly
// that type. Main block 6 shows the caller it refuses.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public final class Discounts {
/**
* Every discount on a cart, added up, capped at what is owed. Totals.price's middle stage.
*
* `? extends Promotion` because this method only ever takes promotions OUT of the list. It never
* puts one in, so it does not care whether the list is a List<Promotion>, a
* List<PercentageCoupon> or a List<MultiBuyPromotion>.
*/
public static long total(List<? extends Promotion> promotions, List<LineItem> lines, long subtotalMinor) {
long owed = subtotalMinor;
long discount = 0;
for (Promotion promotion : inStageOrder(promotions)) {
long off = Math.min(Math.max(0, promotion.discountMinor(lines, owed)), owed);
discount += off;
owed -= off;
}
return discount;
}
/**
* The promotions sorted into the order the requirement fixes: item promotions, then percentage
* coupons, then fixed amounts.
*
* The copy is not about the wildcard. `promotions.sort(...)` compiles on a
* List<? extends Promotion> — sort takes a Comparator<? super E> and Comparator<Promotion>
* satisfies that. It would sort the caller's list, which is a side effect on an argument this
* method was only asked to read.
*/
public static List<Promotion> inStageOrder(List<? extends Promotion> promotions) {
List<Promotion> ordered = new ArrayList<>(promotions);
ordered.sort(Comparator.comparing(Promotion::stage));
return ordered;
}
/**
* Cart.activePromotions in the shape that does not need a List<Promotion> to write into.
*
* `? super Promotion` because this method only ever puts promotions IN. Any list that can hold a
* Promotion will do, including a List<Object>, and the caller keeps its own wider type.
*/
public static void collectInto(List<? super Promotion> sink,
List<? extends Promotion> standing,
CodeIndex<? extends Promotion> couponBook) {
sink.addAll(standing);
sink.addAll(couponBook.all());
}
private Discounts() {}
}worked/src/Erasure.java104 lines
// Erasure.java — the evidence that CodeIndex<Sku> and CodeIndex<Promotion> are one class.
//
// Everything here reads the running program rather than describing it: the Class objects, the
// method signatures the JVM actually holds, and the invariance rule against the array rule.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
public final class Erasure {
/** Two parameterisations, one Class object. This is erasure, observed. */
static void oneClassNotTwo(CodeIndex<Sku> catalogue, CodeIndex<Promotion> couponBook) {
System.out.println(" catalogue.getClass() == couponBook.getClass() : "
+ (catalogue.getClass() == couponBook.getClass()));
System.out.println(" both report : " + catalogue.getClass().getName());
List<Sku> skus = new ArrayList<>();
List<String> codes = new ArrayList<>();
System.out.println(" List<Sku> and List<String> share a Class too : "
+ (skus.getClass() == codes.getClass()));
}
/** What the JVM holds for require and toArray, after javac finished with them. */
static void erasedSignatures() {
Arrays.stream(CodeIndex.class.getDeclaredMethods())
.filter(m -> m.getName().equals("require") || m.getName().equals("toArray"))
.sorted((a, b) -> a.getName().compareTo(b.getName()))
.forEach(m -> System.out.println(" " + m.getReturnType().getSimpleName()
+ " " + m.getName() + "(" + Arrays.stream(m.getParameterTypes())
.map(Class::getSimpleName).reduce((a, b) -> a + ", " + b).orElse("") + ")"));
System.out.println(" T became Object, and the caller got a cast it did not write");
}
/**
* The one instanceof question you are allowed to ask, and the answer it gives.
*
* `o instanceof List<Promotion>` does not compile. `o instanceof List<?>` does, and it tells you
* nothing about what is inside, so a list of skus answers true to "is this a list of promotions".
*/
static void whatInstanceofCanStillSee(List<Sku> skus) {
Object o = skus;
System.out.println(" a List<Sku> answers `o instanceof List<?>` : " + (o instanceof List<?>));
List<?> anyList = (List<?>) o;
System.out.println(" first element's real class : "
+ anyList.get(0).getClass().getSimpleName());
System.out.println(" so the elements can be checked, the list cannot");
}
/**
* Generics are invariant. Arrays are covariant. The asymmetry is the trap.
*
* A List<PercentageCoupon> is not a List<Promotion> and javac says so. A Sku[] IS an Object[],
* javac says nothing, and the JVM catches the store at run time instead.
*/
static void invarianceAgainstArrays() {
Sku[] catalogue = {
new Sku("TEA", "Loose leaf tea", 450),
new Sku("MUG", "Enamel mug", 1250),
};
Object[] anything = catalogue; // legal: arrays are covariant
System.out.println(" Sku[] assigned to Object[] : compiles, runs");
try {
anything[0] = "TEA"; // a String into a Sku[]
System.out.println(" storing a String in it : allowed");
} catch (ArrayStoreException stored) {
System.out.println(" storing a String in it : "
+ stored.getClass().getName() + ": " + stored.getMessage());
}
System.out.println(" the same mistake through a List<Sku> is a compile error, which is the point");
}
/**
* The unchecked cast, and where its exception lands.
*
* toArrayTheWayItLooks returns normally. The throw happens on the assignment below, because that
* is where javac inserted the checkcast — so the stack frame names the caller, not the cast.
*/
static void whereTheCastActuallyIs(CodeIndex<Sku> catalogue) {
Sku[] right = catalogue.toArray(Sku[]::new);
System.out.println(" toArray(Sku[]::new) : "
+ right.length + " skus, first " + right[0].code());
try {
Sku[] wrong = catalogue.toArrayTheWayItLooks();
System.out.println(" toArrayTheWayItLooks() : " + wrong.length);
} catch (ClassCastException cast) {
System.out.println(" toArrayTheWayItLooks() : "
+ cast.getClass().getName());
System.out.println(" message : " + cast.getMessage().split(" \\(")[0]);
System.out.println(" thrown at: " + cast.getStackTrace()[0]);
}
}
/** A cheap way to see that Map.of() carries no type information at run time either. */
static void mapsToo() {
Map<String, Sku> byCode = Map.of();
Map<String, Promotion> byCoupon = Map.of();
System.out.println(" Map<String,Sku> and Map<String,Promotion> : "
+ (byCode.getClass() == byCoupon.getClass()) + ", both "
+ byCode.getClass().getSimpleName());
}
private Erasure() {}
}worked/src/FixedAmountCoupon.java37 lines
// Copied unchanged from corpus/shopping-cart/curveballs/01-coupons-that-stack/reference-patch/FixedAmountCoupon.java.
import java.util.List;
/**
* A flat amount off what is owed — the {@code FIVER} coupon is one of these with 500.
*
* <p>Note what it does <b>not</b> do: it does not check whether 500 is more than the cart is
* worth. It answers the only question it is competent to answer — "how much do I take off?" — and
* {@link Totals} caps the answer at what is still owed. That is why the requirement's "we never
* pay a customer to shop with us" needed no code written here: the cap was already in the one
* place that can see all the discounts at once.
*
* <p>{@link DiscountStage#FIXED_AMOUNT_COUPON} is the whole of "percentage first, then the flat
* amount". The order is this class's own property rather than a position in a list somewhere else,
* so it cannot be wired up wrongly.
*/
public final class FixedAmountCoupon implements Promotion {
private final long amountMinor;
public FixedAmountCoupon(long amountMinor) {
if (amountMinor < 0) {
throw new IllegalArgumentException("a voucher takes money off, not on: " + amountMinor);
}
this.amountMinor = amountMinor;
}
@Override
public DiscountStage stage() {
return DiscountStage.FIXED_AMOUNT_COUPON;
}
@Override
public long discountMinor(List<LineItem> lines, long amountOwedMinor) {
return amountMinor;
}
}worked/src/LineItem.java36 lines
// Copied unchanged from corpus/shopping-cart/contract/LineItem.java.
import java.util.Objects;
/**
* A snapshot of one line in the cart: what it is, how many, and what the line comes to.
*
* A <i>snapshot</i>, not the line itself. Handing one out never lets a caller change the cart,
* and two snapshots of the same sku taken before and after a quantity change are two different
* values.
*
* <p>{@code lineTotalMinor} is redundant on purpose — it is always
* {@code sku.unitPriceMinor() * quantity} and the constructor refuses anything else. It is
* carried because a line total is what a receipt prints, and computing it in two places is how
* two places come to disagree.
*
* @param sku what is on the line. Never null
* @param quantity how many. Zero or more — a zero-quantity line is what
* {@link ShoppingCartApi#setQuantity(String, int)} hands back to describe
* a line it has just removed. The cart itself never <i>holds</i> a
* zero-quantity line
* @param lineTotalMinor unit price times quantity, in minor units. Exact: no rounding happens
* here, because multiplying whole minor units cannot produce a fraction
*/
public record LineItem(Sku sku, int quantity, long lineTotalMinor) {
public LineItem {
Objects.requireNonNull(sku, "sku");
if (quantity < 0) {
throw new IllegalArgumentException("a line cannot hold " + quantity + " items");
}
if (lineTotalMinor != sku.unitPriceMinor() * quantity) {
throw new IllegalArgumentException("a line total must be unit price times quantity: "
+ sku.unitPriceMinor() + " x " + quantity + " is not " + lineTotalMinor);
}
}
}worked/src/MultiBuyPromotion.java55 lines
// Copied unchanged from corpus/shopping-cart/curveballs/02-buy-two-get-one/reference-patch/MultiBuyPromotion.java.
import java.util.List;
import java.util.Objects;
/**
* "N for the price of N-1" on one sku: three teas for the price of two is
* {@code new MultiBuyPromotion("TEA", 3)}.
*
* <h2>Why it reads the lines and not the amount owed</h2>
* This is the first promotion in the design that cares <i>what</i> is in the basket rather than
* only <i>how much</i> it comes to, which is exactly why {@link Promotion} was given the lines as
* well as the running total. Nothing about that signature changed to let this exist.
*
* <p>It takes the line's quantity as it stands and charges nothing for every {@code groupSize}-th
* item: {@code quantity / groupSize} free at the line's own unit price. Integer division is the
* whole of "seven teas still means two free" — no special case, and no rounding, because a count of
* free items is a count.
*
* <p>{@link DiscountStage#ITEM_PROMOTION} places it before the coupons, so the percentage applies
* to what is left after the free tea. That was already the stated order; this class only declares
* which stage it belongs to.
*
* <p>Note what it does not do: it does not change the line. The basket still shows three teas at
* 450, because the warehouse still picks three and the customer still wants to see what they saved.
* A design that decremented the quantity would have to un-decrement it when the offer ended, and
* would report the wrong subtotal in the meantime.
*/
public final class MultiBuyPromotion implements Promotion {
private final String skuCode;
private final int groupSize;
public MultiBuyPromotion(String skuCode, int groupSize) {
this.skuCode = Objects.requireNonNull(skuCode, "skuCode");
if (groupSize < 2) {
throw new IllegalArgumentException("a multi-buy needs at least two to buy, not " + groupSize);
}
this.groupSize = groupSize;
}
@Override
public DiscountStage stage() {
return DiscountStage.ITEM_PROMOTION;
}
@Override
public long discountMinor(List<LineItem> lines, long amountOwedMinor) {
for (LineItem line : lines) {
if (line.sku().code().equals(skuCode)) {
return (long) (line.quantity() / groupSize) * line.sku().unitPriceMinor();
}
}
return 0;
}
}worked/src/PercentageCoupon.java38 lines
// Copied unchanged from corpus/shopping-cart/reference/src/PercentageCoupon.java.
import java.util.List;
/**
* A percentage off what is owed — the {@code SAVE10} coupon is one of these with 10.
*
* <h2>The only rounding in the whole problem, and it is integer arithmetic</h2>
* {@code (amount * percent + 50) / 100} is <b>half up</b> in whole minor units:
* 10% of 899 is 8990 + 50 = 9040, over 100, is 90. There is no {@code double} in it, so there is
* nothing to lose precision and nothing to drift. The {@code + 50} <i>is</i> the rounding rule,
* written once, in the one class whose job it is.
*
* <p>{@code amount * percent} is a {@code long} multiplication of two values bounded by a cart
* total and 100, so it cannot overflow for any cart a shop can physically fulfil.
*/
public final class PercentageCoupon implements Promotion {
private static final long HALF_UP = 50;
private final long percent;
public PercentageCoupon(long percent) {
if (percent < 0 || percent > 100) {
throw new IllegalArgumentException("a percentage off is between 0 and 100, not " + percent);
}
this.percent = percent;
}
@Override
public DiscountStage stage() {
return DiscountStage.PERCENTAGE_COUPON;
}
@Override
public long discountMinor(List<LineItem> lines, long amountOwedMinor) {
return (amountOwedMinor * percent + HALF_UP) / 100;
}
}worked/src/Promotion.java31 lines
// Copied unchanged from corpus/shopping-cart/reference/src/Promotion.java.
import java.util.List;
/**
* Something that takes money off a cart: a coupon, a multi-buy, a seasonal offer.
*
* <p>Two methods, and the second one is <b>pure</b>: it is handed the lines and the amount still
* owed, and it answers with a number. It cannot see the cart, cannot change anything, and cannot
* decide whether it is allowed to be here. That is what makes discounts composable — {@link
* Totals} can run several of them in a defined order, cap the result, and know that asking twice
* gives the same answer.
*
* <p>The interface is deliberately about <i>discount</i>, not about <i>coupon</i>. A coupon is one
* way a discount gets attached to a cart (a code the customer typed); a multi-buy is another (it
* is simply always on). Both compute money off, so both are this.
*/
public interface Promotion {
/** When this one is worked out relative to the others. Never null. */
DiscountStage stage();
/**
* How much to take off, in minor units.
*
* @param lines the cart's lines, for a promotion that cares what is in the basket
* @param amountOwedMinor what is still owed after the earlier stages — never negative
* @return zero or more. Returning more than is owed is not a bug: {@link Totals} caps it, so
* a promotion never has to think about the other promotions
*/
long discountMinor(List<LineItem> lines, long amountOwedMinor);
}worked/src/Sku.java33 lines
// Copied unchanged from corpus/shopping-cart/contract/Sku.java.
import java.util.Objects;
/**
* One thing that can be bought: its code, its name and what one of it costs.
*
* A <b>value</b>, not an entity. Two skus with the same code and a different price are two
* different values, and the cart is free to model its own catalogue however it likes — this is
* only what crosses the boundary.
*
* <p>{@code unitPriceMinor} is in <b>minor units</b> (cents, paise, pence) held in a
* {@code long}. There is no {@code double} and no {@code float} anywhere in this problem: money
* is counted, not measured. See {@link ShoppingCartApi} for the whole money convention.
*
* @param code the catalogue code, e.g. "TEA". Never null, never blank. Compared
* exactly — codes are case-sensitive
* @param name what a human calls it, e.g. "Loose leaf tea". Never null
* @param unitPriceMinor the price of one, in minor units. Zero or more; a free gift is a
* legitimate sku
*/
public record Sku(String code, String name, long unitPriceMinor) {
public Sku {
Objects.requireNonNull(code, "code");
Objects.requireNonNull(name, "name");
if (code.isBlank()) {
throw new IllegalArgumentException("a sku needs a code");
}
if (unitPriceMinor < 0) {
throw new IllegalArgumentException("a price cannot be negative: " + unitPriceMinor);
}
}
}worked/src/Main.java144 lines
// Main.java — runs every claim in this lesson and prints what actually happened.
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public final class Main {
static CodeIndex<Sku> standardCatalogue() {
Map<String, Sku> byCode = new LinkedHashMap<>();
for (Sku sku : List.of(
new Sku("TEA", "Loose leaf tea", 450),
new Sku("MUG", "Enamel mug", 1250),
new Sku("SOCK", "Wool socks", 899),
new Sku("BEAN", "Coffee beans 1kg", 1899),
new Sku("LAMP", "Desk lamp", 4599))) {
byCode.put(sku.code(), sku);
}
return new CodeIndex<>("sku", byCode);
}
static CodeIndex<Promotion> standardCoupons() {
Map<String, Promotion> byCode = new LinkedHashMap<>();
byCode.put("SAVE10", new PercentageCoupon(10));
byCode.put("FIVER", new FixedAmountCoupon(500));
return new CodeIndex<>("coupon", byCode);
}
public static void main(String[] args) {
CodeIndex<Sku> catalogue = standardCatalogue();
CodeIndex<Promotion> coupons = standardCoupons();
System.out.println("== 1 - Catalog and CouponBook are one class here, and the label is why ==");
System.out.println(" require(\"TEA\") " + catalogue.require("TEA"));
System.out.println(" require(\"SAVE10\") " + coupons.require("SAVE10").stage());
refuse(() -> catalogue.require("NOPE"), " catalogue.require(\"NOPE\")");
refuse(() -> coupons.require("SAVE99"), " coupons.require(\"SAVE99\")");
System.out.println(" the two messages differ only because \"sku\" and \"coupon\" were passed in");
System.out.println();
System.out.println("== 2 - one class, not two ==");
Erasure.oneClassNotTwo(catalogue, coupons);
Erasure.mapsToo();
Erasure.erasedSignatures();
System.out.println();
System.out.println("== 3 - new T[n] does not exist, so the caller makes the array ==");
Erasure.whereTheCastActuallyIs(catalogue);
System.out.println();
System.out.println("== 4 - static is shared, because there is one class to hold it ==");
System.out.println(" catalogue.lookups() : " + catalogue.lookups());
System.out.println(" coupons.lookups() : " + coupons.lookups());
System.out.println(" CodeIndex.lookupsAcrossAllIndexes() : "
+ CodeIndex.lookupsAcrossAllIndexes() + " <- both, added up");
System.out.println();
System.out.println("== 5 - generics are invariant, arrays are covariant ==");
Erasure.invarianceAgainstArrays();
Erasure.whatInstanceofCanStillSee(catalogue.all());
System.out.println();
System.out.println("== 6 - PECS on Totals.price's second parameter ==");
List<LineItem> lines = List.of(
new LineItem(catalogue.require("SOCK"), 1, 899),
new LineItem(catalogue.require("MUG"), 4, 5000));
long subtotal = 899 + 5000;
List<PercentageCoupon> onlyPercentages = List.of(new PercentageCoupon(10));
// Wired up in the order a factory happens to call plusPromotion, which is not stage order.
List<Promotion> mixed = new ArrayList<>(List.of(
new FixedAmountCoupon(500),
new PercentageCoupon(10),
new MultiBuyPromotion("MUG", 4)));
System.out.printf(" subtotal : %d%n", subtotal);
System.out.printf(" total(List<PercentageCoupon>, ...) : %d%n",
Discounts.total(onlyPercentages, lines, subtotal));
System.out.printf(" total(List<Promotion>, ...) : %d%n",
Discounts.total(mixed, lines, subtotal));
System.out.println(" the mixed list as it was wired up : " + stages(mixed));
System.out.println(" inStageOrder(...) hands back : "
+ stages(Discounts.inStageOrder(mixed)));
System.out.println(" the caller's list afterwards : " + stages(mixed));
System.out.println(" the last two lines differ, so the copy is doing real work");
List<Object> anythingAtAll = new ArrayList<>();
Discounts.collectInto(anythingAtAll, onlyPercentages, coupons);
System.out.println(" collectInto(List<Object>, ...) : accepted, "
+ anythingAtAll.size() + " promotions written");
System.out.println();
System.out.println("== 7 - there is no Map<String, int>, so absent is null ==");
CartQuantities quantities = new CartQuantities();
quantities.set("TEA", 4);
quantities.set("MUG", 100);
System.out.println(" quantityOf(\"TEA\") : " + quantities.quantityOf("TEA"));
System.out.println(" quantityOf(\"LAMP\"), never added : " + quantities.quantityOf("LAMP"));
System.out.println(" itemCount() : " + quantities.itemCount());
System.out.println(" holdsExactly(\"MUG\", 100) : "
+ quantities.holdsExactly("MUG", 100));
System.out.println(" holdsExactlyByReference(\"MUG\", 100) : "
+ quantities.holdsExactlyByReference("MUG", 100) + " <- passes, by luck");
quantities.set("MUG", 200);
System.out.println(" holdsExactly(\"MUG\", 200) : "
+ quantities.holdsExactly("MUG", 200));
System.out.println(" holdsExactlyByReference(\"MUG\", 200) : "
+ quantities.holdsExactlyByReference("MUG", 200) + " <- same code, 200 instead of 100");
System.out.println();
System.out.println("== 8 - what boxing costs, measured on this JVM ==");
Boxing.readRow(5, 11, 2_000_000);
Boxing.readRow(50, 11, 500_000);
Boxing.readRow(1_000, 11, 50_000);
Boxing.readRow(1_000_000, 5, 20);
Boxing.buildRow(5, 11, 1_000_000);
Boxing.buildRow(50, 11, 200_000);
Boxing.buildRow(1_000, 11, 20_000);
Boxing.heapRow(1_000_000);
Boxing.integerCache();
}
private static List<DiscountStage> stages(List<? extends Promotion> promotions) {
List<DiscountStage> out = new ArrayList<>();
for (Promotion promotion : promotions) {
out.add(promotion.stage());
}
return out;
}
/** Runs something expected to fail and prints how it failed, as corpus Demo.java does. */
private static void refuse(Runnable attempt, String what) {
try {
attempt.run();
System.out.println(what + ": UNEXPECTEDLY ALLOWED");
} catch (RuntimeException failed) {
System.out.println(what + ": " + failed.getClass().getSimpleName()
+ ": " + failed.getMessage());
}
}
private Main() {}
}The faded stage is not here, on purpose
In the app, the third stage of a lesson hands you the worked design with a few lines
replaced by // GAP: markers, then compiles your completion and runs a JUnit suite
against it. That needs javac, and a static site has no compiler — so rather than show a
control that cannot work, this page stops at the worked source.
Run the app for the drill: it is the download in the header, and it works offline once unpacked.