I suggest that value semantics are appropriate for stacks - that one stack containing
[1, 2, 3] and another stack containing
[1, 2, 3] should be considered as equal, because there’s no way to tell them apart should one be swapped for another.
We begin by modifying our interface declaration to include
IEquatable<T>; this provides a better API for our consumers than just overriding
As we want to compare two stacks to see if they are equal, we need the items in our stacks to be comparable as well, so we include the constraint on T.
The implementation for
EmptyImmutableStack<T> is very easy, as every instance can be substituted for any other, so we only need the check for null and a check for the type.
Performance is something to consider when we implement for
SimpleImmutableStack<T>, as we don’t want to be comparing every item in the stack if we don’t have to.
Remember that implementing equality involves overriding
Equals(object), and that requires also overriding
GetHashCode(). The contract between these methods is simple - equal objects must have equal hash codes, and the hash code must never change during the lifetime of the object.
We can use this contract to make our code more efficient - we’ll cache the value of
GetHashCode() to avoid recalculation every time we use it, and we’ll use it to short-circuit our
How does this work?
- If other is null or an empty queue, we’re obviously not equal.
- If the hash codes are different, we’re not equal.
- If both
otherare the same exact instance, we’re equal.
- If the items on the top of the stack not equal, we’re not equal.
- Otherwise, check the remainder of the stack for equality.