2 // System.Collections.Specialized.ListDictionary.cs
4 // Copyright (C) 2004, 2005 Novell (http://www.novell.com)
8 // Permission is hereby granted, free of charge, to any person obtaining
9 // a copy of this software and associated documentation files (the
10 // "Software"), to deal in the Software without restriction, including
11 // without limitation the rights to use, copy, modify, merge, publish,
12 // distribute, sublicense, and/or sell copies of the Software, and to
13 // permit persons to whom the Software is furnished to do so, subject to
14 // the following conditions:
16 // The above copyright notice and this permission notice shall be
17 // included in all copies or substantial portions of the Software.
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
23 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
24 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
25 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28 using System.Runtime.Serialization;
30 namespace System.Collections.Specialized
33 public class ListDictionary : IDictionary, ICollection, IEnumerable {
36 private DictionaryNode head;
37 private IComparer comparer;
39 public ListDictionary ()
47 public ListDictionary (IComparer comparer) : this ()
49 this.comparer = comparer;
52 private DictionaryNode FindEntry (object key)
55 throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
57 DictionaryNode entry = head;
58 DictionaryNode prev = null;
59 if (comparer == null) {
60 while (entry != null) {
61 if (key.Equals (entry.key))
67 while (entry != null) {
68 if (comparer.Compare (key, entry.key) == 0)
76 private DictionaryNode FindEntry (object key, out DictionaryNode prev)
79 throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
81 DictionaryNode entry = head;
83 if (comparer == null) {
84 while (entry != null) {
85 if (key.Equals (entry.key))
91 while (entry != null) {
92 if (comparer.Compare (key, entry.key) == 0)
101 private void AddImpl (object key, object value, DictionaryNode prev)
104 // Code in the MCS compiler (doc.cs) appears to depend on the new entry being
105 // added at the end, even though we don't promise any such thing.
106 // Preferably, this code would just have been:
108 // head = new DictionaryNode (key, value, head);
111 head = new DictionaryNode (key, value, head);
113 prev.next = new DictionaryNode (key, value, prev.next);
118 // IEnumerable Interface
119 IEnumerator IEnumerable.GetEnumerator ()
121 return new DictionaryNodeEnumerator (this);
124 // ICollection Interface
126 get { return count; }
129 public bool IsSynchronized {
130 get { return false; }
133 public object SyncRoot {
137 public void CopyTo (Array array, int index)
140 throw new ArgumentNullException ("array", "Array cannot be null.");
142 throw new ArgumentOutOfRangeException ("index", "index is less than 0");
143 if (index > array.Length)
144 throw new IndexOutOfRangeException ("index is too large");
145 if (Count > array.Length - index)
146 throw new ArgumentException ("Not enough room in the array");
148 foreach (DictionaryEntry entry in this)
149 array.SetValue (entry, index++);
152 // IDictionary Interface
153 public bool IsFixedSize {
154 get { return false; }
157 public bool IsReadOnly {
158 get { return false; }
162 public object this [object key] {
164 DictionaryNode entry = FindEntry (key);
165 return entry == null ? null : entry.value;
170 DictionaryNode entry = FindEntry (key, out prev);
174 AddImpl (key, value, prev);
178 public ICollection Keys {
179 get { return new DictionaryNodeCollection (this, true); }
182 public ICollection Values {
183 get { return new DictionaryNodeCollection (this, false); }
186 public void Add (object key, object value)
189 DictionaryNode entry = FindEntry (key, out prev);
191 throw new ArgumentException ("key", "Duplicate key in add.");
193 AddImpl (key, value, prev);
203 public bool Contains (object key)
205 return FindEntry (key) != null;
208 public IDictionaryEnumerator GetEnumerator ()
210 return new DictionaryNodeEnumerator (this);
213 public void Remove (object key)
216 DictionaryNode entry = FindEntry (key, out prev);
222 prev.next = entry.next;
230 private class DictionaryNode {
233 public DictionaryNode next;
234 public DictionaryNode (object key, object value, DictionaryNode next)
242 private class DictionaryNodeEnumerator : IEnumerator, IDictionaryEnumerator {
243 private ListDictionary dict;
244 private bool isAtStart;
245 private DictionaryNode current;
248 public DictionaryNodeEnumerator (ListDictionary dict)
251 version = dict.version;
255 private void FailFast()
257 if (version != dict.version) {
258 throw new InvalidOperationException (
259 "The ListDictionary's contents changed after this enumerator was instantiated.");
263 public bool MoveNext ()
266 if (current == null && !isAtStart)
268 current = isAtStart ? dict.head : current.next;
270 return current != null;
280 public object Current {
281 get { return Entry; }
284 private DictionaryNode DictionaryNode {
288 throw new InvalidOperationException (
289 "Enumerator is positioned before the collection's first element or after the last element.");
294 // IDictionaryEnumerator
295 public DictionaryEntry Entry {
297 object key = DictionaryNode.key;
298 return new DictionaryEntry (key, current.value);
303 get { return DictionaryNode.key; }
306 public object Value {
307 get { return DictionaryNode.value; }
311 private class DictionaryNodeCollection : ICollection {
312 private ListDictionary dict;
313 private bool isKeyList;
315 public DictionaryNodeCollection (ListDictionary dict, bool isKeyList)
318 this.isKeyList = isKeyList;
321 // ICollection Interface
323 get { return dict.Count; }
326 public bool IsSynchronized {
327 get { return false; }
330 public object SyncRoot {
331 get { return dict.SyncRoot; }
334 public void CopyTo (Array array, int index)
337 throw new ArgumentNullException ("array", "Array cannot be null.");
339 throw new ArgumentOutOfRangeException ("index", "index is less than 0");
340 if (index > array.Length)
341 throw new IndexOutOfRangeException ("index is too large");
342 if (Count > array.Length - index)
343 throw new ArgumentException ("Not enough room in the array");
345 foreach (object obj in this)
346 array.SetValue (obj, index++);
349 // IEnumerable Interface
350 public IEnumerator GetEnumerator()
352 return new DictionaryNodeCollectionEnumerator (dict.GetEnumerator (), isKeyList);
355 private class DictionaryNodeCollectionEnumerator : IEnumerator {
356 private IDictionaryEnumerator inner;
357 private bool isKeyList;
359 public DictionaryNodeCollectionEnumerator (IDictionaryEnumerator inner, bool isKeyList)
362 this.isKeyList = isKeyList;
365 public object Current {
366 get { return isKeyList ? inner.Key : inner.Value; }
369 public bool MoveNext ()
371 return inner.MoveNext ();