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
- Core Java Coding Questions: Creating a custom hierarchical List in Java -- Part 1: subList with a predicate functionality.
- Core Java Coding Questions: Creating a custom hierarchical List in Java -- Part 2: toString( ) method to print the hierachy.
- Core Java Coding Questions: Creating a custom hierarchical List in Java -- Part 3: add(...) method to add new items and propagate that to parent and children.
- Core Java Coding Questions: Creating a custom hierarchical List in Java -- Part 4: remove(...) method to remove items and propagate that to parent and children.
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
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home