LinkedSet.cs 1.8 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
  1. using System;
  2. using System.Collections.Generic;
  3. namespace cakeslice
  4. {
  5. /// <summary>
  6. /// A collection with the fast iteration time of a List and the no-duplicates and fast Remove/Contains time of a HashSet.
  7. /// </summary>
  8. public class LinkedSet<T> : IEnumerable<T>
  9. {
  10. private LinkedList<T> list;
  11. private Dictionary<T, LinkedListNode<T>> dictionary;
  12. public LinkedSet()
  13. {
  14. list = new LinkedList<T>();
  15. dictionary = new Dictionary<T, LinkedListNode<T>>();
  16. }
  17. public LinkedSet(IEqualityComparer<T> comparer)
  18. {
  19. list = new LinkedList<T>();
  20. dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
  21. }
  22. /// <summary>
  23. /// returns true if the item did not already exist in the LinkedSet
  24. /// </summary>
  25. public bool Add(T t)
  26. {
  27. if (dictionary.ContainsKey(t))
  28. return false;
  29. LinkedListNode<T> node = list.AddLast(t);
  30. dictionary.Add(t, node);
  31. return true;
  32. }
  33. /// <summary>
  34. /// returns true if the item did previously exist in the LinkedSet
  35. /// </summary>
  36. public bool Remove(T t)
  37. {
  38. LinkedListNode<T> node;
  39. if (dictionary.TryGetValue(t, out node))
  40. {
  41. dictionary.Remove(t);
  42. list.Remove(node);
  43. return true;
  44. }
  45. else
  46. {
  47. return false;
  48. }
  49. }
  50. public void Clear()
  51. {
  52. list.Clear();
  53. dictionary.Clear();
  54. }
  55. public bool Contains(T t)
  56. => dictionary.ContainsKey(t);
  57. public int Count
  58. => list.Count;
  59. public IEnumerator<T> GetEnumerator()
  60. => list.GetEnumerator();
  61. System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  62. => list.GetEnumerator();
  63. }
  64. }