The Labs \ Source Viewer \ SSCLI \ System.Collections.Specialized \ NodeEnumerator

  1. //------------------------------------------------------------------------------
  2. // <copyright file="ListDictionary.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. namespace System.Collections.Specialized
  16. {
  17.    
  18.     using System.Collections;
  19.     using Microsoft.Win32;
  20.    
  21.     /// <devdoc>
  22.     /// <para>
  23.     /// This is a simple implementation of IDictionary using a singly linked list. This
  24.     /// will be smaller and faster than a Hashtable if the number of elements is 10 or less.
  25.     /// This should not be used if performance is important for large numbers of elements.
  26.     /// </para>
  27.     /// </devdoc>
  28.     [Serializable()]
  29.     public class ListDictionary : IDictionary
  30.     {
  31.         DictionaryNode head;
  32.         int version;
  33.         int count;
  34.         IComparer comparer;
  35.         [NonSerialized()]
  36.         private object _syncRoot;
  37.        
  38.         /// <devdoc>
  39.         /// <para>[To be supplied.]</para>
  40.         /// </devdoc>
  41.         public ListDictionary()
  42.         {
  43.         }
  44.        
  45.         /// <devdoc>
  46.         /// <para>[To be supplied.]</para>
  47.         /// </devdoc>
  48.         public ListDictionary(IComparer comparer)
  49.         {
  50.             this.comparer = comparer;
  51.         }
  52.        
  53.         /// <devdoc>
  54.         /// <para>[To be supplied.]</para>
  55.         /// </devdoc>
  56.         public object this[object key]
  57.         {
  58.             get {
  59.                 if (key == null) {
  60.                     throw new ArgumentNullException("key", SR.GetString(SR.ArgumentNull_Key));
  61.                 }
  62.                 DictionaryNode node = head;
  63.                 if (comparer == null) {
  64.                     while (node != null) {
  65.                         object oldKey = node.key;
  66.                         if (oldKey != null && oldKey.Equals(key)) {
  67.                             return node.value;
  68.                         }
  69.                         node = node.next;
  70.                     }
  71.                 }
  72.                 else {
  73.                     while (node != null) {
  74.                         object oldKey = node.key;
  75.                         if (oldKey != null && comparer.Compare(oldKey, key) == 0) {
  76.                             return node.value;
  77.                         }
  78.                         node = node.next;
  79.                     }
  80.                 }
  81.                 return null;
  82.             }
  83.             set {
  84.                 if (key == null) {
  85.                     throw new ArgumentNullException("key", SR.GetString(SR.ArgumentNull_Key));
  86.                 }
  87.                 version++;
  88.                 DictionaryNode last = null;
  89.                 DictionaryNode node;
  90.                 for (node = head; node != null; node = node.next) {
  91.                     object oldKey = node.key;
  92.                     if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0) {
  93.                         break;
  94.                     }
  95.                     last = node;
  96.                 }
  97.                 if (node != null) {
  98.                     // Found it
  99.                     node.value = value;
  100.                     return;
  101.                 }
  102.                 // Not found, so add a new one
  103.                 DictionaryNode newNode = new DictionaryNode();
  104.                 newNode.key = key;
  105.                 newNode.value = value;
  106.                 if (last != null) {
  107.                     last.next = newNode;
  108.                 }
  109.                 else {
  110.                     head = newNode;
  111.                 }
  112.                 count++;
  113.             }
  114.         }
  115.        
  116.         /// <devdoc>
  117.         /// <para>[To be supplied.]</para>
  118.         /// </devdoc>
  119.         public int Count {
  120.             get { return count; }
  121.         }
  122.        
  123.         /// <devdoc>
  124.         /// <para>[To be supplied.]</para>
  125.         /// </devdoc>
  126.         public ICollection Keys {
  127.             get { return new NodeKeyValueCollection(this, true); }
  128.         }
  129.        
  130.         /// <devdoc>
  131.         /// <para>[To be supplied.]</para>
  132.         /// </devdoc>
  133.         public bool IsReadOnly {
  134.             get { return false; }
  135.         }
  136.        
  137.         /// <devdoc>
  138.         /// <para>[To be supplied.]</para>
  139.         /// </devdoc>
  140.         public bool IsFixedSize {
  141.             get { return false; }
  142.         }
  143.        
  144.         /// <devdoc>
  145.         /// <para>[To be supplied.]</para>
  146.         /// </devdoc>
  147.         public bool IsSynchronized {
  148.             get { return false; }
  149.         }
  150.        
  151.         /// <devdoc>
  152.         /// <para>[To be supplied.]</para>
  153.         /// </devdoc>
  154.         public object SyncRoot {
  155.             get {
  156.                 if (_syncRoot == null) {
  157.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  158.                 }
  159.                 return _syncRoot;
  160.             }
  161.         }
  162.        
  163.         /// <devdoc>
  164.         /// <para>[To be supplied.]</para>
  165.         /// </devdoc>
  166.         public ICollection Values {
  167.             get { return new NodeKeyValueCollection(this, false); }
  168.         }
  169.        
  170.         /// <devdoc>
  171.         /// <para>[To be supplied.]</para>
  172.         /// </devdoc>
  173.         public void Add(object key, object value)
  174.         {
  175.             if (key == null) {
  176.                 throw new ArgumentNullException("key", SR.GetString(SR.ArgumentNull_Key));
  177.             }
  178.             version++;
  179.             DictionaryNode last = null;
  180.             DictionaryNode node;
  181.             for (node = head; node != null; node = node.next) {
  182.                 object oldKey = node.key;
  183.                 if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0) {
  184.                     throw new ArgumentException(SR.GetString(SR.Argument_AddingDuplicate));
  185.                 }
  186.                 last = node;
  187.             }
  188.             // Not found, so add a new one
  189.             DictionaryNode newNode = new DictionaryNode();
  190.             newNode.key = key;
  191.             newNode.value = value;
  192.             if (last != null) {
  193.                 last.next = newNode;
  194.             }
  195.             else {
  196.                 head = newNode;
  197.             }
  198.             count++;
  199.         }
  200.        
  201.         /// <devdoc>
  202.         /// <para>[To be supplied.]</para>
  203.         /// </devdoc>
  204.         public void Clear()
  205.         {
  206.             count = 0;
  207.             head = null;
  208.             version++;
  209.         }
  210.        
  211.         /// <devdoc>
  212.         /// <para>[To be supplied.]</para>
  213.         /// </devdoc>
  214.         public bool Contains(object key)
  215.         {
  216.             if (key == null) {
  217.                 throw new ArgumentNullException("key", SR.GetString(SR.ArgumentNull_Key));
  218.             }
  219.             for (DictionaryNode node = head; node != null; node = node.next) {
  220.                 object oldKey = node.key;
  221.                 if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0) {
  222.                     return true;
  223.                 }
  224.             }
  225.             return false;
  226.         }
  227.        
  228.         /// <devdoc>
  229.         /// <para>[To be supplied.]</para>
  230.         /// </devdoc>
  231.         public void CopyTo(Array array, int index)
  232.         {
  233.             if (array == null)
  234.                 throw new ArgumentNullException("array");
  235.             if (index < 0)
  236.                 throw new ArgumentOutOfRangeException("index", SR.GetString(SR.ArgumentOutOfRange_NeedNonNegNum));
  237.            
  238.             if (array.Length - index < count)
  239.                 throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace));
  240.            
  241.             for (DictionaryNode node = head; node != null; node = node.next) {
  242.                 array.SetValue(new DictionaryEntry(node.key, node.value), index);
  243.                 index++;
  244.             }
  245.         }
  246.        
  247.         /// <devdoc>
  248.         /// <para>[To be supplied.]</para>
  249.         /// </devdoc>
  250.         public IDictionaryEnumerator GetEnumerator()
  251.         {
  252.             return new NodeEnumerator(this);
  253.         }
  254.        
  255.         IEnumerator IEnumerable.GetEnumerator()
  256.         {
  257.             return new NodeEnumerator(this);
  258.         }
  259.        
  260.         /// <devdoc>
  261.         /// <para>[To be supplied.]</para>
  262.         /// </devdoc>
  263.         public void Remove(object key)
  264.         {
  265.             if (key == null) {
  266.                 throw new ArgumentNullException("key", SR.GetString(SR.ArgumentNull_Key));
  267.             }
  268.             version++;
  269.             DictionaryNode last = null;
  270.             DictionaryNode node;
  271.             for (node = head; node != null; node = node.next) {
  272.                 object oldKey = node.key;
  273.                 if ((comparer == null) ? oldKey.Equals(key) : comparer.Compare(oldKey, key) == 0) {
  274.                     break;
  275.                 }
  276.                 last = node;
  277.             }
  278.             if (node == null) {
  279.                 return;
  280.             }
  281.             if (node == head) {
  282.                 head = node.next;
  283.             }
  284.             else {
  285.                 last.next = node.next;
  286.             }
  287.             count--;
  288.         }
  289.        
  290.         private class NodeEnumerator : IDictionaryEnumerator
  291.         {
  292.             ListDictionary list;
  293.             DictionaryNode current;
  294.             int version;
  295.             bool start;
  296.            
  297.            
  298.             public NodeEnumerator(ListDictionary list)
  299.             {
  300.                 this.list = list;
  301.                 version = list.version;
  302.                 start = true;
  303.                 current = null;
  304.             }
  305.            
  306.             public object Current {
  307.                 get { return Entry; }
  308.             }
  309.            
  310.             public DictionaryEntry Entry {
  311.                 get {
  312.                     if (current == null) {
  313.                         throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumOpCantHappen));
  314.                     }
  315.                     return new DictionaryEntry(current.key, current.value);
  316.                 }
  317.             }
  318.            
  319.             public object Key {
  320.                 get {
  321.                     if (current == null) {
  322.                         throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumOpCantHappen));
  323.                     }
  324.                     return current.key;
  325.                 }
  326.             }
  327.            
  328.             public object Value {
  329.                 get {
  330.                     if (current == null) {
  331.                         throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumOpCantHappen));
  332.                     }
  333.                     return current.value;
  334.                 }
  335.             }
  336.            
  337.             public bool MoveNext()
  338.             {
  339.                 if (version != list.version) {
  340.                     throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
  341.                 }
  342.                 if (start) {
  343.                     current = list.head;
  344.                     start = false;
  345.                 }
  346.                 else if (current != null) {
  347.                     current = current.next;
  348.                 }
  349.                 return (current != null);
  350.             }
  351.            
  352.             public void Reset()
  353.             {
  354.                 if (version != list.version) {
  355.                     throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
  356.                 }
  357.                 start = true;
  358.                 current = null;
  359.             }
  360.            
  361.         }
  362.        
  363.        
  364.         private class NodeKeyValueCollection : ICollection
  365.         {
  366.             ListDictionary list;
  367.             bool isKeys;
  368.            
  369.             public NodeKeyValueCollection(ListDictionary list, bool isKeys)
  370.             {
  371.                 this.list = list;
  372.                 this.isKeys = isKeys;
  373.             }
  374.            
  375.             void ICollection.CopyTo(Array array, int index)
  376.             {
  377.                 if (array == null)
  378.                     throw new ArgumentNullException("array");
  379.                 if (index < 0)
  380.                     throw new ArgumentOutOfRangeException("index", SR.GetString(SR.ArgumentOutOfRange_NeedNonNegNum));
  381.                 for (DictionaryNode node = list.head; node != null; node = node.next) {
  382.                     array.SetValue(isKeys ? node.key : node.value, index);
  383.                     index++;
  384.                 }
  385.             }
  386.            
  387.             int ICollection.Count {
  388.                 get {
  389.                     int count = 0;
  390.                     for (DictionaryNode node = list.head; node != null; node = node.next) {
  391.                         count++;
  392.                     }
  393.                     return count;
  394.                 }
  395.             }
  396.            
  397.             bool ICollection.IsSynchronized {
  398.                 get { return false; }
  399.             }
  400.            
  401.             object ICollection.SyncRoot {
  402.                 get { return list.SyncRoot; }
  403.             }
  404.            
  405.             IEnumerator IEnumerable.GetEnumerator()
  406.             {
  407.                 return new NodeKeyValueEnumerator(list, isKeys);
  408.             }
  409.            
  410.            
  411.             private class NodeKeyValueEnumerator : IEnumerator
  412.             {
  413.                 ListDictionary list;
  414.                 DictionaryNode current;
  415.                 int version;
  416.                 bool isKeys;
  417.                 bool start;
  418.                
  419.                 public NodeKeyValueEnumerator(ListDictionary list, bool isKeys)
  420.                 {
  421.                     this.list = list;
  422.                     this.isKeys = isKeys;
  423.                     this.version = list.version;
  424.                     this.start = true;
  425.                     this.current = null;
  426.                 }
  427.                
  428.                 public object Current {
  429.                     get {
  430.                         if (current == null) {
  431.                             throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumOpCantHappen));
  432.                         }
  433.                         return isKeys ? current.key : current.value;
  434.                     }
  435.                 }
  436.                
  437.                 public bool MoveNext()
  438.                 {
  439.                     if (version != list.version) {
  440.                         throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
  441.                     }
  442.                     if (start) {
  443.                         current = list.head;
  444.                         start = false;
  445.                     }
  446.                     else {
  447.                         current = current.next;
  448.                     }
  449.                     return (current != null);
  450.                 }
  451.                
  452.                 public void Reset()
  453.                 {
  454.                     if (version != list.version) {
  455.                         throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
  456.                     }
  457.                     start = true;
  458.                     current = null;
  459.                 }
  460.             }
  461.         }
  462.        
  463.         [Serializable()]
  464.         private class DictionaryNode
  465.         {
  466.             public object key;
  467.             public object value;
  468.             public DictionaryNode next;
  469.         }
  470.     }
  471. }

Developer Fusion