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