Core/RangeTreeNode.cs

   1 /* https://github.com/mbuchetics/RangeTree よりコピペ。このファイルのみMITライセンスに従います */
   2 using System;
   3 using System.Collections.Generic;
   4
   5 namespace FooEditEngine
   6 {
   7     /// <summary>
   8     /// A node of the range tree. Given a list of items, it builds
   9     /// its subtree. Also contains methods to query the subtree.
  10     /// Basically, all interval tree logic is here.
  11     /// </summary>
  12     sealed class RangeTreeNode<TKey, T>
  13         where TKey : IComparable<TKey>
  14         where T : IRangeProvider<TKey>
  15     {
  16         private TKey _center;
  17         private RangeTreeNode<TKey, T> _leftNode;
  18         private RangeTreeNode<TKey, T> _rightNode;
  19         private List<T> _items;
  20
  21         private static IComparer<T> s_rangeComparer;
  22
  23         /// <summary>
  24         /// Initializes an empty node.
  25         /// </summary>
  26         /// <param name="rangeComparer">The comparer used to compare two items.</param>
  27         public RangeTreeNode(IComparer<T> rangeComparer = null)
  28         {
  29             if (rangeComparer != null)
  30                 s_rangeComparer = rangeComparer;
  31
  32             _center = default(TKey);
  33             _leftNode = null;
  34             _rightNode = null;
  35             _items = null;
  36         }
  37
  38         /// <summary>
  39         /// Initializes a node with a list of items, builds the sub tree.
  40         /// </summary>
  41         /// <param name="items">The itme is added</param>
  42         /// <param name="rangeComparer">The comparer used to compare two items.</param>
  43         public RangeTreeNode(IEnumerable<T> items, IComparer<T> rangeComparer = null)
  44         {
  45             if (rangeComparer != null)
  46                 s_rangeComparer = rangeComparer;
  47
  48             // first, find the median
  49             var endPoints = new List<TKey>();
  50             foreach (var o in items)
  51             {
  52                 var range = o.Range;
  53                 endPoints.Add(range.From);
  54                 endPoints.Add(range.To);
  55             }
  56             endPoints.Sort();
  57
  58             // the median is used as center value
  59             _center = endPoints[endPoints.Count / 2];
  60             _items = new List<T>();
  61
  62             var left = new List<T>();
  63             var right = new List<T>();
  64
  65             // iterate over all items
  66             // if the range of an item is completely left of the center, add it to the left items
  67             // if it is on the right of the center, add it to the right items
  68             // otherwise (range overlaps the center), add the item to this node's items
  69             foreach (var o in items)
  70             {
  71                 var range = o.Range;
  72
  73                 if (range.To.CompareTo(_center) < 0)
  74                     left.Add(o);
  75                 else if (range.From.CompareTo(_center) > 0)
  76                     right.Add(o);
  77                 else
  78                     _items.Add(o);
  79             }
  80
  81             // sort the items, this way the query is faster later on
  82             if (_items.Count > 0)
  83                 _items.Sort(s_rangeComparer);
  84             else
  85                 _items = null;
  86
  87             // create left and right nodes, if there are any items
  88             if (left.Count > 0)
  89                 _leftNode = new RangeTreeNode<TKey, T>(left);
  90             if (right.Count > 0)
  91                 _rightNode = new RangeTreeNode<TKey, T>(right);
  92         }
  93
  94         /// <summary>
  95         /// Performans a "stab" query with a single value.
  96         /// All items with overlapping ranges are returned.
  97         /// </summary>
  98         public List<T> Query(TKey value)
  99         {
 100             var results = new List<T>();
 101
 102             // If the node has items, check their ranges.
 103             if (_items != null)
 104             {
 105                 foreach (var o in _items)
 106                 {
 107                     if (o.Range.From.CompareTo(value) > 0)
 108                         break;
 109                     else if (o.Range.Contains(value))
 110                         results.Add(o);
 111                 }
 112             }
 113
 114             // go to the left or go to the right of the tree, depending
 115             // where the query value lies compared to the center
 116             if (value.CompareTo(_center) < 0 && _leftNode != null)
 117                 results.AddRange(_leftNode.Query(value));
 118             else if (value.CompareTo(_center) > 0 && _rightNode != null)
 119                 results.AddRange(_rightNode.Query(value));
 120
 121             return results;
 122         }
 123
 124         /// <summary>
 125         /// Performans a range query.
 126         /// All items with overlapping ranges are returned.
 127         /// </summary>
 128         public List<T> Query(Range<TKey> range)
 129         {
 130             var results = new List<T>();
 131
 132             // If the node has items, check their ranges.
 133             if (_items != null)
 134             {
 135                 foreach (var o in _items)
 136                 {
 137                     if (o.Range.From.CompareTo(range.To) > 0)
 138                         break;
 139                     else if (o.Range.Intersects(range))
 140                         results.Add(o);
 141                 }
 142             }
 143
 144             // go to the left or go to the right of the tree, depending
 145             // where the query value lies compared to the center
 146             if (range.From.CompareTo(_center) < 0 && _leftNode != null)
 147                 results.AddRange(_leftNode.Query(range));
 148             if (range.To.CompareTo(_center) > 0 && _rightNode != null)
 149                 results.AddRange(_rightNode.Query(range));
 150
 151             return results;
 152         }
 153     }
 154 }