DtrList.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / wpf / src / Framework / MS / Internal / PtsHost / DtrList.cs / 1305600 / DtrList.cs

                            //---------------------------------------------------------------------------- 
//
// Copyright (C) Microsoft Corporation.  All rights reserved.
//
// File: DrtList.cs 
//
// Description: Definition for DtrLits (Dirty Text Range List) which 
//              contains information about tree changes. 
//
// History: 
//  06/06/2003 : [....] - moving from Avalon branch.
//
//---------------------------------------------------------------------------
 
using System;
using System.Diagnostics; 
 
namespace MS.Internal.PtsHost
{ 
    // ---------------------------------------------------------------------
    // DtrLits (Dirty Text Range List) manages sorted list of accumulated
    // tree changes.
    // All entries in DtrList are sorted with respect to StartIndex. 
    // StartIndex is always representing offset in the tree before any
    // changes. 
    // --------------------------------------------------------------------- 
    internal sealed class DtrList
    { 
        // ------------------------------------------------------------------
        // Construct a DtrList. The array of DTRs initially can store up to
        // 4 entries. Upon adding elements the capacity increased in multiples
        // of two as required. 
        // -----------------------------------------------------------------
        internal DtrList() 
        { 
            _dtrs = new DirtyTextRange[_defaultCapacity];
            _count = 0; 
        }

        // ------------------------------------------------------------------
        // Merge new DTR with list of exising DTRs: 
        // 1) Convert startIndex to index reflecting position before any changes.
        // 2) Merge it with existing list of DTRs. 
        // 
        //      dtr - New DTR to be merged with exising list of DTRs.
        // ------------------------------------------------------------------ 
        internal void Merge(DirtyTextRange dtr)
        {
            bool merge = false;
            int i = 0; 
            int startIndexOld = dtr.StartIndex;
 
            // 1) Convert StartIndex to index reflecting position before any changes. 
            //    And find out if there is a need to merge DTRs
            if (_count > 0) 
            {
                while (i < _count)
                {
                    // a) New DTR starts before the next one. In this case there are 
                    //    two possibilities:
                    //    * new DTR does not intersect with the beginning of the next DTR, 
                    //      in this case insert new DTR before the next one. 
                    //    * new DTR does intersect with the beginning of the next DTR,
                    //      in this case merge these 2 DTRs 
                    if (startIndexOld < _dtrs[i].StartIndex)
                    {
                        if (startIndexOld + dtr.PositionsRemoved > _dtrs[i].StartIndex)
                        { 
                            merge = true;
                        } 
                        // else new dtr has to be inserted at position 'i' 
                        break;
                    } 
                    // b) New DTR starts in the range of the previous DTR. In this case
                    //    merge these 2 DTRs
                    else if (startIndexOld <= _dtrs[i].StartIndex + _dtrs[i].PositionsAdded)
                    { 
                        // merge with existing dtr at position 'i'
                        merge = true; 
                        break; 
                    }
                    // c) No intersection has been found, go to the next DTR in the list. 
                    startIndexOld -= _dtrs[i].PositionsAdded - _dtrs[i].PositionsRemoved;
                    ++i;
                }
                // Update dcp of the new DTR, to reflect position before any tree changes. 
                dtr.StartIndex = startIndexOld;
            } 
 
            // 2) Insert new DTR into the list, merge if necessary
            if (i < _count) 
            {
                if (merge)
                {
                    // The simplest way to merge these two DTRs is to add together 
                    // cchAdded/cchDeleted form both DTRs, but it will invalidate more
                    // than required. Formula used below is more accurate. 
 
                    // a) New DTR does intersect with the beginning of the next DTR,
                    //    in this case merge these 2 DTRs. 
                    // * dcp = dcpN (since it starts before dcpO)
                    // * add = addN + addO - min(addO, delN - (dcpO - dcpN))
                    // * del = delN + delO - min(addO, delN - (dcpO - dcpN))
                    // NOTE: dcpO - dcpN is always <= delN 
                    if (dtr.StartIndex < _dtrs[i].StartIndex)
                    { 
                        int delta  = _dtrs[i].StartIndex - dtr.StartIndex; 
                        int adjust = Math.Min(_dtrs[i].PositionsAdded, dtr.PositionsRemoved - delta);
                        _dtrs[i].StartIndex        = dtr.StartIndex; 
                        _dtrs[i].PositionsAdded   += dtr.PositionsAdded   - adjust;
                        _dtrs[i].PositionsRemoved += dtr.PositionsRemoved - adjust;
                    }
                    // b) New DTR starts in the range of the previous DTR. In this case 
                    //    merge these 2 DTRs.
                    // * dcp = dcpO (since it starts before dcpN) 
                    // * add = addN + addO - min(delN, addO - (dcpN - dcpO)) 
                    // * del = delN + delO - min(delN, addO - (dcpN - dcpO))
                    // NOTE: dcpN - dcpO is always <= addO 
                    else
                    {
                        int delta  = dtr.StartIndex - _dtrs[i].StartIndex;
                        int adjust = Math.Min(dtr.PositionsRemoved, _dtrs[i].PositionsAdded - delta); 
                        //_dtrs[i].dcp: no need to change it
                        _dtrs[i].PositionsAdded   += dtr.PositionsAdded   - adjust; 
                        _dtrs[i].PositionsRemoved += dtr.PositionsRemoved - adjust; 
                    }
                } 
                else
                {
                    // The new DTR has to be inserted before DTR at position 'i'.
                    if (_count == _dtrs.Length) { Resize(); } 
                    Array.Copy(_dtrs, i, _dtrs, i+1, _count-i);
                    _dtrs[i] = dtr; 
                    ++_count; 
                }
                MergeWithNext(i); 
            }
            else
            {
                // The new DTR has to be appended to the end of the list. 
                if (_count == _dtrs.Length) { Resize(); }
                _dtrs[_count] = dtr; 
                ++_count; 
            }
 
#if TEXTPANELLAYOUTDEBUG
            System.Text.StringBuilder msg = new System.Text.StringBuilder();
            msg.Append("Merge DTR (" + dtr.StartIndex + "," + dtr.PositionsAdded + "," + dtr.PositionsRemoved + ") ->");
            for (i = 0; i < _count; i++) 
            {
                msg.Append(" (" + _dtrs[i].StartIndex + "," + _dtrs[i].PositionsAdded + "," + _dtrs[i].PositionsRemoved + ")"); 
            } 
            TextPanelDebug.Log(msg.ToString(), TextPanelDebug.Category.ContentChange);
#endif 
        }

        // -----------------------------------------------------------------
        // Retrieve list of dtrs from range. 
        //
        //      dcpNew - Distance from the beginning of TextContainer after all 
        //              tree changes. 
        //      cchOld - Number of characters in the range, but before any
        //              tree changes. 
        //
        // Returns: List of DRTs for specified range.
        // ------------------------------------------------------------------
        internal DtrList DtrsFromRange(int dcpNew, int cchOld) 
        {
            DtrList dtrs = null; 
            int i = 0; 
            int first, last;
            int positionsAdded = 0; 

            // Find the first dtr intersecting with the specified range.
            // Since DTRs store dcp before any changes, during iteration
            // accumulate positionsAdded (number of characters added to the tree 
            // up to the current point).
            while (i < _count) 
            { 
                if (dcpNew <= _dtrs[i].StartIndex + positionsAdded + _dtrs[i].PositionsAdded)
                { 
                    break;
                }
                positionsAdded += _dtrs[i].PositionsAdded - _dtrs[i].PositionsRemoved;
                ++i; 
            }
            first = i; 
 
            // Find the last dtr intersecting with the specified range.
            // dcpNew-positionsAdded points to position before any tree changes, from 
            // where we start counting cchOld.
            // Do not add characters (positionsAdded), since start position has been already found.
            while (i < _count)
            { 
                if (dcpNew - positionsAdded + cchOld <= _dtrs[i].StartIndex + _dtrs[i].PositionsRemoved)
                { 
                    // If there is no intersection with the current DTR, go to the previous one. 
                    if (dcpNew - positionsAdded + cchOld < _dtrs[i].StartIndex)
                    { 
                        --i;
                    }
                    break;
                } 
                ++i;
            } 
            last = (i < _count) ? i : _count-1; 

            // If there are DTRs in the specified range, create new DtrList object 
            if (last >= first)
            {
                dtrs = new DtrList();
                while (last >= first) 
                {
                    // Since dcpNew is after tree changes, add positionsAdded to all dtrs 
                    // to build dtr list relative to dcpNew position. 
                    DirtyTextRange dtr = _dtrs[first];
                    dtr.StartIndex += positionsAdded; 
                    dtrs.Append(dtr);
                    ++first;
                }
            } 
            return dtrs;
        } 
 
        // -----------------------------------------------------------------
        // Merge DRT at position 'index' with the next one, if possible. 
        //
        //      index - Index of the DTR to be merged with next one.
        // -----------------------------------------------------------------
        private void MergeWithNext(int index) 
        {
            while (index + 1 < _count) 
            { 
                DirtyTextRange dtrNext = _dtrs[index+1];
 
                // DTR starts in the range of the previous DTR. In this case
                // merge these 2 DTRs.
                if (dtrNext.StartIndex <= _dtrs[index].StartIndex + _dtrs[index].PositionsRemoved)
                { 
                    //_dtrs[index].dcp: no need to change it
                    _dtrs[index].PositionsAdded += dtrNext.PositionsAdded; 
                    _dtrs[index].PositionsRemoved += dtrNext.PositionsRemoved; 

                    // Remove merged entry 
                    for (int i = index + 2; i < _count; i++)
                    {
                        _dtrs[i - 1] = _dtrs[i];
                    } 

                    --_count; 
                } 
                else
                { 
                    break;
                }
            }
        } 

        // ----------------------------------------------------------------- 
        // Append new DTR to the list. 
        //
        //      dtr - DTR to be appended to the list. 
        // ------------------------------------------------------------------
        private void Append(DirtyTextRange dtr)
        {
            if (_count == _dtrs.Length) { Resize(); } 
            _dtrs[_count] = dtr;
            ++_count; 
        } 

        // ----------------------------------------------------------------- 
        // Increases the capacity of the DTR array.
        //  = *2.
        // ------------------------------------------------------------------
        private void Resize() 
        {
            Debug.Assert(_dtrs.Length > 0); 
 
            // Allocate new array and copy all existing entries into it
            DirtyTextRange [] newdtrs = new DirtyTextRange[_dtrs.Length * 2]; 
            Array.Copy(_dtrs, newdtrs, _dtrs.Length);
            _dtrs = newdtrs;
        }
 
        // ------------------------------------------------------------------
        // Array like access to list of DTRs. 
        // ----------------------------------------------------------------- 
        internal int Length
        { 
            get { return _count; }
        }
        internal DirtyTextRange this[int index]
        { 
            get { return _dtrs[index]; }
        } 
 
        // ------------------------------------------------------------------
        // Array of DTRs. This array stores sorted list of DTRs. 
        // -----------------------------------------------------------------
        private DirtyTextRange [] _dtrs;

        // ----------------------------------------------------------------- 
        // Default capacity of the DTRs array. The array capacity is always
        // increased in multiples of two as required: 4*(2^N). 
        // ----------------------------------------------------------------- 
        private const int _defaultCapacity = 4;
        private int _count; 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
//---------------------------------------------------------------------------- 
//
// Copyright (C) Microsoft Corporation.  All rights reserved.
//
// File: DrtList.cs 
//
// Description: Definition for DtrLits (Dirty Text Range List) which 
//              contains information about tree changes. 
//
// History: 
//  06/06/2003 : [....] - moving from Avalon branch.
//
//---------------------------------------------------------------------------
 
using System;
using System.Diagnostics; 
 
namespace MS.Internal.PtsHost
{ 
    // ---------------------------------------------------------------------
    // DtrLits (Dirty Text Range List) manages sorted list of accumulated
    // tree changes.
    // All entries in DtrList are sorted with respect to StartIndex. 
    // StartIndex is always representing offset in the tree before any
    // changes. 
    // --------------------------------------------------------------------- 
    internal sealed class DtrList
    { 
        // ------------------------------------------------------------------
        // Construct a DtrList. The array of DTRs initially can store up to
        // 4 entries. Upon adding elements the capacity increased in multiples
        // of two as required. 
        // -----------------------------------------------------------------
        internal DtrList() 
        { 
            _dtrs = new DirtyTextRange[_defaultCapacity];
            _count = 0; 
        }

        // ------------------------------------------------------------------
        // Merge new DTR with list of exising DTRs: 
        // 1) Convert startIndex to index reflecting position before any changes.
        // 2) Merge it with existing list of DTRs. 
        // 
        //      dtr - New DTR to be merged with exising list of DTRs.
        // ------------------------------------------------------------------ 
        internal void Merge(DirtyTextRange dtr)
        {
            bool merge = false;
            int i = 0; 
            int startIndexOld = dtr.StartIndex;
 
            // 1) Convert StartIndex to index reflecting position before any changes. 
            //    And find out if there is a need to merge DTRs
            if (_count > 0) 
            {
                while (i < _count)
                {
                    // a) New DTR starts before the next one. In this case there are 
                    //    two possibilities:
                    //    * new DTR does not intersect with the beginning of the next DTR, 
                    //      in this case insert new DTR before the next one. 
                    //    * new DTR does intersect with the beginning of the next DTR,
                    //      in this case merge these 2 DTRs 
                    if (startIndexOld < _dtrs[i].StartIndex)
                    {
                        if (startIndexOld + dtr.PositionsRemoved > _dtrs[i].StartIndex)
                        { 
                            merge = true;
                        } 
                        // else new dtr has to be inserted at position 'i' 
                        break;
                    } 
                    // b) New DTR starts in the range of the previous DTR. In this case
                    //    merge these 2 DTRs
                    else if (startIndexOld <= _dtrs[i].StartIndex + _dtrs[i].PositionsAdded)
                    { 
                        // merge with existing dtr at position 'i'
                        merge = true; 
                        break; 
                    }
                    // c) No intersection has been found, go to the next DTR in the list. 
                    startIndexOld -= _dtrs[i].PositionsAdded - _dtrs[i].PositionsRemoved;
                    ++i;
                }
                // Update dcp of the new DTR, to reflect position before any tree changes. 
                dtr.StartIndex = startIndexOld;
            } 
 
            // 2) Insert new DTR into the list, merge if necessary
            if (i < _count) 
            {
                if (merge)
                {
                    // The simplest way to merge these two DTRs is to add together 
                    // cchAdded/cchDeleted form both DTRs, but it will invalidate more
                    // than required. Formula used below is more accurate. 
 
                    // a) New DTR does intersect with the beginning of the next DTR,
                    //    in this case merge these 2 DTRs. 
                    // * dcp = dcpN (since it starts before dcpO)
                    // * add = addN + addO - min(addO, delN - (dcpO - dcpN))
                    // * del = delN + delO - min(addO, delN - (dcpO - dcpN))
                    // NOTE: dcpO - dcpN is always <= delN 
                    if (dtr.StartIndex < _dtrs[i].StartIndex)
                    { 
                        int delta  = _dtrs[i].StartIndex - dtr.StartIndex; 
                        int adjust = Math.Min(_dtrs[i].PositionsAdded, dtr.PositionsRemoved - delta);
                        _dtrs[i].StartIndex        = dtr.StartIndex; 
                        _dtrs[i].PositionsAdded   += dtr.PositionsAdded   - adjust;
                        _dtrs[i].PositionsRemoved += dtr.PositionsRemoved - adjust;
                    }
                    // b) New DTR starts in the range of the previous DTR. In this case 
                    //    merge these 2 DTRs.
                    // * dcp = dcpO (since it starts before dcpN) 
                    // * add = addN + addO - min(delN, addO - (dcpN - dcpO)) 
                    // * del = delN + delO - min(delN, addO - (dcpN - dcpO))
                    // NOTE: dcpN - dcpO is always <= addO 
                    else
                    {
                        int delta  = dtr.StartIndex - _dtrs[i].StartIndex;
                        int adjust = Math.Min(dtr.PositionsRemoved, _dtrs[i].PositionsAdded - delta); 
                        //_dtrs[i].dcp: no need to change it
                        _dtrs[i].PositionsAdded   += dtr.PositionsAdded   - adjust; 
                        _dtrs[i].PositionsRemoved += dtr.PositionsRemoved - adjust; 
                    }
                } 
                else
                {
                    // The new DTR has to be inserted before DTR at position 'i'.
                    if (_count == _dtrs.Length) { Resize(); } 
                    Array.Copy(_dtrs, i, _dtrs, i+1, _count-i);
                    _dtrs[i] = dtr; 
                    ++_count; 
                }
                MergeWithNext(i); 
            }
            else
            {
                // The new DTR has to be appended to the end of the list. 
                if (_count == _dtrs.Length) { Resize(); }
                _dtrs[_count] = dtr; 
                ++_count; 
            }
 
#if TEXTPANELLAYOUTDEBUG
            System.Text.StringBuilder msg = new System.Text.StringBuilder();
            msg.Append("Merge DTR (" + dtr.StartIndex + "," + dtr.PositionsAdded + "," + dtr.PositionsRemoved + ") ->");
            for (i = 0; i < _count; i++) 
            {
                msg.Append(" (" + _dtrs[i].StartIndex + "," + _dtrs[i].PositionsAdded + "," + _dtrs[i].PositionsRemoved + ")"); 
            } 
            TextPanelDebug.Log(msg.ToString(), TextPanelDebug.Category.ContentChange);
#endif 
        }

        // -----------------------------------------------------------------
        // Retrieve list of dtrs from range. 
        //
        //      dcpNew - Distance from the beginning of TextContainer after all 
        //              tree changes. 
        //      cchOld - Number of characters in the range, but before any
        //              tree changes. 
        //
        // Returns: List of DRTs for specified range.
        // ------------------------------------------------------------------
        internal DtrList DtrsFromRange(int dcpNew, int cchOld) 
        {
            DtrList dtrs = null; 
            int i = 0; 
            int first, last;
            int positionsAdded = 0; 

            // Find the first dtr intersecting with the specified range.
            // Since DTRs store dcp before any changes, during iteration
            // accumulate positionsAdded (number of characters added to the tree 
            // up to the current point).
            while (i < _count) 
            { 
                if (dcpNew <= _dtrs[i].StartIndex + positionsAdded + _dtrs[i].PositionsAdded)
                { 
                    break;
                }
                positionsAdded += _dtrs[i].PositionsAdded - _dtrs[i].PositionsRemoved;
                ++i; 
            }
            first = i; 
 
            // Find the last dtr intersecting with the specified range.
            // dcpNew-positionsAdded points to position before any tree changes, from 
            // where we start counting cchOld.
            // Do not add characters (positionsAdded), since start position has been already found.
            while (i < _count)
            { 
                if (dcpNew - positionsAdded + cchOld <= _dtrs[i].StartIndex + _dtrs[i].PositionsRemoved)
                { 
                    // If there is no intersection with the current DTR, go to the previous one. 
                    if (dcpNew - positionsAdded + cchOld < _dtrs[i].StartIndex)
                    { 
                        --i;
                    }
                    break;
                } 
                ++i;
            } 
            last = (i < _count) ? i : _count-1; 

            // If there are DTRs in the specified range, create new DtrList object 
            if (last >= first)
            {
                dtrs = new DtrList();
                while (last >= first) 
                {
                    // Since dcpNew is after tree changes, add positionsAdded to all dtrs 
                    // to build dtr list relative to dcpNew position. 
                    DirtyTextRange dtr = _dtrs[first];
                    dtr.StartIndex += positionsAdded; 
                    dtrs.Append(dtr);
                    ++first;
                }
            } 
            return dtrs;
        } 
 
        // -----------------------------------------------------------------
        // Merge DRT at position 'index' with the next one, if possible. 
        //
        //      index - Index of the DTR to be merged with next one.
        // -----------------------------------------------------------------
        private void MergeWithNext(int index) 
        {
            while (index + 1 < _count) 
            { 
                DirtyTextRange dtrNext = _dtrs[index+1];
 
                // DTR starts in the range of the previous DTR. In this case
                // merge these 2 DTRs.
                if (dtrNext.StartIndex <= _dtrs[index].StartIndex + _dtrs[index].PositionsRemoved)
                { 
                    //_dtrs[index].dcp: no need to change it
                    _dtrs[index].PositionsAdded += dtrNext.PositionsAdded; 
                    _dtrs[index].PositionsRemoved += dtrNext.PositionsRemoved; 

                    // Remove merged entry 
                    for (int i = index + 2; i < _count; i++)
                    {
                        _dtrs[i - 1] = _dtrs[i];
                    } 

                    --_count; 
                } 
                else
                { 
                    break;
                }
            }
        } 

        // ----------------------------------------------------------------- 
        // Append new DTR to the list. 
        //
        //      dtr - DTR to be appended to the list. 
        // ------------------------------------------------------------------
        private void Append(DirtyTextRange dtr)
        {
            if (_count == _dtrs.Length) { Resize(); } 
            _dtrs[_count] = dtr;
            ++_count; 
        } 

        // ----------------------------------------------------------------- 
        // Increases the capacity of the DTR array.
        //  = *2.
        // ------------------------------------------------------------------
        private void Resize() 
        {
            Debug.Assert(_dtrs.Length > 0); 
 
            // Allocate new array and copy all existing entries into it
            DirtyTextRange [] newdtrs = new DirtyTextRange[_dtrs.Length * 2]; 
            Array.Copy(_dtrs, newdtrs, _dtrs.Length);
            _dtrs = newdtrs;
        }
 
        // ------------------------------------------------------------------
        // Array like access to list of DTRs. 
        // ----------------------------------------------------------------- 
        internal int Length
        { 
            get { return _count; }
        }
        internal DirtyTextRange this[int index]
        { 
            get { return _dtrs[index]; }
        } 
 
        // ------------------------------------------------------------------
        // Array of DTRs. This array stores sorted list of DTRs. 
        // -----------------------------------------------------------------
        private DirtyTextRange [] _dtrs;

        // ----------------------------------------------------------------- 
        // Default capacity of the DTRs array. The array capacity is always
        // increased in multiples of two as required: 4*(2^N). 
        // ----------------------------------------------------------------- 
        private const int _defaultCapacity = 4;
        private int _count; 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK