For the Ls class:

(i use java and EclipseIDE, thank you)

1. Write a startsWith method that returns true if the beginning of an Ls list has the same elements as a list passed as an argument, otherwise false. Note all lists startsWith and empty list.

Example:

new Ls(1,2,3,4,5).startsWith(new Ls(1,2,3)) returns true

new Ls(1,2,3,4,5).startsWith(new Ls(1,3,2)) returns false

new Ls(1,2,3).startsWith(new Ls()) returns true

2. Write an indexOf method such that the argument could be an Ls list. It should return the index where the argument is found as a sub-list. Suggest using the startsWith method. It may be helpful.

Example:

new Ls(1,2,3,4,5).indexOf(new Ls(3,4)) returns 2.

Should return -1 if the sublist cannot be found.

3. Write a concat method with returns a new list formed out of append a second Ls to the Ls list.

Example:

new Ls(1,2,3,4).concat(new Ls(5,6,7)) returns a list (1,2,3,4,5,6,7)

4. Write a sublist method with returns a sublist having the similar semantics to Javas substring method that takes argument. Have sublist throw an IndexOutOfBoundsException if the parameters are out of bounds.

Example:

new Ls(1,2,3,4).sublist(2) returns a list (3,4)

5. Write a sublist method with returns a sublist having the similar semantics to Javas substring method that takes two arguments. Have sublist throw an IndexOutOfBoundsException if the parameters are out of bounds.

Example:

new Ls(1,2,3,4).sublist(1,3) returns a list (2,3)

6. Write a flatten method with returns a flattened list out of a list that may contain other lists, as so on.

Example:

new Ls(1,2,new Ls(3,4),5,new Ls(new Ls(7))) returns a list (1,2,3,4,5,6,7)

7. Write a replace method to perform a replace all and anywhere within a hierarchical Ls list (lists within lists).

Example:

new Ls(1,2,new Ls(1,2,3), 2, 1).replaceAll(1,99) returns a list

(99,2,(99,2,3),2,99)

8. Write a compareTo method compare the list against another list. For this task, have the Ls implement Javas Comparable interface. You can assume the car implements Comparable (it is OK if the method throws ClassCastException). Make sure to handle the case where one list is simply longer than the other, but all values are the same up to the shortest length are the same.

Example:

new Ls(1,2,3,4).compareTo(new Ls(1,2,4)) returns -1

new Ls(1,2,3,4).compareTo(new Ls(1,2,3)) returns 1

Requirements:

Your solutions must use recursion.

The list must be immutable. Thus, the methods return new instances of an Ls list when needed.

Write a jUnit test program to thoroughly test each of the above methods (dont just use the examples above).

Source Codes:

Ls.java:

import java.util.NoSuchElementException;

/** * A class that has similar semantics to Scheme/Lisp lists, except it is object * oriented instead of functional. Base methods are car, cdr, and cons: * * car returns the value of the first element in the list, cdr returns the * sublist past the first element, and cons returns a new list composed of new car * inserted at the beginning of a list * * Ls lists are considered to be non-mutable. That is a given instance must not * change its contained set of elements. Any modifications, must result in * creation of new Ls lists. * * Ls lists can be instantiated yet be considered to be empty. A method isEmpty * returns true for an empty Ls list, otherwise false. * * @author */ public class Ls { private E car; private Ls cdr;

/** * Constructor to build a scheme list. * * @param car * the car of the list * @param cdr * the cdr for the list, must not be null * @throws RuntimeException * on attempt to create a Ls list with a null cdr */ private Ls(E car, Ls cdr) { this.car = car; this.cdr = cdr; }

/** * Private constructor to recursively construct a scheme list over a * variable list of parameters. * * @param i * the current position when constructing the list * @param parms * the variable list of parameters */ private Ls(int i, E... parms) { if (i < parms.length) { car = parms[i]; cdr = new Ls(i + 1, parms); } else { car = null; cdr = null; // Ls with an empty cdr is the end marker node } }

/** * Constructor to create a scheme list from its parameters. * * @param parms * the variable list of parameters */ public Ls(E... parms) { this(0, parms); }

/** * Get the car * * @return the car - the first element in the list * @throws NoSuchElementException on an empty list */ public E car() { if (cdr == null) { throw new NoSuchElementException(); } return car; }

/** * Get the cdr * * @return the cdr - Ls list past the first element * @throws NoSuchElementException on an empty list */ public Ls cdr() { if (cdr == null) { throw new NoSuchElementException(); } return cdr; }

/** * Cons a new car onto a list. * * @param car * the new car. * @return a new scheme list with the car at the front of the list */ public Ls cons(E car) { return new Ls(car, this); }

/** * Identify if a scheme list is empty * * @return true if the scheme list is empty, otherwise false. */ public boolean isEmpty() { return cdr == null; }

/** * Get the string representation of the list. The string representation is a * comma separated list of elements (as strings) enclosed in parentheses. * * @return string representation of a list. */ public String toString() { return "(" + toRemainingString(); }

/** * Private method to print the string representation of a list past the * leading square bracket. If empty, prints the closing parenthesis, * otherwise prints the car and then uses recursion to print the remaining * elements. * * @return string representation of a list past the leading parenthesis. */ private String toRemainingString() { return isEmpty() ? ")" : car.toString() + (cdr.isEmpty() ? "" : ",") + cdr.toRemainingString(); }

/** * Get the size of the list * @return number of elements in the list */ public int size() { if (isEmpty()) { return 0; } else { return 1 + cdr.size(); } }

/** * Compares the specified object with this Ls for equality. Returns * true only if the specified object is also an Ls, both * lists have the same size, and all corresponding pairs of elements in * the two lists are equal. In other words, two Ls lists are defined to be * equal if they contain the same elements in the same order. * * @param other the other object * @return true if equals, otherwise false */ public boolean equals(Object other) { if (!(other instanceof Ls)) { return false; }

Ls otherLs = (Ls) other;

if (isEmpty() && otherLs.isEmpty()) { return true; }

if (isEmpty() || otherLs.isEmpty()) { return false; }

if (car.equals(otherLs.car())) { return cdr.equals(otherLs.cdr); } else { return false; } } }

TestLs.java:

public class TestLs {

public static void main(String[] args) { Ls l = new Ls(1,3,4);

System.out.println(l); } }