import java.util.*;
/* Question 1a. Write the entire RandomStringChooser class.
*
* Possible answers include a RandomStringChooser class that:
* has an unshuffled array.
* has an unshuffled constant array.
* has an efficient unshuffled constant array.
* has an unshuffled list of type ArrayList.
* has an unshuffled list of type LinkedList.
* has a shuffled array.
* extends a RandomItemChooser<String> class that has a shuffled stack.
* extends a RandomItemChooser<String> class that uses ArrayOfItems.
* has a RandomItemChooser<String> object that uses ArrayOfItems.
*/
/** A RandomStringChooser object is constructed from an array of non-null String values.
* When the object is first constructed, all of the strings are considered available.
* The RandomStringChooser class has a getNext method, which has the following behavior.
* A call to getNext returns a randomly chosen string from the available strings in the
* object. Once a particular string has been returned from a call to getNext, it is no
* longer available to be returned from subsequent calls to getNext. If no strings are
* available to be returned, getNext returns "NONE".
*/
class RandomStringChooser
{
/** Refers to an unshuffled array of String values. When a string becomes
* unavailable, it is removed from the array. All strings in the array
* referred to by unshuffledStrings are available for selection.
*/
private String[] unshuffledStrings;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
final int n = strings.length;
unshuffledStrings = new String[n];
for (int i = 0; i < n; i++) {
unshuffledStrings[i] = strings[i];
}
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
final int n = unshuffledStrings.length;
return (n == 0) ? "NONE" : remove((int)(Math.random() * n));
}
/** Removes the string at position i in unshuffledStrings by setting
* unshuffledStrings equal to a new array that is one less in size
* than the previously referenced array and copying all of the other
* strings to the new array while maintaining the original order of
* the strings. Returns a reference to the string that was removed.
*/
private String remove(int i) {
final int n = unshuffledStrings.length;
final String[] previouslyAvailable = unshuffledStrings;
unshuffledStrings = new String[n - 1];
for (int j=0, k=0; j < n; j++) {
if (i != j) {
unshuffledStrings[k++] = previouslyAvailable[j];
}
}
return previouslyAvailable[i];
}
}
class RandomStringChooser
{
/** Refers to an unshuffled array of String values where none, some,
* or all of the strings might actually be available for selection
* depending on the value of the private variable named count.
*/
private final String[] unshuffledStrings;
/** A count of the number of strings in unshuffledStrings that are
* available for selection. Strings with indices greater than or
* equal to the value of count are not available.
*/
private int count;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
count = strings.length;
unshuffledStrings = new String[count];
for (int i = 0; i < count; i++) {
unshuffledStrings[i] = strings[i];
}
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
return (count == 0) ? "NONE" : remove((int)(Math.random() * count));
}
/** Effectively removes the string at position i in unshuffledStrings
* by shifting any available strings that are to the right of the string
* being removed to the left one position and decreasing count by one.
* Returns a reference to the string that was removed.
*/
private String remove(int i) {
String removedString = unshuffledStrings[i];
count = count - 1;
while (i < count) {
unshuffledStrings[i] = unshuffledStrings[i + 1];
i = i + 1;
}
return removedString;
}
}
class RandomStringChooser
{
/** Refers to an unshuffled array of String values where none, some,
* or all of the strings might actually be available for selection
* depending on the value of the private variable named count.
*/
private final String[] unshuffledStrings;
/** A count of the number of strings in unshuffledStrings that are
* available for selection. Strings with indices greater than or
* equal to the value of count are not available.
*/
private int count;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
count = strings.length;
unshuffledStrings = new String[count];
for (int i = 0; i < count; i++) {
unshuffledStrings[i] = strings[i];
}
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
return (count == 0) ? "NONE" : remove((int)(Math.random() * count));
}
/** Effectively removes the string at position i in unshuffledStrings
* by decreasing count by one and then replacing the value of
* unshuffledStrings[i] with the value of unshuffledStrings[count].
* Returns a reference to the string that was removed.
*/
private String remove(int i) {
String removedString = unshuffledStrings[i];
count = count - 1;
unshuffledStrings[i] = unshuffledStrings[count];
return removedString;
}
}
class RandomStringChooser
{
/** Refers to an unshuffled list of String values. When a string becomes
* unavailable, it is removed from the list. All strings in the list
* referred to by unshuffledStrings are available for selection.
*/
private final List<String> unshuffledStrings;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
final int initialCapacity = strings.length;
unshuffledStrings = new ArrayList<String>(initialCapacity);
for (String str : strings) {
unshuffledStrings.add(str);
}
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
final int n = unshuffledStrings.size();
return (n == 0) ? "NONE" : unshuffledStrings.remove((int)(Math.random() * n));
}
}
class RandomStringChooser
{
/** Refers to an unshuffled list of String values. When a string becomes
* unavailable, it is removed from the list. All strings in the list
* referred to by unshuffledStrings are available for selection.
*/
private final List<String> unshuffledStrings;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
unshuffledStrings = new LinkedList<String>();
for (String str : strings) {
unshuffledStrings.add(str);
}
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
final int n = unshuffledStrings.size();
return (n == 0) ? "NONE" : unshuffledStrings.remove((int)(Math.random() * n));
}
}
class RandomStringChooser
{
/** Refers to an shuffled array of String values where none, some,
* or all of the strings might actually be available for selection
* depending on the value of the private variable named count.
*/
private final String[] shuffledStrings;
/** A count of the number of strings in shuffledStrings that are
* available for selection. Strings with indices greater than or
* equal to the value of count are not available.
*/
private int count;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
shuffledStrings = getShuffledArray(strings);
count = shuffledStrings.length;
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
return (count > 0) ? shuffledStrings[--count] : "NONE";
}
/* PRIVATE METHODS */
private static String[] getShuffledArray(String[] strings) {
return shuffle(getCopy(strings));
}
private static String[] getCopy(String[] strings) {
final int n = strings.length;
final String[] copy = new String[n];
for (int i = 0; i < n; i++) {
copy[i] = strings[i];
}
return copy;
}
private static String[] shuffle(String[] strings) {
for (int n = strings.length; n > 1; n--) {
swap(strings, n - 1, (int)(Math.random() * n));
}
return strings;
}
private static void swap(String[] strings, int i, int j) {
String tmp = strings[i];
strings[i] = strings[j];
strings[j] = tmp;
}
}
class RandomStringChooser extends RandomItemChooser<String>
{
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
super(strings);
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
@Override
public final String getNext() {
final String next = super.getNext();
return next == null ? "NONE" : next;
}
}
class RandomItemChooser<T>
{
/** A shuffled stack of items. */
private final Stack<T> shuffledItems;
/** Constructs a random item chooser using the given array of items.
* Precondition: items is an array of non-null items.
*/
public RandomItemChooser(T[] items) {
shuffledItems = getShuffledStack(items);
}
/** Returns the next random item from the set of available items
* maintained by the RandomItemChooser object and makes the item
* returned unavailable. Returns null if no items are available.
*/
public T getNext() {
return shuffledItems.isEmpty() ? null : shuffledItems.pop();
}
/* PRIVATE METHODS */
private static <T> Stack<T> getShuffledStack(T[] items) {
return shuffle(getCopy(items));
}
private static <T> List<T> getCopy(T[] items) {
final int n = items.length;
final List<T> copy = new LinkedList<T>();
for (T item : items) {
copy.add(item);
}
return copy;
}
private static <T> Stack<T> shuffle(List<T> items) {
Stack<T> stack = new Stack<T>();
for (int n = items.size(); n > 0; n = items.size()) {
int i = (int)(Math.random() * n);
stack.push(items.remove(i));
}
return stack;
}
}
class RandomStringChooser extends RandomItemChooser<String>
{
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
super(strings);
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
@Override
public final String getNext() {
final String next = super.getNext();
return next == null ? "NONE" : next;
}
}
class RandomItemChooser<T>
{
/** A shuffled stack of items. */
private final Stack<T> shuffledItems;
/** Constructs a random item chooser using the given array of items.
* Precondition: items is an array of non-null items.
*/
public RandomItemChooser(T[] items) {
shuffledItems = ArrayOfItems.getShuffledStack(items);
}
/** Returns the next random item from the set of available items
* maintained by the RandomItemChooser object and makes the item
* returned unavailable. Returns null if no items are available.
*/
public T getNext() {
return shuffledItems.isEmpty() ? null : shuffledItems.pop();
}
}
/** A collection of utilities related to a generic array of items. */
final class ArrayOfItems
{
/** Returns a Stack object consisting of the items provided as
* as the input to the method arranged in a random order.
* Precondition: items refers to a non-null array of objects.
*/
public static <T> Stack<T> getShuffledStack(T[] items) {
Stack<T> stack = new Stack<T>();
for (int i : getRandomOrder(items.length)) {
stack.push(items[i]);
}
return stack;
}
/** Returns an array containing the values between zero (inclusive)
* and n (exclusive) arranged in random order.
* Precondition: the value of n is a non-negative integer.
*/
public static Integer[] getRandomOrder(int n) {
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
order[i] = i;
}
return shuffle(order);
}
/** Rearranges the values of items in a random order and returns
* a reference to the array.
* Precondition: items refers to a non-null array of objects.
*/
public static <T> T[] shuffle(T[] items) {
for (int n = items.length; n > 1; n--) {
swap(items, n - 1, (int)(Math.random() * n));
}
return items;
}
/** Exchanges the values at positions i and j in items.
* Precondition: itmes refers to a non-null array of objects, and
* the values of i and j are valid indices, i.e. they are integers
* between zero (inclusive) and the number of items in the array
* provided as input to the method (exclusive).
*/
public static <T> void swap(T[] items, int i, int j) {
T item_i = items[i];
items[i] = items[j];
items[j] = item_i;
}
}
class RandomStringChooser
{
private final RandomItemChooser<String> chooser;
/** Constructs a random string chooser using the given array of strings.
* Precondition: strings is an array of non-null String values.
*/
public RandomStringChooser(String[] strings) {
chooser = new RandomItemChooser<String>(strings);
}
/** Returns the next random string from the set of available strings
* maintained by the RandomStringChooser object and makes the string
* returned unavailable. Returns "NONE" if no strings are available.
*/
public final String getNext() {
final String next = chooser.getNext();
return next == null ? "NONE" : next;
}
}
class RandomItemChooser<T>
{
/** A shuffled stack of items. */
private final Stack<T> shuffledItems;
/** Constructs a random item chooser using the given array of items.
* Precondition: items is an array of non-null items.
*/
public RandomItemChooser(T[] items) {
shuffledItems = ArrayOfItems.getShuffledStack(items);
}
/** Returns the next random item from the set of available items
* maintained by the RandomItemChooser object and makes the item
* returned unavailable. Returns null if no items are available.
*/
public T getNext() {
return shuffledItems.isEmpty() ? null : shuffledItems.pop();
}
}
/** A collection of utilities related to a generic array of items. */
final class ArrayOfItems
{
/** Returns a Stack object consisting of the items provided as
* as the input to the method arranged in a random order.
* Precondition: items refers to a non-null array of objects.
*/
public static <T> Stack<T> getShuffledStack(T[] items) {
Stack<T> stack = new Stack<T>();
for (int i : getRandomOrder(items.length)) {
stack.push(items[i]);
}
return stack;
}
/** Returns an array containing the values between zero (inclusive)
* and n (exclusive) arranged in random order.
* Precondition: the value of n is a non-negative integer.
*/
public static Integer[] getRandomOrder(int n) {
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) {
order[i] = i;
}
return shuffle(order);
}
/** Rearranges the values of items in a random order and returns
* a reference to the array.
* Precondition: items refers to a non-null array of objects.
*/
public static <T> T[] shuffle(T[] items) {
for (int n = items.length; n > 1; n--) {
swap(items, n - 1, (int)(Math.random() * n));
}
return items;
}
/** Exchanges the values at positions i and j in items.
* Precondition: itmes refers to a non-null array of objects, and
* the values of i and j are valid indices, i.e. they are integers
* between zero (inclusive) and the number of items in the array
* provided as input to the method (exclusive).
*/
public static <T> void swap(T[] items, int i, int j) {
T item_i = items[i];
items[i] = items[j];
items[j] = item_i;
}
}
/** RandomLetterChooser Class */
class RandomLetterChooser extends RandomStringChooser
{
/** An answer to question 1b.
* Constructs a random letter chooser using the giving string str.
* Precondition: str contains only letters.
*/
public RandomLetterChooser(String str) {
super(getSingleLetters(str));
}
/** Returns an array of single-letter strings.
* Each of these strings consists of a single letter from str. Element k
* of the returned array contains the single letter at position k of str.
* For example, getSingleLetters("cat") returns the
* array { "c", "a", "t" }.
*/
public static final String[] getSingleLetters(String str) {
final int n = str.length();
String[] singleLetters = new String[n];
for (int i = 0; i < n; i++) {
Character ch = str.charAt(i);
singleLetters[i] = ch.toString();
}
return singleLetters;
}
}
public class Question1
{
private static final String theWord = "cat";
private static final String[] theLettersArray = {"c", "a", "t"};
private static final String[] theWordsArray = {"wheels", "on", "the", "bus"};
public final static String[] test1a() {
final int n = 6;
String[] randomWords = new String[n];
RandomStringChooser strChooser = new RandomStringChooser(theWordsArray);
for (int i = 0; i < n; i++) {
randomWords[i] = strChooser.getNext();
}
return randomWords;
}
public final static String[] test1b() {
final int n = 4;
String[] randomLetters = new String[n];
RandomLetterChooser letterChooser = new RandomLetterChooser(theWord);
for (int i = 0; i < n; i++) {
randomLetters[i] = letterChooser.getNext();
}
return randomLetters;
}
public static void main(String[] args) {
final int n = 100000;
String[][] randomWordsArrays = new String[n][];
String[][] randomLettersArrays = new String[n][];
final long startTime = System.currentTimeMillis();
for (int i = 0; i < n; i++) {
randomWordsArrays[i] = test1a();
randomLettersArrays[i] = test1b();
}
System.out.println("time: " + (System.currentTimeMillis() - startTime));
System.out.println();
analyze(randomWordsArrays, theWordsArray);
analyze(randomLettersArrays, theLettersArray);
}
private static void analyze(String[][] wordArrays, String[] strings) {
final int n = strings.length;
final int[][] counts = new int[n][n];
final int m = wordArrays.length;
for (int i = 0; i < n; i++) {
String word = strings[i];
for (int j = 0; j < m; j++) {
for (int k = 0; k < n; k++) {
if (wordArrays[j][k].equals(word)) {
counts[i][k]++;
}
}
}
for (int p = 0; p < n; p++) {
System.out.println(word + " at position " + p + ": " + counts[i][p]);
}
System.out.println();
}
}
}
Additional Exercises — Question 1a
Analyze the answers provided for question 1, part a.
Analyze the answers in terms of both their time and space efficiency.
Discuss the cost of constructing an object vs. the cost of using the method getNext to return a random string.
Where applicable, discuss the consequences of using an object of type ArrayList<String> vs. an object of type LinkedList<String> as the value of a variable declared to be of type List<String>.
Compare the strengths and weaknesses of different answers under the following conditions.
You know that a single RandomStringChooser object will be initialized with an array of a small number of short strings.
You know that a single RandomStringChooser object will be initialized with an array of a large number of short strings.
You know that a single RandomStringChooser object will initialized with an array of a small number of long strings.
You know that a large number of RandomStringChooser objects will exist simultaneously and their respective getNext methods will be called frequently and at random.
Nothing is known about the potential number of RandomStringChooser objects, how they will be initialized, or how they will be used.
Are the space and/or time performance differences between any of the answers provided significant enough to justify using one solution instead of another under any circumstances?
If so, explain the circumstances. Support your answer with data.
When would it make sense to go to the trouble of using generic classes, as some of the answers provided do?
Which answers are easiest for you to read and understand? Why?
Additional Exercises — Question 1b
Use the method substring instead of charAt to implement getSingleLetters.
Source Code — Question 2
import java.util.*;
/** Log messages have the format machineId:description, where machineId identifies
* the computer and description describes the event being logged. Exactly one
* colon (":") appears in a log message. There are no blanks either immediately
* before or immediately after the colon.
*/
class LogMessage
{
private String machineId;
private String description;
/** Mr. Spurgeon's answer to question 2a.
* Precondition: message is a valid log message.
*/
public LogMessage(String message)
{
final int i = message.indexOf(":");
machineId = message.substring(0, i);
description = message.substring(i + 1, message.length());
}
/** Various answers to question 2b:
* Mr. Spurgeon's answer.
* The answer from the Scoring Guidelines document.
* A clever Aha! answer.
* Returns true if the description in this log message properly contains keyword;
* false otherwise.
*
* A description properly contains a keyword if all three of the following
* conditions are true.
*
* a) the keyword is a substring of the description;
* b) the keyword is either at the beginning of the description or is immediately
* preceded by a space;
* c) the keyword is either at the end of the description or it is immediately
* followed by a space.
*/
public boolean containsWord(String keyword)
{
// Relative to description, keyword must be either:
// i) a substring preceded AND followed by a space;
if (description.indexOf(' ' + keyword + ' ') >= 0)
return true;
// ii) or, a substring at the beginning AND at the end (i.e. equal to);
if (description.equals(keyword))
return true;
// iii) or, a substring at the beginning AND followed by a space;
if (description.indexOf(keyword + ' ') == 0)
return true;
// iv) or, a substring at the end AND preceded by a space.
// Be careful: "DISK" does NOT properly contain "disk"!
final int i = description.indexOf(' ' + keyword);
if (i >= 0 && i + 1 == description.length() - keyword.length())
return true;
// Otherwise, description does NOT properly contain keyword.
return false;
}
{
/* Credit: The College Board */
if (description.equals(keyword))
{ return true; }
if (description.indexOf(keyword + " ") == 0)
{ return true; }
if (description.indexOf(" " + keyword + " ") != -1)
{ return true; }
if (description.length() > keyword.length())
{
if ((description.substring(description.length() -
keyword.length() - 1).equals(
" " + keyword)))
{
return true;
}
}
return false;
}
public String getMachineId() {
return machineId;
}
public String getDescription() {
return description;
}
public String toString() {
return machineId + ":" + description;
}
public static void main(String[] args) {
String text;
LogMessage message;
// Question 2a.
text = "DeepThought:The answer is 42.";
message = new LogMessage(text);
System.out.println(message.getMachineId());
System.out.println(message.getDescription());
// Question 2b.
final String mid = "foobar"; // machine id
final String keyword = "disk";
final String[] descriptions = {
"disk",
"error on disk",
"error on /dev/disk disk",
"error on disk DSK1",
"DISK",
"error on disk3",
"error on /dev/disk",
"diskette",
"diskerror on some disk", // Be careful!
"diskerror on /dev/disk" // Strings that make you go hmmmm...
};
System.out.println();
for (String dsc : descriptions) {
text = mid + ":" + dsc;
message = new LogMessage(text);
System.out.print('"' + dsc + "\" properly contains \"" + keyword + "\": ");
System.out.println(message.containsWord(keyword));
}
}
}
/** An object representing a mutable list of LogMessage objects. */
public class SystemLog
{
/** Contains all the entries in this system log.
* Guaranteed not to be null and to contain only non-null entries.
*/
private List<LogMessage> messageList;
/** Constructs a SystemLog object containing the LogMessage objects in messages.
* Precondition: messages is not null and consists of zero or more non-null
* LogMessage objects.
*/
public SystemLog(LogMessage[] messages) {
messageList = new ArrayList<LogMessage>(messages.length);
for (LogMessage message : messages) {
messageList.add(message);
}
}
/** Returns a String composed of a series of substrings: each substring is the
* String representation of one of the LogMessage objects of this SystemLog
* object followed by a newline character.
*/
public String toString() {
StringBuilder sb = new StringBuilder();
for (LogMessage message : messageList) {
sb.append(message.toString());
sb.append("\n");
}
return sb.toString();
}
/** Mr. Spurgeon's answer to question 2c.
* Removes from the system log all entries whose descriptions properly contain keyword,
* and returns a list (possibly empty) containing the removed entries.
* Postcondition:
* - Entries in the returned list properly contain keyword and
* are in the order in which they appeared in the system log.
* - The remaining entries in the system log do not properly contain keyword and
* are in their original order.
* - The returned list is empty if no messages properly contain keyword.
*/
public List<LogMessage> removeMessages(String keyword)
{
List<LogMessage> removedMessages = new LinkedList<LogMessage>();
int i = 0;
while (i < messageList.size()) {
final LogMessage message = messageList.get(i);
if (message.containsWord(keyword)) {
messageList.remove(i);
removedMessages.add(message);
}
else {
i++;
}
}
return removedMessages;
}
public static void main(String[] args) {
// Questions 2a and 2b.
LogMessage.main(args);
// Question 2c.
final LogMessage[] theMessages = {
new LogMessage("CLIENT3:Security alert - repeated login failures"),
new LogMessage("Webserver:disk offline"),
new LogMessage("SERVER1:file not found"),
new LogMessage("SERVER2:read error on disk DSK1"),
new LogMessage("SERVER1:write error on disk DSK2"),
new LogMessage("Webserver:error on /dev/disk")
};
final SystemLog theLog = new SystemLog(theMessages);
List<LogMessage> removedMessages = theLog.removeMessages("disk");
System.out.println();
System.out.println("REMOVED:");
for (LogMessage message : removedMessages) {
System.out.println(message);
}
System.out.println("\nNOT REMOVED:");
System.out.println(theLog);
}
}
Additional Exercises — Question 2b
Design a programming problem that involves removing some, but not all, items from a list and adding the removed items to another list while maintaining the original order of the items in both lists. Write a program that solves the problem.
Traverse a list forwards (beginning with the item at position/index zero) and remove as you go.
Traverse a list backwards (ended with the item at position/index zero) and remove as you go.