source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/PowerCollections/ReadOnlyListBase.cs @ 1927

Last change on this file since 1927 was 1927, checked in by matkovic, 11 years ago

-added PowerCollection library
-added QuadTree
-improved path finding performance

File size: 28.6 KB
Line 
1//******************************
2// Written by Peter Golde
3// Copyright (c) 2004-2007, Wintellect
4//
5// Use and restribution of this code is subject to the license agreement
6// contained in the file "License.txt" accompanying this file.
7//******************************
8
9using System;
10using System.Collections;
11using System.Collections.Generic;
12
13namespace Wintellect.PowerCollections
14{
15    /// <summary>
16    /// ReadOnlyListBase is an abstract class that can be used as a base class for a read-only collection that needs
17    /// to implement the generic IList&lt;T&gt; and non-generic IList collections. The derived class needs
18    /// to override the Count property and the get part of the indexer. The implementation
19    /// of all the other methods in IList&lt;T&gt; and IList are handled by ListBase.
20    /// </summary>
21    /// <typeparam name="T"></typeparam>
22    [Serializable]
23    public abstract class ReadOnlyListBase<T> : ReadOnlyCollectionBase<T>, IList<T>, IList
24    {
25        /// <summary>
26        /// Throws an NotSupportedException stating that this collection cannot be modified.
27        /// </summary>
28        private void MethodModifiesCollection()
29        {
30            throw new NotSupportedException(string.Format(Strings.CannotModifyCollection, Util.SimpleClassName(this.GetType())));
31        }
32
33        /// <summary>
34        /// The property must be overridden by the derived class to return the number of
35        /// items in the list.
36        /// </summary>
37        /// <value>The number of items in the list.</value>
38        public abstract override int Count { get;}
39
40        /// <summary>
41        /// The get part of the indexer must be overridden by the derived class to get
42        /// values of the list at a particular index.
43        /// </summary>
44        /// <param name="index">The index in the list to get or set an item at. The
45        /// first item in the list has index 0, and the last has index Count-1.</param>
46        /// <returns>The item at the given index.</returns>
47        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
48        /// less than zero or greater than or equal to Count.</exception>
49        public virtual T this[int index]
50        {
51            get
52            {
53                throw new NotImplementedException(Strings.MustOverrideIndexerGet);
54            }
55
56            set
57            {
58                MethodModifiesCollection();
59            }
60        }
61
62        /// <summary>
63        /// Enumerates all of the items in the list, in order. The item at index 0
64        /// is enumerated first, then the item at index 1, and so on.
65        /// </summary>
66        /// <returns>An IEnumerator&lt;T&gt; that enumerates all the
67        /// items in the list.</returns>
68        public override IEnumerator<T> GetEnumerator()
69        {
70            int count = Count;
71            for (int i = 0; i < count; ++i) {
72                yield return this[i];
73            }
74        }
75
76        /// <summary>
77        /// Determines if the list contains any item that compares equal to <paramref name="item"/>.
78        /// The implementation simply checks whether IndexOf(item) returns a non-negative value.
79        /// </summary>
80        /// <remarks>Equality in the list is determined by the default sense of
81        /// equality for T. If T implements IComparable&lt;T&gt;, the
82        /// Equals method of that interface is used to determine equality. Otherwise,
83        /// Object.Equals is used to determine equality.</remarks>
84        /// <param name="item">The item to search for.</param>
85        /// <returns>True if the list contains an item that compares equal to <paramref name="item"/>.</returns>
86        public override bool Contains(T item)
87        {
88            return (IndexOf(item) >= 0);
89        }
90
91        /// <summary>
92        /// Copies all the items in the list, in order, to <paramref name="array"/>,
93        /// starting at index 0.
94        /// </summary>
95        /// <param name="array">The array to copy to. This array must have a size
96        /// that is greater than or equal to Count.</param>
97        public virtual void CopyTo(T[] array)
98        {
99            this.CopyTo(array, 0);
100        }
101
102        /// <summary>
103        /// Copies a range of elements from the list to <paramref name="array"/>,
104        /// starting at <paramref name="arrayIndex"/>.
105        /// </summary>
106        /// <param name="index">The starting index in the source list of the range to copy.</param>
107        /// <param name="array">The array to copy to. This array must have a size
108        /// that is greater than or equal to Count + arrayIndex.</param>
109        /// <param name="arrayIndex">The starting index in <paramref name="array"/>
110        /// to copy to.</param>
111        /// <param name="count">The number of items to copy.</param>
112        public virtual void CopyTo(int index, T[] array, int arrayIndex, int count)
113        {
114            Range(index, count).CopyTo(array, arrayIndex);
115        }
116
117        /// <summary>
118        /// Finds the first item in the list that satisfies the condition
119        /// defined by <paramref name="predicate"/>. If no item matches the condition, than
120        /// the default value for T (null or all-zero) is returned.
121        /// </summary>
122        /// <remarks>If the default value for T (null or all-zero) matches the condition defined by <paramref name="predicate"/>,
123        /// and the list might contain the default value, then it is impossible to distinguish the different between finding
124        /// the default value and not finding any item. To distinguish these cases, use <see cref="TryFind"/>.</remarks>
125        /// <param name="predicate">A delegate that defined the condition to check for.</param>
126        /// <returns>The first item that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
127        /// condition, the default value for T is returned.</returns>
128        /// <seealso cref="TryFind"/>
129        public virtual T Find(Predicate<T> predicate)
130        {
131            return Algorithms.FindFirstWhere(this, predicate);
132        }
133
134        /// <summary>
135        /// Finds the first item in the list that satisfies the condition
136        /// defined by <paramref name="predicate"/>.
137        /// </summary>
138        /// <param name="predicate">A delegate that defines the condition to check for.</param>
139        /// <param name="foundItem">If true is returned, this parameter receives the first item in the list
140        /// that satifies the condition defined by <paramref name="predicate"/>.</param>
141        /// <returns>True if an item that  satisfies the condition <paramref name="predicate"/> was found. False
142        /// if no item in the list satisfies that condition.</returns>
143        public virtual bool TryFind(Predicate<T> predicate, out T foundItem)
144        {
145            return Algorithms.TryFindFirstWhere(this, predicate, out foundItem);
146        }
147
148        /// <summary>
149        /// Finds the last item in the list that satisfies the condition
150        /// defined by <paramref name="predicate"/>. If no item matches the condition, than
151        /// the default value for T (null or all-zero) is returned.
152        /// </summary>
153        /// <remarks>If the default value for T (null or all-zero) matches the condition defined by <paramref name="predicate"/>,
154        /// and the list might contain the default value, then it is impossible to distinguish the different between finding
155        /// the default value and not finding any item. To distinguish these cases, use <see cref="TryFindLast"/>.</remarks>
156        /// <param name="predicate">A delegate that defined the condition to check for.</param>
157        /// <returns>The last item that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
158        /// condition, the default value for T is returned.</returns>
159        /// <seealso cref="TryFindLast"/>
160        public virtual T FindLast(Predicate<T> predicate)
161        {
162            return Algorithms.FindLastWhere(this, predicate);
163        }
164
165        /// <summary>
166        /// Finds the last item in the list that satisfies the condition
167        /// defined by <paramref name="predicate"/>.
168        /// </summary>
169        /// <param name="predicate">A delegate that defines the condition to check for.</param>
170        /// <param name="foundItem">If true is returned, this parameter receives the last item in the list
171        /// that satifies the condition defined by <paramref name="predicate"/>.</param>
172        /// <returns>True if an item that  satisfies the condition <paramref name="predicate"/> was found. False
173        /// if no item in the list satisfies that condition.</returns>
174        public virtual bool TryFindLast(Predicate<T> predicate, out T foundItem)
175        {
176            return Algorithms.TryFindLastWhere(this, predicate, out foundItem);
177        }
178
179        /// <summary>
180        /// Finds the index of the first item in the list that satisfies the condition
181        /// defined by <paramref name="predicate"/>. If no item matches the condition, -1 is returned.
182        /// </summary>
183        /// <param name="predicate">A delegate that defined the condition to check for.</param>
184        /// <returns>The index of the first item that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
185        /// condition, -1 is returned.</returns>
186        public virtual int FindIndex(Predicate<T> predicate)
187        {
188            return Algorithms.FindFirstIndexWhere(this, predicate);
189        }
190
191        /// <summary>
192        /// Finds the index of the first item, in the range of items extending from <paramref name="index"/> to the end, that satisfies the condition
193        /// defined by <paramref name="predicate"/>. If no item matches the condition, -1 is returned.
194        /// </summary>
195        /// <param name="predicate">A delegate that defined the condition to check for.</param>
196        /// <param name="index">The starting index of the range to check.</param>
197        /// <returns>The index of the first item in the given range that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
198        /// condition, -1 is returned.</returns>
199        public virtual int FindIndex(int index, Predicate<T> predicate)
200        {
201            int foundIndex = Algorithms.FindFirstIndexWhere(Range(index, Count - index), predicate);
202            if (foundIndex < 0)
203                return -1;
204            else
205                return foundIndex + index;
206        }
207
208        /// <summary>
209        /// Finds the index of the first item, in the range of <paramref name="count"/> items starting from <paramref name="index"/>, that satisfies the condition
210        /// defined by <paramref name="predicate"/>. If no item matches the condition, -1 is returned.
211        /// </summary>
212        /// <param name="predicate">A delegate that defined the condition to check for.</param>
213        /// <param name="index">The starting index of the range to check.</param>
214        /// <param name="count">The number of items in range to check.</param>
215        /// <returns>The index of the first item in the given range that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
216        /// condition, -1 is returned.</returns>
217        public virtual int FindIndex(int index, int count, Predicate<T> predicate)
218        {
219            int foundIndex = Algorithms.FindFirstIndexWhere(Range(index, count), predicate);
220            if (foundIndex < 0)
221                return -1;
222            else
223                return foundIndex + index;
224        }
225
226        /// <summary>
227        /// Finds the index of the last item in the list that satisfies the condition
228        /// defined by <paramref name="predicate"/>. If no item matches the condition, -1 is returned.
229        /// </summary>
230        /// <param name="predicate">A delegate that defined the condition to check for.</param>
231        /// <returns>The index of the last item that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
232        /// condition, -1 is returned.</returns>
233        public virtual int FindLastIndex(Predicate<T> predicate)
234        {
235            return Algorithms.FindLastIndexWhere(this, predicate);
236        }
237
238        /// <summary>
239        /// Finds the index of the last item, in the range of items extending from the beginning
240        /// of the list to <paramref name="index"/>, that satisfies the condition
241        /// defined by <paramref name="predicate"/>. If no item matches the condition, -1 is returned.
242        /// </summary>
243        /// <param name="predicate">A delegate that defined the condition to check for.</param>
244        /// <param name="index">The ending index of the range to check.</param>
245        /// <returns>The index of the last item in the given range that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
246        /// condition, -1 is returned.</returns>
247        public virtual int FindLastIndex(int index, Predicate<T> predicate)
248        {
249            return Algorithms.FindLastIndexWhere(Range(0, index + 1), predicate);
250        }
251
252        /// <summary>
253        /// Finds the index of the last item, in the range of <paramref name="count"/> items ending at <paramref name="index"/>, that satisfies the condition
254        /// defined by <paramref name="predicate"/>. If no item matches the condition, -1 is returned.
255        /// </summary>
256        /// <param name="predicate">A delegate that defined the condition to check for.</param>
257        /// <param name="index">The ending index of the range to check.</param>
258        /// <param name="count">The number of items in range to check.</param>
259        /// <returns>The index of the last item in the given range that satisfies the condition <paramref name="predicate"/>. If no item satisfies that
260        /// condition, -1 is returned.</returns>
261        public virtual int FindLastIndex(int index, int count, Predicate<T> predicate)
262        {
263            int foundIndex = Algorithms.FindLastIndexWhere(Range(index - count + 1, count), predicate);
264
265            if (foundIndex >= 0)
266                return foundIndex + index - count + 1;
267            else
268                return -1;
269        }
270
271        /// <summary>
272        /// Finds the index of the first item in the list that is equal to <paramref name="item"/>.
273        /// </summary>
274        /// <remarks>The default implementation of equality for type T is used in the search. This is the
275        /// equality defined by IComparable&lt;T&gt; or object.Equals.</remarks>
276        /// <param name="item">The item to search fror.</param>
277        /// <returns>The index of the first item in the list that that is equal to <paramref name="item"/>.  If no item is equal
278        /// to <paramref name="item"/>, -1 is returned.</returns>
279        public virtual int IndexOf(T item)
280        {
281            return Algorithms.FirstIndexOf(this, item, EqualityComparer<T>.Default);
282        }
283
284        /// <summary>
285        /// Finds the index of the first item, in the range of items extending from <paramref name="index"/> to the end, 
286        /// that is equal to <paramref name="item"/>.
287        /// </summary>
288        /// <remarks>The default implementation of equality for type T is used in the search. This is the
289        /// equality defined by IComparable&lt;T&gt; or object.Equals.</remarks>
290        /// <param name="item">The item to search fror.</param>
291        /// <param name="index">The starting index of the range to check.</param>
292        /// <returns>The index of the first item in the given range that that is equal to <paramref name="item"/>.  If no item is equal
293        /// to <paramref name="item"/>, -1 is returned.</returns>
294        public virtual int IndexOf(T item, int index)
295        {
296            int foundIndex = Algorithms.FirstIndexOf(Range(index, Count - index), item, EqualityComparer<T>.Default);
297
298            if (foundIndex >= 0)
299                return foundIndex + index;
300            else
301                return -1;
302        }
303
304        /// <summary>
305        /// Finds the index of the first item, in the range of <paramref name="count"/> items starting from <paramref name="index"/>, 
306        /// that is equal to <paramref name="item"/>.
307        /// </summary>
308        /// <remarks>The default implementation of equality for type T is used in the search. This is the
309        /// equality defined by IComparable&lt;T&gt; or object.Equals.</remarks>
310        /// <param name="item">The item to search fror.</param>
311        /// <param name="index">The starting index of the range to check.</param>
312        /// <param name="count">The number of items in range to check.</param>
313        /// <returns>The index of the first item in the given range that that is equal to <paramref name="item"/>.  If no item is equal
314        /// to <paramref name="item"/>, -1 is returned.</returns>
315        public virtual int IndexOf(T item, int index, int count)
316        {
317            int foundIndex = Algorithms.FirstIndexOf(Range(index, count), item, EqualityComparer<T>.Default);
318
319            if (foundIndex >= 0)
320                return foundIndex + index;
321            else
322                return -1;
323        }
324
325        /// <summary>
326        /// Finds the index of the last item in the list that is equal to <paramref name="item"/>.
327        /// </summary>
328        /// <remarks>The default implementation of equality for type T is used in the search. This is the
329        /// equality defined by IComparable&lt;T&gt; or object.Equals.</remarks>
330        /// <param name="item">The item to search fror.</param>
331        /// <returns>The index of the last item in the list that that is equal to <paramref name="item"/>.  If no item is equal
332        /// to <paramref name="item"/>, -1 is returned.</returns>
333        public virtual int LastIndexOf(T item)
334        {
335            return Algorithms.LastIndexOf(this, item, EqualityComparer<T>.Default);
336        }
337
338        /// <summary>
339        /// Finds the index of the last item, in the range of items extending from the beginning
340        /// of the list to <paramref name="index"/>, that is equal to <paramref name="item"/>.
341        /// </summary>
342        /// <remarks>The default implementation of equality for type T is used in the search. This is the
343        /// equality defined by IComparable&lt;T&gt; or object.Equals.</remarks>
344        /// <param name="item">The item to search fror.</param>
345        /// <param name="index">The ending index of the range to check.</param>
346        /// <returns>The index of the last item in the given range that that is equal to <paramref name="item"/>.  If no item is equal
347        /// to <paramref name="item"/>, -1 is returned.</returns>
348        public virtual int LastIndexOf(T item, int index)
349        {
350            int foundIndex = Algorithms.LastIndexOf(Range(0, index + 1), item, EqualityComparer<T>.Default);
351
352            return foundIndex;
353        }
354
355        /// <summary>
356        /// Finds the index of the last item, in the range of <paramref name="count"/> items ending at <paramref name="index"/>,
357        /// that is equal to <paramref name="item"/>.
358        /// </summary>
359        /// <remarks>The default implementation of equality for type T is used in the search. This is the
360        /// equality defined by IComparable&lt;T&gt; or object.Equals.</remarks>
361        /// <param name="item">The item to search for.</param>
362        /// <param name="index">The ending index of the range to check.</param>
363        /// <param name="count">The number of items in range to check.</param>
364        /// <returns>The index of the last item in the given range that that is equal to <paramref name="item"/>.  If no item is equal
365        /// to <paramref name="item"/>, -1 is returned.</returns>
366        public virtual int LastIndexOf(T item, int index, int count)
367        {
368            int foundIndex = Algorithms.LastIndexOf(Range(index - count + 1, count), item, EqualityComparer<T>.Default);
369
370            if (foundIndex >= 0)
371                return foundIndex + index - count + 1;
372            else
373                return -1;
374        }
375
376        /// <summary>
377        /// Returns a view onto a sub-range of this list. Items are not copied; the
378        /// returned IList&lt;T&gt; is simply a different view onto the same underlying items.
379        /// </summary>
380        /// <remarks>
381        /// <para>This method can be used to apply an algorithm to a portion of a list. For example:</para>
382        /// <code>Algorithms.Reverse(deque.Range(3, 6))</code>
383        /// will return the reverse opf the 6 items beginning at index 3.</remarks>
384        /// <param name="start">The starting index of the view.</param>
385        /// <param name="count">The number of items in the view.</param>
386        /// <returns>A list that is a view onto the given sub-part of this list. </returns>
387        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> or <paramref name="count"/> is negative.</exception>
388        /// <exception cref="ArgumentOutOfRangeException"><paramref name="start"/> + <paramref name="count"/> is greater than the
389        /// size of the list.</exception>
390        public virtual IList<T> Range(int start, int count)
391        {
392            return Algorithms.Range(this, start, count);
393        }
394
395        /// <summary>
396        /// Inserts a new item at the given index. This implementation throws a NotSupportedException
397        /// indicating that the list is read-only.
398        /// </summary>
399        /// <param name="index">The index in the list to insert the item at. After the
400        /// insertion, the inserted item is located at this index. The
401        /// first item in the list has index 0.</param>
402        /// <param name="item">The item to insert at the given index.</param>
403        /// <exception cref="NotSupportedException">Always thrown.</exception>
404        void IList<T>.Insert(int index, T item)
405        {
406            MethodModifiesCollection();
407        }
408
409        /// <summary>
410        /// Removes the item at the given index.  This implementation throws a NotSupportedException
411        /// indicating that the list is read-only.
412        /// </summary>
413        /// <param name="index">The index in the list to remove the item at. The
414        /// first item in the list has index 0.</param>
415        /// <exception cref="NotSupportedException">Always thrown.</exception>
416        void IList<T>.RemoveAt(int index)
417        {
418            MethodModifiesCollection();
419        }
420
421        /// <summary>
422        /// Adds an item to the end of the list. This implementation throws a NotSupportedException
423        /// indicating that the list is read-only.
424        /// </summary>
425        /// <param name="value">The item to add to the list.</param>
426        /// <exception cref="NotSupportedException">Always thrown.</exception>
427        int IList.Add(object value)
428        {
429            MethodModifiesCollection();
430            return -1;
431        }
432
433        /// <summary>
434        /// Removes all the items from the list, resulting in an empty list. This implementation throws a NotSupportedException
435        /// indicating that the list is read-only.
436        /// </summary>
437        /// <exception cref="NotSupportedException">Always thrown.</exception>
438        void IList.Clear()
439        {
440            MethodModifiesCollection();
441        }
442
443        /// <summary>
444        /// Determines if the list contains any item that compares equal to <paramref name="value"/>.
445        /// </summary>
446        /// <remarks>Equality in the list is determined by the default sense of
447        /// equality for T. If T implements IComparable&lt;T&gt;, the
448        /// Equals method of that interface is used to determine equality. Otherwise,
449        /// Object.Equals is used to determine equality.</remarks>
450        /// <param name="value">The item to search for.</param>
451        bool IList.Contains(object value)
452        {
453            if (value is T || value == null)
454                return Contains((T)value);
455            else
456                return false;
457        }
458
459        /// <summary>
460        /// Find the first occurrence of an item equal to <paramref name="value"/>
461        /// in the list, and returns the index of that item.
462        /// </summary>
463        /// <remarks>Equality in the list is determined by the default sense of
464        /// equality for T. If T implements IComparable&lt;T&gt;, the
465        /// Equals method of that interface is used to determine equality. Otherwise,
466        /// Object.Equals is used to determine equality.</remarks>
467        /// <param name="value">The item to search for.</param>
468        /// <returns>The index of <paramref name="value"/>, or -1 if no item in the
469        /// list compares equal to <paramref name="value"/>.</returns>
470        int IList.IndexOf(object value)
471        {
472            if (value is T || value == null)
473                return IndexOf((T)value);
474            else
475                return -1;
476        }
477
478        /// <summary>
479        /// Insert a new item at the given index. This implementation throws a NotSupportedException
480        /// indicating that the list is read-only.
481        /// </summary>
482        /// <param name="index">The index in the list to insert the item at. After the
483        /// insertion, the inserted item is located at this index. The
484        /// first item in the list has index 0.</param>
485        /// <param name="value">The item to insert at the given index.</param>
486        /// <exception cref="NotSupportedException">Always thrown.</exception>
487        void IList.Insert(int index, object value)
488        {
489            MethodModifiesCollection();
490        }
491
492        /// <summary>
493        /// Returns whether the list is a fixed size. This implementation always returns true.
494        /// </summary>
495        /// <value>Alway true, indicating that the list is fixed size.</value>
496        bool IList.IsFixedSize
497        {
498            get { return true; }
499        }
500
501        /// <summary>
502        /// Returns whether the list is read only. This implementation always returns true.
503        /// </summary>
504        /// <value>Alway true, indicating that the list is read-only.</value>
505        bool IList.IsReadOnly
506        {
507            get { return true; }
508        }
509
510        /// <summary>
511        /// Searches the list for the first item that compares equal to <paramref name="value"/>.
512        /// If one is found, it is removed. Otherwise, the list is unchanged.  This implementation throws a NotSupportedException
513        /// indicating that the list is read-only.
514        /// </summary>
515        /// <remarks>Equality in the list is determined by the default sense of
516        /// equality for T. If T implements IComparable&lt;T&gt;, the
517        /// Equals method of that interface is used to determine equality. Otherwise,
518        /// Object.Equals is used to determine equality.</remarks>
519        /// <param name="value">The item to remove from the list.</param>
520        /// <exception cref="NotSupportedException">Always thrown.</exception>
521        void IList.Remove(object value)
522        {
523            MethodModifiesCollection();
524        }
525
526        /// <summary>
527        /// Removes the item at the given index. This implementation throws a NotSupportedException
528        /// indicating that the list is read-only.
529        /// </summary>
530        /// <param name="index">The index in the list to remove the item at. The
531        /// first item in the list has index 0.</param>
532        /// <exception cref="NotSupportedException">Always thrown.</exception>
533        void IList.RemoveAt(int index)
534        {
535            MethodModifiesCollection();
536        }
537
538        /// <summary>
539        /// Gets or sets the value at a particular index in the list.
540        /// </summary>
541        /// <param name="index">The index in the list to get or set an item at. The
542        /// first item in the list has index 0, and the last has index Count-1.</param>
543        /// <value>The item at the given index.</value>
544        /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is
545        /// less than zero or greater than or equal to Count.</exception>
546        /// <exception cref="ArgumentException"><paramref name="value"/> cannot be converted to T.</exception>
547        /// <exception cref="NotSupportedException">Always thrown from the setter, indicating that the list
548        /// is read-only.</exception>
549        object IList.this[int index]
550        {
551            get
552            {
553                return this[index];
554            }
555
556            set
557            {
558                MethodModifiesCollection();
559            }
560        }
561    }
562}
Note: See TracBrowser for help on using the repository browser.