Package cs1302.adt

Interface StringList

All Known Implementing Classes:

OracleStringList

public interface StringList

StringList is an abstract data type (ADT) that defines operations for a sequence of references to non-empty String objects. Any object that implements this interface is a string list object , and each String reference in the sequence it represents is an item.

UML Diagram for StringList

Programmers that use a string list have precise control over the items in the sequence it represents. They may place or access an item using an index value (i.e., a nonnegative integer that denotes a position). If they exist, the index values for the first and last items are always 0 and size() - 1, respectively, and a string list that has no items is empty.

Remember, the items of a string list are references to non-empty String objects. In Java, a reference is either null or refers to some object. This implies that an item cannot be null. If you inspect the documentation for any method that inserts an item into a string list, you will find that a NullPointerException and IllegalArgumentException are expected to be thrown whenever there is an attempt to insert null or an empty string, respectively. A string is considered empty in Java if, and only if, its length is 0. A blank string may be inserted into a string list so long as that blank string is not empty.

Required Constructors

All classes that implement StringList are required to have the public constructors described below, where ClassName refers to name of the implementing class (i.e., replace ClassName as needed).

Default Constructor

public ClassName()

Constructs an empty string list.

Storage and Internal Data Structures

Since StringList is an ADT, any class that implements this interface is theoretically free to store its items using any kind of data structure that the author wants so long as objects of the class all behave like string lists as documented in the methods of this interface. For example, the class for one implementaton might use a linked list of nodes to store its items, while another implementation might use an array. The OracleStringList class is example of an implementation; it is provided to illustrate how to use and test string list objects later in this ADT documentation.

Assumptions

Since many implementations of the interface may exist, this ADT documentation makes no assumptions about any internal data structures that might by used by a particular implementation; it merely communicates how all implementations are expected to behave from an external perspective.

String List Size vs. Data Structure Size

Unless explicitly stated otherwise, any mention of size found in this documentation specifically refers to the size of a string list object and not the size of its underlying data structure. Please keep this in mind, for example, when observing the conditions for the IndexOutOfBoundsException in the documentation for various methods.

The idea that the size of the underlying data structure may be different than the size of the string list may seem foreign to some, but understanding the difference is critical for certain implementations. For example, in a string list that uses an array to store its items, the array might have more elements than the number of items currently in the string list (i.e., the array's size might be bigger than the string list's size); this is usually done to minimize the number of times the the string list's array is resized. In Java, an array object cannot actually be resized, so the verb resize is usually taken to mean the creation of a new, usually larger, array object and the loop(s) needed to copy over the elements from the original array object to the new one.

Examples and Unit Tests

While all of the examples in this section are written using OracleStringList, you should be able to replace "new OracleStringList()" with a default constructor call for any implementation of the StringList interface, including the concrete ones that you write for your project. The examples provided here are not exhaustive; you are expected to come up with your own examples and test them.

Example: New, Empty String List

A new string list is size 0 and therefore empty. An example of how to test this is provided in the project description. We also provide some sample code below:

 // setup
 StringList list = new OracleStringList();

 // test by printing
 System.out.println(list.size());    // 0
 System.out.println(list.isEmpty()); // true

 // test by asserting (requires -ea option when running java)
 assert list.size() == 0 : "size() is not 0!";
 assert list.isEmpty() : "isEmpty() is false!";
 

Example: Non-Empty String List

After adding three items to a new string list, it is size() 3 and therefore not empty:

 // setup
 StringList list = new OracleStringList();
 list.add(0, "a");
 list.add(1, "b");
 list.add(2, "c");

 // test by printing
 System.out.println(list.size());    // 3
 System.out.println(list.isEmpty()); // false
 System.out.println(list.get(0));    // a
 System.out.println(list.get(1));    // b
 System.out.println(list.get(2));    // c

 // test by asserting (requires -ea option when running java)
 assert list.size() == 3 : "size() is not 3!";
 assert !list.isEmpty() : "isEmpty() is true!";
 assert list.get(0).equals("a") : "get(0) is not \"a\"!";
 assert list.get(1).equals("b") : "get(1) is not \"b\"!";
 assert list.get(2).equals("c") : "get(2) is not \"c\"!";
 

Example: No Empty Items in a String List

It is not possible to add an empty string; the documentation for add(int, String) says that it should throw an exception if such an attempt is made:

 // setup
 StringList list = new OracleStringList();

 // test by calling
 list.add(0, ""); // Exception java.lang.IllegalArgumentException

 // test by asserting (requires -ea option when running java)
 try {
     list.add(0, "");
     assert false : "add(0, \"\") did not throw an IllegalArgumentException";
 } catch(IllegalArgumentException iae) {
     assert true;
 } // try
 

Example: No Gaps in a String List

The out of bounds criteria that is documented in the @throws description for the add(int, String) method makes it impossible to introduce "gaps" into a properly implemented string list object:

 // setup
 StringList list = new OracleStringList();
 list.add(0, "a");
 list.add(1, "b");

 // test by printing
 list.add(3, "c"); // Exception java.lang.IndexOutOfBoundsException

 // test by asserting (requires -ea option when running java)
 try {
     list.add(3, "c");
     assert false : "add(3, \"c\") did not throw an IndexOutOfBoundsException";
 } catch(IndexOutOfBoundsException ioobe) {
     assert true;
 } // try
 

Very Important Note

You do not need to write the .java file for this interface (nor should you)!

A compiled version of this StringList interface is made available to you in a JAR file that is distributed alongside the project description. Simply follow the instructions in that document to get and use the JAR file.

Author:

Michael E. Cotterell

Method Summary

Modifier and Type	Method	Description
boolean	add(int index, StringList itemList)	Inserts multiple items into this string list at the specified index position.
boolean	add(int index, String item)	Inserts an item into this string list at the specified index position.
void	clear()	Removes all of the items from this string list.
boolean	contains(int start, String target)	Returns true if start >= 0 and there exists an item at or after the start index that equals the target string.
String	get(int index)	Returns the item at the specified index position in this string list.
boolean	isEmpty()	Returns true if this string list has no items.
String	makeString(String start, String sep, String end)	Returns a string representation of this string list that begins with start and ends with end, with every string in the string list separated by sep.
String	remove(int index)	Removes the item at the specified index position in this string list.
StringList	reverse()	Returns a new string list that contains the items from this string list in reverse order.
int	size()	Returns the number of items in this string list.
StringList	slice(int start, int stop)	Returns a new string list that contains the items from this list between the specified start index (inclusive) and stop index (exclusive).
String	toString()	Returns makeString("[", ", ", "]").

Method Details

size

int size()

Returns the number of items in this string list.

Returns:

the number of items in this string list

isEmpty

boolean isEmpty()

Returns true if this string list has no items. More formally, a string list is empty if, and only if, its size is zero.

Returns:

true if this string list is empty; false otherwise

add

boolean add(int index,
 String item)

Inserts an item into this string list at the specified index position. If an item was already at that position, then that item and subsequent items are shifted to the right (i.e., one is added to their indices).

This method either returns true or throws one of its documented exceptions, but never both.

Parameters:

index - index at which the specified string is to be inserted

item - item to be inserted

Returns:

true if this list changed as a result of the call

Throws:

NullPointerException - if item is null

IllegalArgumentException - if item is empty

IndexOutOfBoundsException - if index is out of range (index < 0 || index > size())

add

boolean add(int index,
 StringList itemList)

Inserts multiple items into this string list at the specified index position. The relative order of inserted items is preserved. If items were already at that or subsequent positions, then those items are shifted to the right (i.e., itemList.size() is added to their indices).

Instead of inserting items into a string list one at a time, this method enables users to insert multiple items into a string list all at once. Here are some examples:

 // first list
 StringList list1 = new OracleStringList();
 list1.add(0, "a");
 list1.add(1, "b");

 // second list
 StringList list2 = new OracleStringList();
 list2.add(0, "0");
 list2.add(1, "1");

 // insert second list into first list
 list1.add(1, list2);
 System.out.println(list1); // [a, 0, 1, b]

 // insert modified first list into itself
 list1.add(1, list1);
 System.out.println(list1); // [a, a, 0, 1, b, 0, 1, b]
 

The last code snippet shown above is an example of self-reference; that is, it is a scenario where the source and destination objects are the very same object. This is allowed! Implementers should take special care to avoid accidental infinite loops in situations involving self reference since the size of the source string list may change as items are inserted into the destination string list.

This method should return !itemList.isEmpty() or throw one of its documented exceptions, but never both. It should also support self-reference as described above; that is, a call to this method should still work when itemList refers to the calling string list object itself.

Parameters:

index - index at which the specified items are to be inserted

itemList - string list of items to be inserted

Returns:

true if this list changed as a result of the call

Throws:

NullPointerException - if itemList is null

IndexOutOfBoundsException - if index is out of range (index < 0 || index > size())

get

String get(int index)

Returns the item at the specified index position in this string list.

Parameters:

index - index of the item to return

Returns:

the item at the specified position in this string list

Throws:

IndexOutOfBoundsException - if index is out of range (index < 0 || index >= size())

contains

boolean contains(int start,
 String target)

Returns true if start >= 0 and there exists an item at or after the start index that equals the target string. If no such item exists, then false is returned. Unlike the add methods that throws exceptions when called with bad arguments, this contains method simply returns false instead.

Parameters:

start - the index from which to start the search

target - the item to search for

Returns:

true if there exists an item at or after start such that item.equals(target), or false if there is no such occurrence

remove

String remove(int index)

Removes the item at the specified index position in this string list. Any items in the string list that were after the removed string are shifted to the left (i.e., one is subtracted from their indices).

Parameters:

index - index of the item to remove

Returns:

the string that was removed

Throws:

IndexOutOfBoundsException - if index is out of range (index < 0 || index >= size())

reverse

StringList reverse()

Returns a new string list that contains the items from this string list in reverse order. The returned string list must be an object of the same class as the calling object.

Returns:

a new string list with items from this list in reverse order

makeString

String makeString(String start,
 String sep,
 String end)

Returns a string representation of this string list that begins with start and ends with end, with every string in the string list separated by sep. Here is an example, assuming list refers to an empty StringList:

 String result1 = list.makeString("~", "!", "#");
 String result2 = list.makeString(null, null, null);
 list.add(0, "a");
 list.add(1, "b");
 list.add(2, "c");
 String result3 = list.makeString("~", "!", "#");
 String result4 = list.makeString(null, null, null);

 System.out.println(result1);
 System.out.println(result2);
 System.out.println(result3);
 System.out.println(result4);
 

The output would be:

 ~#
 nullnull
 ~a!b!c#
 nullanullbnullcnull
 

Each argument to this method may be null. If null is used for an argument, then "null" should be used. This is consistent with the regular rules for string concatenation and does not usually require any extra code to handle (i.e., you don't usually need an extra case to handle this).

Parameters:

start - specified starting string

sep - the specified separator string

end - the specified ending string

Returns:

a string representation of this string list that begins with start and ends with end, with every string in the string list separated by sep

toString

String toString()

Returns makeString("[", ", ", "]").

Overrides:

toString in class Object

Returns:

makeString("[", ", ", "]")

clear

void clear()

Removes all of the items from this string list. The string list will be empty after this method returns.

slice

StringList slice(int start,
 int stop)

Returns a new string list that contains the items from this list between the specified start index (inclusive) and stop index (exclusive). This method does not modify the calling object. If start and stop are in bounds and equal, then the returned string list is empty. The returned string list must be an object of the same class as the calling object. Here is an example, assuming list refers to a non-empty string list with items referring to "a", "b", "c", and "d":

 System.out.println(list);    // [a, b, c, d]

 StringList slice0 = list.slice(0, 4);
 System.out.println(slice0);  // [a, b, c, d]
 System.out.println(list);    // [a, b, c, d]

 StringList slice1 = list.slice(1, 3);
 System.out.println(slice1);  // [b, c]
 System.out.println(list);    // [a, b, c, d]

 StringList slice2 = list.slice(2, 4);
 System.out.println(slice2);  // [c, d]
 System.out.println(list);    // [a, b, c, d]

 StringList slice3 = list.slice(1, 1);
 System.out.println(slice3);  // []
 System.out.println(list);    // [a, b, c, d]

The "calling object" in the method description refers to the object that you call slice on. For example, if you call list.slice(0, 1) and list refers to an ArrayStringList object, then list.slice(0, 1) should return a reference to a new ArrayStringList object containing the desired items. Since ArrayStringList is compatible with StringList, the object's reference can be returned without casting and without modifying the method's return type.

Parameters:

start - left endpoint (inclusive) of the slice

stop - right endpoint (exclusive) of the slice

Returns:

a new string list with the items from this list from start (inclusive) to stop (exclusive)

Throws:

IndexOutOfBoundsException - for an illegal endpoint index value (start < 0 || stop > size() || start > stop)