1 /* https://github.com/mbuchetics/RangeTree よりコピペ。このファイルのみMITライセンスに従います */
3 using System.Collections.Generic;
6 using System.Threading.Tasks;
8 namespace FooEditEngine
13 internal interface IRange
16 /// マーカーの開始位置。-1を設定した場合、そのマーカーはレタリングされません
18 int start { get; set; }
20 /// マーカーの長さ。0を設定した場合、そのマーカーはレタリングされません
22 int length { get; set; }
25 internal sealed class RangeCollection<T> : IEnumerable<T>
30 public RangeCollection()
35 public RangeCollection(IEnumerable<T> collection)
37 if (collection == null)
38 this.collection = new List<T>();
40 this.collection = new List<T>(collection);
47 return this.collection[i];
51 this.collection[i] = value;
59 return this.collection.Count;
63 public void Add(T item)
65 this.collection.Add(item);
66 for (int i = this.collection.Count - 1; i >= 0; i--)
68 if (i > 0 && this.collection[i].start < this.collection[i - 1].start)
70 T temp = this.collection[i];
71 this.collection[i] = this.collection[i - 1];
72 this.collection[i - 1] = temp;
81 public void Remove(int start, int length)
83 if (this.collection.Count == 0)
86 int at = this.IndexOf(start);
88 int endAt = this.IndexOf(start + length - 1);
90 if(at != -1 && endAt != -1)
92 for (int i = endAt; i >= at; i--)
94 this.collection.RemoveAt(i);
99 this.collection.RemoveAt(at);
103 this.collection.RemoveAt(endAt);
107 public void RemoveNearest(int start, int length)
109 if (this.collection.Count == 0)
113 int at = this.IndexOfNearest(start, out nearAt);
118 int endAt = this.IndexOfNearest(start + length - 1, out nearEndAt);
122 int end = start + length - 1;
123 for (int i = endAt; i >= at; i--)
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);
134 public void RemoveAt(int index)
136 this.collection.RemoveAt(index);
139 public int IndexOf(int start)
142 return this.IndexOfNearest(start, out dummy);
145 int IndexOfNearest(int start,out int nearIndex)
148 int left = 0, right = this.collection.Count - 1, mid;
149 while (left <= right)
151 mid = (left + right) / 2;
152 T item = this.collection[mid];
153 if (start >= item.start && start < item.start + item.length)
157 if (start < item.start)
166 System.Diagnostics.Debug.Assert(left >= 0 || right >= 0);
167 nearIndex = left >= 0 ? left : right;
168 if (nearIndex > this.collection.Count - 1)
173 public IEnumerable<T> Get(int index)
175 int at = this.IndexOf(index);
178 yield return this.collection[at];
181 public IEnumerable<T> Get(int start, int length)
184 int at = this.IndexOfNearest(start,out nearAt);
191 int end = start + length - 1;
192 for (int i = at; i < this.collection.Count; i++)
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)
207 this.collection.Clear();
210 public IEnumerator<T> GetEnumerator()
212 foreach (T item in this.collection)
216 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
218 throw new NotImplementedException();