mcs/tests/gen-115.cs

   1 //-- ex-gen-class-linkedlist
   2 //-- ex-anonymous-method-linkedlist
   3 //-- ex-gen-printable
   4 //-- ex-gen-interface-ilist
   5 //-- ex-gen-linkedlist-map
   6 //-- ex-gen-linkedlistenumerator
   7 //-- ex-gen-delegate-fun
   8
   9 // A generic LinkedList class
  10
  11 using System;
  12 using System.IO;                        // TextWriter
  13 using System.Collections.Generic;       // IEnumerable<T>, IEnumerator<T>
  14
  15 public delegate R Mapper<A,R>(A x);
  16
  17 public interface IMyList<T> : IEnumerable<T> {
  18   int Count { get; }                    // Number of elements
  19   T this[int i] { get; set; }           // Get or set element at index i
  20   void Add(T item);                     // Add element at end
  21   void Insert(int i, T item);           // Insert element at index i
  22   void RemoveAt(int i);                 // Remove element at index i
  23   IMyList<U> Map<U>(Mapper<T,U> f);     // Map f over all elements
  24 }
  25
  26 public class LinkedList<T> : IMyList<T> {
  27   protected int size;               // Number of elements in the list
  28   protected Node first, last;       // Invariant: first==null iff last==null
  29
  30   protected class Node {
  31     public Node prev, next;
  32     public T item;
  33
  34     public Node(T item) {
  35       this.item = item;
  36     }
  37
  38     public Node(T item, Node prev, Node next) {
  39       this.item = item; this.prev = prev; this.next = next;
  40     }
  41   }
  42
  43   public LinkedList() {
  44     first = last = null;
  45     size = 0;
  46   }
  47
  48   public LinkedList(params T[] arr) : this() {
  49     foreach (T x in arr)
  50       Add(x);
  51   }
  52
  53   public int Count {
  54     get { return size; }
  55   }
  56
  57   public T this[int i] {
  58     get { return get(i).item; }
  59     set { get(i).item = value; }
  60   }
  61
  62   private Node get(int n) {
  63     if (n < 0 || n >= size)
  64       throw new IndexOutOfRangeException();
  65     else if (n < size/2) {              // Closer to front
  66       Node node = first;
  67       for (int i=0; i<n; i++)
  68         node = node.next;
  69       return node;
  70     } else {                            // Closer to end
  71       Node node = last;
  72       for (int i=size-1; i>n; i--)
  73         node = node.prev;
  74       return node;
  75     }
  76   }
  77
  78   public void Add(T item) {
  79     Insert(size, item);
  80   }
  81
  82   public void Insert(int i, T item) {
  83     if (i == 0) {
  84       if (first == null) // and thus last == null
  85         first = last = new Node(item);
  86       else {
  87         Node tmp = new Node(item, null, first);
  88         first.prev = tmp;
  89         first = tmp;
  90       }
  91       size++;
  92     } else if (i == size) {
  93       if (last == null) // and thus first = null
  94         first = last = new Node(item);
  95       else {
  96         Node tmp = new Node(item, last, null);
  97         last.next = tmp;
  98         last = tmp;
  99       }
 100       size++;
 101     } else {
 102       Node node = get(i);
 103       // assert node.prev != null;
 104       Node newnode = new Node(item, node.prev, node);
 105       node.prev.next = newnode;
 106       node.prev = newnode;
 107       size++;
 108     }
 109   }
 110
 111   public void RemoveAt(int i) {
 112     Node node = get(i);
 113     if (node.prev == null)
 114       first = node.next;
 115     else
 116       node.prev.next = node.next;
 117     if (node.next == null)
 118       last = node.prev;
 119     else
 120       node.next.prev = node.prev;
 121     size--;
 122   }
 123
 124   public override bool Equals(Object that) {
 125     if (that != null && GetType() == that.GetType()
 126         && this.size == ((IMyList<T>)that).Count) {
 127       Node thisnode = this.first;
 128       IEnumerator<T> thatenm = ((IMyList<T>)that).GetEnumerator();
 129       while (thisnode != null) {
 130         if (!thatenm.MoveNext())
 131           throw new ApplicationException("Impossible: LinkedList<T>.Equals");
 132         // assert MoveNext() was true (because of the above size test)
 133         if (!thisnode.item.Equals(thatenm.Current))
 134           return false;
 135         thisnode = thisnode.next;
 136       }
 137       // assert !MoveNext(); // because of the size test
 138       return true;
 139     } else
 140       return false;
 141   }
 142
 143   public override int GetHashCode() {
 144     int hash = 0;
 145     foreach (T x in this)
 146       hash ^= x.GetHashCode();
 147     return hash;
 148   }
 149
 150   public static explicit operator LinkedList<T>(T[] arr) {
 151     return new LinkedList<T>(arr);
 152   }
 153
 154   public static LinkedList<T> operator +(LinkedList<T> xs1, LinkedList<T> xs2) {
 155     LinkedList<T> res = new LinkedList<T>();
 156     foreach (T x in xs1)
 157       res.Add(x);
 158     foreach (T x in xs2)
 159       res.Add(x);
 160     return res;
 161   }
 162
 163   public IMyList<U> Map<U>(Mapper<T,U> f) {
 164     LinkedList<U> res = new LinkedList<U>();
 165     foreach (T x in this)
 166       res.Add(f(x));
 167     return res;
 168   }
 169
 170   public IEnumerator<T> GetEnumerator() {
 171     return new LinkedListEnumerator(this);
 172   }
 173
 174   private class LinkedListEnumerator : IEnumerator<T> {
 175     T curr;                     // The enumerator's current element
 176     bool valid;                 // Is the current element valid?
 177     Node next;                  // Node holding the next element, or null
 178
 179     public LinkedListEnumerator(LinkedList<T> lst) {
 180       next = lst.first; valid = false;
 181     }
 182
 183     public T Current {
 184       get {
 185         if (valid)
 186           return curr;
 187         else
 188           throw new InvalidOperationException();
 189       }
 190     }
 191
 192     public bool MoveNext() {
 193       if (next != null)  {
 194         curr = next.item; next = next.next; valid = true;
 195       } else
 196         valid = false;
 197       return valid;
 198     }
 199
 200     public void Dispose() {
 201       curr = default(T); next = null; valid = false;
 202     }
 203   }
 204 }
 205
 206 class SortedList<T> : LinkedList<T> where T : IComparable<T> {
 207   // Sorted insertion
 208   public void Insert(T x) {
 209     Node node = first;
 210     while (node != null && x.CompareTo(node.item) > 0)
 211       node = node.next;
 212     if (node == null)           // x > all elements; insert at end
 213       Add(x);
 214     else {                      // x <= node.item; insert before node
 215       Node newnode = new Node(x);
 216       if (node.prev == null)    // insert as first element
 217         first = newnode;
 218       else
 219         node.prev.next = newnode;
 220       newnode.next = node;
 221       newnode.prev = node.prev;
 222       node.prev = newnode;
 223     }
 224   }
 225 }
 226
 227 interface IPrintable {
 228   void Print(TextWriter fs);
 229 }
 230 class PrintableLinkedList<T> : LinkedList<T>, IPrintable where T : IPrintable {
 231   public void Print(TextWriter fs) {
 232     bool firstElement = true;
 233     foreach (T x in this) {
 234       x.Print(fs);
 235       if (firstElement)
 236         firstElement = false;
 237       else
 238         fs.Write(", ");
 239     }
 240   }
 241 }
 242
 243 class MyString : IComparable<MyString> {
 244   private readonly String s;
 245   public MyString(String s) {
 246     this.s = s;
 247   }
 248   public int CompareTo(MyString that) {
 249     return String.Compare(that.Value, s);       // Reverse ordering
 250   }
 251   public bool Equals(MyString that) {
 252     return that.Value == s;
 253   }
 254   public String Value {
 255     get { return s; }
 256   }
 257 }
 258
 259 class MyTest {
 260   public static void Main(String[] args) {
 261     LinkedList<double> dLst = new LinkedList<double>(7.0, 9.0, 13.0, 0.0);
 262     foreach (double d in dLst)
 263       Console.Write("{0} ", d);
 264     Console.WriteLine();
 265     IMyList<int> iLst =
 266       dLst.Map<int>(new Mapper<double, int>(Math.Sign));
 267     foreach (int i in iLst)
 268       Console.Write("{0} ", i);
 269     Console.WriteLine();
 270     IMyList<String> sLst =
 271       dLst.Map<String>(delegate(double d) { return "s" + d; });
 272     foreach (String s in sLst)
 273       Console.Write("{0} ", s);
 274     Console.WriteLine();
 275     // Testing SortedList<MyString>
 276     SortedList<MyString> sortedLst = new SortedList<MyString>();
 277     sortedLst.Insert(new MyString("New York"));
 278     sortedLst.Insert(new MyString("Rome"));
 279     sortedLst.Insert(new MyString("Dublin"));
 280     sortedLst.Insert(new MyString("Riyadh"));
 281     sortedLst.Insert(new MyString("Tokyo"));
 282     foreach (MyString s in sortedLst)
 283       Console.Write("{0}   ", s.Value);
 284     Console.WriteLine();
 285   }
 286 }