Span.cs source code in C# .NET

                        
Code:
                         / DotNET / DotNET / 8.0 / untmp / WIN_WINDOWS / lh_tools_devdiv_wpf / Windows / wcp / Core / 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 : [....] - 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.