tomlev

C# Trie

Aug 2nd, 2011
164
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5.  
  6. namespace MyCollections
  7. {
  8.     public class Trie<TValue> : IDictionary<string, TValue>
  9.     {
  10.         private int _count;
  11.         private readonly TrieNode _rootNode;
  12.  
  13.         public Trie()
  14.         {
  15.             _rootNode = new TrieNode('\0', null);
  16.         }
  17.  
  18.         #region Core implementation
  19.  
  20.         private IEnumerable<KeyValuePair<string, TValue>> Enumerate(TrieNode root, string prefix)
  21.         {
  22.             string key;
  23.             if (root == _rootNode)
  24.                 key = prefix + string.Empty;
  25.             else
  26.                 key = prefix + root.PartialKey;
  27.  
  28.             if (root.HasValue)
  29.                 yield return new KeyValuePair<string, TValue>(key, root.Value);
  30.            
  31.             foreach (var child in root.Children)
  32.             {
  33.                 foreach (var kvp in Enumerate(child, key))
  34.                 {
  35.                     yield return kvp;
  36.                 }
  37.             }
  38.         }
  39.  
  40.         private static TrieNode FindNode(TrieNode root, char[] key, int depth, bool create, out bool created)
  41.         {
  42.             created = false;
  43.  
  44.             if (depth == key.Length)
  45.                 return root;
  46.  
  47.             foreach (var child in root.Children)
  48.             {
  49.                 if (child.PartialKey == key[depth])
  50.                     return FindNode(child, key, depth + 1, create, out created);
  51.             }
  52.  
  53.             if (create)
  54.             {
  55.                 var current = root;
  56.                 TrieNode node = null;
  57.                 for (int i = depth; i < key.Length; i++)
  58.                 {
  59.                     node = new TrieNode(key[i], current);
  60.                     current.Children.Add(node);
  61.                     current = node;
  62.                 }
  63.                 created = true;
  64.                 return node;
  65.             }
  66.  
  67.             return null;
  68.         }
  69.  
  70.         private TrieNode FindNode(string key, bool create, out bool created)
  71.         {
  72.             return FindNode(_rootNode, key.ToCharArray(), 0, create, out created);
  73.         }
  74.  
  75.         private TrieNode FindNode(string key, bool create)
  76.         {
  77.             bool created;
  78.             return FindNode(_rootNode, key.ToCharArray(), 0, create, out created);
  79.         }
  80.  
  81.         private static void Prune(TrieNode removedNode)
  82.         {
  83.             var current = removedNode;
  84.             while (current != null)
  85.             {
  86.                 if (current.Children.Any() || current.HasValue)
  87.                     break;
  88.                 if (current.Parent != null)
  89.                 {
  90.                     current.Parent.Children.Remove(current);
  91.                 }
  92.                 current = current.Parent;
  93.             }
  94.         }
  95.  
  96.         class TrieNode
  97.         {
  98.             private readonly char _partialKey;
  99.             private TValue _value;
  100.             private bool _hasValue;
  101.             private readonly TrieNode _parent;
  102.             private readonly List<TrieNode> _children;
  103.  
  104.             public TrieNode(char partialKey, TrieNode parent)
  105.             {
  106.                 _partialKey = partialKey;
  107.                 _parent = parent;
  108.                 _children = new List<TrieNode>();
  109.             }
  110.  
  111.             public TrieNode Parent
  112.             {
  113.                 get { return _parent; }
  114.             }
  115.  
  116.             public char PartialKey
  117.             {
  118.                 get { return _partialKey; }
  119.             }
  120.  
  121.             public bool HasValue
  122.             {
  123.                 get { return _hasValue; }
  124.             }
  125.  
  126.             public TValue Value
  127.             {
  128.                 get { return _value; }
  129.                 set
  130.                 {
  131.                     _value = value;
  132.                     _hasValue = true;
  133.                 }
  134.             }
  135.  
  136.             public void ClearValue()
  137.             {
  138.                 _hasValue = false;
  139.             }
  140.  
  141.             public ICollection<TrieNode> Children
  142.             {
  143.                 get { return _children; }
  144.             }
  145.         }
  146.  
  147.         #endregion
  148.  
  149.         #region IDictionary<string, TValue> implementation
  150.  
  151.         public IEnumerator<KeyValuePair<string, TValue>> GetEnumerator()
  152.         {
  153.             return Enumerate(_rootNode, null).GetEnumerator();
  154.         }
  155.  
  156.         IEnumerator IEnumerable.GetEnumerator()
  157.         {
  158.             return GetEnumerator();
  159.         }
  160.  
  161.         void ICollection<KeyValuePair<string, TValue>>.Add(KeyValuePair<string, TValue> item)
  162.         {
  163.             Add(item.Key, item.Value);
  164.         }
  165.  
  166.         public void Clear()
  167.         {
  168.             _rootNode.ClearValue();
  169.             _rootNode.Children.Clear();
  170.         }
  171.  
  172.         bool ICollection<KeyValuePair<string, TValue>>.Contains(KeyValuePair<string, TValue> item)
  173.         {
  174.             TValue value;
  175.             if (TryGetValue(item.Key, out value))
  176.                 return Equals(value, item.Value);
  177.             return false;
  178.         }
  179.  
  180.         void ICollection<KeyValuePair<string, TValue>>.CopyTo(KeyValuePair<string, TValue>[] array, int arrayIndex)
  181.         {
  182.             if (_count + arrayIndex > array.Length)
  183.                 throw new ArgumentException("The destination array is not large enough");
  184.             int index = arrayIndex;
  185.             foreach (var item in Enumerate(_rootNode, null))
  186.             {
  187.                 array[index] = item;
  188.                 index++;
  189.             }
  190.         }
  191.  
  192.         bool ICollection<KeyValuePair<string, TValue>>.Remove(KeyValuePair<string, TValue> item)
  193.         {
  194.             var node = FindNode(item.Key, false);
  195.             if (node == null)
  196.                 return false;
  197.             if (node.HasValue && Equals(node.Value, item.Value))
  198.             {
  199.                 node.ClearValue();
  200.                 _count--;
  201.                 return true;
  202.             }
  203.             return false;
  204.         }
  205.  
  206.         public int Count
  207.         {
  208.             get { return _count; }
  209.         }
  210.  
  211.         public bool IsReadOnly
  212.         {
  213.             get { return false; }
  214.         }
  215.  
  216.         public bool ContainsKey(string key)
  217.         {
  218.             var node = FindNode(key, false);
  219.             if (node != null)
  220.                 return node.HasValue;
  221.             return false;
  222.         }
  223.  
  224.         public void Add(string key, TValue value)
  225.         {
  226.             var node = FindNode(key, true);
  227.             if (node.HasValue)
  228.                 throw new ArgumentException("An element with the same key already exists in the trie.");
  229.             node.Value = value;
  230.             _count++;
  231.         }
  232.  
  233.         public bool Remove(string key)
  234.         {
  235.             var node = FindNode(key, false);
  236.             if (node == null)
  237.                 return false;
  238.            
  239.             if (node.HasValue)
  240.             {
  241.                 node.ClearValue();
  242.                 Prune(node);
  243.                 _count--;
  244.             }
  245.             return false;
  246.         }
  247.  
  248.         public bool TryGetValue(string key, out TValue value)
  249.         {
  250.             value = default(TValue);
  251.             var node = FindNode(key, false);
  252.             if (node == null)
  253.                 return false;
  254.             if (node.HasValue)
  255.             {
  256.                 value = node.Value;
  257.                 return true;
  258.             }
  259.             return false;
  260.         }
  261.  
  262.         public TValue this[string key]
  263.         {
  264.             get
  265.             {
  266.                 TValue value;
  267.                 if (TryGetValue(key, out value))
  268.                     return value;
  269.                 throw new KeyNotFoundException();
  270.             }
  271.             set
  272.             {
  273.                 bool created;
  274.                 var node = FindNode(key, true, out created);
  275.                 node.Value = value;
  276.                 if (created)
  277.                     _count++;
  278.             }
  279.         }
  280.  
  281.         public ICollection<string> Keys
  282.         {
  283.             get { return Enumerate(_rootNode, null).Select(kvp => kvp.Key).ToList(); }
  284.         }
  285.  
  286.         public ICollection<TValue> Values
  287.         {
  288.             get { return Enumerate(_rootNode, null).Select(kvp => kvp.Value).ToList(); }
  289.         }
  290.  
  291.         #endregion
  292.  
  293.         #region Public trie-specific methods
  294.  
  295.         public bool ContainsPrefix(string prefix)
  296.         {
  297.             var node = FindNode(prefix, false);
  298.             return (node.HasValue || node.Children.Any());
  299.         }
  300.  
  301.         public bool RemovePrefix(string prefix)
  302.         {
  303.             var node = FindNode(prefix, false);
  304.             if (node == null)
  305.                 return false;
  306.  
  307.             int count = Enumerate(node, null).Count();
  308.             if (count == 0)
  309.                 return false;
  310.  
  311.             node.Children.Clear();
  312.             node.ClearValue();
  313.             Prune(node);
  314.             _count -= count;
  315.  
  316.             return true;
  317.         }
  318.  
  319.         public IEnumerable<KeyValuePair<string, TValue>> FindPrefix(string prefix)
  320.         {
  321.             var node = FindNode(prefix, false);
  322.             if (node == null)
  323.                 yield break;
  324.  
  325.             string prefix2 = null;
  326.             if (prefix.Length > 0)
  327.                 prefix2 = prefix.Substring(0, prefix.Length - 1);
  328.             foreach (var kvp in Enumerate(node, prefix2))
  329.             {
  330.                 yield return kvp;
  331.             }
  332.         }
  333.  
  334.         #endregion
  335.     }
  336. }
RAW Paste Data