1 // Permission is hereby granted, free of charge, to any person obtaining
2 // a copy of this software and associated documentation files (the
3 // "Software"), to deal in the Software without restriction, including
4 // without limitation the rights to use, copy, modify, merge, publish,
5 // distribute, sublicense, and/or sell copies of the Software, and to
6 // permit persons to whom the Software is furnished to do so, subject to
7 // the following conditions:
9 // The above copyright notice and this permission notice shall be
10 // included in all copies or substantial portions of the Software.
12 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
13 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
14 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
15 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
16 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
17 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
20 // Alejandro Serrano "Serras" (trupill@yahoo.es)
24 using System.Collections;
25 using System.Collections.Generic;
29 internal class InternalOrderedSequence<TElement, K> : IOrderedEnumerable<TElement>
31 IEnumerable<TElement> source;
32 Func<TElement, K> key_selector;
33 IComparer<K> comparer;
35 IOrderedEnumerable<TElement> previous;
37 internal InternalOrderedSequence (IEnumerable<TElement> source, Func<TElement, K> keySelector,
38 IComparer<K> comparer, bool descending, IOrderedEnumerable<TElement> previous)
41 this.key_selector = keySelector;
42 this.comparer = comparer;
43 this.descending = descending;
44 this.previous = previous;
48 IEnumerable<TElement> Sort (IEnumerable<TElement> previousList)
51 return PerformSort (previousList);
53 return previous.CreateOrderedEnumerable (key_selector, comparer, descending);
56 public IEnumerator<TElement> GetEnumerator ()
58 return Sort (source).GetEnumerator ();
61 IEnumerator IEnumerable.GetEnumerator ()
63 return this.GetEnumerator ();
66 public IOrderedEnumerable<TElement> CreateOrderedEnumerable<TKey> (
67 Func<TElement, TKey> selector, IComparer<TKey> comparer, bool descending)
69 throw new NotImplementedException ();
72 List<TElement> source_list;
76 private IEnumerable<TElement> PerformSort (IEnumerable<TElement> items)
78 // It first enumerates source, collecting all elements
79 source_list = new List<TElement> (items);
81 // If the source contains just zero or one element, there's no need to sort
82 if (source_list.Count <= 1)
85 // Then evaluate the keySelector function for each element,
86 // collecting the key values
87 keys = new K [source_list.Count];
88 for (int i = 0; i < source_list.Count; i++)
89 keys[i] = key_selector(source_list [i]);
91 // Then sorts the elements according to the collected
92 // key values and the selected ordering
93 indexes = new int [keys.Length];
94 for (int i = 0; i < indexes.Length; i++)
97 QuickSort(indexes, 0, indexes.Length - 1);
99 // Return the values as IEnumerable<TElement>
100 TElement[] orderedList = new TElement [indexes.Length];
101 for (int i = 0; i < indexes.Length; i++)
102 orderedList [i] = source_list [indexes [i]];
106 private int CompareItems (int firstIndex, int secondIndex)
110 if (comparer == null)
111 comparison = ((IComparable<K>)keys [firstIndex]).CompareTo (keys [secondIndex]);
113 comparison = comparer.Compare (keys [firstIndex], keys [secondIndex]);
115 // If descending, return the opposite comparison
116 return (descending ? -comparison : comparison);
119 /** QuickSort implementation
120 Based on implementation found in Wikipedia
121 http://en.wikipedia.org/wiki/Quicksort_implementations
122 that was released under the GNU Free Documentation License **/
124 private void QuickSort (int[] array, int left, int right)
128 Random random = new Random ();
129 int pivot = random.Next (left, right);
130 Swap (array, pivot, left);
134 while (right >= left) {
135 int leftComparison = CompareItems (indexes [left], indexes [pivot]);
136 int rightComparison = CompareItems (indexes [right], indexes [pivot]);
137 if (leftComparison >= 0 && rightComparison < 0)
138 Swap (array, left, right);
139 else if (leftComparison >= 0)
141 else if (rightComparison < 0)
149 Swap (array, pivot, right);
152 QuickSort (array, lhold, pivot);
153 if (rhold > pivot + 1)
154 QuickSort (array, pivot + 1, rhold);
157 private void Swap (int[] items, int left, int right)
159 int temp = items [right];
160 items [right] = items [left];