+//
+// System.Collections.Specialized.ListDictionary.cs
+//
+// Copyright (C) 2004, 2005 Novell (http://www.novell.com)
+//
//
// Permission is hereby granted, free of charge, to any person obtaining
// distribute, sublicense, and/or sell copies of the Software, and to
// permit persons to whom the Software is furnished to do so, subject to
// the following conditions:
-//
+//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
-//
+//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-namespace System.Collections.Specialized\r
-{\r
- [Serializable]\r
- public class ListDictionary : IDictionary, ICollection, IEnumerable\r
- {\r
- private int count;\r
- private int modCount;\r
- private ListEntry root;\r
- private IComparer comparer;\r
- \r
- \r
- public ListDictionary()\r
- {\r
- count = 0;\r
- modCount = 0;\r
- comparer = null;\r
- root = null;\r
- }\r
- \r
- public ListDictionary(IComparer comparer) : this()\r
- {\r
- this.comparer = comparer;\r
- }\r
- \r
- private bool AreEqual(object obj1, object obj2)\r
- {\r
- if (comparer != null) {\r
- if (comparer.Compare(obj1, obj2) == 0) {\r
- return true;\r
- }\r
- } else {\r
- if (obj1.Equals(obj2)) {\r
- return true;\r
- }\r
- }\r
- \r
- return false;\r
- }\r
- \r
- private ListEntry FindEntry(object key)\r
- {\r
- if (key == null) {\r
- throw new ArgumentNullException("Attempted lookup for a null key.");\r
- }\r
- \r
- if (root == null) {\r
- return null;\r
- } else {\r
- ListEntry entry = root;\r
- \r
- while (entry != null) {\r
- if (AreEqual(key, entry.key)) {\r
- return entry;\r
- }\r
- \r
- entry = entry.next;\r
- }\r
- }\r
- \r
- return null;\r
- }\r
-\r
- private void AddImpl(object key, object value)\r
- {\r
- if (key == null) {\r
- throw new ArgumentNullException("Attempted add with a null key.");\r
- }\r
- \r
- if (root == null) {\r
- root = new ListEntry();\r
- root.key = key;\r
- root.value = value;\r
- } else {\r
- ListEntry entry = root;\r
- \r
- while (entry != null) {\r
- if (AreEqual(key, entry.key)) {\r
- throw new ArgumentException("Duplicate key in add.");\r
- }\r
- \r
- if (entry.next == null) {\r
- break;\r
- }\r
- \r
- entry = entry.next;\r
- }\r
- \r
- entry.next = new ListEntry();\r
- entry.next.key = key;\r
- entry.next.value = value;\r
- }\r
- \r
- count++;\r
- modCount++;\r
- }\r
- \r
- // IEnumerable Interface\r
- IEnumerator IEnumerable.GetEnumerator()\r
- {\r
- return new ListEntryEnumerator(this);\r
- }\r
- \r
- // ICollection Interface\r
- public int Count {\r
- get {\r
- return count;\r
- }\r
- }\r
- \r
- public bool IsSynchronized {\r
- get {\r
- return false;\r
- }\r
- }\r
- \r
- public object SyncRoot {\r
- get {\r
- return this;\r
- }\r
- }\r
-\r
- public void CopyTo(Array array, int index)\r
- {\r
- if (array == null)\r
- throw new ArgumentNullException(\r
- "array",\r
- "Array cannot be null.");\r
-\r
- if (index < 0)\r
- throw new ArgumentOutOfRangeException("index", "index is less than 0");\r
-\r
- int i = index;\r
- foreach ( DictionaryEntry entry in this )\r
- array.SetValue( entry, i++ );\r
- }\r
- \r
- // IDictionary Interface\r
- public bool IsFixedSize\r
- {\r
- get {\r
- return false;\r
- }\r
- }\r
- \r
- public bool IsReadOnly\r
- {\r
- get {\r
- return false;\r
- }\r
- }\r
- \r
- // Indexer\r
- public object this[object key]\r
- {\r
- get {\r
- ListEntry entry = FindEntry(key);\r
- return entry == null ? entry : entry.value;\r
- }\r
- \r
- set {\r
- ListEntry entry = FindEntry(key);\r
- if (entry != null)\r
- entry.value = value;\r
- else\r
- AddImpl(key, value);\r
- }\r
- }\r
- \r
- public ICollection Keys\r
- {\r
- get {\r
- return new ListEntryCollection(this, true);\r
- }\r
- }\r
- \r
- public ICollection Values\r
- {\r
- get {\r
- return new ListEntryCollection(this, false);\r
- }\r
- }\r
- \r
- public void Add(object key, object value)\r
- {\r
- AddImpl(key, value);\r
- }\r
- \r
- public void Clear()\r
- {\r
- root = null;\r
- count = 0;\r
- modCount++;\r
- }\r
- \r
- public bool Contains(object key)\r
- {\r
- return FindEntry(key) != null ? true : false;\r
- }\r
- \r
- public IDictionaryEnumerator GetEnumerator()\r
- {\r
- return new ListEntryEnumerator(this);\r
- }\r
- \r
- public void Remove(object key)\r
- {\r
- if (key == null)\r
- throw new ArgumentNullException(\r
- "key",\r
- "Key cannot be null.");\r
-\r
- \r
- ListEntry entry = root;\r
- \r
- for (ListEntry prev = null; entry != null; prev = entry, entry = entry.next) {\r
- if (AreEqual(key, entry.key)) {\r
- if (prev != null) {\r
- prev.next = entry.next;\r
- } else {\r
- root = entry.next;\r
- }\r
- \r
- entry.value = null;\r
- count--;\r
- modCount++;\r
- }\r
- }\r
- }\r
- \r
-\r
- [Serializable]\r
- private class ListEntry\r
- {\r
- public object key = null;\r
- public object value = null;\r
- public ListEntry next = null;\r
- }\r
-\r
-\r
- private class ListEntryEnumerator : IEnumerator, IDictionaryEnumerator\r
- {\r
- private ListDictionary dict;\r
- private bool isAtStart;\r
- private ListEntry current;\r
- private int version;\r
- \r
- public ListEntryEnumerator(ListDictionary dict)\r
- {\r
- this.dict = dict;\r
- version = dict.modCount;\r
- Reset();\r
- }\r
-\r
- private void FailFast()\r
- {\r
- if (version != dict.modCount) {\r
- throw new InvalidOperationException(\r
- "The ListDictionary's contents changed after this enumerator was instantiated.");\r
- }\r
- }\r
- \r
- public bool MoveNext()\r
- {\r
- FailFast();\r
- \r
- if (isAtStart) {\r
- current = dict.root;\r
- isAtStart = false;\r
- } else {\r
- current = current.next;\r
- }\r
- \r
- return current != null ? true : false; \r
- }\r
- \r
- public void Reset()\r
- {\r
- FailFast();\r
-\r
- isAtStart = true;\r
- current = null;\r
- }\r
- \r
- public object Current\r
- {\r
- get {\r
- FailFast();\r
- \r
- if (isAtStart || current == null) {\r
- throw new InvalidOperationException(\r
- "Enumerator is positioned before the collection's first element or after the last element.");\r
- }\r
- \r
- return new DictionaryEntry(current.key, current.value);\r
- }\r
- }\r
- \r
- // IDictionaryEnumerator\r
- public DictionaryEntry Entry\r
- {\r
- get {\r
- FailFast();\r
- return (DictionaryEntry) Current;\r
- }\r
- }\r
- \r
- public object Key\r
- {\r
- get {\r
- FailFast();\r
- \r
- if (isAtStart || current == null) {\r
- throw new InvalidOperationException(\r
- "Enumerator is positioned before the collection's first element or after the last element.");\r
- }\r
- \r
- return current.key;\r
- }\r
- }\r
- \r
- public object Value\r
- {\r
- get {\r
- FailFast();\r
- \r
- if (isAtStart || current == null) {\r
- throw new InvalidOperationException(\r
- "Enumerator is positioned before the collection's first element or after the last element.");\r
- }\r
- \r
- return current.value;\r
- }\r
- }\r
- }\r
- \r
- private class ListEntryCollection : ICollection\r
- {\r
- private ListDictionary dict;\r
- private bool isKeyList;\r
- \r
- public ListEntryCollection(ListDictionary dict, bool isKeyList)\r
- {\r
- this.dict = dict;\r
- this.isKeyList = isKeyList;\r
- }\r
- \r
- // ICollection Interface\r
- public int Count {\r
- get {\r
- return dict.Count;\r
- }\r
- }\r
- \r
- public bool IsSynchronized\r
- {\r
- get {\r
- return false;\r
- }\r
- }\r
- \r
- public object SyncRoot\r
- {\r
- get {\r
- return dict.SyncRoot;\r
- }\r
- }\r
-\r
- public void CopyTo(Array array, int index)\r
- {\r
- int i = index;\r
- foreach ( object obj in this )\r
- array.SetValue( obj, i++ );\r
- }\r
- \r
- // IEnumerable Interface\r
- public IEnumerator GetEnumerator()\r
- {\r
- return new ListEntryCollectionEnumerator(dict, isKeyList);\r
- }\r
- \r
- private class ListEntryCollectionEnumerator : IEnumerator\r
- {\r
- private ListDictionary dict;\r
- private bool isKeyList;\r
- private bool isAtStart;\r
- private int version;\r
- private ListEntry current;\r
- \r
- public ListEntryCollectionEnumerator(ListDictionary dict, bool isKeyList)\r
- {\r
- this.dict = dict;\r
- this.isKeyList = isKeyList;\r
- isAtStart = true;\r
- version = dict.modCount;\r
- }\r
-\r
- private void FailFast()\r
- {\r
- if (version != dict.modCount) {\r
- throw new InvalidOperationException(\r
- "The Collection's contents changed after this " +\r
- "enumerator was instantiated.");\r
- }\r
- }\r
- \r
- public object Current\r
- {\r
- get {\r
- FailFast();\r
- \r
- if (isAtStart || current == null) {\r
- throw new InvalidOperationException(\r
- "Enumerator is positioned before the collection's " +\r
- "first element or after the last element.");\r
- }\r
- \r
- return isKeyList ? current.key : current.value;\r
- }\r
- }\r
- \r
- public bool MoveNext()\r
- {\r
- FailFast();\r
- \r
- if (isAtStart) {\r
- current = dict.root;\r
- isAtStart = false;\r
- } else {\r
- current = current.next;\r
- }\r
- \r
- return current != null ? true : false;\r
- }\r
- \r
- public void Reset()\r
- {\r
- FailFast();\r
- isAtStart = true;\r
- current = null;\r
- }\r
- }\r
- }\r
- }\r
-}\r
+using System;
+using System.Runtime.Serialization;
+
+namespace System.Collections.Specialized
+{
+ [Serializable]
+ public class ListDictionary : IDictionary, ICollection, IEnumerable {
+ private int count;
+ private int version;
+ private DictionaryNode head;
+ private IComparer comparer;
+
+ public ListDictionary ()
+ {
+ count = 0;
+ version = 0;
+ comparer = null;
+ head = null;
+ }
+
+ public ListDictionary (IComparer comparer) : this ()
+ {
+ this.comparer = comparer;
+ }
+
+ private DictionaryNode FindEntry (object key)
+ {
+ if (key == null)
+ throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
+
+ DictionaryNode entry = head;
+ DictionaryNode prev = null;
+ if (comparer == null) {
+ while (entry != null) {
+ if (key.Equals (entry.key))
+ break;
+ prev = entry;
+ entry = entry.next;
+ }
+ } else {
+ while (entry != null) {
+ if (comparer.Compare (key, entry.key) == 0)
+ break;
+ prev = entry;
+ entry = entry.next;
+ }
+ }
+ return entry;
+ }
+ private DictionaryNode FindEntry (object key, out DictionaryNode prev)
+ {
+ if (key == null)
+ throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
+
+ DictionaryNode entry = head;
+ prev = null;
+ if (comparer == null) {
+ while (entry != null) {
+ if (key.Equals (entry.key))
+ break;
+ prev = entry;
+ entry = entry.next;
+ }
+ } else {
+ while (entry != null) {
+ if (comparer.Compare (key, entry.key) == 0)
+ break;
+ prev = entry;
+ entry = entry.next;
+ }
+ }
+ return entry;
+ }
+
+ private void AddImpl (object key, object value, DictionaryNode prev)
+ {
+ //
+ // Code in the MCS compiler (doc.cs) appears to depend on the new entry being
+ // added at the end, even though we don't promise any such thing.
+ // Preferably, this code would just have been:
+ //
+ // head = new DictionaryNode (key, value, head);
+ //
+ if (prev == null)
+ head = new DictionaryNode (key, value, head);
+ else
+ prev.next = new DictionaryNode (key, value, prev.next);
+ ++count;
+ ++version;
+ }
+
+ // IEnumerable Interface
+ IEnumerator IEnumerable.GetEnumerator ()
+ {
+ return new DictionaryNodeEnumerator (this);
+ }
+
+ // ICollection Interface
+ public int Count {
+ get { return count; }
+ }
+
+ public bool IsSynchronized {
+ get { return false; }
+ }
+
+ public object SyncRoot {
+ get { return this; }
+ }
+
+ public void CopyTo (Array array, int index)
+ {
+ if (array == null)
+ throw new ArgumentNullException ("array", "Array cannot be null.");
+ if (index < 0)
+ throw new ArgumentOutOfRangeException ("index", "index is less than 0");
+ if (index > array.Length)
+ throw new IndexOutOfRangeException ("index is too large");
+ if (Count > array.Length - index)
+ throw new ArgumentException ("Not enough room in the array");
+
+ foreach (DictionaryEntry entry in this)
+ array.SetValue (entry, index++);
+ }
+
+ // IDictionary Interface
+ public bool IsFixedSize {
+ get { return false; }
+ }
+
+ public bool IsReadOnly {
+ get { return false; }
+ }
+
+ // Indexer
+ public object this [object key] {
+ get {
+ DictionaryNode entry = FindEntry (key);
+ return entry == null ? null : entry.value;
+ }
+
+ set {
+ DictionaryNode prev;
+ DictionaryNode entry = FindEntry (key, out prev);
+ if (entry != null)
+ entry.value = value;
+ else
+ AddImpl (key, value, prev);
+ }
+ }
+
+ public ICollection Keys {
+ get { return new DictionaryNodeCollection (this, true); }
+ }
+
+ public ICollection Values {
+ get { return new DictionaryNodeCollection (this, false); }
+ }
+
+ public void Add (object key, object value)
+ {
+ DictionaryNode prev;
+ DictionaryNode entry = FindEntry (key, out prev);
+ if (entry != null)
+ throw new ArgumentException ("key", "Duplicate key in add.");
+
+ AddImpl (key, value, prev);
+ }
+
+ public void Clear ()
+ {
+ head = null;
+ count = 0;
+ version++;
+ }
+
+ public bool Contains (object key)
+ {
+ return FindEntry (key) != null;
+ }
+
+ public IDictionaryEnumerator GetEnumerator ()
+ {
+ return new DictionaryNodeEnumerator (this);
+ }
+
+ public void Remove (object key)
+ {
+ DictionaryNode prev;
+ DictionaryNode entry = FindEntry (key, out prev);
+ if (entry == null)
+ return;
+ if (prev == null)
+ head = entry.next;
+ else
+ prev.next = entry.next;
+ entry.value = null;
+ count--;
+ version++;
+ }
+
+
+ [Serializable]
+ private class DictionaryNode {
+ public object key;
+ public object value;
+ public DictionaryNode next;
+ public DictionaryNode (object key, object value, DictionaryNode next)
+ {
+ this.key = key;
+ this.value = value;
+ this.next = next;
+ }
+ }
+
+ private class DictionaryNodeEnumerator : IEnumerator, IDictionaryEnumerator {
+ private ListDictionary dict;
+ private bool isAtStart;
+ private DictionaryNode current;
+ private int version;
+
+ public DictionaryNodeEnumerator (ListDictionary dict)
+ {
+ this.dict = dict;
+ version = dict.version;
+ Reset();
+ }
+
+ private void FailFast()
+ {
+ if (version != dict.version) {
+ throw new InvalidOperationException (
+ "The ListDictionary's contents changed after this enumerator was instantiated.");
+ }
+ }
+
+ public bool MoveNext ()
+ {
+ FailFast ();
+ if (current == null && !isAtStart)
+ return false;
+ current = isAtStart ? dict.head : current.next;
+ isAtStart = false;
+ return current != null;
+ }
+
+ public void Reset ()
+ {
+ FailFast ();
+ isAtStart = true;
+ current = null;
+ }
+
+ public object Current {
+ get { return Entry; }
+ }
+
+ private DictionaryNode DictionaryNode {
+ get {
+ FailFast ();
+ if (current == null)
+ throw new InvalidOperationException (
+ "Enumerator is positioned before the collection's first element or after the last element.");
+ return current;
+ }
+ }
+
+ // IDictionaryEnumerator
+ public DictionaryEntry Entry {
+ get {
+ object key = DictionaryNode.key;
+ return new DictionaryEntry (key, current.value);
+ }
+ }
+
+ public object Key {
+ get { return DictionaryNode.key; }
+ }
+
+ public object Value {
+ get { return DictionaryNode.value; }
+ }
+ }
+
+ private class DictionaryNodeCollection : ICollection {
+ private ListDictionary dict;
+ private bool isKeyList;
+
+ public DictionaryNodeCollection (ListDictionary dict, bool isKeyList)
+ {
+ this.dict = dict;
+ this.isKeyList = isKeyList;
+ }
+
+ // ICollection Interface
+ public int Count {
+ get { return dict.Count; }
+ }
+
+ public bool IsSynchronized {
+ get { return false; }
+ }
+
+ public object SyncRoot {
+ get { return dict.SyncRoot; }
+ }
+
+ public void CopyTo (Array array, int index)
+ {
+ if (array == null)
+ throw new ArgumentNullException ("array", "Array cannot be null.");
+ if (index < 0)
+ throw new ArgumentOutOfRangeException ("index", "index is less than 0");
+ if (index > array.Length)
+ throw new IndexOutOfRangeException ("index is too large");
+ if (Count > array.Length - index)
+ throw new ArgumentException ("Not enough room in the array");
+
+ foreach (object obj in this)
+ array.SetValue (obj, index++);
+ }
+
+ // IEnumerable Interface
+ public IEnumerator GetEnumerator()
+ {
+ return new DictionaryNodeCollectionEnumerator (dict.GetEnumerator (), isKeyList);
+ }
+
+ private class DictionaryNodeCollectionEnumerator : IEnumerator {
+ private IDictionaryEnumerator inner;
+ private bool isKeyList;
+
+ public DictionaryNodeCollectionEnumerator (IDictionaryEnumerator inner, bool isKeyList)
+ {
+ this.inner = inner;
+ this.isKeyList = isKeyList;
+ }
+
+ public object Current {
+ get { return isKeyList ? inner.Key : inner.Value; }
+ }
+
+ public bool MoveNext ()
+ {
+ return inner.MoveNext ();
+ }
+
+ public void Reset ()
+ {
+ inner.Reset ();
+ }
+ }
+ }
+ }
+}
projects / mono.git / blobdiff