import java.util.*;
/**************/
/* Interfaces */
/**************/
interface GerminalList<T>
{
T getSentinel();
boolean isEmpty();
int size();
String toString(final String delimiter);
String toString(final String delimiter, final String begin, final String end);
}
interface DecomposableList<T> extends GerminalList<T>
{
int indexOf(final T item);
boolean contains(final T item);
T get(int index);
T getFirst();
T getLast();
}
interface RightAppendableList<T> extends GerminalList<T>
{
RightAppendableList<T> add(final T item);
RightAppendableList<T> addMultiple(final T[] items);
RightAppendableList<T> addMultiple(final List<T> items);
}
interface LeftAppendableList<T> extends GerminalList<T>
{
LeftAppendableList<T> insert(final T item);
LeftAppendableList<T> insertMultiple(final T[] items);
LeftAppendableList<T> insertMultiple(final List<T> items);
}
interface RightTruncatableList<T> extends GerminalList<T>
{
T removeLast();
}
interface LeftTruncatableList<T> extends GerminalList<T>
{
T removeFirst();
}
interface ShortenableList<T> extends RightTruncatableList<T>, LeftTruncatableList<T>
{
T remove(final int index);
}
interface LengthenableList<T> extends RightAppendableList<T>, LeftAppendableList<T>
{
LengthenableList<T> insert(int index, final T item);
}
interface RandomizibleList<T> extends GerminalList<T>
{
int getRandomIndex();
RandomizibleList<T> insertRandom(T item);
T getRandom();
T removeRandom();
RandomizibleList<T> shuffle();
}
interface SortableList<T> extends GerminalList<T>
{
SortableList<T> sort(final Comparator<T> comparator);
}
interface LIFOStack<T>
extends RightAppendableList<T>, RightTruncatableList<T>
{
T getLast();
}
interface FIFOQueue<T>
extends LeftAppendableList<T>, LeftTruncatableList<T>
{
T getFirst();
}
interface DEQueue<T> extends LIFOStack<T>, FIFOQueue<T>
{
DEQueue<T> insert(final T item);
}
/********************/
/* Abstract Classes */
/********************/
abstract class VersatileList<T> implements
GerminalList<T>,
ShortenableList<T>,
LengthenableList<T>,
DecomposableList<T>,
SortableList<T>,
RandomizibleList<T>,
LIFOStack<T>,
FIFOQueue<T>,
DEQueue<T>
{
private final T sentinel;
private final List<T> elements;
protected VersatileList(final List<T> list, final T sentinel) {
elements = list;
this.sentinel = sentinel;
}
public VersatileList<T> add(final T item) {
elements.add(item);
return this;
}
public VersatileList<T> insertRandom(final T item) {
elements.add(getRandomIndex(), item);
return this;
}
public final VersatileList<T> addMultiple(final T[] items) {
if (items != null) for (T item : items) add(item);
return this;
}
public final VersatileList<T> addMultiple(final List<T> items) {
if (items != null) for (T item : items) add(item);
return this;
}
public boolean contains(final T item) {
return elements.indexOf(item) >= 0;
}
public T get(final int index) {
return (index >= 0 && index < elements.size()) ? elements.get(index) : sentinel;
}
public final int getRandomIndex() {
return elements.size() > 0 ? (int)(Math.random() * elements.size()) : -1;
}
public final T getFirst() {
return get(0);
}
public final T getLast() {
return get(elements.size() - 1);
}
public final T getRandom() {
return get(getRandomIndex());
}
public final T getSentinel() {
return sentinel;
}
public final int indexOf(final T item) {
return elements.indexOf(item);
}
public VersatileList<T> insert(final T item) {
elements.add(0, item);
return this;
}
public VersatileList<T> insert(int index, final T item) {
elements.add(index, item);
return this;
}
public final VersatileList<T> insertMultiple(final T[] items) {
if (items != null) for (T item : items) insert(item);
return this;
}
public final VersatileList<T> insertMultiple(final List<T> items) {
if (items != null) for (T item : items) insert(item);
return this;
}
public boolean isEmpty() {
return elements.size() == 0;
}
public final T remove(final int index) {
return (index >= 0 && index < elements.size()) ? remove(index) : sentinel;
}
public final T removeFirst() {
return remove(0);
}
public final T removeLast() {
return remove(elements.size() - 1);
}
public final T removeRandom() {
return remove(getRandomIndex());
}
public final int size() {
return elements.size();
}
public final VersatileList<T> shuffle() {
for (int n = size(); n > 1; n = n - 1)
swap(n-1, (int)(Math.random() * n));
return this;
}
public final VersatileList<T> sort(final Comparator<T> comparator) {
Collections.sort(elements, comparator);
return this;
}
protected final VersatileList<T> swap(final int i, final int j) {
// Precondition: Values of i and j must be valid indices of elements.
T item = elements.get(i);
elements.set(i, elements.get(j));
elements.set(j, item);
return this;
}
public String toString() {
return toString(", ");
}
public String toString(final String delimiter) {
return toString(delimiter, "{", "}");
}
public String toString(final String delimiter, final String begin, final String end) {
final int n = elements.size();
StringBuilder sb = new StringBuilder(begin);
if (n > 0) {
sb.append(elements.get(0).toString());
}
for (int i = 1; i < n; i = i + 1) {
sb.append(delimiter + elements.get(i).toString());
}
sb.append(end);
return sb.toString();
}
}
abstract class VersatileListSet<T> extends VersatileList<T> {
protected VersatileListSet(final List<T> list, final T sentinel) {
super(list, sentinel);
}
public final VersatileListSet<T> add(final T item) {
if (!contains(item)) super.add(item);
return this;
}
public final VersatileListSet<T> insert(final int index, final T item) {
if (!contains(item)) insert(index, item);
return this;
}
}
abstract class VersatileListMultiset<T> extends VersatileList<T> {
protected VersatileListMultiset(final List<T> list, final T sentinel) {
super(list, sentinel);
}
}
/********************/
/* Concrete Classes */
/********************/
class ArrayListSet<T> extends VersatileListSet<T>
{
public ArrayListSet(final T sentinel) {
super(new ArrayList<T>(), sentinel);
}
public ArrayListSet() {
this(null);
}
}
class LinkedListSet<T> extends VersatileListSet<T>
{
public LinkedListSet(final T sentinel) {
super(new LinkedList<T>(), sentinel);
}
public LinkedListSet() {
this(null);
}
}
class ArrayListMultiset<T> extends VersatileListMultiset<T>
{
public ArrayListMultiset(final T sentinel) {
super(new ArrayList<T>(), sentinel);
}
public ArrayListMultiset() {
this(null);
}
}
class LinkedListMultiset<T> extends VersatileListMultiset<T>
{
public LinkedListMultiset(final T sentinel) {
super(new LinkedList<T>(), sentinel);
}
public LinkedListMultiset() {
this(null);
}
}
/***********/
/* Program */
/***********/
public class LinearLists {
public static void main(String args[]) {
final VersatileList<String> list = new ArrayListMultiset<String>().addMultiple(args).shuffle();
final LIFOStack<String> stack = list;
final FIFOQueue<String> queue = list;
System.out.println(list);
System.out.println(stack.toString(", ", "LIFO Stack: {", "} < in-out >"));
System.out.println(queue.toString(", ", "FIFO Queue: < out {", "} < in"));
}
}