Common/StringBuffer.cs

   1 /*\r
   2  * Copyright (C) 2013 FooProject\r
   3  * * This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by\r
   4  * the Free Software Foundation; either version 3 of the License, or (at your option) any later version.\r
   5 \r
   6  * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of \r
   7  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.\r
   8 \r
   9 You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>.\r
  10  */\r
  11 using System;\r
  12 using System.Collections.Generic;\r
  13 using System.Globalization;\r
  14 using System.Linq;\r
  15 using System.Text;\r
  16 using System.Threading;\r
  17 using System.Threading.Tasks;\r
  18 using Slusser.Collections.Generic;\r
  19 \r
  20 namespace FooEditEngine\r
  21 {\r
  22     /// <summary>\r
  23     /// ランダムアクセス可能な列挙子を提供するインターフェイス\r
  24     /// </summary>\r
  25     /// <typeparam name="T"></typeparam>\r
  26     public interface IRandomEnumrator<T>\r
  27     {\r
  28         /// <summary>\r
  29         /// インデクサーを表す\r
  30         /// </summary>\r
  31         /// <param name="index">インデックス</param>\r
  32         /// <returns>Tを返す</returns>\r
  33         T this[int index]{get;}\r
  34     }\r
  35 \r
  36     sealed class StringBuffer : IEnumerable<char>, IRandomEnumrator<char>\r
  37     {\r
  38         GapBuffer<char> buf = new GapBuffer<char>();\r
  39 \r
  40         public StringBuffer()\r
  41         {\r
  42             this.Update += (s, e) => { };\r
  43         }\r
  44 \r
  45         public StringBuffer(StringBuffer buffer)\r
  46             : this()\r
  47         {\r
  48             buf.AddRange(buffer.buf, buffer.Length);\r
  49         }\r
  50 \r
  51         public char this[int index]\r
  52         {\r
  53             get\r
  54             {\r
  55                 char c = buf[index];\r
  56                 return c;\r
  57             }\r
  58         }\r
  59 \r
  60         public string ToString(int index, int length)\r
  61         {\r
  62             StringBuilder temp = new StringBuilder();\r
  63             temp.Clear();\r
  64             for (int i = index; i < index + length; i++)\r
  65                 temp.Append(buf[i]);\r
  66             return temp.ToString();\r
  67         }\r
  68 \r
  69         public IEnumerable<string> GetLines(int startIndex, int endIndex, int maxCharCount = -1)\r
  70         {\r
  71             foreach (Tuple<int, int> range in this.ForEachLines(startIndex, endIndex, maxCharCount))\r
  72             {\r
  73                 StringBuilder temp = new StringBuilder();\r
  74                 temp.Clear();\r
  75                 int lineEndIndex = range.Item1;\r
  76                 if (range.Item2 > 0)\r
  77                     lineEndIndex += range.Item2 - 1;\r
  78                 for (int i = range.Item1; i <= lineEndIndex; i++)\r
  79                     temp.Append(buf[i]);\r
  80                 yield return temp.ToString();\r
  81             }\r
  82         }\r
  83 \r
  84         public IEnumerable<Tuple<int,int>> ForEachLines(int startIndex, int endIndex, int maxCharCount = -1)\r
  85         {\r
  86             int currentLineHeadIndex = startIndex;\r
  87             int currentLineLength = 0;\r
  88             \r
  89             for (int i = startIndex; i <= endIndex; i++)\r
  90             {\r
  91                 currentLineLength++;\r
  92                 char c = this.buf[i];\r
  93                 if (c == Document.NewLine ||\r
  94                     (maxCharCount != -1 && currentLineLength >= maxCharCount))\r
  95                 {\r
  96                     UnicodeCategory uc = CharUnicodeInfo.GetUnicodeCategory(c);\r
  97                     if (uc != UnicodeCategory.NonSpacingMark &&\r
  98                     uc != UnicodeCategory.SpacingCombiningMark &&\r
  99                     uc != UnicodeCategory.EnclosingMark &&\r
 100                     uc != UnicodeCategory.Surrogate)\r
 101                     {\r
 102                         yield return new Tuple<int,int>(currentLineHeadIndex, currentLineLength);\r
 103                         currentLineHeadIndex += currentLineLength;\r
 104                         currentLineLength = 0;\r
 105                     }\r
 106                 }\r
 107             }\r
 108             if (currentLineLength > 0)\r
 109                 yield return new Tuple<int, int>(currentLineHeadIndex, currentLineLength);\r
 110         }\r
 111         \r
 112         public int Length\r
 113         {\r
 114             get { return this.buf.Count; }\r
 115         }\r
 116 \r
 117         internal event DocumentUpdateEventHandler Update;\r
 118 \r
 119         internal void Replace(StringBuffer buf)\r
 120         {\r
 121             this.Replace(buf.buf);\r
 122         }\r
 123 \r
 124         internal void Replace(GapBuffer<char> buf)\r
 125         {\r
 126             this.Clear();\r
 127             this.buf = buf;\r
 128             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, 0, 0, buf.Count));\r
 129         }\r
 130 \r
 131         internal void Replace(int index, int length, IEnumerable<char> chars,int count)\r
 132         {\r
 133             if (length > 0)\r
 134                 this.buf.RemoveRange(index, length);\r
 135             this.buf.InsertRange(index, chars,count);\r
 136             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, index, length, count));\r
 137         }\r
 138 \r
 139         internal async Task LoadAsync(IStreamReader fs, CancellationTokenSource tokenSource = null)\r
 140         {\r
 141             char[] str = new char[1024 * 256];\r
 142             int readCount;\r
 143             do\r
 144             {\r
 145                 int index = this.Length;\r
 146                 if (index < 0)\r
 147                     index = 0;\r
 148 \r
 149                 readCount = await fs.ReadAsync(str, 0, str.Length).ConfigureAwait(false);\r
 150                 \r
 151                 //内部形式に変換する\r
 152                 var internal_str = from s in str where s != '\r' && s != '\0' select s;\r
 153 \r
 154                 //str.lengthは事前に確保しておくために使用するので影響はない\r
 155                 this.buf.InsertRange(index, internal_str, str.Length);\r
 156 \r
 157                 if (tokenSource != null)\r
 158                     tokenSource.Token.ThrowIfCancellationRequested();\r
 159 #if TEST_ASYNC\r
 160                     System.Threading.Thread.Sleep(10);\r
 161 #endif\r
 162                 Array.Clear(str, 0, str.Length);\r
 163             } while (readCount > 0);\r
 164             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Clear, -1, -1, -1));\r
 165             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, 0, 0, buf.Count));\r
 166         }\r
 167 \r
 168         internal void Replace(string target, string pattern,bool ci = false)\r
 169         {\r
 170             TextSearch ts = new TextSearch(target,ci);\r
 171             int left = 0, right = 0;\r
 172             char[] pattern_chars = pattern.ToCharArray();\r
 173             while((right = ts.IndexOf(this.buf,left)) != -1)\r
 174             {\r
 175                 this.buf.RemoveRange(right, target.Length);\r
 176                 this.buf.InsertRange(right, pattern_chars, pattern.Length);\r
 177                 left = right + pattern.Length;\r
 178             }\r
 179             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Clear, -1, -1, -1));\r
 180             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Replace, 0, 0, buf.Count));\r
 181         }\r
 182 \r
 183         internal int IndexOf(string target, int start,bool ci = false)\r
 184         {\r
 185             TextSearch ts = new TextSearch(target,ci);\r
 186             return ts.IndexOf(this.buf, start);\r
 187         }\r
 188 \r
 189         /// <summary>\r
 190         /// 文字列を削除する\r
 191         /// </summary>\r
 192         internal void Clear()\r
 193         {\r
 194             this.buf.Clear();\r
 195             this.Update(this, new DocumentUpdateEventArgs(UpdateType.Clear, 0, this.buf.Count,0));\r
 196         }\r
 197 \r
 198         internal IEnumerable<char> GetEnumerator(int start, int length)\r
 199         {\r
 200             for (int i = start; i < start + length; i++)\r
 201                 yield return this.buf[i];\r
 202         }\r
 203 \r
 204         #region IEnumerable<char> メンバー\r
 205 \r
 206         public IEnumerator<char> GetEnumerator()\r
 207         {\r
 208             for (int i = 0; i < this.Length; i++)\r
 209                 yield return this.buf[i];\r
 210         }\r
 211 \r
 212         #endregion\r
 213 \r
 214         #region IEnumerable メンバー\r
 215 \r
 216         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()\r
 217         {\r
 218             for (int i = 0; i < this.Length; i++)\r
 219                 yield return this[i];\r
 220         }\r
 221 \r
 222         #endregion\r
 223     }\r
 224 \r
 225     sealed class TextSearch\r
 226     {\r
 227         char[] pattern;\r
 228         int patternLength;\r
 229         Dictionary<char, int> qsTable = new Dictionary<char, int>();\r
 230         bool caseInsenstive;\r
 231         public TextSearch(string pattern,bool ci = false)\r
 232         {\r
 233             this.patternLength = pattern.Length;\r
 234             this.caseInsenstive = ci;\r
 235             if (ci)\r
 236             {\r
 237                 this.CreateQSTable(pattern.ToLower());\r
 238                 this.CreateQSTable(pattern.ToUpper());\r
 239                 this.pattern = new char[pattern.Length];\r
 240                 for (int i = 0; i < pattern.Length; i++)\r
 241                     this.pattern[i] = CharTool.ToUpperFastIf(pattern[i]);\r
 242             }\r
 243             else\r
 244             {\r
 245                 this.CreateQSTable(pattern);\r
 246                 this.pattern = pattern.ToCharArray();\r
 247             }\r
 248         }\r
 249         void CreateQSTable(string pattern)\r
 250         {\r
 251             int len = pattern.Length;\r
 252             for (int i = 0; i < len; i++)\r
 253             {\r
 254                 if (!this.qsTable.ContainsKey(pattern[i]))\r
 255                     this.qsTable.Add(pattern[i], len - i);\r
 256                 else\r
 257                     this.qsTable[pattern[i]] = len - i;\r
 258             }\r
 259         }\r
 260         public int IndexOf(GapBuffer<char> buf, int start)\r
 261         {\r
 262             //QuickSearch法\r
 263             int buflen = buf.Count - 1;\r
 264             int plen = this.patternLength;\r
 265             int i = start;\r
 266             int end = buf.Count - plen;\r
 267             //最適化のためわざとコピペした\r
 268             if (this.caseInsenstive)\r
 269             {\r
 270                 while (i <= end)\r
 271                 {\r
 272                     int j = 0;\r
 273                     while (j < plen)\r
 274                     {\r
 275                         if (CharTool.ToUpperFastIf(buf[i + j]) != this.pattern[j])\r
 276                             break;\r
 277                         j++;\r
 278                     }\r
 279                     if (j == plen)\r
 280                     {\r
 281                         return i;\r
 282                     }\r
 283                     else\r
 284                     {\r
 285                         int k = i + plen;\r
 286                         if (k <= buflen)        //buffer以降にアクセスする可能性がある\r
 287                         {\r
 288                             int moveDelta;\r
 289                             if (this.qsTable.TryGetValue(buf[k], out moveDelta))\r
 290                                 i += moveDelta;\r
 291                             else\r
 292                                 i += plen;\r
 293                         }\r
 294                         else\r
 295                         {\r
 296                             break;\r
 297                         }\r
 298                     }\r
 299                 }\r
 300 \r
 301             }\r
 302             else\r
 303             {\r
 304                 while (i <= end)\r
 305                 {\r
 306                     int j = 0;\r
 307                     while (j < plen)\r
 308                     {\r
 309                         if (buf[i + j] != this.pattern[j])\r
 310                             break;\r
 311                         j++;\r
 312                     }\r
 313                     if (j == plen)\r
 314                     {\r
 315                         return i;\r
 316                     }\r
 317                     else\r
 318                     {\r
 319                         int k = i + plen;\r
 320                         if (k <= buflen)        //buffer以降にアクセスする可能性がある\r
 321                         {\r
 322                             int moveDelta;\r
 323                             if (this.qsTable.TryGetValue(buf[k], out moveDelta))\r
 324                                 i += moveDelta;\r
 325                             else\r
 326                                 i += plen;\r
 327                         }\r
 328                         else\r
 329                         {\r
 330                             break;\r
 331                         }\r
 332                     }\r
 333                 }\r
 334             }\r
 335             return -1;\r
 336         }\r
 337     }\r
 338     static class CharTool\r
 339     {\r
 340         /// <summary>\r
 341         /// Converts characters to lowercase.\r
 342         /// </summary>\r
 343         const string _lookupStringL =\r
 344         "---------------------------------!-#$%&-()*+,-./0123456789:;<=>?@abcdefghijklmnopqrstuvwxyz[-]^_`abcdefghijklmnopqrstuvwxyz{|}~-";\r
 345 \r
 346         /// <summary>\r
 347         /// Converts characters to uppercase.\r
 348         /// </summary>\r
 349         const string _lookupStringU =\r
 350         "---------------------------------!-#$%&-()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[-]^_`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~-";\r
 351 \r
 352         /// <summary>\r
 353         /// Get lowercase version of this ASCII character.\r
 354         /// </summary>\r
 355         public static char ToLower(char c)\r
 356         {\r
 357             return _lookupStringL[c];\r
 358         }\r
 359 \r
 360         /// <summary>\r
 361         /// Get uppercase version of this ASCII character.\r
 362         /// </summary>\r
 363         public static char ToUpper(char c)\r
 364         {\r
 365             return _lookupStringU[c];\r
 366         }\r
 367 \r
 368         /// <summary>\r
 369         /// Translate uppercase ASCII characters to lowercase.\r
 370         /// </summary>\r
 371         public static char ToLowerFastIf(char c)\r
 372         {\r
 373             if (c >= 'A' && c <= 'Z')\r
 374             {\r
 375                 return (char)(c + 32);\r
 376             }\r
 377             else\r
 378             {\r
 379                 return c;\r
 380             }\r
 381         }\r
 382 \r
 383         /// <summary>\r
 384         /// Translate lowercase ASCII characters to uppercase.\r
 385         /// </summary>\r
 386         public static char ToUpperFastIf(char c)\r
 387         {\r
 388             if (c >= 'a' && c <= 'z')\r
 389             {\r
 390                 return (char)(c - 32);\r
 391             }\r
 392             else\r
 393             {\r
 394                 return c;\r
 395             }\r
 396         }\r
 397     }\r
 398 }