/* https://github.com/mbuchetics/RangeTree よりコピペ。このファイルのみMITライセンスに従います */
using System;
using System.Collections.Generic;
using System.Linq;
namespace FooEditEngine
{
///
/// Range tree interface.
///
/// The type of the range.
/// The type of the data items.
interface IRangeTree
where TKey : IComparable
where T : IRangeProvider
{
IEnumerable Items { get; }
int Count { get; }
List Query(TKey value);
List Query(Range range);
void Rebuild();
void Add(T item);
void Add(IEnumerable items);
void Remove(T item);
void Remove(IEnumerable items);
void Clear();
}
///
/// The standard range tree implementation. Keeps a root node and
/// forwards all queries to it.
/// Whenenver new items are added or items are removed, the tree
/// goes "out of sync" and is rebuild when it's queried next.
///
/// The type of the range.
/// The type of the data items.
sealed class RangeTree : IRangeTree
where TKey : IComparable
where T : IRangeProvider
{
private RangeTreeNode _root;
private List _items;
private bool _isInSync;
private bool _autoRebuild;
private IComparer _rangeComparer;
///
/// Whether the tree is currently in sync or not. If it is "out of sync"
/// you can either rebuild it manually (call Rebuild) or let it rebuild
/// automatically when you query it next.
///
public bool IsInSync
{
get { return _isInSync; }
}
///
/// All items of the tree.
///
public IEnumerable Items
{
get { return _items; }
}
///
/// Count of all items.
///
public int Count
{
get { return _items.Count; }
}
///
/// Whether the tree should be rebuild automatically. Defaults to true.
///
public bool AutoRebuild
{
get { return _autoRebuild; }
set { _autoRebuild = value; }
}
///
/// Initializes an empty tree.
///
public RangeTree(IComparer rangeComparer)
{
_rangeComparer = rangeComparer;
_root = new RangeTreeNode(rangeComparer);
_items = new List();
_isInSync = true;
_autoRebuild = true;
}
///
/// Initializes a tree with a list of items to be added.
///
public RangeTree(IEnumerable items, IComparer rangeComparer)
{
_rangeComparer = rangeComparer;
_root = new RangeTreeNode(items, rangeComparer);
_items = items.ToList();
_isInSync = true;
_autoRebuild = true;
}
///
/// Performans a "stab" query with a single value.
/// All items with overlapping ranges are returned.
///
public List Query(TKey value)
{
if (!_isInSync && _autoRebuild)
Rebuild();
return _root.Query(value);
}
///
/// Performans a range query.
/// All items with overlapping ranges are returned.
///
public List Query(Range range)
{
if (!_isInSync && _autoRebuild)
Rebuild();
return _root.Query(range);
}
///
/// Rebuilds the tree if it is out of sync.
///
public void Rebuild()
{
if (_isInSync)
return;
_root = new RangeTreeNode(_items, _rangeComparer);
_isInSync = true;
}
///
/// Adds the specified item. Tree will go out of sync.
///
public void Add(T item)
{
_isInSync = false;
_items.Add(item);
}
///
/// Adds the specified items. Tree will go out of sync.
///
public void Add(IEnumerable items)
{
_isInSync = false;
_items.AddRange(items);
}
///
/// Removes the specified item. Tree will go out of sync.
///
public void Remove(T item)
{
_isInSync = false;
_items.Remove(item);
}
///
/// Removes the specified items. Tree will go out of sync.
///
public void Remove(IEnumerable items)
{
_isInSync = false;
foreach (var item in items)
_items.Remove(item);
}
///
/// Clears the tree (removes all items).
///
public void Clear()
{
_root = new RangeTreeNode(_rangeComparer);
_items = new List();
_isInSync = true;
}
}
}