import java.util.Set;
import java.util.List;
import java.util.Queue;
import java.util.Random;
import java.util.HashSet;
import java.util.TreeSet;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.Collections;
import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.LinkedHashSet;

public class TestDataStructure {

  public static <T> Collection<T> toCollection(T[] a) {
    Collection<T> c = new LinkedList<T>();
    for (T s : a) {
      c.add(s);
    }
    return c;
  }

  public static <T> void iterate1(Collection<T> c) {
    Iterator<T> i = c.iterator();
    while (i.hasNext()) {
      System.out.print(i.next() + " ");
    }
    System.out.println();
  }

  public static <T> void iterate2(Collection<T> c) {
    for (T s : c) {
      System.out.print(s + " ");
    }
    System.out.println();
  }

  public static <T> void remove(Collection<T> c, T s) {
    Iterator<T> i = c.iterator();
    while (i.hasNext()) {
      T aux = i.next();
      if (aux.equals(s)) {
        i.remove();
      }
    }
  }

  public static <T> Collection<T> removeDups(Collection<T> c) {
    Collection<T> noDups = new LinkedHashSet<T>(c);
    return noDups;
  }

  public static <T> Collection<T> findDups(Collection<T> c) {
    Set<T> elements = new HashSet<T>();
    Collection<T> dups = new LinkedList<T>();
    for (T e : c) {
      if (!elements.add(e)) {
        dups.add(e);
      }
    }
    return dups;
  }

  public static <T> Collection<T> findUnique(Collection<T> c) {
    Set<T> elements = new TreeSet<T>(c);
    Collection<T> dups = findDups(c);
    elements.removeAll(dups);
    return elements;
  }

  public static <E> void swap(List<E> a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
  }

  // public static <T> void shuffle(List<T> list) {
  public static void shuffle(List<?> list) {
    Random rnd = new Random();
    for (int i = list.size(); i > 1; i--)
      swap(list, i - 1, rnd.nextInt(i));
  }

  public static <E> void replace(List<E> list, E val, E newVal) {
    for (ListIterator<E> it = list.listIterator(); it.hasNext(); )
      if (val.equals(it.next()))
        it.set(newVal);
  }

  public static <E> void replace(List<E> list, E val,
      List<? extends E> newVals) {
    for (ListIterator<E> it = list.listIterator(); it.hasNext(); ){
      if (val.equals(it.next())) {
        it.remove();
        for (E e : newVals)
          it.add(e);
      }
    }
  }

  public static <E> List<E> dealHand(List<E> deck, int n) {
    int deckSize = deck.size();
    List<E> handView = deck.subList(deckSize - n, deckSize);
    List<E> hand = new ArrayList<E>(handView);
    handView.clear();
    return hand;
  }

  static <E> List<E> heapSort(Collection<E> c) {
    Queue<E> queue = new PriorityQueue<E>(c);
    List<E> result = new ArrayList<E>();
    while (!queue.isEmpty())
      result.add(queue.remove());
    return result;
  }

  public static void main(String args[]) {
    Collection<String> c = toCollection(args);
    iterate1(c);
    iterate2(c);
    remove(c, "a");
    iterate1(c);
    System.out.println("List of unique words:");
    iterate2(removeDups(c));
    System.out.println("List of duplicate words:");
    iterate1(findDups(c));
    System.out.println("List of unique words:");
    iterate2(findUnique(c));
    System.out.println("List of elements in Random order:");
    List<String> l1 = new LinkedList<String>(findUnique(c));
    shuffle(l1);
    iterate1(l1);
    System.out.println("Another way to print in Random order:");
    List<String> l2 = new LinkedList<String>(findUnique(c));
    Collections.shuffle(l2);
    iterate1(l2);
    // Testing the mono-replace:
    replace(l1, l1.get(0), l1.get(l1.size() - 1));
    iterate2(l1);
    // Testing the multi-replace:
    replace(l1, l1.get(0), l2);
    iterate2(l1);
    iterate2(heapSort(l1));
  }
}