1 //-- ex-gen-class-linkedlist
2 //-- ex-anonymous-method-linkedlist
4 //-- ex-gen-interface-ilist
5 //-- ex-gen-linkedlist-map
6 //-- ex-gen-linkedlistenumerator
7 //-- ex-gen-delegate-fun
9 // A generic LinkedList class
12 using System.IO; // TextWriter
13 using System.Collections;
14 using System.Collections.Generic; // IEnumerable<T>, IEnumerator<T>
16 public delegate R Mapper<A,R>(A x);
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
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
31 protected class Node {
32 public Node prev, next;
39 public Node(T item, Node prev, Node next) {
40 this.item = item; this.prev = prev; this.next = next;
49 public LinkedList(params T[] arr) : this() {
58 public T this[int i] {
59 get { return get(i).item; }
60 set { get(i).item = value; }
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
68 for (int i=0; i<n; i++)
71 } else { // Closer to end
73 for (int i=size-1; i>n; i--)
79 public void Add(T item) {
83 public void Insert(int i, T item) {
85 if (first == null) // and thus last == null
86 first = last = new Node(item);
88 Node tmp = new Node(item, null, first);
93 } else if (i == size) {
94 if (last == null) // and thus first = null
95 first = last = new Node(item);
97 Node tmp = new Node(item, last, null);
104 // assert node.prev != null;
105 Node newnode = new Node(item, node.prev, node);
106 node.prev.next = newnode;
112 public void RemoveAt(int i) {
114 if (node.prev == null)
117 node.prev.next = node.next;
118 if (node.next == null)
121 node.next.prev = node.prev;
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))
136 thisnode = thisnode.next;
138 // assert !MoveNext(); // because of the size test
144 public override int GetHashCode() {
146 foreach (T x in this)
147 hash ^= x.GetHashCode();
151 public static explicit operator LinkedList<T>(T[] arr) {
152 return new LinkedList<T>(arr);
155 public static LinkedList<T> operator +(LinkedList<T> xs1, LinkedList<T> xs2) {
156 LinkedList<T> res = new LinkedList<T>();
164 public IMyList<U> Map<U>(Mapper<T,U> f) {
165 LinkedList<U> res = new LinkedList<U>();
166 foreach (T x in this)
171 public IEnumerator<T> GetEnumerator() {
172 return new LinkedListEnumerator(this);
175 IEnumerator IEnumerable.GetEnumerator() {
176 return new LinkedListEnumerator(this);
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
184 public LinkedListEnumerator(LinkedList<T> lst) {
185 next = lst.first; valid = false;
193 throw new InvalidOperationException();
197 object IEnumerator.Current {
198 get { return Current; }
201 public bool MoveNext() {
203 curr = next.item; next = next.next; valid = true;
209 public void Reset() {
210 throw new NotImplementedException ();
213 public void Dispose() {
214 curr = default(T); next = null; valid = false;
219 class SortedList<T> : LinkedList<T> where T : IComparable<T> {
221 public void Insert(T x) {
223 while (node != null && x.CompareTo(node.item) > 0)
225 if (node == null) // x > all elements; insert at end
227 else { // x <= node.item; insert before node
228 Node newnode = new Node(x);
229 if (node.prev == null) // insert as first element
232 node.prev.next = newnode;
234 newnode.prev = node.prev;
240 interface IPrintable {
241 void Print(TextWriter fs);
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) {
249 firstElement = false;
256 class MyString : IComparable<MyString> {
257 private readonly String s;
258 public MyString(String s) {
261 public int CompareTo(MyString that) {
262 return String.Compare(that.Value, s); // Reverse ordering
264 public bool Equals(MyString that) {
265 return that.Value == s;
267 public String Value {
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);
279 dLst.Map<int>(new Mapper<double, int>(Math.Sign));
280 foreach (int i in iLst)
281 Console.Write("{0} ", i);
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);
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);