/**
* Copyright (C) 2022 by Martin Robillard. See https://codesample.info/about.html
*/
package e2.chapter3;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
/**
* Represents a deck of playing cards. In this version, the cards in the
* deck are stored in a list and the list of cards in the deck can
* be obtained by client code using an immutable wrapper object.
*
* This version of the Deck class also implements {@link CardSource}
* and has a sort() method to demonstrate the use of comparators.
*
* The Deck is also iterable: it fulfills the role of ConcreteIterable
* in the Iterator design pattern.
*/
public class Deck implements CardSource, {
private List<Card> aCards = new ArrayList<>();
/**
* Creates a new deck of 52 cards, shuffled.
*/
public Deck() {
shuffle();
}
/**
* Reinitializes the deck with all 52 cards, and shuffles them.
*/
public void shuffle() {
aCards.clear();
for( Suit suit : Suit.values() ) {
for( Rank rank : Rank.values() ) {
aCards.add( new Card( rank, suit ));
}
}
Collections.shuffle(aCards);
}
/**
* Places pCard on top of the deck.
* @param pCard The card to place on top
* of the deck.
* @pre pCard !=null
*/
public void push(Card pCard) {
assert pCard != null;
aCards.add(pCard);
}
/**
* Draws a card from the deck: removes the card from the top
* of the deck and returns it.
* @return The card drawn.
* @pre !isEmpty()
*/
@Override
public Card draw() {
assert !isEmpty();
return aCards.remove(aCards.size() - 1);
}
/**
* @return True if and only if there are no cards in the deck.
*/
@Override
public boolean isEmpty() {
return aCards.isEmpty();
}
/**
* @return An unmodifiable list of all the cards in the deck.
*/
public List<Card> {
return Collections.unmodifiableList(aCards);
}
/**
* Sorts the cards in the deck by ascending rank.
*/
public void sort() {
Collections.sort(aCards, new () {
@Override
public int compare(Card pCard1, Card pCard2) {
return pCard1.getRank().compareTo(pCard2.getRank());
}
});
}
@Override
public Iterator<Card> {
return aCards.iterator();
}
}
This code takes advantage of the static method values(), which
is implicitly defined on any enumerated type. This method returns
an array of all the enumerated values for the type, in their declaration order.
This code takes advantage of the static method values(), which
is implicitly defined on any enumerated type. This method returns
an array of all the enumerated values for the type, in their declaration order.
This method illustrates a way to obtain all the cards in the deck without breaking encapsulation. It relies on a library method that returns an unmodifiable view of the field.
This method illustrates a way to obtain all the cards in the deck without breaking encapsulation. It relies on a library method that returns an unmodifiable view of the field.
This code supplies an anonymous function object of type Comparator<Card>
as second argument to method sort.
This code supplies an anonymous function object of type Comparator<Card>
as second argument to method sort.
This method returns an object that fulfills the role of the iterator in the Iterator design pattern. The return type of the method is an abstract iterator (an interface), but the method returns a concrete iterator (an actual object).
This method returns an object that fulfills the role of the iterator in the Iterator design pattern. The return type of the method is an abstract iterator (an interface), but the method returns a concrete iterator (an actual object).
This statement illustrates the concept of delegation, which we will revisit in
Chapter 6. The contract of the interface requires this method to return an object
of type Iterator. Instead of creating an new Iterator, this method requests
the iterator object provided by the underlying list stored in field aCards, and returns it
instead. The iterator supplied by ArrayList works here because it's an iterator
over Card objects that will provide an iteration over exactly the sequence of cards
represented by the Deck. Note that this code technically breaks encapsulation because
interface Iterator has a remove method that changes the underlying collection. However,
for simplicity, we assume that by convention, this remove method will never be called in our code.
This statement illustrates the concept of delegation, which we will revisit in
Chapter 6. The contract of the interface requires this method to return an object
of type Iterator. Instead of creating an new Iterator, this method requests
the iterator object provided by the underlying list stored in field aCards, and returns it
instead. The iterator supplied by ArrayList works here because it's an iterator
over Card objects that will provide an iteration over exactly the sequence of cards
represented by the Deck. Note that this code technically breaks encapsulation because
interface Iterator has a remove method that changes the underlying collection. However,
for simplicity, we assume that by convention, this remove method will never be called in our code.
An alternative to clearing the list would be to create a new one. However, clearing the list makes the program easier to understand, because we only have one list object to track. This notion is covered in detail in Chapter 4.
An alternative to clearing the list would be to create a new one. However, clearing the list makes the program easier to understand, because we only have one list object to track. This notion is covered in detail in Chapter 4.
Defines the role of the abstract iterable in the Iterator design pattern. An abstract iterable is any object on which it is possible to iterate.
Chapter 3, insight #4
Use library interface types, such as Comparable, to implement commonly expected behavior
for statement (sometimes called the "for-each loop" statement).Defines the role of the abstract iterable in the Iterator design pattern. An abstract iterable is any object on which it is possible to iterate.
Chapter 3, insight #4
Use library interface types, such as Comparable, to implement commonly expected behavior
for statement (sometimes called the "for-each loop" statement).for statementList interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
List list = Collections.synchronizedList(new ArrayList(...));
The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
This class is a member of the Java Collections Framework.
The main difference between Comparable and Comparator is that Comparable
is implemented by the objects that are being compared, whereas Comparator
is implemented by some other object that does the comparison. For this
reason, method compare of Comparator requires to pass in both
objects being compared.
Collections.sort or Arrays.sort) to allow precise control over the sort order.
Comparators can also be used to control the order of certain data
structures (such as sorted sets or
sorted maps), or to provide an ordering for
collections of objects that don't have a natural ordering.The main difference between Comparable and Comparator is that Comparable
is implemented by the objects that are being compared, whereas Comparator
is implemented by some other object that does the comparison. For this
reason, method compare of Comparator requires to pass in both
objects being compared.
Collections.sort or Arrays.sort) to allow precise control over the sort order.
Comparators can also be used to control the order of certain data
structures (such as sorted sets or
sorted maps), or to provide an ordering for
collections of objects that don't have a natural ordering.
The ordering imposed by a comparator c on a set of elements
S is said to be consistent with equals if and only if
c.compare(e1, e2)==0 has the same boolean value as
e1.equals(e2) for every e1 and e2 in
S.
Caution should be exercised when using a comparator capable of imposing an
ordering inconsistent with equals to order a sorted set (or sorted map).
Suppose a sorted set (or sorted map) with an explicit comparator c
is used with elements (or keys) drawn from a set S. If the
ordering imposed by c on S is inconsistent with equals,
the sorted set (or sorted map) will behave "strangely." In particular the
sorted set (or sorted map) will violate the general contract for set (or
map), which is defined in terms of equals.
For example, suppose one adds two elements a and b such that
(a.equals(b) && c.compare(a, b) != 0)
to an empty TreeSet with comparator c.
The second add operation will return
true (and the size of the tree set will increase) because a and
b are not equivalent from the tree set's perspective, even though
this is contrary to the specification of the
Set.add method.
Note: It is generally a good idea for comparators to also implement
java.io.Serializable, as they may be used as ordering methods in
serializable data structures (like TreeSet, TreeMap). In
order for the data structure to serialize successfully, the comparator (if
provided) must implement Serializable.
For the mathematically inclined, the relation that defines the
imposed ordering that a given comparator c imposes on a
given set of objects S is:
{(x, y) such that c.compare(x, y) <= 0}.
The quotient for this total order is: {(x, y) such that c.compare(x, y) == 0}.
It follows immediately from the contract for compare that the
quotient is an equivalence relation on S, and that the
imposed ordering is a total order on S. When we say that
the ordering imposed by c on S is consistent with
equals, we mean that the quotient for the ordering is the equivalence
relation defined by the objects' equals(Object) method(s): {(x, y) such that x.equals(y)}.
In other words, when the imposed ordering is consistent with
equals, the equivalence classes defined by the equivalence relation
of the equals method and the equivalence classes defined by
the quotient of the compare method are the same.
Unlike Comparable, a comparator may optionally permit
comparison of null arguments, while maintaining the requirements for
an equivalence relation.
This interface is a member of the Java Collections Framework.
compareTo in interface Comparable<E extends Enum<E>>
o - the object to be compared.
The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.
The documentation for the polymorphic algorithms contained in this class generally includes a brief description of the implementation. Such descriptions should be regarded as implementation notes, rather than parts of the specification. Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to. (For example, the algorithm used by sort does not have to be a mergesort, but it does have to be stable.)
The "destructive" algorithms contained in this class, that is, the algorithms that modify the collection on which they operate, are specified to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. These algorithms may, but are not required to, throw this exception if an invocation would have no effect on the collection. For example, invoking the sort method on an unmodifiable list that is already sorted may or may not throw UnsupportedOperationException.
This class is a member of the Java Collections Framework.
The hedge "approximately" is used in the foregoing description because default source of randomness is only approximately an unbiased source of independently chosen bits. If it were a perfect source of randomly chosen bits, then the algorithm would choose permutations with perfect uniformity.
This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.
RandomAccess interface and is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential access" list in place.
list - the list to be shuffled.
UnsupportedOperationException - if the specified list or its list-iterator does not support the set operation.
Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
size in interface Collection<E>
index - the index of the element to be removed
UnsupportedOperationException - if the remove operation is not supported by this list
IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size())
true if this list contains no elements.
true if this list contains no elements.
isEmpty in interface Collection<E>
true if this list contains no elements
UnsupportedOperationException.
UnsupportedOperationException.
The returned list will be serializable if the specified list is serializable. Similarly, the returned list will implement RandomAccess if the specified list does.
T - the class of the objects in the list
list - the list for which an unmodifiable view is to be returned.
c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the list).
c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the list).
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The specified list must be modifiable, but need not be resizable.
List.sort(Comparator) method using the specified list and comparator.
T - the class of the objects in the list
list - the list to be sorted.
c - the comparator to determine the order of the list. A null value indicates that the elements' natural ordering should be used.
ClassCastException - if the list contains elements that are not mutually comparable using the specified comparator.
UnsupportedOperationException - if the specified list's list-iterator does not support the set operation.
IllegalArgumentException - (optional) if the comparator is found to violate the Comparator contract
Iterator takes the place of
Enumeration in the Java Collections Framework. Iterators
differ from enumerations in two ways:
Iterator takes the place of
Enumeration in the Java Collections Framework. Iterators
differ from enumerations in two ways:
This interface is a member of the Java Collections Framework.
Enumeration can be converted into an Iterator by
using the Enumeration.asIterator() method. Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.
The List interface places additional stipulations, beyond those specified in the Collection interface, on the contracts of the iterator, add, remove, equals, and hashCode methods. Declarations for other inherited methods are also included here for convenience.
The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.
The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and bidirectional access in addition to the normal operations that the Iterator interface provides. A method is provided to obtain a list iterator that starts at a specified position in the list.
The List interface provides two methods to search for a specified object. From a performance standpoint, these methods should be used with caution. In many implementations they will perform costly linear searches.
The List interface provides two methods to efficiently insert and remove multiple elements at an arbitrary point in the list.
Note: While it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a list.
Some list implementations have restrictions on the elements that they may contain. For example, some implementations prohibit null elements, and some have restrictions on the types of their elements. Attempting to add an ineligible element throws an unchecked exception, typically NullPointerException or ClassCastException. Attempting to query the presence of an ineligible element may throw an exception, or it may simply return false; some implementations will exhibit the former behavior and some will exhibit the latter. More generally, attempting an operation on an ineligible element whose completion would not result in the insertion of an ineligible element into the list may throw an exception or it may succeed, at the option of the implementation. Such exceptions are marked as "optional" in the specification for this interface.
The List.of and List.copyOf static factory methods provide a convenient way to create unmodifiable lists. The List instances created by these methods have the following characteristics:
UnsupportedOperationException to be thrown. However, if the contained elements are themselves mutable, this may cause the List's contents to appear to change. null elements. Attempts to create them with null elements result in NullPointerException. subList views implement the RandomAccess interface. This interface is a member of the Java Collections Framework.
Lists that support this operation may place limitations on what elements may be added to this list. In particular, some lists will refuse to add null elements, and others will impose restrictions on the type of elements that may be added. List classes should clearly specify in their documentation any restrictions on what elements may be added.
add in interface Collection<E>
e - element to be appended to this list
true (as specified by Collection.add(E))
UnsupportedOperationException - if the add operation is not supported by this list
ClassCastException - if the class of the specified element prevents it from being added to this list
NullPointerException - if the specified element is null and this list does not permit null elements
IllegalArgumentException - if some property of this element prevents it from being added to this list
clear in interface Collection<E>
UnsupportedOperationException - if the clear operation is not supported by this list