Common/RangeCollection.cs

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