|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using System.Collections.Generic;
using System.Text;
namespace System.ServiceModel.Channels
{
internal abstract class SequenceRangeCollection
{
private static readonly LowerComparer s_lowerComparer = new LowerComparer();
private static readonly UpperComparer s_upperComparer = new UpperComparer();
public static SequenceRangeCollection Empty { get; } = new EmptyRangeCollection();
public abstract SequenceRange this[int index] { get; }
public abstract int Count { get; }
public abstract bool Contains(long number);
public abstract SequenceRangeCollection MergeWith(long number);
public abstract SequenceRangeCollection MergeWith(SequenceRange range);
private static SequenceRangeCollection GeneralCreate(SequenceRange[] sortedRanges)
{
if (sortedRanges.Length == 0)
{
return Empty;
}
else if (sortedRanges.Length == 1)
{
return new SingleItemRangeCollection(sortedRanges[0]);
}
else
{
return new MultiItemRangeCollection(sortedRanges);
}
}
private static SequenceRangeCollection GeneralMerge(SequenceRange[] sortedRanges, SequenceRange range)
{
if (sortedRanges.Length == 0)
{
return new SingleItemRangeCollection(range);
}
int lowerBound;
if (sortedRanges.Length == 1)
{
// Avoid performance hit of binary search in single range case
if (range.Lower == sortedRanges[0].Upper)
{
lowerBound = 0;
}
else if (range.Lower < sortedRanges[0].Upper)
{
lowerBound = ~0;
}
else
{
lowerBound = ~1;
}
}
else
{
lowerBound = Array.BinarySearch(sortedRanges, new SequenceRange(range.Lower), s_upperComparer);
}
if (lowerBound < 0)
{
lowerBound = ~lowerBound;
if ((lowerBound > 0) && (sortedRanges[lowerBound - 1].Upper == range.Lower - 1))
{
lowerBound--;
}
if (lowerBound == sortedRanges.Length)
{
SequenceRange[] returnedRanges = new SequenceRange[sortedRanges.Length + 1];
Array.Copy(sortedRanges, returnedRanges, sortedRanges.Length);
returnedRanges[sortedRanges.Length] = range;
return GeneralCreate(returnedRanges);
}
}
int upperBound;
if (sortedRanges.Length == 1)
{
// Avoid performance hit of binary search in single range case
if (range.Upper == sortedRanges[0].Lower)
{
upperBound = 0;
}
else if (range.Upper < sortedRanges[0].Lower)
{
upperBound = ~0;
}
else
{
upperBound = ~1;
}
}
else
{
upperBound = Array.BinarySearch(sortedRanges, new SequenceRange(range.Upper), s_lowerComparer);
}
if (upperBound < 0)
{
upperBound = ~upperBound;
if (upperBound > 0)
{
if ((upperBound == sortedRanges.Length) || (sortedRanges[upperBound].Lower != range.Upper + 1))
{
upperBound--;
}
}
else if (sortedRanges[0].Lower > range.Upper + 1)
{
SequenceRange[] returnedRanges = new SequenceRange[sortedRanges.Length + 1];
Array.Copy(sortedRanges, 0, returnedRanges, 1, sortedRanges.Length);
returnedRanges[0] = range;
return GeneralCreate(returnedRanges);
}
}
long newLower = (range.Lower < sortedRanges[lowerBound].Lower) ? range.Lower : sortedRanges[lowerBound].Lower;
long newUpper = (range.Upper > sortedRanges[upperBound].Upper) ? range.Upper : sortedRanges[upperBound].Upper;
int rangesRemoved = upperBound - lowerBound + 1;
int rangesRemaining = sortedRanges.Length - rangesRemoved + 1;
if (rangesRemaining == 1)
{
return new SingleItemRangeCollection(newLower, newUpper);
}
else
{
SequenceRange[] returnedRanges = new SequenceRange[rangesRemaining];
Array.Copy(sortedRanges, returnedRanges, lowerBound);
returnedRanges[lowerBound] = new SequenceRange(newLower, newUpper);
Array.Copy(sortedRanges, upperBound + 1, returnedRanges, lowerBound + 1, sortedRanges.Length - upperBound - 1);
return GeneralCreate(returnedRanges);
}
}
public override string ToString()
{
StringBuilder builder = new StringBuilder();
for (int i = 0; i < Count; i++)
{
SequenceRange range = this[i];
if (i > 0)
{
builder.Append(',');
}
builder.Append(range.Lower);
builder.Append('-');
builder.Append(range.Upper);
}
return builder.ToString();
}
private class EmptyRangeCollection : SequenceRangeCollection
{
public override SequenceRange this[int index] => throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new ArgumentOutOfRangeException(nameof(index)));
public override int Count => 0;
public override bool Contains(long number) => false;
public override SequenceRangeCollection MergeWith(long number) => new SingleItemRangeCollection(number, number);
public override SequenceRangeCollection MergeWith(SequenceRange range) => new SingleItemRangeCollection(range);
}
private class MultiItemRangeCollection : SequenceRangeCollection
{
private readonly SequenceRange[] _ranges;
public MultiItemRangeCollection(SequenceRange[] sortedRanges)
{
_ranges = sortedRanges;
}
public override SequenceRange this[int index]
{
get
{
if (index < 0 || index >= _ranges.Length)
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new ArgumentOutOfRangeException(nameof(index), index,
SRP.Format(SRP.ValueMustBeInRange, 0, _ranges.Length - 1)));
return _ranges[index];
}
}
public override int Count => _ranges.Length;
public override bool Contains(long number)
{
if (_ranges.Length == 0)
{
return false;
}
else if (_ranges.Length == 1)
{
return _ranges[0].Contains(number);
}
SequenceRange searchFor = new SequenceRange(number);
int searchValue = Array.BinarySearch(_ranges, searchFor, s_lowerComparer);
if (searchValue >= 0)
{
return true;
}
searchValue = ~searchValue;
if (searchValue == 0)
{
return false;
}
return (_ranges[searchValue - 1].Upper >= number);
}
public override SequenceRangeCollection MergeWith(long number) => MergeWith(new SequenceRange(number));
public override SequenceRangeCollection MergeWith(SequenceRange newRange) => GeneralMerge(_ranges, newRange);
}
private class SingleItemRangeCollection : SequenceRangeCollection
{
private SequenceRange _range;
public SingleItemRangeCollection(SequenceRange range)
{
_range = range;
}
public SingleItemRangeCollection(long lower, long upper)
{
_range = new SequenceRange(lower, upper);
}
public override SequenceRange this[int index]
{
get
{
if (index != 0)
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new ArgumentOutOfRangeException(nameof(index)));
return _range;
}
}
public override int Count => 1;
public override bool Contains(long number) => _range.Contains(number);
public override SequenceRangeCollection MergeWith(long number)
{
if (number == _range.Upper + 1)
{
return new SingleItemRangeCollection(_range.Lower, number);
}
else
{
return MergeWith(new SequenceRange(number));
}
}
public override SequenceRangeCollection MergeWith(SequenceRange newRange)
{
if (newRange.Lower == _range.Upper + 1)
{
return new SingleItemRangeCollection(_range.Lower, newRange.Upper);
}
else if (_range.Contains(newRange))
{
return this;
}
else if (newRange.Contains(_range))
{
return new SingleItemRangeCollection(newRange);
}
else if (newRange.Upper == _range.Lower - 1)
{
return new SingleItemRangeCollection(newRange.Lower, _range.Upper);
}
else
{
return GeneralMerge(new SequenceRange[] { _range }, newRange);
}
}
}
private class LowerComparer : IComparer<SequenceRange>
{
public int Compare(SequenceRange x, SequenceRange y)
{
if (x.Lower < y.Lower)
{
return -1;
}
else if (x.Lower > y.Lower)
{
return 1;
}
else
{
return 0;
}
}
}
private class UpperComparer : IComparer<SequenceRange>
{
public int Compare(SequenceRange x, SequenceRange y)
{
if (x.Upper < y.Upper)
{
return -1;
}
else if (x.Upper > y.Upper)
{
return 1;
}
else
{
return 0;
}
}
}
}
}
|