Common/RangeTree.cs

   1 /* https://github.com/mbuchetics/RangeTree よりコピペ。このファイルのみMITライセンスに従います */
   2 using System;
   3 using System.Collections.Generic;
   4 using System.Linq;
   5
   6 namespace FooEditEngine
   7 {
   8     /// <summary>
   9     /// Range tree interface.
  10     /// </summary>
  11     /// <typeparam name="TKey">The type of the range.</typeparam>
  12     /// <typeparam name="T">The type of the data items.</typeparam>
  13     interface IRangeTree<TKey, T>
  14         where TKey : IComparable<TKey>
  15         where T : IRangeProvider<TKey>
  16     {
  17         IEnumerable<T> Items { get; }
  18         int Count { get; }
  19
  20         List<T> Query(TKey value);
  21         List<T> Query(Range<TKey> range);
  22
  23         void Rebuild();
  24         void Add(T item);
  25         void Add(IEnumerable<T> items);
  26         void Remove(T item);
  27         void Remove(IEnumerable<T> items);
  28         void Clear();
  29     }
  30
  31     /// <summary>
  32     /// The standard range tree implementation. Keeps a root node and
  33     /// forwards all queries to it.
  34     /// Whenenver new items are added or items are removed, the tree
  35     /// goes "out of sync" and is rebuild when it's queried next.
  36     /// </summary>
  37     /// <typeparam name="TKey">The type of the range.</typeparam>
  38     /// <typeparam name="T">The type of the data items.</typeparam>
  39     sealed class RangeTree<TKey, T> : IRangeTree<TKey, T>
  40         where TKey : IComparable<TKey>
  41         where T : IRangeProvider<TKey>
  42     {
  43         private RangeTreeNode<TKey, T> _root;
  44         private List<T> _items;
  45         private bool _isInSync;
  46         private bool _autoRebuild;
  47         private IComparer<T> _rangeComparer;
  48
  49         /// <summary>
  50         /// Whether the tree is currently in sync or not. If it is "out of sync"
  51         /// you can either rebuild it manually (call Rebuild) or let it rebuild
  52         /// automatically when you query it next.
  53         /// </summary>
  54         public bool IsInSync
  55         {
  56             get { return _isInSync; }
  57         }
  58
  59         /// <summary>
  60         /// All items of the tree.
  61         /// </summary>
  62         public IEnumerable<T> Items
  63         {
  64             get { return _items; }
  65         }
  66
  67         /// <summary>
  68         /// Count of all items.
  69         /// </summary>
  70         public int Count
  71         {
  72             get { return _items.Count; }
  73         }
  74
  75         /// <summary>
  76         /// Whether the tree should be rebuild automatically. Defaults to true.
  77         /// </summary>
  78         public bool AutoRebuild
  79         {
  80             get { return _autoRebuild; }
  81             set { _autoRebuild = value; }
  82         }
  83
  84         /// <summary>
  85         /// Initializes an empty tree.
  86         /// </summary>
  87         public RangeTree(IComparer<T> rangeComparer)
  88         {
  89             _rangeComparer = rangeComparer;
  90             _root = new RangeTreeNode<TKey, T>(rangeComparer);
  91             _items = new List<T>();
  92             _isInSync = true;
  93             _autoRebuild = true;
  94
  95         }
  96
  97         /// <summary>
  98         /// Initializes a tree with a list of items to be added.
  99         /// </summary>
 100         public RangeTree(IEnumerable<T> items, IComparer<T> rangeComparer)
 101         {
 102             _rangeComparer = rangeComparer;
 103             _root = new RangeTreeNode<TKey, T>(items, rangeComparer);
 104             _items = items.ToList();
 105             _isInSync = true;
 106             _autoRebuild = true;
 107         }
 108
 109         /// <summary>
 110         /// Performans a "stab" query with a single value.
 111         /// All items with overlapping ranges are returned.
 112         /// </summary>
 113         public List<T> Query(TKey value)
 114         {
 115             if (!_isInSync && _autoRebuild)
 116                 Rebuild();
 117
 118             return _root.Query(value);
 119         }
 120
 121         /// <summary>
 122         /// Performans a range query.
 123         /// All items with overlapping ranges are returned.
 124         /// </summary>
 125         public List<T> Query(Range<TKey> range)
 126         {
 127             if (!_isInSync && _autoRebuild)
 128                 Rebuild();
 129
 130             return _root.Query(range);
 131         }
 132
 133         /// <summary>
 134         /// Rebuilds the tree if it is out of sync.
 135         /// </summary>
 136         public void Rebuild()
 137         {
 138             if (_isInSync)
 139                 return;
 140
 141             _root = new RangeTreeNode<TKey, T>(_items, _rangeComparer);
 142             _isInSync = true;
 143         }
 144
 145         /// <summary>
 146         /// Adds the specified item. Tree will go out of sync.
 147         /// </summary>
 148         public void Add(T item)
 149         {
 150             _isInSync = false;
 151             _items.Add(item);
 152         }
 153
 154         /// <summary>
 155         /// Adds the specified items. Tree will go out of sync.
 156         /// </summary>
 157         public void Add(IEnumerable<T> items)
 158         {
 159             _isInSync = false;
 160             _items.AddRange(items);
 161         }
 162
 163         /// <summary>
 164         /// Removes the specified item. Tree will go out of sync.
 165         /// </summary>
 166         public void Remove(T item)
 167         {
 168             _isInSync = false;
 169             _items.Remove(item);
 170         }
 171
 172         /// <summary>
 173         /// Removes the specified items. Tree will go out of sync.
 174         /// </summary>
 175         public void Remove(IEnumerable<T> items)
 176         {
 177             _isInSync = false;
 178
 179             foreach (var item in items)
 180                 _items.Remove(item);
 181         }
 182
 183         /// <summary>
 184         /// Clears the tree (removes all items).
 185         /// </summary>
 186         public void Clear()
 187         {
 188             _root = new RangeTreeNode<TKey, T>(_rangeComparer);
 189             _items = new List<T>();
 190             _isInSync = true;
 191         }
 192     }
 193
 194
 195 }