1 /* https://github.com/mbuchetics/RangeTree よりコピペ。このファイルのみMITライセンスに従います */
3 using System.Collections.Generic;
6 namespace FooEditEngine
9 /// Range tree interface.
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>
17 IEnumerable<T> Items { get; }
20 List<T> Query(TKey value);
21 List<T> Query(Range<TKey> range);
25 void Add(IEnumerable<T> items);
27 void Remove(IEnumerable<T> items);
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.
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>
43 private RangeTreeNode<TKey, T> _root;
44 private List<T> _items;
45 private bool _isInSync;
46 private bool _autoRebuild;
47 private IComparer<T> _rangeComparer;
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.
56 get { return _isInSync; }
60 /// All items of the tree.
62 public IEnumerable<T> Items
64 get { return _items; }
68 /// Count of all items.
72 get { return _items.Count; }
76 /// Whether the tree should be rebuild automatically. Defaults to true.
78 public bool AutoRebuild
80 get { return _autoRebuild; }
81 set { _autoRebuild = value; }
85 /// Initializes an empty tree.
87 public RangeTree(IComparer<T> rangeComparer)
89 _rangeComparer = rangeComparer;
90 _root = new RangeTreeNode<TKey, T>(rangeComparer);
91 _items = new List<T>();
98 /// Initializes a tree with a list of items to be added.
100 public RangeTree(IEnumerable<T> items, IComparer<T> rangeComparer)
102 _rangeComparer = rangeComparer;
103 _root = new RangeTreeNode<TKey, T>(items, rangeComparer);
104 _items = items.ToList();
110 /// Performans a "stab" query with a single value.
111 /// All items with overlapping ranges are returned.
113 public List<T> Query(TKey value)
115 if (!_isInSync && _autoRebuild)
118 return _root.Query(value);
122 /// Performans a range query.
123 /// All items with overlapping ranges are returned.
125 public List<T> Query(Range<TKey> range)
127 if (!_isInSync && _autoRebuild)
130 return _root.Query(range);
134 /// Rebuilds the tree if it is out of sync.
136 public void Rebuild()
141 _root = new RangeTreeNode<TKey, T>(_items, _rangeComparer);
146 /// Adds the specified item. Tree will go out of sync.
148 public void Add(T item)
155 /// Adds the specified items. Tree will go out of sync.
157 public void Add(IEnumerable<T> items)
160 _items.AddRange(items);
164 /// Removes the specified item. Tree will go out of sync.
166 public void Remove(T item)
173 /// Removes the specified items. Tree will go out of sync.
175 public void Remove(IEnumerable<T> items)
179 foreach (var item in items)
184 /// Clears the tree (removes all items).
188 _root = new RangeTreeNode<TKey, T>(_rangeComparer);
189 _items = new List<T>();