Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / wpf / src / Core / CSharp / MS / Internal / Generic / Span.cs / 1 / Span.cs
//----------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// Description: Pairing of value and the number of positions sharing that value.
//
// History:
// 9/4/2005 : Wchao - Created a Generic version of the object-based Span classes
//
//---------------------------------------------------------------------------
using System;
using System.Collections;
using System.Collections.Generic;
using System.Windows;
using System.Diagnostics;
using MS.Utility;
namespace MS.Internal.Generic
{
///
/// Pairing of value and the number of positions sharing that value.
///
internal struct Span
{
internal T Value;
internal int Length;
///
/// Construct a span of value of type
///
internal Span(T value, int length)
{
Value = value;
Length = length;
}
}
///
/// Collection of spans
///
internal struct SpanVector : IEnumerable>
{
private FrugalStructList> _spanList;
private T _defaultValue;
///
/// Construct a collection of spans
///
internal SpanVector(T defaultValue)
: this(defaultValue, new FrugalStructList>())
{}
private SpanVector(
T defaultValue,
FrugalStructList> spanList
)
{
_defaultValue = defaultValue;
_spanList = spanList;
}
///
/// Get Generic enumerator of span vector
///
public IEnumerator> GetEnumerator()
{
return new SpanEnumerator(this);
}
///
/// Get enumerator of span vector
///
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
///
/// Add a new span to span vector
///
private void Add(Span span)
{
_spanList.Add(span);
}
///
/// Delete n elements of vector
///
internal void Delete(int index, int count)
{
// Do removes highest index to lowest to minimize the number
// of array entires copied.
for (int i = index + count - 1; i >= index; --i)
{
_spanList.RemoveAt(i);
}
}
///
/// Insert n elements to span vector
///
private void Insert(int index, int count)
{
for (int i = 0; i < count; i++)
_spanList.Insert(index, new Span());
}
///
/// Set a value to a range in span vector
///
internal void Set(int first, int length, T value)
{
// Identify first span affected by update
int fs = 0; // First affected span index
int fc = 0; // Character position at start of first affected span
while ( fs < Count
&& fc + _spanList[fs].Length <= first)
{
fc += _spanList[fs].Length;
fs++;
}
// If the span list terminated before first, just add the new span
if (fs >= Count)
{
// Ran out of Spans before reaching first
Debug.Assert(fc <= first);
if (fc < first)
{
// Create default run up to first
Add(new Span(_defaultValue, first-fc));
}
if ( Count > 0
&& _spanList[Count - 1].Value.Equals(value))
{
// New Element matches end Element, just extend end Element
Span lastSpan = _spanList[Count - 1];
_spanList[Count - 1] = new Span(lastSpan.Value, lastSpan.Length + length);
}
else
{
Add(new Span(value, length));
}
return;
}
// fs = index of first span partly or completely updated
// fc = character index at start of fs
// Now find the last span affected by the update
int ls = fs;
int lc = fc;
while ( ls < Count
&& lc + _spanList[ls].Length <= first + length)
{
lc += _spanList[ls].Length;
ls++;
}
// ls = first span following update to remain unchanged in part or in whole
// lc = character index at start of ls
// expand update region backwards to include existing Spans of identical
// Element type
if (first == fc)
{
// Item at [fs] is completely replaced. Check prior item
if ( fs > 0
&& _spanList[fs - 1].Value.Equals(value))
{
// Expand update area over previous run of equal classification
fs--;
fc -= _spanList[fs].Length;
first = fc;
length += _spanList[fs].Length;
}
}
else
{
// Item at [fs] is partially replaced. Check if it is same as update
if (_spanList[fs].Value.Equals(value))
{
// Expand update area back to start of first affected equal valued run
length = first + length - fc;
first = fc;
}
}
// Expand update region forwards to include existing Spans of identical
// Element type
if ( ls < Count
&& _spanList[ls].Value.Equals( value))
{
// Extend update region to end of existing split run
length = lc + _spanList[ls].Length - first;
lc += _spanList[ls].Length;
ls++;
}
// If no old Spans remain beyond area affected by update, handle easily:
if (ls >= Count)
{
// None of the old span list extended beyond the update region
if (fc < first)
{
// Updated region leaves some of [fs]
if (Count != fs + 2)
{
if (!Resize(fs + 2))
throw new OutOfMemoryException();
}
Span currentSpan = _spanList[fs];
_spanList[fs] = new Span(currentSpan.Value, first - fc);
_spanList[fs + 1] = new Span(value, length);
}
else
{
// Updated item replaces [fs]
if (Count != fs + 1)
{
if (!Resize(fs + 1))
throw new OutOfMemoryException();
}
_spanList[fs] = new Span(value, length);
}
return; // DONE
}
// Record partial elementtype at end, if any
T trailingValue = (new Span()).Value;
int trailingLength = 0;
if (first + length > lc)
{
trailingValue = _spanList[ls].Value;
trailingLength = lc + _spanList[ls].Length - (first + length);
}
// Calculate change in number of Spans
int spanDelta = 1 // The new span
+ (first > fc ? 1 : 0) // part span at start
- (ls - fs); // existing affected span count
// Note part span at end doesn't affect the calculation - the run may need
// updating, but it doesn't need creating.
if (spanDelta < 0)
{
Delete(fs + 1, -spanDelta);
}
else if (spanDelta > 0)
{
Insert(fs + 1, spanDelta);
// Initialize inserted Spans
for (int i = 0; i < spanDelta; i++)
{
_spanList[fs + 1 + i] = new Span();
}
}
// Assign Element values
// Correct Length of split span before updated range
if (fc < first)
{
Span currentSpan = _spanList[fs];
_spanList[fs] = new Span(currentSpan.Value, first - fc);
fs++;
}
// Record Element type for updated range
_spanList[fs] = new Span(value, length);
fs++;
// Correct Length of split span following updated range
if (lc < first + length)
{
_spanList[fs] = new Span(trailingValue, trailingLength);
}
// Phew, all done ....
return;
}
///
/// Number of spans in span vector
///
internal int Count
{
get { return _spanList.Count; }
}
///
/// The default value of span vector
///
internal T DefaultValue
{
get { return _defaultValue; }
}
///
/// Indexer of span vector
///
internal Span this[int index]
{
get { return _spanList[index]; }
}
private bool Resize(int targetCount)
{
if (targetCount > Count)
{
for (int c = 0; c < targetCount - Count; c++)
{
_spanList.Add(new Span());
}
}
else if (targetCount < Count)
{
Delete(targetCount, Count - targetCount);
}
return true;
}
///
/// Enumerator of span vector to facilitate iterating of spans
///
private struct SpanEnumerator : IEnumerator>
{
private SpanVector _vector;
private int _current;
internal SpanEnumerator(SpanVector vector)
{
_vector = vector;
_current = -1;
}
void IDisposable.Dispose()
{ }
///
/// The current span
///
public Span Current
{
get { return _vector[_current]; }
}
///
/// The current span
///
object IEnumerator.Current
{
get { return this.Current; }
}
///
/// Move to the next span
///
public bool MoveNext()
{
_current++;
return _current < _vector.Count;
}
///
/// Reset the enumerator
///
public void Reset()
{
_current = -1;
}
}
}
///
/// Span rider facilitates random access of value at any position in the span vector
///
internal struct SpanRider
{
private const int MaxCch = int.MaxValue;
private SpanVector _vector;
private Span _defaultSpan;
private int _current; // current span
private int _cp; // current cp
private int _dcp; // dcp from start to the start of current span
private int _cch; // length of the current span
internal SpanRider(SpanVector vector)
{
_defaultSpan = new Span(vector.DefaultValue, MaxCch);
_vector = vector;
_current = 0;
_cp = 0;
_dcp = 0;
_cch = 0;
At(0);
}
///
/// Position the rider at the specfied position
///
/// position to move to
internal bool At(int cp)
{
#if DEBUG
{
// Check that current position details are valid
int dcp = 0;
int i = 0;
// advance to current value start
while (dcp < _dcp && i < _vector.Count)
{
dcp += _vector[i].Length;
i++;
}
Debug.Assert(
i <= _vector.Count // current value is within valid range
&& i == _current // current value is valid
&& dcp == _dcp // current value start is valid
&& ( i == _vector.Count
|| _cp <= dcp + _vector[i].Length), // current cp is within range of current value
"Span vector is corrupted!"
);
}
#endif
if (cp < _dcp)
{
// Need to start from 0 again
_cp = _dcp = _current = _cch = 0;
}
// Advance to value containing cp
Span span = new Span();
while( _current < _vector.Count
&& _dcp + (span = _vector[_current]).Length <= cp)
{
_dcp += span.Length;
_current++;
}
if (_current < _vector.Count)
{
_cch = _vector[_current].Length - cp + _dcp;
_cp = cp;
return true;
}
else
{
_cch = _defaultSpan.Length;
_cp = Math.Min(cp, _dcp);
return false;
}
}
///
/// The first position of the current span
///
internal int CurrentSpanStart
{
get { return _dcp; }
}
///
/// The remaining length of the current span start from the current position
///
internal int Length
{
get { return _cch; }
}
///
/// The current position
///
internal int CurrentPosition
{
get { return _cp; }
}
///
/// The value of the current span
///
internal T CurrentValue
{
get { return _current >= _vector.Count ? _defaultSpan.Value : _vector[_current].Value; }
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//----------------------------------------------------------------------------
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// Description: Pairing of value and the number of positions sharing that value.
//
// History:
// 9/4/2005 : Wchao - Created a Generic version of the object-based Span classes
//
//---------------------------------------------------------------------------
using System;
using System.Collections;
using System.Collections.Generic;
using System.Windows;
using System.Diagnostics;
using MS.Utility;
namespace MS.Internal.Generic
{
///
/// Pairing of value and the number of positions sharing that value.
///
internal struct Span
{
internal T Value;
internal int Length;
///
/// Construct a span of value of type
///
internal Span(T value, int length)
{
Value = value;
Length = length;
}
}
///
/// Collection of spans
///
internal struct SpanVector : IEnumerable>
{
private FrugalStructList> _spanList;
private T _defaultValue;
///
/// Construct a collection of spans
///
internal SpanVector(T defaultValue)
: this(defaultValue, new FrugalStructList>())
{}
private SpanVector(
T defaultValue,
FrugalStructList> spanList
)
{
_defaultValue = defaultValue;
_spanList = spanList;
}
///
/// Get Generic enumerator of span vector
///
public IEnumerator> GetEnumerator()
{
return new SpanEnumerator(this);
}
///
/// Get enumerator of span vector
///
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
///
/// Add a new span to span vector
///
private void Add(Span span)
{
_spanList.Add(span);
}
///
/// Delete n elements of vector
///
internal void Delete(int index, int count)
{
// Do removes highest index to lowest to minimize the number
// of array entires copied.
for (int i = index + count - 1; i >= index; --i)
{
_spanList.RemoveAt(i);
}
}
///
/// Insert n elements to span vector
///
private void Insert(int index, int count)
{
for (int i = 0; i < count; i++)
_spanList.Insert(index, new Span());
}
///
/// Set a value to a range in span vector
///
internal void Set(int first, int length, T value)
{
// Identify first span affected by update
int fs = 0; // First affected span index
int fc = 0; // Character position at start of first affected span
while ( fs < Count
&& fc + _spanList[fs].Length <= first)
{
fc += _spanList[fs].Length;
fs++;
}
// If the span list terminated before first, just add the new span
if (fs >= Count)
{
// Ran out of Spans before reaching first
Debug.Assert(fc <= first);
if (fc < first)
{
// Create default run up to first
Add(new Span(_defaultValue, first-fc));
}
if ( Count > 0
&& _spanList[Count - 1].Value.Equals(value))
{
// New Element matches end Element, just extend end Element
Span lastSpan = _spanList[Count - 1];
_spanList[Count - 1] = new Span(lastSpan.Value, lastSpan.Length + length);
}
else
{
Add(new Span(value, length));
}
return;
}
// fs = index of first span partly or completely updated
// fc = character index at start of fs
// Now find the last span affected by the update
int ls = fs;
int lc = fc;
while ( ls < Count
&& lc + _spanList[ls].Length <= first + length)
{
lc += _spanList[ls].Length;
ls++;
}
// ls = first span following update to remain unchanged in part or in whole
// lc = character index at start of ls
// expand update region backwards to include existing Spans of identical
// Element type
if (first == fc)
{
// Item at [fs] is completely replaced. Check prior item
if ( fs > 0
&& _spanList[fs - 1].Value.Equals(value))
{
// Expand update area over previous run of equal classification
fs--;
fc -= _spanList[fs].Length;
first = fc;
length += _spanList[fs].Length;
}
}
else
{
// Item at [fs] is partially replaced. Check if it is same as update
if (_spanList[fs].Value.Equals(value))
{
// Expand update area back to start of first affected equal valued run
length = first + length - fc;
first = fc;
}
}
// Expand update region forwards to include existing Spans of identical
// Element type
if ( ls < Count
&& _spanList[ls].Value.Equals( value))
{
// Extend update region to end of existing split run
length = lc + _spanList[ls].Length - first;
lc += _spanList[ls].Length;
ls++;
}
// If no old Spans remain beyond area affected by update, handle easily:
if (ls >= Count)
{
// None of the old span list extended beyond the update region
if (fc < first)
{
// Updated region leaves some of [fs]
if (Count != fs + 2)
{
if (!Resize(fs + 2))
throw new OutOfMemoryException();
}
Span currentSpan = _spanList[fs];
_spanList[fs] = new Span(currentSpan.Value, first - fc);
_spanList[fs + 1] = new Span(value, length);
}
else
{
// Updated item replaces [fs]
if (Count != fs + 1)
{
if (!Resize(fs + 1))
throw new OutOfMemoryException();
}
_spanList[fs] = new Span(value, length);
}
return; // DONE
}
// Record partial elementtype at end, if any
T trailingValue = (new Span()).Value;
int trailingLength = 0;
if (first + length > lc)
{
trailingValue = _spanList[ls].Value;
trailingLength = lc + _spanList[ls].Length - (first + length);
}
// Calculate change in number of Spans
int spanDelta = 1 // The new span
+ (first > fc ? 1 : 0) // part span at start
- (ls - fs); // existing affected span count
// Note part span at end doesn't affect the calculation - the run may need
// updating, but it doesn't need creating.
if (spanDelta < 0)
{
Delete(fs + 1, -spanDelta);
}
else if (spanDelta > 0)
{
Insert(fs + 1, spanDelta);
// Initialize inserted Spans
for (int i = 0; i < spanDelta; i++)
{
_spanList[fs + 1 + i] = new Span();
}
}
// Assign Element values
// Correct Length of split span before updated range
if (fc < first)
{
Span currentSpan = _spanList[fs];
_spanList[fs] = new Span(currentSpan.Value, first - fc);
fs++;
}
// Record Element type for updated range
_spanList[fs] = new Span(value, length);
fs++;
// Correct Length of split span following updated range
if (lc < first + length)
{
_spanList[fs] = new Span(trailingValue, trailingLength);
}
// Phew, all done ....
return;
}
///
/// Number of spans in span vector
///
internal int Count
{
get { return _spanList.Count; }
}
///
/// The default value of span vector
///
internal T DefaultValue
{
get { return _defaultValue; }
}
///
/// Indexer of span vector
///
internal Span this[int index]
{
get { return _spanList[index]; }
}
private bool Resize(int targetCount)
{
if (targetCount > Count)
{
for (int c = 0; c < targetCount - Count; c++)
{
_spanList.Add(new Span());
}
}
else if (targetCount < Count)
{
Delete(targetCount, Count - targetCount);
}
return true;
}
///
/// Enumerator of span vector to facilitate iterating of spans
///
private struct SpanEnumerator : IEnumerator>
{
private SpanVector _vector;
private int _current;
internal SpanEnumerator(SpanVector vector)
{
_vector = vector;
_current = -1;
}
void IDisposable.Dispose()
{ }
///
/// The current span
///
public Span Current
{
get { return _vector[_current]; }
}
///
/// The current span
///
object IEnumerator.Current
{
get { return this.Current; }
}
///
/// Move to the next span
///
public bool MoveNext()
{
_current++;
return _current < _vector.Count;
}
///
/// Reset the enumerator
///
public void Reset()
{
_current = -1;
}
}
}
///
/// Span rider facilitates random access of value at any position in the span vector
///
internal struct SpanRider
{
private const int MaxCch = int.MaxValue;
private SpanVector _vector;
private Span _defaultSpan;
private int _current; // current span
private int _cp; // current cp
private int _dcp; // dcp from start to the start of current span
private int _cch; // length of the current span
internal SpanRider(SpanVector vector)
{
_defaultSpan = new Span(vector.DefaultValue, MaxCch);
_vector = vector;
_current = 0;
_cp = 0;
_dcp = 0;
_cch = 0;
At(0);
}
///
/// Position the rider at the specfied position
///
/// position to move to
internal bool At(int cp)
{
#if DEBUG
{
// Check that current position details are valid
int dcp = 0;
int i = 0;
// advance to current value start
while (dcp < _dcp && i < _vector.Count)
{
dcp += _vector[i].Length;
i++;
}
Debug.Assert(
i <= _vector.Count // current value is within valid range
&& i == _current // current value is valid
&& dcp == _dcp // current value start is valid
&& ( i == _vector.Count
|| _cp <= dcp + _vector[i].Length), // current cp is within range of current value
"Span vector is corrupted!"
);
}
#endif
if (cp < _dcp)
{
// Need to start from 0 again
_cp = _dcp = _current = _cch = 0;
}
// Advance to value containing cp
Span span = new Span();
while( _current < _vector.Count
&& _dcp + (span = _vector[_current]).Length <= cp)
{
_dcp += span.Length;
_current++;
}
if (_current < _vector.Count)
{
_cch = _vector[_current].Length - cp + _dcp;
_cp = cp;
return true;
}
else
{
_cch = _defaultSpan.Length;
_cp = Math.Min(cp, _dcp);
return false;
}
}
///
/// The first position of the current span
///
internal int CurrentSpanStart
{
get { return _dcp; }
}
///
/// The remaining length of the current span start from the current position
///
internal int Length
{
get { return _cch; }
}
///
/// The current position
///
internal int CurrentPosition
{
get { return _cp; }
}
///
/// The value of the current span
///
internal T CurrentValue
{
get { return _current >= _vector.Count ? _defaultSpan.Value : _vector[_current].Value; }
}
}
}
// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- ToolStripScrollButton.cs
- FreezableCollection.cs
- EventProxy.cs
- RijndaelManaged.cs
- DataGridViewAutoSizeModeEventArgs.cs
- EntityContainerEntitySetDefiningQuery.cs
- DispatcherSynchronizationContext.cs
- LineGeometry.cs
- EventSourceCreationData.cs
- TrackBarDesigner.cs
- MailWebEventProvider.cs
- TemplateManager.cs
- CompModSwitches.cs
- StreamGeometry.cs
- ArgIterator.cs
- HScrollProperties.cs
- ComPersistableTypeElement.cs
- ChtmlTextWriter.cs
- SafeNativeMethods.cs
- BindToObject.cs
- StateItem.cs
- ResourceDescriptionAttribute.cs
- CSharpCodeProvider.cs
- BinarySecretKeyIdentifierClause.cs
- CharacterBuffer.cs
- CmsInterop.cs
- HatchBrush.cs
- DataGridViewCheckBoxColumn.cs
- ObjectSet.cs
- TextEditorLists.cs
- ToolStripLocationCancelEventArgs.cs
- Attributes.cs
- FileCodeGroup.cs
- InternalDuplexBindingElement.cs
- SQLMoney.cs
- ContextBase.cs
- ContourSegment.cs
- RTTrackingProfile.cs
- MatrixCamera.cs
- XmlSchemaComplexContentExtension.cs
- AsymmetricSignatureDeformatter.cs
- CompositeTypefaceMetrics.cs
- ObjectReferenceStack.cs
- ConsoleTraceListener.cs
- BitmapData.cs
- Helpers.cs
- ScrollProperties.cs
- BrowserTree.cs
- SafeHandles.cs
- Listen.cs
- Point.cs
- HtmlElementCollection.cs
- ResourceReferenceKeyNotFoundException.cs
- BinaryObjectWriter.cs
- DiscoveryDocumentLinksPattern.cs
- CalendarDay.cs
- BridgeDataRecord.cs
- AssociationType.cs
- XamlBrushSerializer.cs
- SQLGuidStorage.cs
- DataGridViewCellStyleChangedEventArgs.cs
- ClassImporter.cs
- ServicePrincipalNameElement.cs
- LogRecordSequence.cs
- DetailsViewInsertEventArgs.cs
- PackagingUtilities.cs
- ExpressionLexer.cs
- UIHelper.cs
- __ComObject.cs
- IconConverter.cs
- SqlMetaData.cs
- X509Certificate2Collection.cs
- XsltArgumentList.cs
- ToolStripDropDownClosedEventArgs.cs
- NativeMethods.cs
- FlowDocumentReaderAutomationPeer.cs
- XPathDocumentBuilder.cs
- LabelLiteral.cs
- VirtualDirectoryMappingCollection.cs
- FontNameConverter.cs
- RSAPKCS1KeyExchangeFormatter.cs
- IODescriptionAttribute.cs
- HttpRequestTraceRecord.cs
- SQLUtility.cs
- RawStylusInput.cs
- MediaCommands.cs
- ConfigXmlWhitespace.cs
- Resources.Designer.cs
- LocalValueEnumerator.cs
- DataGridViewRowEventArgs.cs
- SqlTypeConverter.cs
- CommonServiceBehaviorElement.cs
- SchemaImporterExtension.cs
- XmlFormatWriterGenerator.cs
- RightsManagementResourceHelper.cs
- QuotaThrottle.cs
- WebEvents.cs
- SoundPlayer.cs
- DesignerTransactionCloseEvent.cs
- TransportDefaults.cs