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.Generic; // IEnumerable<T>, IEnumerator<T>
15 public delegate R Mapper<A,R>(A x);
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
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
30 protected class Node {
31 public Node prev, next;
38 public Node(T item, Node prev, Node next) {
39 this.item = item; this.prev = prev; this.next = next;
48 public LinkedList(params T[] arr) : this() {
57 public T this[int i] {
58 get { return get(i).item; }
59 set { get(i).item = value; }
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
67 for (int i=0; i<n; i++)
70 } else { // Closer to end
72 for (int i=size-1; i>n; i--)
78 public void Add(T item) {
82 public void Insert(int i, T item) {
84 if (first == null) // and thus last == null
85 first = last = new Node(item);
87 Node tmp = new Node(item, null, first);
92 } else if (i == size) {
93 if (last == null) // and thus first = null
94 first = last = new Node(item);
96 Node tmp = new Node(item, last, null);
103 // assert node.prev != null;
104 Node newnode = new Node(item, node.prev, node);
105 node.prev.next = newnode;
111 public void RemoveAt(int i) {
113 if (node.prev == null)
116 node.prev.next = node.next;
117 if (node.next == null)
120 node.next.prev = node.prev;
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))
135 thisnode = thisnode.next;
137 // assert !MoveNext(); // because of the size test
143 public override int GetHashCode() {
145 foreach (T x in this)
146 hash ^= x.GetHashCode();
150 public static explicit operator LinkedList<T>(T[] arr) {
151 return new LinkedList<T>(arr);
154 public static LinkedList<T> operator +(LinkedList<T> xs1, LinkedList<T> xs2) {
155 LinkedList<T> res = new LinkedList<T>();
163 public IMyList<U> Map<U>(Mapper<T,U> f) {
164 LinkedList<U> res = new LinkedList<U>();
165 foreach (T x in this)
170 public IEnumerator<T> GetEnumerator() {
171 return new LinkedListEnumerator(this);
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
179 public LinkedListEnumerator(LinkedList<T> lst) {
180 next = lst.first; valid = false;
188 throw new InvalidOperationException();
192 public bool MoveNext() {
194 curr = next.item; next = next.next; valid = true;
200 public void Dispose() {
201 curr = default(T); next = null; valid = false;
206 class SortedList<T> : LinkedList<T> where T : IComparable<T> {
208 public void Insert(T x) {
210 while (node != null && x.CompareTo(node.item) > 0)
212 if (node == null) // x > all elements; insert at end
214 else { // x <= node.item; insert before node
215 Node newnode = new Node(x);
216 if (node.prev == null) // insert as first element
219 node.prev.next = newnode;
221 newnode.prev = node.prev;
227 interface IPrintable {
228 void Print(TextWriter fs);
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) {
236 firstElement = false;
243 class MyString : IComparable<MyString> {
244 private readonly String s;
245 public MyString(String s) {
248 public int CompareTo(MyString that) {
249 return String.Compare(that.Value, s); // Reverse ordering
251 public bool Equals(MyString that) {
252 return that.Value == s;
254 public String Value {
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);
266 dLst.Map<int>(new Mapper<double, int>(Math.Sign));
267 foreach (int i in iLst)
268 Console.Write("{0} ", i);
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);
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);