// Example 125 from page 95

//

import java.io.*;

import java.util.*;

/*

This generic interface represents a function from A to R; in C# one

would use a generic delegate instead.

In MyLinkedList method equals(Object), the cast to MyList<T> is

unchecked and may fail at runtime.

*/

interface Mapper<A,R> {

R call(A x);

}

// A generic linked-list class with elements of type T

interface MyList<T> extends Iterable<T> {

int getCount(); // Number of elements

T get(int i); // Get element at index i

void set(int i, T item); // Set element at index i

void add(T item); // Add element at end

void insert(int i, T item); // Insert element at index i

void removeAt(int i); // Remove element at index i

<U> MyList<U> map(Mapper<T,U> f); // Map f over all elements

}

class MyLinkedList<T> implements MyList<T> {

protected int size; // Number of elements in the list

protected Node<T> first, last; // Invariant: first==null iff last==null

protected static class Node<U> {

public Node<U> prev, next;

public U item;

public Node(U item) {

this.item = item;

}

public Node(U item, Node<U> prev, Node<U> next) {

this.item = item; this.prev = prev; this.next = next;

}

}

public MyLinkedList() {

first = last = null;

size = 0;

}

@SafeVarargs

public MyLinkedList(T... arr) {

this();

for (T x : arr)

add(x);

}

@Override

public int getCount() {

return size;

}

@Override

public T get(int i) {

return getNode(i).item;

}

@Override

public void set(int i, T item) {

getNode(i).item = item;

}

private Node<T> getNode(int n) {

if (n < 0 || n >= size)

throw new IndexOutOfBoundsException();

else if (n < size/2) { // Closer to front

Node<T> node = first;

for (int i=0; i<n; i++)

node = node.next;

return node;

} else { // Closer to end

Node<T> node = last;

for (int i=size-1; i>n; i--)

node = node.prev;

return node;

}

}

@Override

public void add(T item) {

insert(size, item);

}

@Override

public void insert(int i, T item) {

if (i == 0) {

if (first == null) // and thus last == null

first = last = new Node<T>(item);

else {

Node<T> tmp = new Node<T>(item, null, first);

first.prev = tmp;

first = tmp;

}

size++;

} else if (i == size) {

if (last == null) // and thus first = null

first = last = new Node<T>(item);

else {

Node<T> tmp = new Node<T>(item, last, null);

last.next = tmp;

last = tmp;

}

size++;

} else {

Node<T> node = getNode(i);

// assert node.prev != null;

Node<T> newnode = new Node<T>(item, node.prev, node);

node.prev.next = newnode;

node.prev = newnode;

size++;

}

}

@Override

public void removeAt(int i) {

Node<T> node = getNode(i);

if (node.prev == null)

first = node.next;

else

node.prev.next = node.next;

if (node.next == null)

last = node.prev;

else

node.next.prev = node.prev;

size--;

}

@Override

@SuppressWarnings("unchecked")

public boolean equals(Object that) {

return equals((MyList<T>)that); // Unchecked cast

}

public boolean equals(MyList<T> that) {

if (that != null && this.size == that.getCount()) {

Node<T> thisnode = this.first;

Iterator<T> thatiter = that.iterator();

while (thisnode != null) {

if (!thatiter.hasNext())

throw new RuntimeException("Impossible: MyLinkedList<T>.equals");

// assert next() will succeed (because of the above size test)

if (!thisnode.item.equals(thatiter.next()))

return false;

thisnode = thisnode.next;

}

// assert !hasNext(); // because of the size test

return true;

} else

return false;

}

public <U> MyList<U> map(Mapper<T,U> f) {

MyLinkedList<U> res = new MyLinkedList<U>();

for (T x : this)

res.add(f.call(x));

return res;

}

public Iterator<T> iterator() {

return new MyLinkedListIterator();

}

private class MyLinkedListIterator implements Iterator<T> {

Node<T> next; // Node holding current element, or null

public MyLinkedListIterator() {

next = first;

}

public T next() {

if (next != null) {

T res = next.item;

next = next.next;

return res;

} else

throw new NoSuchElementException();

}

public boolean hasNext() {

return next != null;

}

public void remove() {

throw new UnsupportedOperationException();

}

}

}

class SortedList<T extends Comparable<T>> extends MyLinkedList<T> {

// Sorted insertion (not an @Override)

public void insert(T x) {

Node<T> node = first;

while (node != null && x.compareTo(node.item) > 0)

node = node.next;

if (node == null) // x > all elements; insert at end

add(x);

else { // x <= node.item; insert before node

Node<T> newnode = new Node<T>(x);

if (node.prev == null) // insert as first element

first = newnode;

else

node.prev.next = newnode;

newnode.next = node;

newnode.prev = node.prev;

node.prev = newnode;

}

}

}

interface Printable {

void print(PrintWriter fs);

}

class PrintableMyLinkedList<T extends Printable>

extends MyLinkedList<T> implements Printable

{

@Override

public void print(PrintWriter fs) {

boolean firstElement = true;

for (T x : this) {

x.print(fs);

if (firstElement)

firstElement = false;

else

fs.print(", ");

}

}

}

class MyString implements Comparable<MyString> {

public final String s;

public MyString(String s) {

if (s == null)

throw new RuntimeException("null string");

else

this.s = s;

}

public int compareTo(MyString that) {

return s.compareTo(that.s);

}

}

class Example125 {

public static void main(String[] args) {

MyLinkedList<Double> dLst

= new MyLinkedList<Double>(7.0, 9.0, 13.0, 0.0);

for (double d : dLst)

System.out.print(d + " ");

System.out.println();

MyList<Integer> iLst =

dLst.map(new Mapper<Double, Integer>() {

public Integer call(Double d) {

return d < 0 ? -1 : d > 0 ? +1 : 0;

}

});

for (int i : iLst)

System.out.print(i + " ");

System.out.println();

MyList<String> sLst =

dLst.map(new Mapper<Double, String>() {

public String call(Double d) {

return "s" + d;

}

});

for (String s : sLst)

System.out.print(s + " ");

System.out.println();

// Testing SortedList<MyString>

SortedList<MyString> sortedLst = new SortedList<MyString>();

sortedLst.insert(new MyString("New York"));

sortedLst.insert(new MyString("Rome"));

sortedLst.insert(new MyString("Dublin"));

sortedLst.insert(new MyString("Riyadh"));

sortedLst.insert(new MyString("Tokyo"));

for (MyString s : sortedLst)

System.out.print(s.s + " ");

System.out.println();

}

}