File: Core\CSharp\MS\Internal\Span.cs
Project: wpf\src\PresentationCore.csproj (PresentationCore)
//+-----------------------------------------------------------------------
//
//  Microsoft Avalon
//  Copyright (C) Microsoft Corporation, 2001
//
//  File:      span.cs
//
//  Contents:  Generic span types
//
//  Created:   9-6-2001 Worachai Chaoweeraprasit (wchao)
//             [As of this creation, C# has no real generic type system]
//
//------------------------------------------------------------------------
 
using System.Windows;
using System;
using System.Collections;
using MS.Utility;
using System.Diagnostics;
 
namespace MS.Internal
{    
    /// <summary>
    /// VECTOR: A series of spans
    /// </summary>
    internal class SpanVector : IEnumerable
    {
        /// <summary>
        /// Constructor
        /// </summary>
        public SpanVector(object defaultObject)
            : this(
                defaultObject,
                new FrugalStructList<Span>()
                )
        {}
 
        internal SpanVector(
            object      defaultObject,
            FrugalStructList<Span>   spans
            )
        {
            _defaultObject = defaultObject;
            _spans = spans;
        }
 
 
        /// <summary>
        /// Get enumerator to vector
        /// </summary>
        public IEnumerator GetEnumerator()
        {
            return new SpanEnumerator(this);
        }
 
        /// <summary>
        /// Add a new span to vector
        /// </summary>
        private void Add(Span span)
        {
            _spans.Add(span);
        }
 
        /// <summary>
        /// Delete n elements of vector
        /// </summary>
        internal virtual void Delete(int index, int count, ref SpanPosition latestPosition)
        {
            DeleteInternal(index, count);
 
            if (index <= latestPosition.Index)
                latestPosition = new SpanPosition();
        }
 
        private void DeleteInternal(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)
            {
                _spans.RemoveAt(i);
            }
        }
 
        /// <summary>
        /// Insert n elements to vector
        /// </summary>
        private void Insert(int index, int count)
        {
            for (int c = 0; c < count; c++)
                _spans.Insert(index, new Span(null, 0));
        }
 
        #region Public operation
 
        /// <summary>
        /// Finds the span that contains the specified character position.
        /// </summary>
        /// <param name="cp">position to find</param>
        /// <param name="latestPosition">Position of the most recently accessed span (e.g., the current span
        /// of a SpanRider) for performance; FindSpan runs in O(1) time if the specified cp is in the same span 
        /// or an adjacent span.</param>
        /// <param name="spanPosition">receives the index and first cp of the span that contains the specified 
        /// position or, if the position is past the end of the vector, the index and cp just past the end of 
        /// the last span.</param>
        /// <returns>Returns true if cp is in range or false if not.</returns>
        internal bool FindSpan(int cp, SpanPosition latestPosition, out SpanPosition spanPosition)
        {
            Debug.Assert(cp >= 0);
 
            int spanCount = _spans.Count;
            int spanIndex, spanCP;
 
            if (cp == 0)
            {
                // CP zero always corresponds to span index zero
                spanIndex = 0;
                spanCP = 0;
            }
            else if (cp >= latestPosition.CP || cp * 2 < latestPosition.CP)
            {
                // One of the following is true:
                //  1.  cp is after the latest position (the most recently accessed span)
                //  2.  cp is closer to zero than to the latest position
                if (cp >= latestPosition.CP)
                {
                    // case 1: scan forward from the latest position
                    spanIndex = latestPosition.Index;
                    spanCP = latestPosition.CP;
                }
                else
                {
                    // case 2: scan forward from the start of the span vector
                    spanIndex = 0;
                    spanCP = 0;
                }
 
                // Scan forward until we find the Span that contains the specified CP or
                // reach the end of the SpanVector
                for (; spanIndex < spanCount; ++spanIndex)
                {
                    int spanLength = _spans[spanIndex].length;
 
                    if (cp < spanCP + spanLength)
                    {
                        break;
                    }
 
                    spanCP += spanLength;
                }
            }
            else
            {
                // The specified CP is before the latest position but closer to it than to zero;
                // therefore scan backwards from the latest position
                spanIndex = latestPosition.Index;
                spanCP = latestPosition.CP;
 
                while (spanCP > cp)
                {
                    Debug.Assert(spanIndex > 0);
                    spanCP -= _spans[--spanIndex].length;
                }
            }
 
            // Return index and cp of span in out param.
            spanPosition = new SpanPosition(spanIndex, spanCP);
 
            // Return true if the span is in range.
            return spanIndex != spanCount;
        }
        
 
        /// <summary>
        /// Set an element as a value to a character range
        /// </summary>
        /// <remarks>
        /// Implementation of span element object must implement Object.Equals to
        /// avoid runtime reflection cost on equality check of nested-type object.
        /// </remarks>
        public void SetValue(int first, int length, object element)
        {
            Set(first, length, element, SpanVector._equals, new SpanPosition());
        }
 
        /// <summary>
        /// Set an element as a value to a character range; takes a SpanPosition of a recently accessed
        /// span for performance and returns a known valid SpanPosition
        /// </summary>
        public SpanPosition SetValue(int first, int length, object element, SpanPosition spanPosition)
        {
            return Set(first, length, element, SpanVector._equals, spanPosition);
        }
 
        /// <summary>
        /// Set an element as a reference to a character range
        /// </summary>
        public void SetReference(int first, int length, object element)
        {
            Set(first, length, element, SpanVector._referenceEquals, new SpanPosition());
        }
 
        /// <summary>
        /// Set an element as a reference to a character range; takes a SpanPosition of a recently accessed
        /// span for performance and returns a known valid SpanPosition
        /// </summary>
        public SpanPosition SetReference(int first, int length, object element, SpanPosition spanPosition)
        {
            return Set(first, length, element, SpanVector._referenceEquals, spanPosition);
        }
 
        #endregion
 
 
        private SpanPosition Set(int first, int length, object element, Equals equals, SpanPosition spanPosition)
        {
            bool inRange = FindSpan(first, spanPosition, out spanPosition);
 
            // fs = index of first span partly or completely updated
            // fc = character index at start of fs
            int fs = spanPosition.Index;
            int fc = spanPosition.CP;
 
            // Find the span that contains the first affected cp
            if (!inRange)
            {
                // The first cp is past the end of the last span
                if (fc < first)
                {
                    // Create default run up to first
                    Add(new Span(_defaultObject, first - fc));
                }
 
                if (   Count > 0 
                    && equals(_spans[Count-1].element, element))
                {
                    // New Element matches end Element, just extend end Element
                    _spans[Count - 1].length += length;
 
                    // Make sure fs and fc still agree
                    if (fs == Count)
                    {
                        fc += length;
                    }
                }
                else
                {
                    Add(new Span(element, length));
                }
            }
            else
            {
                // Now find the last span affected by the update
 
                int ls = fs;
                int lc = fc;
                while (   ls < Count 
                       && lc + _spans[ls].length <= first + length)
                {
                    lc += _spans[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
                        && equals(_spans[fs - 1].element, element))
                    {
                        // Expand update area over previous run of equal classification
                        fs--;
                        fc -= _spans[fs].length;
                        first = fc;
                        length += _spans[fs].length;
                    }
                }
                else
                {
                    // Item at [fs] is partially replaced. Check if it is same as update
                    if (equals(_spans[fs].element, element))
                    {
                        // 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
                    && equals(_spans[ls].element, element))
                {
                    // Extend update region to end of existing split run
 
                    length = lc + _spans[ls].length - first;
                    lc += _spans[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();
                        }
                        _spans[fs].length = first - fc;
                        _spans[fs + 1] = new Span(element, length);
                    }
                    else
                    {
                        // Updated item replaces [fs]
                        if (Count != fs + 1)
                        {
                            if (!Resize(fs + 1))
                                throw new OutOfMemoryException();
                        }
                        _spans[fs] = new Span(element, length);
                    }
                }
                else
                {
                    // Record partial elementtype at end, if any
 
                    object trailingElement = null;
                    int trailingLength = 0;
 
                    if (first + length > lc)
                    {
                        trailingElement = _spans[ls].element;
                        trailingLength = lc + _spans[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)
                    {
                        DeleteInternal(fs + 1, -spanDelta);
                    }
                    else if (spanDelta > 0)
                    {
                        Insert(fs + 1, spanDelta);
                        // Initialize inserted Spans
                        for (int i = 0; i < spanDelta; i++)
                        {
                            _spans[fs + 1 + i] = new Span(null, 0);
                        }
                    }
 
                    // Assign Element values
 
                    // Correct Length of split span before updated range
 
                    if (fc < first)
                    {
                        _spans[fs].length = first - fc;
                        fs++;
                        fc = first;
                    }
 
                    // Record Element type for updated range
 
                    _spans[fs] = new Span(element, length);
                    fs++;
                    fc += length;
 
                    // Correct Length of split span following updated range
 
                    if (lc < first + length)
                    {
                        _spans[fs] = new Span(trailingElement, trailingLength);
                    }
                }
            }
 
            // Return a known valid span position.
            return new SpanPosition(fs, fc);
        }
 
        #region Properties
        /// <summary>
        /// Number of spans in vector
        /// </summary>
        public int Count
        {
            get { return _spans.Count; }
        }
 
        /// <summary>
        /// The default element of vector
        /// </summary>
        public object Default
        {
            get { return _defaultObject; }
        }
 
        /// <summary>
        /// Span accessor at nth element
        /// </summary>
        public Span this[int index]
        {
            get { return _spans[index]; }
        }
        #endregion
 
        #region Private members
        private bool Resize(int targetCount)
        {
            if (targetCount > Count)
            {
                for (int c = 0; c < targetCount - Count; c++)
                {
                    _spans.Add(new Span(null, 0));
                }
            }
            else if (targetCount < Count)
            {
                DeleteInternal(targetCount, Count - targetCount);
            }
            return true;
        }
 
        static private Equals _referenceEquals = new Equals(Object.ReferenceEquals);
        static private Equals _equals = new Equals(Object.Equals);
 
        FrugalStructList<Span>  _spans;
        object                  _defaultObject;
        #endregion
    }
 
 
    /// <summary>
    /// Equality check method
    /// </summary>
    internal delegate bool Equals(object first, object second);
 
 
    /// <summary>
    /// ENUMERATOR: To navigate a vector through its element
    /// </summary>
    internal sealed class SpanEnumerator : IEnumerator
    {
        internal SpanEnumerator(SpanVector spans)
        {
            _spans = spans;
            _current = -1;
        }
 
        /// <summary>
        /// The current span
        /// </summary>
        public object Current
        {
            get { return _spans[_current]; }
        }
 
        /// <summary>
        /// Move to the next span
        /// </summary>
        public bool MoveNext()
        {
            _current++;
            return _current < _spans.Count ? true : false;
        }
 
        /// <summary>
        /// Reset the enumerator
        /// </summary>
        public void Reset()
        {
            _current = -1;
        }
 
        SpanVector  _spans;
        int         _current;    // current span
    }
 
 
    /// <summary>
    /// Represents a Span's position as a pair of related values: its index in the 
    /// SpanVector its CP offset from the start of the SpanVector.
    /// </summary>
    internal struct SpanPosition
    {
        internal SpanPosition(int spanIndex, int spanCP)
        {
            _spanIndex = spanIndex;
            _spanCP = spanCP;
        }
 
        internal int Index
        {
            get { return _spanIndex; }
        }
 
        internal int CP
        {
            get { return _spanCP; }
        }
 
        private int _spanIndex;
        private int _spanCP;
    }
 
 
    /// <summary>
    /// RIDER: To navigate a vector through character index
    /// </summary>
    internal struct SpanRider
    {
        public SpanRider(SpanVector spans) : this(spans, new SpanPosition(), 0)
        {
        }
 
        public SpanRider(SpanVector spans, SpanPosition latestPosition) : this(spans, latestPosition, latestPosition.CP)
        {
        }
 
        public SpanRider(SpanVector spans, SpanPosition latestPosition, int cp)
        {
            _spans = spans;
            _spanPosition = new SpanPosition();
            _cp = 0;
            _cch = 0;
            At(latestPosition, cp);
        }
 
        /// <summary>
        /// Move rider to a given cp
        /// </summary>
        public bool At(int cp)
        {
            return At(_spanPosition, cp);
        }
 
        public bool At(SpanPosition latestPosition, int cp)
        {
            bool inRange = _spans.FindSpan(cp, latestPosition, out _spanPosition);
            if (inRange)
            {
                // cp is in range:
                //  - Length is the distance to the end of the span
                //  - CurrentPosition is cp
                _cch = _spans[_spanPosition.Index].length - (cp - _spanPosition.CP);
                _cp = cp;
            }
            else
            {
                // cp is out of range:
                //  - Length is the default span length
                //  - CurrentPosition is the end of the last span
                _cch = int.MaxValue;
                _cp = _spanPosition.CP;
            }
 
            return inRange;
        }
 
        #region Properties
        /// <summary>
        /// The first cp of the current span
        /// </summary>
        public int  CurrentSpanStart
        {
            get { return _spanPosition.CP; }
        }
 
        /// <summary>
        /// The length of current span start from the current cp
        /// </summary>
        public int  Length
        {
            get { return _cch; }
        }
 
        /// <summary>
        /// The current position
        /// </summary>
        public int  CurrentPosition
        {
            get { return _cp; }
        }
 
        /// <summary>
        /// The element of the current span
        /// </summary>
        public object CurrentElement
        {
            get { return _spanPosition.Index >= _spans.Count ? _spans.Default : _spans[_spanPosition.Index].element; }
        }
 
        /// <summary>
        /// Index of the span at the current position.
        /// </summary>
        public int CurrentSpanIndex
        {
            get { return _spanPosition.Index; }
        }
 
        /// <summary>
        /// Index and first cp of the current span.
        /// </summary>
        public SpanPosition SpanPosition
        {
            get { return _spanPosition; }
        }
 
        #endregion
 
        #region Private members
        SpanVector      _spans;         // vector of spans
        SpanPosition    _spanPosition;  // index and cp of current span
        int             _cp;            // current cp (may be greater than start of span)
        int             _cch;           // distance from current cp to end of current span
        #endregion
    }
}