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         /// <param name="count">The count of collction.count is -1 when this method is slowly</param>
 250         /// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference.</exception>
 251                 public void AddRange(IEnumerable<T> collection,int count = -1)
 252                 {
 253                         InsertRange(Count, collection,count);
 254                 }
 255
 256
 257                 /// <summary>
 258                 /// Removes all elements from the <see cref="GapBuffer{T}"/>.
 259                 /// </summary>
 260                 public void Clear()
 261                 {
 262                         // Clearing the buffer means simply enlarging the gap to the
 263                         // entire buffer size
 264
 265                         Array.Clear(this._buffer, 0, this._buffer.Length);
 266                         this._gapStart = 0;
 267                         this._gapEnd = this._buffer.Length;
 268                         this._version++;
 269                 }
 270
 271
 272                 /// <summary>
 273                 /// Determines whether an element is in the <see cref="GapBuffer{T}"/>.
 274                 /// </summary>
 275                 /// <param name="item">The object to locate in the <see cref="GapBuffer{T}"/>. The value
 276                 /// can be null for reference types.</param>
 277                 /// <returns><b>true</b> if item is found in the <see cref="GapBuffer{T}"/>;
 278                 /// otherwise, <b>false</b>.</returns>
 279                 public bool Contains(T item)
 280                 {
 281                         // Search on both sides of the gap for the item
 282
 283                         EqualityComparer<T> comparer = EqualityComparer<T>.Default;
 284                         for (int i = 0; i < this._gapStart; i++)
 285                         {
 286                                 if (comparer.Equals(this._buffer[i], item))
 287                                         return true;
 288                         }
 289                         for (int i = this._gapEnd; i < this._buffer.Length; i++)
 290                         {
 291                                 if (comparer.Equals(this._buffer[i], item))
 292                                         return true;
 293                         }
 294
 295                         return false;
 296                 }
 297
 298
 299                 // Explicit IList implementation
 300                 bool IList.Contains(object value)
 301                 {
 302                         if (IsCompatibleObject(value))
 303                                 return Contains((T)value);
 304
 305                         return false;
 306                 }
 307
 308
 309                 /// <summary>
 310                 /// Copies the <see cref="GapBuffer{T}"/> to a compatible one-dimensional array,
 311                 /// starting at the specified index of the target array.
 312                 /// </summary>
 313                 /// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the elements
 314                 /// copied from <see cref="GapBuffer{T}"/>. The <see cref="Array"/> must have zero-based indexing.</param>
 315                 /// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param>
 316                 /// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference.</exception>
 317         /// <exception cref="ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is less than 0.</exception>
 318                 /// <exception cref="ArgumentException">
 319                 /// <paramref name="array"/> is multidimensional.
 320                 /// <para>-or-</para>
 321                 /// <paramref name="arrayIndex"/> is equal to or greater than the length of <paramref name="array"/>.
 322                 /// <para>-or-</para>
 323                 /// The number of elements in the source <see cref="GapBuffer{T}"/> is greater than the available space
 324                 /// from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.
 325                 /// </exception>
 326                 public void CopyTo(T[] array, int arrayIndex)
 327                 {
 328                         if (array == null)
 329                                 throw new ArgumentNullException("array");
 330
 331                         if (arrayIndex < 0)
 332                                 throw new ArgumentOutOfRangeException("arrayIndex", "");
 333
 334                         if (array.Rank != 1)
 335                                 throw new ArgumentException("", "array");
 336
 337                         if (arrayIndex >= array.Length || arrayIndex + Count > array.Length)
 338                                 throw new ArgumentException("", "arrayIndex");
 339
 340
 341                         // Copy the spans into the destination array at the offset
 342                         Array.Copy(this._buffer, 0, array, arrayIndex, this._gapStart);
 343                         Array.Copy(this._buffer, this._gapEnd, array, arrayIndex + this._gapStart, this._buffer.Length - this._gapEnd);
 344                 }
 345
 346
 347                 // Explicit ICollection implementation
 348                 void ICollection.CopyTo(Array array, int arrayIndex)
 349                 {
 350                         try
 351                         {
 352                                 CopyTo((T[])array, arrayIndex);
 353                         }
 354                         catch (InvalidCastException)
 355                         {
 356                                 throw new ArgumentException("", "array");
 357                         }
 358                         catch
 359                         {
 360                                 throw;
 361                         }
 362                 }
 363
 364
 365                 /// <summary>
 366                 /// Returns an enumerator that iterates through the <see cref="GapBuffer{T}"/>.
 367                 /// </summary>
 368                 /// <returns>A <see cref="GapBuffer{T}.Enumerator"/> for the <see cref="GapBuffer{T}"/>.</returns>
 369                 public GapBuffer<T>.Enumerator GetEnumerator()
 370                 {
 371                         return new GapBuffer<T>.Enumerator(this);
 372                 }
 373
 374
 375                 // Explicit IEnumerable implementation
 376                 IEnumerator IEnumerable.GetEnumerator()
 377                 {
 378                         return new GapBuffer<T>.Enumerator(this);
 379                 }
 380
 381
 382                 // Explicit IEnumerable<T> implementation
 383                 IEnumerator<T> IEnumerable<T>.GetEnumerator()
 384                 {
 385                         return new GapBuffer<T>.Enumerator(this);
 386                 }
 387
 388
 389                 /// <summary>
 390                 /// Searches for the specified object and returns the zero-based index of the first
 391                 /// occurrence within the <see cref="GapBuffer{T}"/>.
 392                 /// </summary>
 393                 /// <param name="item">The object to locate in the <see cref="GapBuffer{T}"/>. The value
 394                 /// can be null for reference types.</param>
 395                 /// <returns>The zero-based index of the first occurrence of <paramref name="item"/> within
 396                 /// the <see cref="GapBuffer{T}"/>, if found; otherwise, \81E.</returns>
 397                 public int IndexOf(T item)
 398                 {
 399                         // Search within the buffer spans
 400
 401                         int index = Array.IndexOf<T>(this._buffer, item, 0, this._gapStart);
 402                         if (index < 0)
 403                         {
 404                                 index = Array.IndexOf<T>(this._buffer, item, this._gapEnd, this._buffer.Length - this._gapEnd);
 405
 406                                 // Translate the internal index to the index in the collection
 407                                 if(index != -1)
 408                                         return index - (this._gapEnd - this._gapStart);
 409                         }
 410
 411                         return index;
 412                 }
 413
 414
 415                 // Explicit IList implementation
 416                 int IList.IndexOf(object item)
 417                 {
 418                         if (IsCompatibleObject(item))
 419                                 return IndexOf((T)item);
 420
 421                         return -1;
 422                 }
 423
 424
 425                 /// <summary>
 426                 /// Inserts an element into the <see cref="GapBuffer{T}"/> at the specified index. Consecutive operations
 427                 /// at or near previous inserts are optimized.
 428                 /// </summary>
 429                 /// <param name="index">The object to insert. The value can be null for reference types.</param>
 430                 /// <param name="item">The zero-based index at which <paramref name="item"/> should be inserted.</param>
 431                 /// <exception cref="ArgumentOutOfRangeException">
 432                 /// <paramref name="index"/> is less than 0.
 433                 /// <para>-or-</para>
 434                 /// <paramref name="index"/> is greater than <see cref="Count"/>.
 435                 /// </exception>
 436                 public void Insert(int index, T item)
 437                 {
 438                         if (index < 0 || index > Count)
 439                                 throw new ArgumentOutOfRangeException("index", "");
 440
 441                         // Prepare the buffer
 442                         PlaceGapStart(index);
 443                         EnsureGapCapacity(1);
 444
 445                         this._buffer[index] = item;
 446                         this._gapStart++;
 447                         this._version++;
 448                 }
 449
 450
 451                 // Explicit IList implementation
 452                 void IList.Insert(int index, object item)
 453                 {
 454                         VerifyValueType(item);
 455                         Insert(index, (T)item);
 456                 }
 457
 458
 459         /// <summary>
 460         /// Inserts the elements of a collection into the <see cref="GapBuffer{T}"/> at the specified index.
 461         /// Consecutive operations at or near previous inserts are optimized.
 462         /// </summary>
 463         /// <param name="index">The zero-based index at which the new elements should be inserted.</param>
 464         /// <param name="col">The collection whose elements should be inserted into the <see cref="GapBuffer{T}"/>.
 465         /// The collection itself cannot be null, but it can contain elements that are null, if
 466         /// type <typeparamref name="T"/> is a reference type.</param>
 467         /// <exception cref="ArgumentNullException"><paramref name="col"/> is a null reference.</exception>
 468         /// <exception cref="ArgumentOutOfRangeException">
 469         /// <paramref name="index"/> is less than 0.
 470         /// <para>-or-</para>
 471         /// <paramref name="index"/> is greater than <see cref="Count"/>.
 472         /// </exception>
 473         public void InsertRange(int index, ICollection<T> col)
 474         {
 475             if (col == null)
 476                 throw new ArgumentNullException("collection");
 477
 478             if (index < 0 || index > Count)
 479                 throw new ArgumentOutOfRangeException("index", "");
 480
 481             if (col != null)
 482             {
 483                 int count = col.Count;
 484                 if (count > 0)
 485                 {
 486                     PlaceGapStart(index);
 487                     EnsureGapCapacity(count);
 488
 489                     // Copy the collection directly into the buffer
 490                     col.CopyTo(this._buffer, this._gapStart);
 491                     this._gapStart += count;
 492                 }
 493             }
 494             this._version++;
 495         }
 496                 /// <summary>
 497                 /// Inserts the elements of a collection into the <see cref="GapBuffer{T}"/> at the specified index.
 498                 /// Consecutive operations at or near previous inserts are optimized.
 499                 /// </summary>
 500                 /// <param name="index">The zero-based index at which the new elements should be inserted.</param>
 501                 /// <param name="collection">The collection whose elements should be inserted into the <see cref="GapBuffer{T}"/>.
 502                 /// The collection itself cannot be null, but it can contain elements that are null, if
 503                 /// type <typeparamref name="T"/> is a reference type.</param>
 504         /// <param name="preallocatCount">The count of collction.count is -1 when this method is slowly</param>
 505                 /// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference.</exception>
 506                 /// <exception cref="ArgumentOutOfRangeException">
 507                 /// <paramref name="index"/> is less than 0.
 508                 /// <para>-or-</para>
 509                 /// <paramref name="index"/> is greater than <see cref="Count"/>.
 510                 /// </exception>
 511         public void InsertRange(int index, IEnumerable<T> collection, int preallocatCount = -1)
 512         {
 513             if (collection == null)
 514                 throw new ArgumentNullException("collection");
 515
 516             if (index < 0 || index > Count)
 517                 throw new ArgumentOutOfRangeException("index", "");
 518
 519             if (preallocatCount == -1)
 520             {
 521                 // Add the items to the buffer one-at-a-time :(
 522                 using (IEnumerator<T> enumerator = collection.GetEnumerator())
 523                 {
 524                     while (enumerator.MoveNext())
 525                     {
 526                         Insert(index, enumerator.Current);
 527                         index++;
 528                     }
 529                 }
 530             }
 531             else if(preallocatCount > 0)
 532             {
 533                 PlaceGapStart(index);
 534                 EnsureGapCapacity(preallocatCount);
 535                 int collectionLength = 0;
 536                 using (IEnumerator<T> enumerator = collection.GetEnumerator())
 537                 {
 538                     while (enumerator.MoveNext())
 539                     {
 540                         this._buffer[index] = enumerator.Current;
 541                         index++;
 542                         collectionLength++;
 543                     }
 544                 }
 545                 this._gapStart += collectionLength;
 546
 547             }
 548             this._version++;
 549         }
 550
 551                 /// <summary>
 552                 /// Removes the first occurrence of a specific object from the <see cref="GapBuffer{T}"/>.
 553                 /// </summary>
 554                 /// <param name="item">The object to remove from the <see cref="GapBuffer{T}"/>. The
 555                 /// value can be null for reference types.</param>
 556                 /// <returns><b>true</b> if <paramref name="item"/> is successfully removed; otherwise,
 557                 /// <b>false</b>. This method also returns <b>false</b> if <paramref name="item"/> was not
 558                 /// found in the <see cref="GapBuffer{T}"/>.</returns>
 559                 public bool Remove(T item)
 560                 {
 561                         // Get the index of the item
 562                         int index = IndexOf(item);
 563                         if (index < 0)
 564                                 return false;
 565
 566                         // Remove the item
 567                         RemoveAt(index);
 568                         return true;
 569                 }
 570
 571
 572                 // Explicit IList implementation
 573                 void IList.Remove(object item)
 574                 {
 575                         if (IsCompatibleObject(item))
 576                                 Remove((T)item);
 577                 }
 578
 579
 580                 /// <summary>
 581                 /// Removes the element at the specified index of the <see cref="GapBuffer{T}"/>.
 582                 /// </summary>
 583                 /// <param name="index">The zero-based index of the element to remove.</param>
 584                 /// <exception cref="ArgumentOutOfRangeException">
 585                 /// <paramref name="index"/> is less than 0.
 586                 /// <para>-or-</para>
 587                 /// <paramref name="index"/> is equal to or greater than <see cref="Count"/>.
 588                 /// </exception>
 589                 public void RemoveAt(int index)
 590                 {
 591                         if (index < 0 || index >= Count)
 592                                 throw new ArgumentOutOfRangeException("index", "");
 593
 594                         // Place the gap at the index and increase the gap size by 1
 595                         PlaceGapStart(index);
 596                         this._buffer[this._gapEnd] = default(T);
 597                         this._gapEnd++;
 598                         this._version++;
 599                 }
 600
 601
 602                 /// <summary>
 603                 /// Removes a range of elements from the <see cref="GapBuffer{T}"/>.
 604                 /// </summary>
 605                 /// <param name="index">The zero-based starting index of the range of elements to remove.</param>
 606                 /// <param name="count">The number of elements to remove.</param>
 607                 /// <exception cref="ArgumentOutOfRangeException">
 608                 /// <paramref name="index"/> is less than 0 or is equal to or greater than <see cref="Count"/>.
 609                 /// <para>-or-</para>
 610                 /// <paramref name="count"/> is less than 0.
 611                 /// <para>-or-</para>
 612                 /// <paramref name="index"/> and <paramref name="count"/> do not denote a valid range of elements in
 613                 /// the <see cref="GapBuffer{T}"/>.
 614                 /// </exception>
 615                 public void RemoveRange(int index, int count)
 616                 {
 617                         int size = Count;
 618
 619                         if (index < 0 || index >= size)
 620                                 throw new ArgumentOutOfRangeException("index", "");
 621
 622                         if (count < 0 || size - index < count)
 623                                 throw new ArgumentOutOfRangeException("count", "");
 624
 625
 626                         // Move the gap over the index and increase the gap size
 627                         // by the number of elements removed. Easy as pie!
 628
 629                         if (count > 0)
 630                         {
 631                                 PlaceGapStart(index);
 632                                 //Array.Clear(this._buffer, this._gapEnd, count);
 633                                 this._gapEnd += count;
 634                                 this._version++;
 635                         }
 636                 }
 637
 638
 639                 /// <summary>
 640                 /// Sets the <see cref="Capacity"/> to the actual number of elements in the <see cref="GapBuffer{T}"/>,
 641                 /// if that number is less than a threshold value.
 642                 /// </summary>
 643                 public void TrimExcess()
 644                 {
 645                         int size = Count;
 646                         int threshold = (int)(_buffer.Length * 0.9);
 647                         if (size < threshold)
 648                         {
 649                                 Capacity = size;
 650                         }
 651                 }
 652
 653
 654                 // Moves the gap start to the given index
 655                 private void PlaceGapStart(int index)
 656                 {
 657                         // Are we already there?
 658                         if (index == this._gapStart)
 659                                 return;
 660
 661                         // Is there even a gap?
 662                         if ((this._gapEnd - this._gapStart) == 0)
 663                         {
 664                                 this._gapStart = index;
 665                                 this._gapEnd = index;
 666                                 return;
 667                         }
 668
 669                         // Which direction do we move the gap?
 670                         if (index < this._gapStart)
 671                         {
 672                                 // Move the gap near (by copying the items at the beginning
 673                                 // of the gap to the end)
 674                                 int count = this._gapStart - index;
 675                                 int deltaCount = (this._gapEnd - this._gapStart < count ? this._gapEnd - this._gapStart : count);
 676                                 Array.Copy(this._buffer, index, this._buffer, this._gapEnd - count, count);
 677                                 this._gapStart -= count;
 678                                 this._gapEnd -= count;
 679
 680                                 // Clear the contents of the gap
 681                                 //Array.Clear(this._buffer, index, deltaCount);
 682                         }
 683                         else
 684                         {
 685                                 // Move the gap far (by copying the items at the end
 686                                 // of the gap to the beginning)
 687                                 int count = index - this._gapStart;
 688                                 int deltaIndex = (index > this._gapEnd ? index : this._gapEnd);
 689                                 Array.Copy(this._buffer, this._gapEnd, this._buffer, this._gapStart, count);
 690                                 this._gapStart += count;
 691                                 this._gapEnd += count;
 692
 693                                 // Clear the contents of the gap
 694                                 //Array.Clear(this._buffer, deltaIndex, this._gapEnd - deltaIndex);
 695                         }
 696                 }
 697
 698
 699                 // Expands the interal array if the required size isn't available
 700                 private void EnsureGapCapacity(int required)
 701                 {
 702                         // Is the available space in the gap?
 703                         if (required > (this._gapEnd - this._gapStart))
 704                         {
 705                                 // Calculate a new size (double the size necessary)
 706                                 int newCapacity = (Count + required) * 2;
 707                                 if (newCapacity < MIN_CAPACITY)
 708                                         newCapacity = MIN_CAPACITY;
 709
 710                                 Capacity = newCapacity;
 711                         }
 712                 }
 713
 714
 715                 private static bool IsCompatibleObject(object value)
 716                 {
 717                         // Ensure the object is compatible with the generic type
 718
 719                         if (!(value is T) && ((value != null) || value is ValueType))
 720                                 return false;
 721
 722                         return true;
 723                 }
 724
 725
 726                 private static void VerifyValueType(object value)
 727                 {
 728                         // Throw an exception if the object is not compatible with
 729                         // the generic type
 730
 731                         if (!IsCompatibleObject(value))
 732                         {
 733                                 throw new ArgumentException("", "value");
 734                         }
 735                 }
 736
 737                 #endregion Methods
 738         }
 739 }