csharp/src/Google.Protobuf/Collections/RepeatedField.cs - third_party/protobuf - Git at Google

 #region Copyright notice and license
 // Protocol Buffers - Google's data interchange format
 // Copyright 2015 Google Inc.  All rights reserved.
 // https://developers.google.com/protocol-buffers/
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 // copyright notice, this list of conditions and the following disclaimer
 // in the documentation and/or other materials provided with the
 // distribution.
 //     * Neither the name of Google Inc. nor the names of its
 // contributors may be used to endorse or promote products derived from
 // this software without specific prior written permission.
 //
 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 #endregion

 using System;
 using System.Collections;
 using System.Collections.Generic;
 using System.IO;
 using System.Security;
 using System.Threading;

 namespace Google.Protobuf.Collections
 {
     /// <summary>
     /// The contents of a repeated field: essentially, a collection with some extra
     /// restrictions (no null values) and capabilities (deep cloning).
     /// </summary>
     /// <remarks>
     /// This implementation does not generally prohibit the use of types which are not
     /// supported by Protocol Buffers but nor does it guarantee that all operations will work in such cases.
     /// </remarks>
     /// <typeparam name="T">The element type of the repeated field.</typeparam>
     public sealed class RepeatedField<T> : IList<T>, IList, IDeepCloneable<RepeatedField<T>>, IEquatable<RepeatedField<T>>
 #if !NET35
         , IReadOnlyList<T>
 #endif
     {
         private static readonly EqualityComparer<T> EqualityComparer = ProtobufEqualityComparers.GetEqualityComparer<T>();
         private static readonly T[] EmptyArray = new T[0];
         private const int MinArraySize = 8;

         private T[] array = EmptyArray;
         private int count = 0;

         /// <summary>
         /// Creates a deep clone of this repeated field.
         /// </summary>
         /// <remarks>
         /// If the field type is
         /// a message type, each element is also cloned; otherwise, it is
         /// assumed that the field type is primitive (including string and
         /// bytes, both of which are immutable) and so a simple copy is
         /// equivalent to a deep clone.
         /// </remarks>
         /// <returns>A deep clone of this repeated field.</returns>
         public RepeatedField<T> Clone()
         {
             RepeatedField<T> clone = new RepeatedField<T>();
             if (array != EmptyArray)
             {
                 clone.array = (T[])array.Clone();
                 IDeepCloneable<T>[] cloneableArray = clone.array as IDeepCloneable<T>[];
                 if (cloneableArray != null)
                 {
                     for (int i = 0; i < count; i++)
                     {
                         clone.array[i] = cloneableArray[i].Clone();
                     }
                 }
             }
             clone.count = count;
             return clone;
         }

         /// <summary>
         /// Adds the entries from the given input stream, decoding them with the specified codec.
         /// </summary>
         /// <param name="input">The input stream to read from.</param>
         /// <param name="codec">The codec to use in order to read each entry.</param>
         public void AddEntriesFrom(CodedInputStream input, FieldCodec<T> codec)
         {
             ParseContext.Initialize(input, out ParseContext ctx);
             try
             {
                 AddEntriesFrom(ref ctx, codec);
             }
             finally
             {
                 ctx.CopyStateTo(input);
             }
         }

         /// <summary>
         /// Adds the entries from the given parse context, decoding them with the specified codec.
         /// </summary>
         /// <param name="ctx">The input to read from.</param>
         /// <param name="codec">The codec to use in order to read each entry.</param>
         [SecuritySafeCritical]
         public void AddEntriesFrom(ref ParseContext ctx, FieldCodec<T> codec)
         {
             // TODO: Inline some of the Add code, so we can avoid checking the size on every
             // iteration.
             uint tag = ctx.state.lastTag;
             var reader = codec.ValueReader;
             // Non-nullable value types can be packed or not.
             if (FieldCodec<T>.IsPackedRepeatedField(tag))
             {
                 int length = ctx.ReadLength();
                 if (length > 0)
                 {
                     int oldLimit = SegmentedBufferHelper.PushLimit(ref ctx.state, length);

                     // If the content is fixed size then we can calculate the length
                     // of the repeated field and pre-initialize the underlying collection.
                     //
                     // Check that the supplied length doesn't exceed the underlying buffer.
                     // That prevents a malicious length from initializing a very large collection.
                     if (codec.FixedSize > 0 && length % codec.FixedSize == 0 && ParsingPrimitives.IsDataAvailable(ref ctx.state, length))
                     {
                         EnsureSize(count + (length / codec.FixedSize));

                         while (!SegmentedBufferHelper.IsReachedLimit(ref ctx.state))
                         {
                             // Only FieldCodecs with a fixed size can reach here, and they are all known
                             // types that don't allow the user to specify a custom reader action.
                             // reader action will never return null.
                             array[count++] = reader(ref ctx);
                         }
                     }
                     else
                     {
                         // Content is variable size so add until we reach the limit.
                         while (!SegmentedBufferHelper.IsReachedLimit(ref ctx.state))
                         {
                             Add(reader(ref ctx));
                         }
                     }
                     SegmentedBufferHelper.PopLimit(ref ctx.state, oldLimit);
                 }
                 // Empty packed field. Odd, but valid - just ignore.
             }
             else
             {
                 // Not packed... (possibly not packable)
                 do
                 {
                     Add(reader(ref ctx));
                 } while (ParsingPrimitives.MaybeConsumeTag(ref ctx.buffer, ref ctx.state, tag));
             }
         }

         /// <summary>
         /// Calculates the size of this collection based on the given codec.
         /// </summary>
         /// <param name="codec">The codec to use when encoding each field.</param>
         /// <returns>The number of bytes that would be written to an output by one of the <c>WriteTo</c> methods,
         /// using the same codec.</returns>
         public int CalculateSize(FieldCodec<T> codec)
         {
             if (count == 0)
             {
                 return 0;
             }
             uint tag = codec.Tag;
             if (codec.PackedRepeatedField)
             {
                 int dataSize = CalculatePackedDataSize(codec);
                 return CodedOutputStream.ComputeRawVarint32Size(tag) +
                     CodedOutputStream.ComputeLengthSize(dataSize) +
                     dataSize;
             }
             else
             {
                 var sizeCalculator = codec.ValueSizeCalculator;
                 int size = count * CodedOutputStream.ComputeRawVarint32Size(tag);
                 if (codec.EndTag != 0)
                 {
                     size += count * CodedOutputStream.ComputeRawVarint32Size(codec.EndTag);
                 }
                 for (int i = 0; i < count; i++)
                 {
                     size += sizeCalculator(array[i]);
                 }
                 return size;
             }
         }

         private int CalculatePackedDataSize(FieldCodec<T> codec)
         {
             int fixedSize = codec.FixedSize;
             if (fixedSize == 0)
             {
                 var calculator = codec.ValueSizeCalculator;
                 int tmp = 0;
                 for (int i = 0; i < count; i++)
                 {
                     tmp += calculator(array[i]);
                 }
                 return tmp;
             }
             else
             {
                 return fixedSize * Count;
             }
         }

         /// <summary>
         /// Writes the contents of this collection to the given <see cref="CodedOutputStream"/>,
         /// encoding each value using the specified codec.
         /// </summary>
         /// <param name="output">The output stream to write to.</param>
         /// <param name="codec">The codec to use when encoding each value.</param>
         public void WriteTo(CodedOutputStream output, FieldCodec<T> codec)
         {
             WriteContext.Initialize(output, out WriteContext ctx);
             try
             {
                 WriteTo(ref ctx, codec);
             }
             finally
             {
                 ctx.CopyStateTo(output);
             }
         }

         /// <summary>
         /// Writes the contents of this collection to the given write context,
         /// encoding each value using the specified codec.
         /// </summary>
         /// <param name="ctx">The write context to write to.</param>
         /// <param name="codec">The codec to use when encoding each value.</param>
         [SecuritySafeCritical]
         public void WriteTo(ref WriteContext ctx, FieldCodec<T> codec)
         {
             if (count == 0)
             {
                 return;
             }
             var writer = codec.ValueWriter;
             var tag = codec.Tag;
             if (codec.PackedRepeatedField)
             {
                 // Packed primitive type
                 int size = CalculatePackedDataSize(codec);
                 ctx.WriteTag(tag);
                 ctx.WriteLength(size);
                 for (int i = 0; i < count; i++)
                 {
                     writer(ref ctx, array[i]);
                 }
             }
             else
             {
                 // Not packed: a simple tag/value pair for each value.
                 // Can't use codec.WriteTagAndValue, as that omits default values.
                 for (int i = 0; i < count; i++)
                 {
                     ctx.WriteTag(tag);
                     writer(ref ctx, array[i]);
                     if (codec.EndTag != 0)
                     {
                         ctx.WriteTag(codec.EndTag);
                     }
                 }
             }
         }

         /// <summary>
         /// Gets and sets the capacity of the RepeatedField's internal array.  WHen set, the internal array is reallocated to the given capacity.
         /// <exception cref="ArgumentOutOfRangeException">The new value is less than Count -or- when Count is less than 0.</exception>
         /// </summary>
         public int Capacity
         {
             get { return array.Length; }
             set
             {
                 if (value < count)
                 {
                     throw new ArgumentOutOfRangeException("Capacity", value,
                         $"Cannot set Capacity to a value smaller than the current item count, {count}");
                 }

                 if (value >= 0 && value != array.Length)
                 {
                     SetSize(value);
                 }
             }
         }

         // May increase the size of the internal array, but will never shrink it.
         private void EnsureSize(int size)
         {
             if (array.Length < size)
             {
                 size = Math.Max(size, MinArraySize);
                 int newSize = Math.Max(array.Length * 2, size);
                 SetSize(newSize);
             }
         }

         // Sets the internal array to an exact size.
         private void SetSize(int size)
         {
             if (size != array.Length)
             {
                 var tmp = new T[size];
                 Array.Copy(array, 0, tmp, 0, count);
                 array = tmp;
             }
         }

         /// <summary>
         /// Adds the specified item to the collection.
         /// </summary>
         /// <param name="item">The item to add.</param>
         public void Add(T item)
         {
             ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
             EnsureSize(count + 1);
             array[count++] = item;
         }

         /// <summary>
         /// Removes all items from the collection.
         /// </summary>
         public void Clear()
         {
             array = EmptyArray;
             count = 0;
         }

         /// <summary>
         /// Determines whether this collection contains the given item.
         /// </summary>
         /// <param name="item">The item to find.</param>
         /// <returns><c>true</c> if this collection contains the given item; <c>false</c> otherwise.</returns>
         public bool Contains(T item)
         {
             return IndexOf(item) != -1;
         }

         /// <summary>
         /// Copies this collection to the given array.
         /// </summary>
         /// <param name="array">The array to copy to.</param>
         /// <param name="arrayIndex">The first index of the array to copy to.</param>
         public void CopyTo(T[] array, int arrayIndex)
         {
             Array.Copy(this.array, 0, array, arrayIndex, count);
         }

         /// <summary>
         /// Removes the specified item from the collection
         /// </summary>
         /// <param name="item">The item to remove.</param>
         /// <returns><c>true</c> if the item was found and removed; <c>false</c> otherwise.</returns>
         public bool Remove(T item)
         {
             int index = IndexOf(item);
             if (index == -1)
             {
                 return false;
             }
             Array.Copy(array, index + 1, array, index, count - index - 1);
             count--;
             array[count] = default(T);
             return true;
         }

         /// <summary>
         /// Gets the number of elements contained in the collection.
         /// </summary>
         public int Count => count;

         /// <summary>
         /// Gets a value indicating whether the collection is read-only.
         /// </summary>
         public bool IsReadOnly => false;

         /// <summary>
         /// Adds all of the specified values into this collection.
         /// </summary>
         /// <param name="values">The values to add to this collection.</param>
         public void AddRange(IEnumerable<T> values)
         {
             ProtoPreconditions.CheckNotNull(values, nameof(values));

             // Optimization 1: If the collection we're adding is already a RepeatedField<T>,
             // we know the values are valid.
             var otherRepeatedField = values as RepeatedField<T>;
             if (otherRepeatedField != null)
             {
                 EnsureSize(count + otherRepeatedField.count);
                 Array.Copy(otherRepeatedField.array, 0, array, count, otherRepeatedField.count);
                 count += otherRepeatedField.count;
                 return;
             }

             // Optimization 2: The collection is an ICollection, so we can expand
             // just once and ask the collection to copy itself into the array.
             var collection = values as ICollection;
             if (collection != null)
             {
                 var extraCount = collection.Count;
                 // For reference types and nullable value types, we need to check that there are no nulls
                 // present. (This isn't a thread-safe approach, but we don't advertise this is thread-safe.)
                 // We expect the JITter to optimize this test to true/false, so it's effectively conditional
                 // specialization.
                 if (default(T) == null)
                 {
                     // TODO: Measure whether iterating once to check and then letting the collection copy
                     // itself is faster or slower than iterating and adding as we go. For large
                     // collections this will not be great in terms of cache usage... but the optimized
                     // copy may be significantly faster than doing it one at a time.
                     foreach (var item in collection)
                     {
                         if (item == null)
                         {
                             throw new ArgumentException("Sequence contained null element", nameof(values));
                         }
                     }
                 }
                 EnsureSize(count + extraCount);
                 collection.CopyTo(array, count);
                 count += extraCount;
                 return;
             }

             // We *could* check for ICollection<T> as well, but very very few collections implement
             // ICollection<T> but not ICollection. (HashSet<T> does, for one...)

             // Fall back to a slower path of adding items one at a time.
             foreach (T item in values)
             {
                 Add(item);
             }
         }

         /// <summary>
         /// Adds all of the specified values into this collection. This method is present to
         /// allow repeated fields to be constructed from queries within collection initializers.
         /// Within non-collection-initializer code, consider using the equivalent <see cref="AddRange"/>
         /// method instead for clarity.
         /// </summary>
         /// <param name="values">The values to add to this collection.</param>
         public void Add(IEnumerable<T> values)
         {
             AddRange(values);
         }

         /// <summary>
         /// Returns an enumerator that iterates through the collection.
         /// </summary>
         /// <returns>
         /// An enumerator that can be used to iterate through the collection.
         /// </returns>
         public IEnumerator<T> GetEnumerator()
         {
             for (int i = 0; i < count; i++)
             {
                 yield return array[i];
             }
         }

         /// <summary>
         /// Determines whether the specified <see cref="System.Object" />, is equal to this instance.
         /// </summary>
         /// <param name="obj">The <see cref="System.Object" /> to compare with this instance.</param>
         /// <returns>
         ///   <c>true</c> if the specified <see cref="System.Object" /> is equal to this instance; otherwise, <c>false</c>.
         /// </returns>
         public override bool Equals(object obj)
         {
             return Equals(obj as RepeatedField<T>);
         }

         /// <summary>
         /// Returns an enumerator that iterates through a collection.
         /// </summary>
         /// <returns>
         /// An <see cref="T:System.Collections.IEnumerator" /> object that can be used to iterate through the collection.
         /// </returns>
         IEnumerator IEnumerable.GetEnumerator()
         {
             return GetEnumerator();
         }

         /// <summary>
         /// Returns a hash code for this instance.
         /// </summary>
         /// <returns>
         /// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table.
         /// </returns>
         public override int GetHashCode()
         {
             int hash = 0;
             for (int i = 0; i < count; i++)
             {
                 hash = hash * 31 + array[i].GetHashCode();
             }
             return hash;
         }

         /// <summary>
         /// Compares this repeated field with another for equality.
         /// </summary>
         /// <param name="other">The repeated field to compare this with.</param>
         /// <returns><c>true</c> if <paramref name="other"/> refers to an equal repeated field; <c>false</c> otherwise.</returns>
         public bool Equals(RepeatedField<T> other)
         {
             if (ReferenceEquals(other, null))
             {
                 return false;
             }
             if (ReferenceEquals(other, this))
             {
                 return true;
             }
             if (other.Count != this.Count)
             {
                 return false;
             }
             EqualityComparer<T> comparer = EqualityComparer;
             for (int i = 0; i < count; i++)
             {
                 if (!comparer.Equals(array[i], other.array[i]))
                 {
                     return false;
                 }
             }
             return true;
         }

         /// <summary>
         /// Returns the index of the given item within the collection, or -1 if the item is not
         /// present.
         /// </summary>
         /// <param name="item">The item to find in the collection.</param>
         /// <returns>The zero-based index of the item, or -1 if it is not found.</returns>
         public int IndexOf(T item)
         {
             ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
             EqualityComparer<T> comparer = EqualityComparer;
             for (int i = 0; i < count; i++)
             {
                 if (comparer.Equals(array[i], item))
                 {
                     return i;
                 }
             }
             return -1;
         }

         /// <summary>
         /// Inserts the given item at the specified index.
         /// </summary>
         /// <param name="index">The index at which to insert the item.</param>
         /// <param name="item">The item to insert.</param>
         public void Insert(int index, T item)
         {
             ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
             if (index < 0 || index > count)
             {
                 throw new ArgumentOutOfRangeException(nameof(index));
             }
             EnsureSize(count + 1);
             Array.Copy(array, index, array, index + 1, count - index);
             array[index] = item;
             count++;
         }

         /// <summary>
         /// Removes the item at the given index.
         /// </summary>
         /// <param name="index">The zero-based index of the item to remove.</param>
         public void RemoveAt(int index)
         {
             if (index < 0 || index >= count)
             {
                 throw new ArgumentOutOfRangeException(nameof(index));
             }
             Array.Copy(array, index + 1, array, index, count - index - 1);
             count--;
             array[count] = default(T);
         }

         /// <summary>
         /// Returns a string representation of this repeated field, in the same
         /// way as it would be represented by the default JSON formatter.
         /// </summary>
         public override string ToString()
         {
             var writer = new StringWriter();
             JsonFormatter.Default.WriteList(writer, this);
             return writer.ToString();
         }

         /// <summary>
         /// Gets or sets the item at the specified index.
         /// </summary>
         /// <value>
         /// The element at the specified index.
         /// </value>
         /// <param name="index">The zero-based index of the element to get or set.</param>
         /// <returns>The item at the specified index.</returns>
         public T this[int index]
         {
             get
             {
                 if (index < 0 || index >= count)
                 {
                     throw new ArgumentOutOfRangeException(nameof(index));
                 }
                 return array[index];
             }
             set
             {
                 if (index < 0 || index >= count)
                 {
                     throw new ArgumentOutOfRangeException(nameof(index));
                 }
                 ProtoPreconditions.CheckNotNullUnconstrained(value, nameof(value));
                 array[index] = value;
             }
         }

         #region Explicit interface implementation for IList and ICollection.
         bool IList.IsFixedSize => false;

         void ICollection.CopyTo(Array array, int index)
         {
             Array.Copy(this.array, 0, array, index, count);
         }

         bool ICollection.IsSynchronized => false;

         object ICollection.SyncRoot => this;

         object IList.this[int index]
         {
             get { return this[index]; }
             set { this[index] = (T)value; }
         }

         int IList.Add(object value)
         {
             Add((T) value);
             return count - 1;
         }

         bool IList.Contains(object value)
         {
             return (value is T && Contains((T)value));
         }

         int IList.IndexOf(object value)
         {
             if (!(value is T))
             {
                 return -1;
             }
             return IndexOf((T)value);
         }

         void IList.Insert(int index, object value)
         {
             Insert(index, (T) value);
         }

         void IList.Remove(object value)
         {
             if (!(value is T))
             {
                 return;
             }
             Remove((T)value);
         }
         #endregion
     }
 }
	#region Copyright notice and license
	// Protocol Buffers - Google's data interchange format
	// Copyright 2015 Google Inc. All rights reserved.
	// https://developers.google.com/protocol-buffers/
	//
	// Redistribution and use in source and binary forms, with or without
	// modification, are permitted provided that the following conditions are
	// met:
	//
	// * Redistributions of source code must retain the above copyright
	// notice, this list of conditions and the following disclaimer.
	// * Redistributions in binary form must reproduce the above
	// copyright notice, this list of conditions and the following disclaimer
	// in the documentation and/or other materials provided with the
	// distribution.
	// * Neither the name of Google Inc. nor the names of its
	// contributors may be used to endorse or promote products derived from
	// this software without specific prior written permission.
	//
	// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	#endregion

	using System;
	using System.Collections;
	using System.Collections.Generic;
	using System.IO;
	using System.Security;
	using System.Threading;

	namespace Google.Protobuf.Collections
	{
	/// <summary>
	/// The contents of a repeated field: essentially, a collection with some extra
	/// restrictions (no null values) and capabilities (deep cloning).
	/// </summary>
	/// <remarks>
	/// This implementation does not generally prohibit the use of types which are not
	/// supported by Protocol Buffers but nor does it guarantee that all operations will work in such cases.
	/// </remarks>
	/// <typeparam name="T">The element type of the repeated field.</typeparam>
	public sealed class RepeatedField<T> : IList<T>, IList, IDeepCloneable<RepeatedField<T>>, IEquatable<RepeatedField<T>>
	#if !NET35
	, IReadOnlyList<T>
	#endif
	{
	private static readonly EqualityComparer<T> EqualityComparer = ProtobufEqualityComparers.GetEqualityComparer<T>();
	private static readonly T[] EmptyArray = new T[0];
	private const int MinArraySize = 8;

	private T[] array = EmptyArray;
	private int count = 0;

	/// <summary>
	/// Creates a deep clone of this repeated field.
	/// </summary>
	/// <remarks>
	/// If the field type is
	/// a message type, each element is also cloned; otherwise, it is
	/// assumed that the field type is primitive (including string and
	/// bytes, both of which are immutable) and so a simple copy is
	/// equivalent to a deep clone.
	/// </remarks>
	/// <returns>A deep clone of this repeated field.</returns>
	public RepeatedField<T> Clone()
	{
	RepeatedField<T> clone = new RepeatedField<T>();
	if (array != EmptyArray)
	{
	clone.array = (T[])array.Clone();
	IDeepCloneable<T>[] cloneableArray = clone.array as IDeepCloneable<T>[];
	if (cloneableArray != null)
	{
	for (int i = 0; i < count; i++)
	{
	clone.array[i] = cloneableArray[i].Clone();
	}
	}
	}
	clone.count = count;
	return clone;
	}

	/// <summary>
	/// Adds the entries from the given input stream, decoding them with the specified codec.
	/// </summary>
	/// <param name="input">The input stream to read from.</param>
	/// <param name="codec">The codec to use in order to read each entry.</param>
	public void AddEntriesFrom(CodedInputStream input, FieldCodec<T> codec)
	{
	ParseContext.Initialize(input, out ParseContext ctx);
	try
	{
	AddEntriesFrom(ref ctx, codec);
	}
	finally
	{
	ctx.CopyStateTo(input);
	}
	}

	/// <summary>
	/// Adds the entries from the given parse context, decoding them with the specified codec.
	/// </summary>
	/// <param name="ctx">The input to read from.</param>
	/// <param name="codec">The codec to use in order to read each entry.</param>
	[SecuritySafeCritical]
	public void AddEntriesFrom(ref ParseContext ctx, FieldCodec<T> codec)
	{
	// TODO: Inline some of the Add code, so we can avoid checking the size on every
	// iteration.
	uint tag = ctx.state.lastTag;
	var reader = codec.ValueReader;
	// Non-nullable value types can be packed or not.
	if (FieldCodec<T>.IsPackedRepeatedField(tag))
	{
	int length = ctx.ReadLength();
	if (length > 0)
	{
	int oldLimit = SegmentedBufferHelper.PushLimit(ref ctx.state, length);

	// If the content is fixed size then we can calculate the length
	// of the repeated field and pre-initialize the underlying collection.
	//
	// Check that the supplied length doesn't exceed the underlying buffer.
	// That prevents a malicious length from initializing a very large collection.
	if (codec.FixedSize > 0 && length % codec.FixedSize == 0 && ParsingPrimitives.IsDataAvailable(ref ctx.state, length))
	{
	EnsureSize(count + (length / codec.FixedSize));

	while (!SegmentedBufferHelper.IsReachedLimit(ref ctx.state))
	{
	// Only FieldCodecs with a fixed size can reach here, and they are all known
	// types that don't allow the user to specify a custom reader action.
	// reader action will never return null.
	array[count++] = reader(ref ctx);
	}
	}
	else
	{
	// Content is variable size so add until we reach the limit.
	while (!SegmentedBufferHelper.IsReachedLimit(ref ctx.state))
	{
	Add(reader(ref ctx));
	}
	}
	SegmentedBufferHelper.PopLimit(ref ctx.state, oldLimit);
	}
	// Empty packed field. Odd, but valid - just ignore.
	}
	else
	{
	// Not packed... (possibly not packable)
	do
	{
	Add(reader(ref ctx));
	} while (ParsingPrimitives.MaybeConsumeTag(ref ctx.buffer, ref ctx.state, tag));
	}
	}

	/// <summary>
	/// Calculates the size of this collection based on the given codec.
	/// </summary>
	/// <param name="codec">The codec to use when encoding each field.</param>
	/// <returns>The number of bytes that would be written to an output by one of the <c>WriteTo</c> methods,
	/// using the same codec.</returns>
	public int CalculateSize(FieldCodec<T> codec)
	{
	if (count == 0)
	{
	return 0;
	}
	uint tag = codec.Tag;
	if (codec.PackedRepeatedField)
	{
	int dataSize = CalculatePackedDataSize(codec);
	return CodedOutputStream.ComputeRawVarint32Size(tag) +
	CodedOutputStream.ComputeLengthSize(dataSize) +
	dataSize;
	}
	else
	{
	var sizeCalculator = codec.ValueSizeCalculator;
	int size = count * CodedOutputStream.ComputeRawVarint32Size(tag);
	if (codec.EndTag != 0)
	{
	size += count * CodedOutputStream.ComputeRawVarint32Size(codec.EndTag);
	}
	for (int i = 0; i < count; i++)
	{
	size += sizeCalculator(array[i]);
	}
	return size;
	}
	}

	private int CalculatePackedDataSize(FieldCodec<T> codec)
	{
	int fixedSize = codec.FixedSize;
	if (fixedSize == 0)
	{
	var calculator = codec.ValueSizeCalculator;
	int tmp = 0;
	for (int i = 0; i < count; i++)
	{
	tmp += calculator(array[i]);
	}
	return tmp;
	}
	else
	{
	return fixedSize * Count;
	}
	}

	/// <summary>
	/// Writes the contents of this collection to the given <see cref="CodedOutputStream"/>,
	/// encoding each value using the specified codec.
	/// </summary>
	/// <param name="output">The output stream to write to.</param>
	/// <param name="codec">The codec to use when encoding each value.</param>
	public void WriteTo(CodedOutputStream output, FieldCodec<T> codec)
	{
	WriteContext.Initialize(output, out WriteContext ctx);
	try
	{
	WriteTo(ref ctx, codec);
	}
	finally
	{
	ctx.CopyStateTo(output);
	}
	}

	/// <summary>
	/// Writes the contents of this collection to the given write context,
	/// encoding each value using the specified codec.
	/// </summary>
	/// <param name="ctx">The write context to write to.</param>
	/// <param name="codec">The codec to use when encoding each value.</param>
	[SecuritySafeCritical]
	public void WriteTo(ref WriteContext ctx, FieldCodec<T> codec)
	{
	if (count == 0)
	{
	return;
	}
	var writer = codec.ValueWriter;
	var tag = codec.Tag;
	if (codec.PackedRepeatedField)
	{
	// Packed primitive type
	int size = CalculatePackedDataSize(codec);
	ctx.WriteTag(tag);
	ctx.WriteLength(size);
	for (int i = 0; i < count; i++)
	{
	writer(ref ctx, array[i]);
	}
	}
	else
	{
	// Not packed: a simple tag/value pair for each value.
	// Can't use codec.WriteTagAndValue, as that omits default values.
	for (int i = 0; i < count; i++)
	{
	ctx.WriteTag(tag);
	writer(ref ctx, array[i]);
	if (codec.EndTag != 0)
	{
	ctx.WriteTag(codec.EndTag);
	}
	}
	}
	}

	/// <summary>
	/// Gets and sets the capacity of the RepeatedField's internal array. WHen set, the internal array is reallocated to the given capacity.
	/// <exception cref="ArgumentOutOfRangeException">The new value is less than Count -or- when Count is less than 0.</exception>
	/// </summary>
	public int Capacity
	{
	get { return array.Length; }
	set
	{
	if (value < count)
	{
	throw new ArgumentOutOfRangeException("Capacity", value,
	$"Cannot set Capacity to a value smaller than the current item count, {count}");
	}

	if (value >= 0 && value != array.Length)
	{
	SetSize(value);
	}
	}
	}

	// May increase the size of the internal array, but will never shrink it.
	private void EnsureSize(int size)
	{
	if (array.Length < size)
	{
	size = Math.Max(size, MinArraySize);
	int newSize = Math.Max(array.Length * 2, size);
	SetSize(newSize);
	}
	}

	// Sets the internal array to an exact size.
	private void SetSize(int size)
	{
	if (size != array.Length)
	{
	var tmp = new T[size];
	Array.Copy(array, 0, tmp, 0, count);
	array = tmp;
	}
	}

	/// <summary>
	/// Adds the specified item to the collection.
	/// </summary>
	/// <param name="item">The item to add.</param>
	public void Add(T item)
	{
	ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
	EnsureSize(count + 1);
	array[count++] = item;
	}

	/// <summary>
	/// Removes all items from the collection.
	/// </summary>
	public void Clear()
	{
	array = EmptyArray;
	count = 0;
	}

	/// <summary>
	/// Determines whether this collection contains the given item.
	/// </summary>
	/// <param name="item">The item to find.</param>
	/// <returns><c>true</c> if this collection contains the given item; <c>false</c> otherwise.</returns>
	public bool Contains(T item)
	{
	return IndexOf(item) != -1;
	}

	/// <summary>
	/// Copies this collection to the given array.
	/// </summary>
	/// <param name="array">The array to copy to.</param>
	/// <param name="arrayIndex">The first index of the array to copy to.</param>
	public void CopyTo(T[] array, int arrayIndex)
	{
	Array.Copy(this.array, 0, array, arrayIndex, count);
	}

	/// <summary>
	/// Removes the specified item from the collection
	/// </summary>
	/// <param name="item">The item to remove.</param>
	/// <returns><c>true</c> if the item was found and removed; <c>false</c> otherwise.</returns>
	public bool Remove(T item)
	{
	int index = IndexOf(item);
	if (index == -1)
	{
	return false;
	}
	Array.Copy(array, index + 1, array, index, count - index - 1);
	count--;
	array[count] = default(T);
	return true;
	}

	/// <summary>
	/// Gets the number of elements contained in the collection.
	/// </summary>
	public int Count => count;

	/// <summary>
	/// Gets a value indicating whether the collection is read-only.
	/// </summary>
	public bool IsReadOnly => false;

	/// <summary>
	/// Adds all of the specified values into this collection.
	/// </summary>
	/// <param name="values">The values to add to this collection.</param>
	public void AddRange(IEnumerable<T> values)
	{
	ProtoPreconditions.CheckNotNull(values, nameof(values));

	// Optimization 1: If the collection we're adding is already a RepeatedField<T>,
	// we know the values are valid.
	var otherRepeatedField = values as RepeatedField<T>;
	if (otherRepeatedField != null)
	{
	EnsureSize(count + otherRepeatedField.count);
	Array.Copy(otherRepeatedField.array, 0, array, count, otherRepeatedField.count);
	count += otherRepeatedField.count;
	return;
	}

	// Optimization 2: The collection is an ICollection, so we can expand
	// just once and ask the collection to copy itself into the array.
	var collection = values as ICollection;
	if (collection != null)
	{
	var extraCount = collection.Count;
	// For reference types and nullable value types, we need to check that there are no nulls
	// present. (This isn't a thread-safe approach, but we don't advertise this is thread-safe.)
	// We expect the JITter to optimize this test to true/false, so it's effectively conditional
	// specialization.
	if (default(T) == null)
	{
	// TODO: Measure whether iterating once to check and then letting the collection copy
	// itself is faster or slower than iterating and adding as we go. For large
	// collections this will not be great in terms of cache usage... but the optimized
	// copy may be significantly faster than doing it one at a time.
	foreach (var item in collection)
	{
	if (item == null)
	{
	throw new ArgumentException("Sequence contained null element", nameof(values));
	}
	}
	}
	EnsureSize(count + extraCount);
	collection.CopyTo(array, count);
	count += extraCount;
	return;
	}

	// We could check for ICollection<T> as well, but very very few collections implement
	// ICollection<T> but not ICollection. (HashSet<T> does, for one...)

	// Fall back to a slower path of adding items one at a time.
	foreach (T item in values)
	{
	Add(item);
	}
	}

	/// <summary>
	/// Adds all of the specified values into this collection. This method is present to
	/// allow repeated fields to be constructed from queries within collection initializers.
	/// Within non-collection-initializer code, consider using the equivalent <see cref="AddRange"/>
	/// method instead for clarity.
	/// </summary>
	/// <param name="values">The values to add to this collection.</param>
	public void Add(IEnumerable<T> values)
	{
	AddRange(values);
	}

	/// <summary>
	/// Returns an enumerator that iterates through the collection.
	/// </summary>
	/// <returns>
	/// An enumerator that can be used to iterate through the collection.
	/// </returns>
	public IEnumerator<T> GetEnumerator()
	{
	for (int i = 0; i < count; i++)
	{
	yield return array[i];
	}
	}

	/// <summary>
	/// Determines whether the specified <see cref="System.Object" />, is equal to this instance.
	/// </summary>
	/// <param name="obj">The <see cref="System.Object" /> to compare with this instance.</param>
	/// <returns>
	/// <c>true</c> if the specified <see cref="System.Object" /> is equal to this instance; otherwise, <c>false</c>.
	/// </returns>
	public override bool Equals(object obj)
	{
	return Equals(obj as RepeatedField<T>);
	}

	/// <summary>
	/// Returns an enumerator that iterates through a collection.
	/// </summary>
	/// <returns>
	/// An <see cref="T:System.Collections.IEnumerator" /> object that can be used to iterate through the collection.
	/// </returns>
	IEnumerator IEnumerable.GetEnumerator()
	{
	return GetEnumerator();
	}

	/// <summary>
	/// Returns a hash code for this instance.
	/// </summary>
	/// <returns>
	/// A hash code for this instance, suitable for use in hashing algorithms and data structures like a hash table.
	/// </returns>
	public override int GetHashCode()
	{
	int hash = 0;
	for (int i = 0; i < count; i++)
	{
	hash = hash * 31 + array[i].GetHashCode();
	}
	return hash;
	}

	/// <summary>
	/// Compares this repeated field with another for equality.
	/// </summary>
	/// <param name="other">The repeated field to compare this with.</param>
	/// <returns><c>true</c> if <paramref name="other"/> refers to an equal repeated field; <c>false</c> otherwise.</returns>
	public bool Equals(RepeatedField<T> other)
	{
	if (ReferenceEquals(other, null))
	{
	return false;
	}
	if (ReferenceEquals(other, this))
	{
	return true;
	}
	if (other.Count != this.Count)
	{
	return false;
	}
	EqualityComparer<T> comparer = EqualityComparer;
	for (int i = 0; i < count; i++)
	{
	if (!comparer.Equals(array[i], other.array[i]))
	{
	return false;
	}
	}
	return true;
	}

	/// <summary>
	/// Returns the index of the given item within the collection, or -1 if the item is not
	/// present.
	/// </summary>
	/// <param name="item">The item to find in the collection.</param>
	/// <returns>The zero-based index of the item, or -1 if it is not found.</returns>
	public int IndexOf(T item)
	{
	ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
	EqualityComparer<T> comparer = EqualityComparer;
	for (int i = 0; i < count; i++)
	{
	if (comparer.Equals(array[i], item))
	{
	return i;
	}
	}
	return -1;
	}

	/// <summary>
	/// Inserts the given item at the specified index.
	/// </summary>
	/// <param name="index">The index at which to insert the item.</param>
	/// <param name="item">The item to insert.</param>
	public void Insert(int index, T item)
	{
	ProtoPreconditions.CheckNotNullUnconstrained(item, nameof(item));
	if (index < 0 \|\| index > count)
	{
	throw new ArgumentOutOfRangeException(nameof(index));
	}
	EnsureSize(count + 1);
	Array.Copy(array, index, array, index + 1, count - index);
	array[index] = item;
	count++;
	}

	/// <summary>
	/// Removes the item at the given index.
	/// </summary>
	/// <param name="index">The zero-based index of the item to remove.</param>
	public void RemoveAt(int index)
	{
	if (index < 0 \|\| index >= count)
	{
	throw new ArgumentOutOfRangeException(nameof(index));
	}
	Array.Copy(array, index + 1, array, index, count - index - 1);
	count--;
	array[count] = default(T);
	}

	/// <summary>
	/// Returns a string representation of this repeated field, in the same
	/// way as it would be represented by the default JSON formatter.
	/// </summary>
	public override string ToString()
	{
	var writer = new StringWriter();
	JsonFormatter.Default.WriteList(writer, this);
	return writer.ToString();
	}

	/// <summary>
	/// Gets or sets the item at the specified index.
	/// </summary>
	/// <value>
	/// The element at the specified index.
	/// </value>
	/// <param name="index">The zero-based index of the element to get or set.</param>
	/// <returns>The item at the specified index.</returns>
	public T this[int index]
	{
	get
	{
	if (index < 0 \|\| index >= count)
	{
	throw new ArgumentOutOfRangeException(nameof(index));
	}
	return array[index];
	}
	set
	{
	if (index < 0 \|\| index >= count)
	{
	throw new ArgumentOutOfRangeException(nameof(index));
	}
	ProtoPreconditions.CheckNotNullUnconstrained(value, nameof(value));
	array[index] = value;
	}
	}

	#region Explicit interface implementation for IList and ICollection.
	bool IList.IsFixedSize => false;

	void ICollection.CopyTo(Array array, int index)
	{
	Array.Copy(this.array, 0, array, index, count);
	}

	bool ICollection.IsSynchronized => false;

	object ICollection.SyncRoot => this;

	object IList.this[int index]
	{
	get { return this[index]; }
	set { this[index] = (T)value; }
	}

	int IList.Add(object value)
	{
	Add((T) value);
	return count - 1;
	}

	bool IList.Contains(object value)
	{
	return (value is T && Contains((T)value));
	}

	int IList.IndexOf(object value)
	{
	if (!(value is T))
	{
	return -1;
	}
	return IndexOf((T)value);
	}

	void IList.Insert(int index, object value)
	{
	Insert(index, (T) value);
	}

	void IList.Remove(object value)
	{
	if (!(value is T))
	{
	return;
	}
	Remove((T)value);
	}
	#endregion
	}
	}