Core/GapBuffer.cs

   1 /*
   2  * Copyright (C) 2013 FooProject
   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
   4  * the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
   5
   6  * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
   7  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
   8
   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/>.
  10  */
  11 #region Using Directives
  12
  13 using System;
  14 using System.Collections.Generic;
  15 using System.Collections;
  16 using System.Text;
  17 using System.Threading;
  18 using System.Globalization;
  19 using System.Diagnostics;
  20
  21 #endregion Using Directives
  22
  23
  24 namespace Slusser.Collections.Generic
  25 {
  26         /// <summary>
  27         /// Represents a strongly typed collection of objects that can be accessed by index. Insertions and
  28         /// deletions to the collection near the same relative index are optimized.
  29         /// </summary>
  30         /// <typeparam name="T">The type of elements in the buffer.</typeparam>
  31         [DebuggerDisplay("Count = {Count}")]
  32         [DebuggerTypeProxy(typeof(CollectionDebugView<>))]
  33     sealed partial class GapBuffer<T> : IList<T>, IList
  34         {
  35                 #region Fields
  36
  37                 private const int MIN_CAPACITY = 4;
  38
  39                 private T[] _buffer;
  40                 private int _gapStart;
  41                 private int _gapEnd;
  42                 private int _version;
  43
  44         private object _syncRoot;
  45
  46                 #endregion Fields
  47
  48
  49                 #region Constructors
  50
  51                 /// <summary>
  52                 /// Initializes a new instance of the <see cref="GapBuffer{T}"/> class.
  53                 /// </summary>
  54                 public GapBuffer()
  55                 {
  56                         this._buffer = new T[MIN_CAPACITY];
  57                         this._gapEnd = this._buffer.Length;
  58                 }
  59
  60                 #endregion Constructors
  61
  62
  63                 #region Properties
  64
  65                 /// <summary>
  66                 /// Gets or sets the total number of elements the internal data structure can hold
  67                 /// without resizing.
  68                 /// </summary>
  69                 /// <value>The number of elements that the <see cref="GapBuffer{T}"/> can contain before
  70                 /// resizing is required.</value>
  71                 /// <exception cref="ArgumentOutOfRangeException">
  72                 /// <see cref="Capacity"/> is set to a value that is less than <see cref="Count"/>.
  73                 /// </exception>
  74                 public int Capacity
  75                 {
  76                         get
  77                         {
  78                                 return this._buffer.Length;
  79                         }
  80                         set
  81                         {
  82                                 // Is there any work to do?
  83                                 if (value == this._buffer.Length)
  84                                         return;
  85
  86                                 // Look for naughty boys and girls
  87                                 if (value < Count)
  88                                         throw new ArgumentOutOfRangeException("value", "");
  89
  90                                 if (value > 0)
  91                                 {
  92                                         // Allocate a new buffer
  93                                         T[] newBuffer = new T[value];
  94                                         int newGapEnd = newBuffer.Length - (this._buffer.Length - this._gapEnd);
  95
  96                                         // Copy the spans into the front and back of the new buffer
  97                                         Array.Copy(this._buffer, 0, newBuffer, 0, this._gapStart);
  98                                         Array.Copy(this._buffer, this._gapEnd, newBuffer, newGapEnd, newBuffer.Length - newGapEnd);
  99                                         this._buffer = newBuffer;
 100                                         this._gapEnd = newGapEnd;
 101                                 }
 102                                 else
 103                                 {
 104                                         // Reset everything
 105                                         this._buffer = new T[MIN_CAPACITY];
 106                                         this._gapStart = 0;
 107                                         this._gapEnd = this._buffer.Length;
 108                                 }
 109                         }
 110                 }
 111
 112
 113                 /// <summary>
 114                 /// Gets the number of elements actually contained in the <see cref="GapBuffer{T}"/>.
 115                 /// </summary>
 116                 /// <value>
 117                 /// The number of elements actually contained in the <see cref="GapBuffer{T}"/>.
 118                 /// </value>
 119                 public int Count
 120                 {
 121                         get
 122                         {
 123                                 return this._buffer.Length - (this._gapEnd - this._gapStart);
 124                         }
 125                 }
 126
 127
 128                 // Explicit IList implementation
 129                 bool IList.IsFixedSize
 130                 {
 131                         get { return false; }
 132                 }
 133
 134
 135                 // Explicit IList implementation
 136                 bool IList.IsReadOnly
 137                 {
 138                         get { return false; }
 139                 }
 140
 141
 142                 // Explicit ICollection<T> implementation
 143                 bool ICollection<T>.IsReadOnly
 144                 {
 145                         get { return false; }
 146                 }
 147
 148
 149                 // Explicit ICollection implementation
 150                 bool ICollection.IsSynchronized
 151                 {
 152                         get { return false; }
 153                 }
 154
 155
 156                 // Explicit ICollection implementation
 157                 object ICollection.SyncRoot
 158                 {
 159                         get
 160                         {
 161                                 if (this._syncRoot == null)
 162                                         Interlocked.CompareExchange(ref this._syncRoot, new object(), null);
 163
 164                                 return this._syncRoot;
 165                         }
 166                 }
 167
 168
 169                 /// <summary>
 170                 /// Gets or sets the element at the specified index.
 171                 /// </summary>
 172                 /// <param name="index">The zero-based index of the element to get or set.</param>
 173                 /// <value>The element at the specified index.</value>
 174                 /// <exception cref="ArgumentOutOfRangeException">
 175                 /// <paramref name="index"/> is less than 0.
 176                 /// <para>-or-</para>
 177                 /// <paramref name="index"/> is equal to or greater than <see cref="Count"/>.
 178                 /// </exception>
 179                 public T this[int index]
 180                 {
 181                         get
 182                         {
 183                                 if (index < 0 || index >= Count)
 184                                         throw new ArgumentOutOfRangeException("index", "");
 185
 186                                 // Find the correct span and get the item
 187                                 if (index >= this._gapStart)
 188                                         index += (this._gapEnd - this._gapStart);
 189
 190                                 return this._buffer[index];
 191                         }
 192                         set
 193                         {
 194                                 if (index < 0 || index >= Count)
 195                                         throw new ArgumentOutOfRangeException("index", "");
 196
 197                                 // Find the correct span and set the item
 198                                 if (index >= this._gapStart)
 199                                         index += (this._gapEnd - this._gapStart);
 200
 201                                 this._buffer[index] = value;
 202                                 this._version++;
 203                         }
 204                 }
 205
 206
 207                 // Explicit IList implementation
 208                 object IList.this[int index]
 209                 {
 210                         get { return this[index]; }
 211                         set
 212                         {
 213                                 VerifyValueType(value);
 214                                 this[index] = (T)value;
 215                         }
 216                 }
 217
 218                 #endregion Properties
 219
 220
 221                 #region Methods
 222
 223                 /// <summary>
 224                 /// Adds an object to the end of the <see cref="GapBuffer{T}"/>.
 225                 /// </summary>
 226                 /// <param name="item">The object to be added to the end of the <see cref="GapBuffer{T}"/>.
 227                 /// The value can be null for reference types.</param>
 228                 public void Add(T item)
 229                 {
 230                         Insert(Count, item);
 231                 }
 232
 233
 234                 // Explicit IList implementation
 235                 int IList.Add(object value)
 236                 {
 237                         VerifyValueType(value);
 238                         Add((T)value);
 239                         return (Count - 1);
 240                 }
 241
 242
 243                 /// <summary>
 244                 /// Adds the elements of the specified collection to the end of the <see cref="GapBuffer{T}"/>.
 245                 /// </summary>
 246                 /// <param name="collection">The collection whose elements should be inserted into the <see cref="GapBuffer{T}"/>.
 247                 /// The collection itself cannot be null, but it can contain elements that are null, if
 248                 /// type <typeparamref name="T"/> is a reference type.</param>
 249         /// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference.</exception>
 250                 public void AddRange(IEnumerable<T> collection)
 251                 {
 252                         InsertRange(Count, collection);
 253                 }
 254
 255
 256                 /// <summary>
 257                 /// Removes all elements from the <see cref="GapBuffer{T}"/>.
 258                 /// </summary>
 259                 public void Clear()
 260                 {
 261                         // Clearing the buffer means simply enlarging the gap to the
 262                         // entire buffer size
 263
 264                         Array.Clear(this._buffer, 0, this._buffer.Length);
 265                         this._gapStart = 0;
 266                         this._gapEnd = this._buffer.Length;
 267                         this._version++;
 268                 }
 269
 270
 271                 /// <summary>
 272                 /// Determines whether an element is in the <see cref="GapBuffer{T}"/>.
 273                 /// </summary>
 274                 /// <param name="item">The object to locate in the <see cref="GapBuffer{T}"/>. The value
 275                 /// can be null for reference types.</param>
 276                 /// <returns><b>true</b> if item is found in the <see cref="GapBuffer{T}"/>;
 277                 /// otherwise, <b>false</b>.</returns>
 278                 public bool Contains(T item)
 279                 {
 280                         // Search on both sides of the gap for the item
 281
 282                         EqualityComparer<T> comparer = EqualityComparer<T>.Default;
 283                         for (int i = 0; i < this._gapStart; i++)
 284                         {
 285                                 if (comparer.Equals(this._buffer[i], item))
 286                                         return true;
 287                         }
 288                         for (int i = this._gapEnd; i < this._buffer.Length; i++)
 289                         {
 290                                 if (comparer.Equals(this._buffer[i], item))
 291                                         return true;
 292                         }
 293
 294                         return false;
 295                 }
 296
 297
 298                 // Explicit IList implementation
 299                 bool IList.Contains(object value)
 300                 {
 301                         if (IsCompatibleObject(value))
 302                                 return Contains((T)value);
 303
 304                         return false;
 305                 }
 306
 307
 308                 /// <summary>
 309                 /// Copies the <see cref="GapBuffer{T}"/> to a compatible one-dimensional array,
 310                 /// starting at the specified index of the target array.
 311                 /// </summary>
 312                 /// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the elements
 313                 /// copied from <see cref="GapBuffer{T}"/>. The <see cref="Array"/> must have zero-based indexing.</param>
 314                 /// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param>
 315                 /// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference.</exception>
 316         /// <exception cref="ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is less than 0.</exception>
 317                 /// <exception cref="ArgumentException">
 318                 /// <paramref name="array"/> is multidimensional.
 319                 /// <para>-or-</para>
 320                 /// <paramref name="arrayIndex"/> is equal to or greater than the length of <paramref name="array"/>.
 321                 /// <para>-or-</para>
 322                 /// The number of elements in the source <see cref="GapBuffer{T}"/> is greater than the available space
 323                 /// from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.
 324                 /// </exception>
 325                 public void CopyTo(T[] array, int arrayIndex)
 326                 {
 327                         if (array == null)
 328                                 throw new ArgumentNullException("array");
 329
 330                         if (arrayIndex < 0)
 331                                 throw new ArgumentOutOfRangeException("arrayIndex", "");
 332
 333                         if (array.Rank != 1)
 334                                 throw new ArgumentException("", "array");
 335
 336                         if (arrayIndex >= array.Length || arrayIndex + Count > array.Length)
 337                                 throw new ArgumentException("", "arrayIndex");
 338
 339
 340                         // Copy the spans into the destination array at the offset
 341                         Array.Copy(this._buffer, 0, array, arrayIndex, this._gapStart);
 342                         Array.Copy(this._buffer, this._gapEnd, array, arrayIndex + this._gapStart, this._buffer.Length - this._gapEnd);
 343                 }
 344
 345
 346                 // Explicit ICollection implementation
 347                 void ICollection.CopyTo(Array array, int arrayIndex)
 348                 {
 349                         try
 350                         {
 351                                 CopyTo((T[])array, arrayIndex);
 352                         }
 353                         catch (InvalidCastException)
 354                         {
 355                                 throw new ArgumentException("", "array");
 356                         }
 357                         catch
 358                         {
 359                                 throw;
 360                         }
 361                 }
 362
 363
 364                 /// <summary>
 365                 /// Returns an enumerator that iterates through the <see cref="GapBuffer{T}"/>.
 366                 /// </summary>
 367                 /// <returns>A <see cref="GapBuffer{T}.Enumerator"/> for the <see cref="GapBuffer{T}"/>.</returns>
 368                 public GapBuffer<T>.Enumerator GetEnumerator()
 369                 {
 370                         return new GapBuffer<T>.Enumerator(this);
 371                 }
 372
 373
 374                 // Explicit IEnumerable implementation
 375                 IEnumerator IEnumerable.GetEnumerator()
 376                 {
 377                         return new GapBuffer<T>.Enumerator(this);
 378                 }
 379
 380
 381                 // Explicit IEnumerable<T> implementation
 382                 IEnumerator<T> IEnumerable<T>.GetEnumerator()
 383                 {
 384                         return new GapBuffer<T>.Enumerator(this);
 385                 }
 386
 387
 388                 /// <summary>
 389                 /// Searches for the specified object and returns the zero-based index of the first
 390                 /// occurrence within the <see cref="GapBuffer{T}"/>.
 391                 /// </summary>
 392                 /// <param name="item">The object to locate in the <see cref="GapBuffer{T}"/>. The value
 393                 /// can be null for reference types.</param>
 394                 /// <returns>The zero-based index of the first occurrence of <paramref name="item"/> within
 395                 /// the <see cref="GapBuffer{T}"/>, if found; otherwise, \81E.</returns>
 396                 public int IndexOf(T item)
 397                 {
 398                         // Search within the buffer spans
 399
 400                         int index = Array.IndexOf<T>(this._buffer, item, 0, this._gapStart);
 401                         if (index < 0)
 402                         {
 403                                 index = Array.IndexOf<T>(this._buffer, item, this._gapEnd, this._buffer.Length - this._gapEnd);
 404
 405                                 // Translate the internal index to the index in the collection
 406                                 if(index != -1)
 407                                         return index - (this._gapEnd - this._gapStart);
 408                         }
 409
 410                         return index;
 411                 }
 412
 413
 414                 // Explicit IList implementation
 415                 int IList.IndexOf(object item)
 416                 {
 417                         if (IsCompatibleObject(item))
 418                                 return IndexOf((T)item);
 419
 420                         return -1;
 421                 }
 422
 423
 424                 /// <summary>
 425                 /// Inserts an element into the <see cref="GapBuffer{T}"/> at the specified index. Consecutive operations
 426                 /// at or near previous inserts are optimized.
 427                 /// </summary>
 428                 /// <param name="index">The object to insert. The value can be null for reference types.</param>
 429                 /// <param name="item">The zero-based index at which <paramref name="item"/> should be inserted.</param>
 430                 /// <exception cref="ArgumentOutOfRangeException">
 431                 /// <paramref name="index"/> is less than 0.
 432                 /// <para>-or-</para>
 433                 /// <paramref name="index"/> is greater than <see cref="Count"/>.
 434                 /// </exception>
 435                 public void Insert(int index, T item)
 436                 {
 437                         if (index < 0 || index > Count)
 438                                 throw new ArgumentOutOfRangeException("index", "");
 439
 440                         // Prepare the buffer
 441                         PlaceGapStart(index);
 442                         EnsureGapCapacity(1);
 443
 444                         this._buffer[index] = item;
 445                         this._gapStart++;
 446                         this._version++;
 447                 }
 448
 449
 450                 // Explicit IList implementation
 451                 void IList.Insert(int index, object item)
 452                 {
 453                         VerifyValueType(item);
 454                         Insert(index, (T)item);
 455                 }
 456
 457
 458         /// <summary>
 459         /// Inserts the elements of a collection into the <see cref="GapBuffer{T}"/> at the specified index.
 460         /// Consecutive operations at or near previous inserts are optimized.
 461         /// </summary>
 462         /// <param name="index">The zero-based index at which the new elements should be inserted.</param>
 463         /// <param name="col">The collection whose elements should be inserted into the <see cref="GapBuffer{T}"/>.
 464         /// The collection itself cannot be null, but it can contain elements that are null, if
 465         /// type <typeparamref name="T"/> is a reference type.</param>
 466         /// <exception cref="ArgumentNullException"><paramref name="col"/> is a null reference.</exception>
 467         /// <exception cref="ArgumentOutOfRangeException">
 468         /// <paramref name="index"/> is less than 0.
 469         /// <para>-or-</para>
 470         /// <paramref name="index"/> is greater than <see cref="Count"/>.
 471         /// </exception>
 472         public void InsertRange(int index, ICollection<T> col)
 473         {
 474             if (col == null)
 475                 throw new ArgumentNullException("collection");
 476
 477             if (index < 0 || index > Count)
 478                 throw new ArgumentOutOfRangeException("index", "");
 479
 480             if (col != null)
 481             {
 482                 int count = col.Count;
 483                 if (count > 0)
 484                 {
 485                     PlaceGapStart(index);
 486                     EnsureGapCapacity(count);
 487
 488                     // Copy the collection directly into the buffer
 489                     col.CopyTo(this._buffer, this._gapStart);
 490                     this._gapStart += count;
 491                 }
 492             }
 493             this._version++;
 494         }
 495                 /// <summary>
 496                 /// Inserts the elements of a collection into the <see cref="GapBuffer{T}"/> at the specified index.
 497                 /// Consecutive operations at or near previous inserts are optimized.
 498                 /// </summary>
 499                 /// <param name="index">The zero-based index at which the new elements should be inserted.</param>
 500                 /// <param name="collection">The collection whose elements should be inserted into the <see cref="GapBuffer{T}"/>.
 501                 /// The collection itself cannot be null, but it can contain elements that are null, if
 502                 /// type <typeparamref name="T"/> is a reference type.</param>
 503                 /// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference.</exception>
 504                 /// <exception cref="ArgumentOutOfRangeException">
 505                 /// <paramref name="index"/> is less than 0.
 506                 /// <para>-or-</para>
 507                 /// <paramref name="index"/> is greater than <see cref="Count"/>.
 508                 /// </exception>
 509         public void InsertRange(int index, IEnumerable<T> collection)
 510         {
 511             if (collection == null)
 512                 throw new ArgumentNullException("collection");
 513
 514             if (index < 0 || index > Count)
 515                 throw new ArgumentOutOfRangeException("index", "");
 516
 517             ICollection<T> col = collection as ICollection<T>;
 518             if (col != null)
 519             {
 520                 int count = col.Count;
 521                 if (count > 0)
 522                 {
 523                     PlaceGapStart(index);
 524                     EnsureGapCapacity(count);
 525
 526                     // Copy the collection directly into the buffer
 527                     col.CopyTo(this._buffer, this._gapStart);
 528                     this._gapStart += count;
 529                 }
 530             }
 531             else
 532             {
 533                 // Add the items to the buffer one-at-a-time :(
 534                 using (IEnumerator<T> enumerator = collection.GetEnumerator())
 535                 {
 536                     while (enumerator.MoveNext())
 537                     {
 538                         Insert(index, enumerator.Current);
 539                         index++;
 540                     }
 541                 }
 542             }
 543             this._version++;
 544         }
 545
 546                 /// <summary>
 547                 /// Removes the first occurrence of a specific object from the <see cref="GapBuffer{T}"/>.
 548                 /// </summary>
 549                 /// <param name="item">The object to remove from the <see cref="GapBuffer{T}"/>. The
 550                 /// value can be null for reference types.</param>
 551                 /// <returns><b>true</b> if <paramref name="item"/> is successfully removed; otherwise,
 552                 /// <b>false</b>. This method also returns <b>false</b> if <paramref name="item"/> was not
 553                 /// found in the <see cref="GapBuffer{T}"/>.</returns>
 554                 public bool Remove(T item)
 555                 {
 556                         // Get the index of the item
 557                         int index = IndexOf(item);
 558                         if (index < 0)
 559                                 return false;
 560
 561                         // Remove the item
 562                         RemoveAt(index);
 563                         return true;
 564                 }
 565
 566
 567                 // Explicit IList implementation
 568                 void IList.Remove(object item)
 569                 {
 570                         if (IsCompatibleObject(item))
 571                                 Remove((T)item);
 572                 }
 573
 574
 575                 /// <summary>
 576                 /// Removes the element at the specified index of the <see cref="GapBuffer{T}"/>.
 577                 /// </summary>
 578                 /// <param name="index">The zero-based index of the element to remove.</param>
 579                 /// <exception cref="ArgumentOutOfRangeException">
 580                 /// <paramref name="index"/> is less than 0.
 581                 /// <para>-or-</para>
 582                 /// <paramref name="index"/> is equal to or greater than <see cref="Count"/>.
 583                 /// </exception>
 584                 public void RemoveAt(int index)
 585                 {
 586                         if (index < 0 || index >= Count)
 587                                 throw new ArgumentOutOfRangeException("index", "");
 588
 589                         // Place the gap at the index and increase the gap size by 1
 590                         PlaceGapStart(index);
 591                         this._buffer[this._gapEnd] = default(T);
 592                         this._gapEnd++;
 593                         this._version++;
 594                 }
 595
 596
 597                 /// <summary>
 598                 /// Removes a range of elements from the <see cref="GapBuffer{T}"/>.
 599                 /// </summary>
 600                 /// <param name="index">The zero-based starting index of the range of elements to remove.</param>
 601                 /// <param name="count">The number of elements to remove.</param>
 602                 /// <exception cref="ArgumentOutOfRangeException">
 603                 /// <paramref name="index"/> is less than 0 or is equal to or greater than <see cref="Count"/>.
 604                 /// <para>-or-</para>
 605                 /// <paramref name="count"/> is less than 0.
 606                 /// <para>-or-</para>
 607                 /// <paramref name="index"/> and <paramref name="count"/> do not denote a valid range of elements in
 608                 /// the <see cref="GapBuffer{T}"/>.
 609                 /// </exception>
 610                 public void RemoveRange(int index, int count)
 611                 {
 612                         int size = Count;
 613
 614                         if (index < 0 || index >= size)
 615                                 throw new ArgumentOutOfRangeException("index", "");
 616
 617                         if (count < 0 || size - index < count)
 618                                 throw new ArgumentOutOfRangeException("count", "");
 619
 620
 621                         // Move the gap over the index and increase the gap size
 622                         // by the number of elements removed. Easy as pie!
 623
 624                         if (count > 0)
 625                         {
 626                                 PlaceGapStart(index);
 627                                 //Array.Clear(this._buffer, this._gapEnd, count);
 628                                 this._gapEnd += count;
 629                                 this._version++;
 630                         }
 631                 }
 632
 633
 634                 /// <summary>
 635                 /// Sets the <see cref="Capacity"/> to the actual number of elements in the <see cref="GapBuffer{T}"/>,
 636                 /// if that number is less than a threshold value.
 637                 /// </summary>
 638                 public void TrimExcess()
 639                 {
 640                         int size = Count;
 641                         int threshold = (int)(_buffer.Length * 0.9);
 642                         if (size < threshold)
 643                         {
 644                                 Capacity = size;
 645                         }
 646                 }
 647
 648
 649                 // Moves the gap start to the given index
 650                 private void PlaceGapStart(int index)
 651                 {
 652                         // Are we already there?
 653                         if (index == this._gapStart)
 654                                 return;
 655
 656                         // Is there even a gap?
 657                         if ((this._gapEnd - this._gapStart) == 0)
 658                         {
 659                                 this._gapStart = index;
 660                                 this._gapEnd = index;
 661                                 return;
 662                         }
 663
 664                         // Which direction do we move the gap?
 665                         if (index < this._gapStart)
 666                         {
 667                                 // Move the gap near (by copying the items at the beginning
 668                                 // of the gap to the end)
 669                                 int count = this._gapStart - index;
 670                                 int deltaCount = (this._gapEnd - this._gapStart < count ? this._gapEnd - this._gapStart : count);
 671                                 Array.Copy(this._buffer, index, this._buffer, this._gapEnd - count, count);
 672                                 this._gapStart -= count;
 673                                 this._gapEnd -= count;
 674
 675                                 // Clear the contents of the gap
 676                                 //Array.Clear(this._buffer, index, deltaCount);
 677                         }
 678                         else
 679                         {
 680                                 // Move the gap far (by copying the items at the end
 681                                 // of the gap to the beginning)
 682                                 int count = index - this._gapStart;
 683                                 int deltaIndex = (index > this._gapEnd ? index : this._gapEnd);
 684                                 Array.Copy(this._buffer, this._gapEnd, this._buffer, this._gapStart, count);
 685                                 this._gapStart += count;
 686                                 this._gapEnd += count;
 687
 688                                 // Clear the contents of the gap
 689                                 //Array.Clear(this._buffer, deltaIndex, this._gapEnd - deltaIndex);
 690                         }
 691                 }
 692
 693
 694                 // Expands the interal array if the required size isn't available
 695                 private void EnsureGapCapacity(int required)
 696                 {
 697                         // Is the available space in the gap?
 698                         if (required > (this._gapEnd - this._gapStart))
 699                         {
 700                                 // Calculate a new size (double the size necessary)
 701                                 int newCapacity = (Count + required) * 2;
 702                                 if (newCapacity < MIN_CAPACITY)
 703                                         newCapacity = MIN_CAPACITY;
 704
 705                                 Capacity = newCapacity;
 706                         }
 707                 }
 708
 709
 710                 private static bool IsCompatibleObject(object value)
 711                 {
 712                         // Ensure the object is compatible with the generic type
 713
 714                         if (!(value is T) && ((value != null) || value is ValueType))
 715                                 return false;
 716
 717                         return true;
 718                 }
 719
 720
 721                 private static void VerifyValueType(object value)
 722                 {
 723                         // Throw an exception if the object is not compatible with
 724                         // the generic type
 725
 726                         if (!IsCompatibleObject(value))
 727                         {
 728                                 throw new ArgumentException("", "value");
 729                         }
 730                 }
 731
 732                 #endregion Methods
 733         }
 734 }