// Simple LinkedList class illustrating properties, indexers, foreach,
// user-defined operators, and delegates in C#
// sestoft@dina.kvl.dk * 2002-04-23

using System;
using System.Collections;

public class TestLinkedList {
  static void Main(string[] args) {
    LinkedList xs = new LinkedList();
    for (int i=0; i<10; i++)
      xs.Add(i);                                    // Implicit boxing of int
    Console.WriteLine(xs.Count + " " + xs[2]);      // Property and indexer
    xs[2] = 102;                                    // Indexer's set-accessor
    int sum = 0;
    foreach (int k in xs)                           // Using an enumerator
      sum += k;
    Console.WriteLine(sum);
    LinkedList twice = xs + xs;                     // Using operator (+)
    twice.apply(new Fun(print));                    // Create delegate
  }

  static void print(object x) { Console.Write(x + " "); }
}

public delegate void Fun(object x);

public class LinkedList : IEnumerable {
  private int size;             // Number of elements in the list
  private Node first, last;     // Invariant: first==null iff last==null

  private class Node {
    public Node prev, next;
    public object item;

    public Node(object item) {
      this.item = item; 
    }

    public Node(object item, Node prev, Node next) {
      this.item = item; this.prev = prev; this.next = next; 
    }
  }

  public LinkedList() {
    first = last = null;
    size = 0;
  }

  public int Count {
    get { return size; }
  }

  public object this[int index] {
    get { return get(index).item; }
    set { get(index).item = value; }
  }      

  private Node get(int n) {
    if (n <0 || n >= size)
      throw new IndexOutOfRangeException();
    else if (n < size/2) {              // Closer to front
      Node node = first;
      for (int i=0; i<n; i++)
        node = node.next;
      return node;
    } else {                            // Closer to end
      Node node = last;
      for (int i=size; i>n; i++)
        node = node.prev;
      return node;
    }
  }

  public bool Add(object item) { 
    if (last == null) // and thus first = null
      first = last = new Node(item);
    else {
      Node tmp = new Node(item, last, null);
      last.next = tmp;
      last = tmp;
    }
    size++; 
    return true;
  }

  public IEnumerator GetEnumerator() {
    return new LinkedListEnumerator(this);
  }

  class LinkedListEnumerator : IEnumerator {    // Iterator in Java
    LinkedList lst;
    Node curr;
    bool valid;
    object item;

    public LinkedListEnumerator(LinkedList lst) {
      this.lst = lst; Reset();
    }
    
    public object Current {
      get { 
        if (valid) 
          return item; 
        else
          throw new InvalidOperationException();
      }
    }
    
    public bool MoveNext() {
      if (curr != null)  {
        item = curr.item;
        curr = curr.next;
        return valid = true;
      } else 
        return valid = false; 
    }

    public void Reset() {
      curr = lst.first; 
      valid = false;
    }
  }

  public static LinkedList operator +(LinkedList xs1, LinkedList xs2) {
    LinkedList res = new LinkedList();
    foreach (object x in xs1)
      res.Add(x);
    foreach (object x in xs2)
      res.Add(x);
    return res;
  }

  public void apply(Fun f) {
    foreach (object x in this) 
      f(x);
  }
}