Google

Jun 16, 2014

Core Java Coding Questions: Creating a custom hierarchical List in Java -- Part 5

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:

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home