Core/RangeCollection.cs

   1 /* https://github.com/mbuchetics/RangeTree よりコピペ。このファイルのみMITライセンスに従います */
   2 using System;
   3 using System.Collections.Generic;
   4 using System.Linq;
   5 using System.Text;
   6 using System.Threading.Tasks;
   7
   8 namespace FooEditEngine
   9 {
  10     /// <summary>
  11     /// マーカーを表す
  12     /// </summary>
  13     internal interface IRange
  14     {
  15         /// <summary>
  16         /// マーカーの開始位置。-1を設定した場合、そのマーカーはレタリングされません
  17         /// </summary>
  18         int start { get; set; }
  19         /// <summary>
  20         /// マーカーの長さ。0を設定した場合、そのマーカーはレタリングされません
  21         /// </summary>
  22         int length { get; set; }
  23     }
  24
  25     internal sealed class RangeCollection<T> : IEnumerable<T>
  26         where T : IRange
  27     {
  28         List<T> collection;
  29
  30         public RangeCollection()
  31             : this(null)
  32         {
  33         }
  34
  35         public RangeCollection(IEnumerable<T> collection)
  36         {
  37             if (collection == null)
  38                 this.collection = new List<T>();
  39             else
  40                 this.collection = new List<T>(collection);
  41         }
  42
  43         public T this[int i]
  44         {
  45             get
  46             {
  47                 return this.collection[i];
  48             }
  49             set
  50             {
  51                 this.collection[i] = value;
  52             }
  53         }
  54
  55         public int Count
  56         {
  57             get
  58             {
  59                 return this.collection.Count;
  60             }
  61         }
  62
  63         public void Add(T item)
  64         {
  65             this.collection.Add(item);
  66             for (int i = this.collection.Count - 1; i >= 0; i--)
  67             {
  68                 if (i > 0 && this.collection[i].start < this.collection[i - 1].start)
  69                 {
  70                     T temp = this.collection[i];
  71                     this.collection[i] = this.collection[i - 1];
  72                     this.collection[i - 1] = temp;
  73                 }
  74                 else
  75                 {
  76                     break;
  77                 }
  78             }
  79         }
  80
  81         public void Remove(int start, int length)
  82         {
  83             if (this.collection.Count == 0)
  84                 return;
  85
  86             int at = this.IndexOf(start);
  87
  88             int endAt = this.IndexOf(start + length - 1);
  89
  90             if(at != -1 && endAt != -1)
  91             {
  92                 for (int i = endAt; i >= at; i--)
  93                 {
  94                     this.collection.RemoveAt(i);
  95                 }
  96             }
  97             else if (at != -1)
  98             {
  99                 this.collection.RemoveAt(at);
 100             }
 101             else if(endAt != -1)
 102             {
 103                 this.collection.RemoveAt(endAt);
 104             }
 105         }
 106
 107         public void RemoveNearest(int start, int length)
 108         {
 109             if (this.collection.Count == 0)
 110                 return;
 111
 112             int nearAt;
 113             int at = this.IndexOfNearest(start, out nearAt);
 114             if (at == -1)
 115                 at = nearAt;
 116
 117             int nearEndAt;
 118             int endAt = this.IndexOfNearest(start + length - 1, out nearEndAt);
 119             if (endAt == -1)
 120                 endAt = nearEndAt;
 121
 122             int end = start + length - 1;
 123             for (int i = endAt; i >= at; i--)
 124             {
 125                 int markerEnd = this.collection[i].start + this.collection[i].length - 1;
 126                 if (this.collection[i].start >= start && markerEnd <= end ||
 127                     markerEnd >= start && markerEnd <= end ||
 128                     this.collection[i].start >= start && this.collection[i].start <= end ||
 129                     this.collection[i].start < start && markerEnd > end)
 130                     this.collection.RemoveAt(i);
 131             }
 132         }
 133
 134         public void RemoveAt(int index)
 135         {
 136             this.collection.RemoveAt(index);
 137         }
 138
 139         public int IndexOf(int start)
 140         {
 141             int dummy;
 142             return this.IndexOfNearest(start, out dummy);
 143         }
 144
 145         int IndexOfNearest(int start,out int nearIndex)
 146         {
 147             nearIndex = -1;
 148             int left = 0, right = this.collection.Count - 1, mid;
 149             while (left <= right)
 150             {
 151                 mid = (left + right) / 2;
 152                 T item = this.collection[mid];
 153                 if (start >= item.start && start < item.start + item.length)
 154                 {
 155                     return mid;
 156                 }
 157                 if (start < item.start)
 158                 {
 159                     right = mid - 1;
 160                 }
 161                 else
 162                 {
 163                     left = mid + 1;
 164                 }
 165             }
 166             System.Diagnostics.Debug.Assert(left >= 0 || right >= 0);
 167             nearIndex = left >= 0 ? left : right;
 168             if (nearIndex > this.collection.Count - 1)
 169                 nearIndex = right;
 170             return -1;
 171         }
 172
 173         public IEnumerable<T> Get(int index)
 174         {
 175             int at = this.IndexOf(index);
 176             if (at == -1)
 177                 yield break;
 178             yield return this.collection[at];
 179         }
 180
 181         public IEnumerable<T> Get(int start, int length)
 182         {
 183             int nearAt;
 184             int at = this.IndexOfNearest(start,out nearAt);
 185             if (at == -1)
 186                 at = nearAt;
 187
 188             if (at == -1)
 189                 yield break;
 190
 191             int end = start + length - 1;
 192             for (int i = at; i < this.collection.Count; i++)
 193             {
 194                 int markerEnd = this.collection[i].start + this.collection[i].length - 1;
 195                 if (this.collection[i].start >= start && markerEnd <= end ||
 196                     markerEnd >= start && markerEnd <= end ||
 197                     this.collection[i].start >= start && this.collection[i].start <= end ||
 198                     this.collection[i].start < start && markerEnd > end)
 199                     yield return this.collection[i];
 200                 else if (this.collection[i].start > start + length)
 201                     yield break;
 202             }
 203         }
 204
 205         public void Clear()
 206         {
 207             this.collection.Clear();
 208         }
 209
 210         public IEnumerator<T> GetEnumerator()
 211         {
 212             foreach (T item in this.collection)
 213                 yield return item;
 214         }
 215
 216         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
 217         {
 218             throw new NotImplementedException();
 219         }
 220     }
 221
 222 }