Q. Can you write a custom list class that supports following features?
1. Allows you to maintain a parent/child hierarchy of sub lists.
2. Allows you to create
sublists from a given list and a predicate (i.e a condition)
3. If you add an item or element to a list, the addition must be propagated to its parent and child lists.
4. If you remove an element from a list, the removal must be propagated to its parent and child lists.
In the previous parts
In this part, you will see the complete code with an iterator implementation added as a subclass. The iterator method uses the
iterator design pattern.
package test;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
public class CustomList<E> implements List<E> {
private CustomList<E> parent = null; // parent
protected List<E> list = null; // initial list
private List<CustomList<E>> sublists = new ArrayList<CustomList<E>>(); // children
private Predicate<E> predicate; // used to create sublists based on the
// predicate
/**
* DEFINE THE CONSTRUCTORS
*/
public CustomList(List<E> sourceList) {
this.list = sourceList;
}
// default constructor with an empty list
public CustomList() {
this(new ArrayList<E>()); // invokes the above constructor by supplying
// an empty list
}
/**
* access modifier is protected to only invoke from within the package and
* subclasses from the other packages. This protected constructor creates
* sub lists from the source or parent lists based on the supplied predicate
*
* @param sourceList
* @param predicate
*/
protected CustomList(List<E> sourceList, Predicate<E> predicate) {
if (predicate == null) {
throw new IllegalArgumentException("Expected to receive a non-null predicate on which to base the sublist!");
}
this.predicate = predicate;
// Each CustomList decorates a concrete List...
this.list = new ArrayList<E>(sourceList.size());
// Evaluate each item in the source to create the sublist
// not using for each loop as we have not defined the iterator method
// currently iterator() is throwing UnSupportedOperationException
//you can change to for each once the iterator is defined.
for (int i = 0; i < sourceList.size(); i++) {
E item = sourceList.get(i);
if (predicate.evaluate(item)) {
this.list.add(item);
}
}
}
/**
* access modifier is protected to only invoke from within the package and
* subclasses from the other packages
*
* @param sourceList
* @param predicate
*/
protected CustomList(CustomList<E> parent, Predicate<E> predicate) {
this((List<E>) parent, predicate); // creates the sublist
this.parent = parent;
// Add ourselves (i.e. the new sublist created by this predicate)
// to the parent subList
parent.sublists.add(this);
}
/**
* CREATING SUB LISTS
*/
public CustomList<E> subList(Predicate<E> subListPredicate) {
return new CustomList<E>(this, subListPredicate);
}
/**
* Methods that need to be implemented for the List<E> interface to satisfy
* the List interface contract
*/
@Override
public int size() {
return this.list.size();
}
@Override
public boolean isEmpty() {
return this.list.isEmpty();
}
@Override
public boolean contains(Object o) {
return this.list.contains(o);
}
@Override
public Iterator<E> iterator() {
return new CustomListIterator(this.list.iterator());
}
@Override
public Object[] toArray() {
return this.list.toArray();
}
@Override
public <T> T[] toArray(T[] a) {
return this.list.toArray(a);
}
@Override
public boolean add(E e) {
return add(e, null);
}
@SuppressWarnings("unchecked")
@Override
public boolean remove(Object o) {
return remove((E)o, null);
}
@Override
public boolean containsAll(Collection<?> c) {
return this.list.containsAll(c);
}
@Override
public boolean addAll(Collection<? extends E> c) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
throw new UnsupportedOperationException();
}
@Override
public boolean removeAll(Collection<?> c) {
throw new UnsupportedOperationException();
}
@Override
public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException();
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public E get(int index) {
return this.list.get(index);
}
@Override
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
@Override
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
@Override
public E remove(int index) {
E item = this.list.get(index);
return (item != null && remove(item)) ? item : null;
}
@Override
public int indexOf(Object o) {
return this.list.indexOf(o);
}
@Override
public int lastIndexOf(Object o) {
return this.list.lastIndexOf(o);
}
@Override
public ListIterator<E> listIterator() {
throw new UnsupportedOperationException();
}
@Override
public ListIterator<E> listIterator(int index) {
throw new UnsupportedOperationException();
}
@Override
public List<E> subList(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
}
/**
* add to the parent and children if the predicate is satisfied Recursion is
* used to add if the condition (i.e. predicate) is met
*/
protected boolean add(E e, CustomList<E> givenList) {
// check if the predicate (i.e. condition is met)
if (!evaluate(e)) {
return false;
}
boolean hasAdded = true;
// if parent exists, add to the parent
if (parent != null && parent != givenList) {
// Recursive method call. The parent takes care of siblings...
hasAdded = parent.add(e, this);
}
// if addition fails, return false
if (!hasAdded) {
return false;
}
hasAdded = this.list.add(e);
if (!hasAdded) {
if (parent != null) {
throw new IllegalStateException("Failed to add !!");
} else {
return false;
}
}
// Add to the sublists
for (CustomList<E> sublist : sublists) {
if (sublist != givenList) {
// recursive method call
sublist.add(e, this);
}
}
return true;
}
/**
* remove from the parent and children if the predicate is satisfied
*/
protected boolean remove(E e, CustomList<E> givenList) {
// First evaluate whether or not the item is likely to be in this
// list...
if (!evaluate(e)) {
return false;
}
boolean hasRemoved = true;
// if parent exists, remove from the parent
if (parent != null && parent != givenList) {
// Recursive method call. The parent takes care of siblings...
hasRemoved = parent.remove(e, this);
}
// if removal fails, return false
if (!hasRemoved) {
return false;
}
// Remove from this
if (givenList != this) {
hasRemoved = this.list.remove(e);
}
if (!hasRemoved) {
if (parent != null) {
throw new IllegalStateException("Failed to remove !!");
} else {
return false;
}
}
// Remove from the sublists
for (CustomList<E> sublist : sublists) {
if (sublist != givenList) {
sublist.remove(e, this);
}
}
return true;
}
private boolean evaluate(E e) {
return (this.predicate != null) ? this.predicate.evaluate(e) : true;
}
/**
* advanced toString() method
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Deque<CustomList<Integer>> allParents = getAllParents();
while (!allParents.isEmpty()) {
CustomList<Integer> parent = allParents.pop();
sb.append("parent: " + parent.list.toString() + "\n");
}
sb.append("list: " + list.toString() + "\n");
Deque<CustomList<Integer>> allChildren = getAllChildren();
while (!allChildren.isEmpty()) {
CustomList<Integer> child = allChildren.remove();
sb.append("child: " + child.list.toString() + "\n");
}
return sb.toString();
}
@SuppressWarnings("unchecked")
private Deque<CustomList<Integer>> getAllParents() {
Deque<CustomList<Integer>> queue = new ArrayDeque<CustomList<Integer>>();
CustomList<Integer> currentCs = (CustomList<Integer>) this;
// push each parent to the stack
while (currentCs != null && currentCs.parent != null) {
queue.push(currentCs.parent);
currentCs = currentCs.parent;
}
return queue;
}
@SuppressWarnings("unchecked")
private Deque<CustomList<Integer>> getAllChildren() {
Deque<CustomList<Integer>> queue = new ArrayDeque<CustomList<Integer>>(); // for
// processing
// iteratively
Deque<CustomList<Integer>> queueResult = new ArrayDeque<CustomList<Integer>>(); // for
// holding
// the
// results
if (this != null) {
queue.push((CustomList<Integer>) this);
}
while (!queue.isEmpty()) {
CustomList<Integer> cl = queue.pop();
if (cl.sublists != null) {
for (CustomList<Integer> child : cl.sublists) {
queue.push(child);
queueResult.add(child);
}
}
}
return queueResult;
}
protected class CustomListIterator implements Iterator<E> {
private Iterator<E> delegate;
private E current;
public CustomListIterator(Iterator<E> delegate) {
this.delegate = delegate;
}
@Override
public boolean hasNext() {
return this.delegate.hasNext();
}
@Override
public E next() {
this.current = this.delegate.next();
return current;
}
@Override
public void remove() {
this.delegate.remove();
//propagate the removal to parent and children
CustomList.this.remove(current, CustomList.this);
}
}
}
The class with the main method to run.
package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CustomListTest {
public static void main(String[] args) {
/**
* Arrays.asList returns a List wrapper around an array. This wrapper
* has a fixed size and is directly backed by the array, and as such
* calls to set will modify the array, and any other method that
* modifies the list will throw an UnsupportedOperationException.
* hence creating a new ArrayList(...) instance
*/
List<Integer> initialList = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
CustomList<Integer> customList = new CustomList<Integer>(initialList);
System.out.println("customList: " + customList);
Predicate<Integer> oddNumberPredicate = new OddNumberPredicate<Integer>();
CustomList<Integer> oddNumbersSubList = customList.subList(oddNumberPredicate);
System.out.println("oddNumbersSubList: " + oddNumbersSubList);
Predicate<Integer> factorOf5Predicate = new FactorOf5Predicate<Integer>();
CustomList<Integer> factorOf5SubList = customList.subList(factorOf5Predicate);
System.out.println("factorOf5SubList: " + factorOf5SubList);
Predicate<Integer> factorOf3Predicate = new FactorOf3Predicate<Integer>();
CustomList<Integer> factorOf3SubList = oddNumbersSubList.subList(factorOf3Predicate);
System.out.println("factorOf3SubList : " + factorOf3SubList);
System.out.println("Demonstrate printing customList again");
System.out.println("customList : " + customList);
// add an item or element
customList.add(11); // this should be added to customList and
// oddNumbersSubList
customList.add(15); // this should be added to all four lists.
System.out.println("After adding 11 & 15: ");
System.out.println("customList : " + customList);
customList.remove(new Integer(15));
System.out.println("After removing 15: ");
System.out.println("customList : " + customList);
}
}
The
output is:
customList: list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
oddNumbersSubList: parent: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list: [1, 3, 5, 7, 9]
factorOf5SubList: parent: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
list: [5, 10]
factorOf3SubList : parent: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
parent: [1, 3, 5, 7, 9]
list: [3, 9]
Demonstrate printing customList again
customList : list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
child: [1, 3, 5, 7, 9]
child: [5, 10]
child: [3, 9]
After adding 11 & 15:
customList : list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15]
child: [1, 3, 5, 7, 9, 11, 15]
child: [5, 10, 15]
child: [3, 9, 15]
After removing 15:
customList : list: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
child: [1, 3, 5, 7, 9, 11]
child: [5, 10]
child: [3, 9]
Labels: Coding
