File: src\Framework\MS\Internal\Data\LiveShapingBlock.cs
Project: wpf\PresentationFramework.csproj (PresentationFramework)
//---------------------------------------------------------------------------
//
// <copyright file="LiveShapingBlock.cs" company="Microsoft">
//    Copyright (C) by Microsoft Corporation.  All rights reserved.
// </copyright>
//
//
// Description: A component of the list data structure used for live shaping.
//
//---------------------------------------------------------------------------
 
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
 
using System.Windows;
using System.Windows.Data;
 
namespace MS.Internal.Data
{
    internal class LiveShapingBlock : RBNode<LiveShapingItem>
    {
        internal LiveShapingBlock() : base() {}
        internal LiveShapingBlock(bool b) : base(b) {}
        LiveShapingBlock ParentBlock { get { return Parent as LiveShapingBlock; } }
        LiveShapingBlock LeftChildBlock { get { return (LiveShapingBlock)LeftChild; } }
        LiveShapingBlock RightChildBlock { get { return (LiveShapingBlock)RightChild; } }
 
        internal LiveShapingList List
        {
            get { return ((LiveShapingTree)GetRoot(this)).List; }
        }
 
        public override LiveShapingItem SetItemAt(int offset, LiveShapingItem lsi)
        {
            base.SetItemAt(offset, lsi);
            if (lsi != null)
                lsi.Block = this;
            return lsi;
        }
 
        protected override void Copy(RBNode<LiveShapingItem> sourceNode, int sourceOffset, RBNode<LiveShapingItem> destNode, int destOffset, int count)
        {
            #if LiveShapingInstrumentation
            ++_copies;
            _totalCopySize += count;
            #endif
 
            base.Copy(sourceNode, sourceOffset, destNode, destOffset, count);
 
            if (sourceNode != destNode)
            {
                LiveShapingBlock destBlock = (LiveShapingBlock)destNode;
 
                for (int k=0; k<count; ++k, ++destOffset)
                {
                    destNode.GetItemAt(destOffset).Block = destBlock;
                }
            }
        }
 
        internal RBFinger<LiveShapingItem> GetFinger(LiveShapingItem lsi)
        {
            int baseIndex;
            int offset = OffsetOf(lsi);
            GetRootAndIndex(this, out baseIndex);
            return new RBFinger<LiveShapingItem>() { Node=this, Offset=offset, Index=baseIndex+offset, Found=true };
        }
 
        // find the current and desired position of the given item (called while restoring live sorting)
        // The hurdle here is that items marked IsSortDirty should be ignored - their sort property
        // has changed, so they are possibly not in the right place.
        internal void FindPosition(LiveShapingItem item, out RBFinger<LiveShapingItem> oldFinger, out RBFinger<LiveShapingItem> newFinger, Comparison<LiveShapingItem> comparison)
        {
            // within this block, find the first and last sort-clean items, the given item
            // itself, and the nearest sort-clean items on either side of the given item
            int size = Size;
            int index;
            int first=-1, last, left=-1, right;
            LiveShapingItem lsi;
 
            for (index=0; index<size; ++index)
            {   // linear search finds the item, the first clean item, and the left-nearest
                lsi = GetItemAt(index);
                if (item == lsi)
                    break;
 
                if (!lsi.IsSortDirty)
                {
                    left = index;
                    if (first < 0)
                        first = index;
                }
            }
 
            Debug.Assert(index < size, "FindPosition called with item not in its block");
 
            for (right=index+1; right<size; ++right)
            {   // continue the linear search to find the right-nearest
                lsi = GetItemAt(right);
                if (!lsi.IsSortDirty)
                    break;
            }
 
            last = right;
            for (int k=size-1; k>last; --k)
            {   // reverse linear search to find the last clean item
                lsi = GetItemAt(k);
                if (!lsi.IsSortDirty)
                    last = k;
            }
 
            // now we know enough to create the oldFinger
            int baseIndex;
            GetRootAndIndex(this, out baseIndex);
            oldFinger = new RBFinger<LiveShapingItem>() { Node=this, Offset=index, Index=baseIndex+index, Found=true };
 
            // find the newFinger
            // The current picture is:
            //      first       left    index       right       last
            // |----v-----------v-------v-----------v-----------v-----------|
            // |****|           |*******|***********|           |***********|
            // |------------------------------------------------------------|
            // Items under the pointers are clean (unless the pointers fall off the
            // end).  The shaded regions are dirty, the unshaded regions can be
            // a mixture of clean and dirty.  Any of the regions might be empty,
            // as the pointers can coincide.
 
            LiveShapingItem leftItem = (left >= 0) ? GetItemAt(left) : null;
            LiveShapingItem rightItem = (right < size) ? GetItemAt(right) : null;
            int cL=0, cR=0; // result of comparisons
 
            if (leftItem != null && (cL=comparison(item, leftItem)) < 0)
            {
                if (first != left)
                    cL = comparison(item, GetItemAt(first));
                if (cL >= 0)
                {   // item belongs between first and left
                    newFinger = LocalSearch(item, first+1, left, comparison);
                }
                else
                {   // item belongs to the left of this block
                    newFinger = SearchLeft(item, first, comparison);
                }
            }
            else if (rightItem != null && (cR=comparison(item, rightItem)) > 0)
            {
                if (last != right)
                    cR = comparison(item, GetItemAt(last));
                if (cR <= 0)
                {   // item belongs between right and last
                    newFinger = LocalSearch(item, right+1, last, comparison);
                }
                else
                {   // item belongs to the right of this block
                    newFinger = SearchRight(item, last+1, comparison);
                }
            }
            else if (leftItem != null)  // hence item >= leftItem
            {
                if (rightItem != null)  // hence item <= rightItem
                {   // item is already in a good position
                    newFinger = oldFinger;
                }
                else
                {   // item belongs to the right of this block
                    newFinger = SearchRight(item, index, comparison);
                }
            }
            else // leftItem == null
            {
                if (rightItem != null)  // hence item <= rightItem
                {
                    newFinger = SearchLeft(item, index, comparison);
                }
                else
                {   // no other clean items in this block - item could belong anywhere
                    newFinger = SearchLeft(item, index, comparison);
                    if (newFinger.Node == this)
                    {   // couldn't find it for sure on the left - look right
                        newFinger = SearchRight(item, index, comparison);
                    }
                }
            }
        }
 
        // binary search that ignores dirty items
        RBFinger<LiveShapingItem> LocalSearch(LiveShapingItem item, int left, int right, Comparison<LiveShapingItem> comparison)
        {
            int k;
            while (right - left > BinarySearchThreshold)
            {
                int mid = (left + right) / 2;
                for (k=mid; k>=left; --k)
                {
                    if (!GetItemAt(k).IsSortDirty)
                        break;
                }
 
                if (k < left || comparison(GetItemAt(k), item) <= 0)
                {
                    left = mid + 1;
                }
                else
                {
                    right = k;
                }
            }
 
            for (k=left; k<right; ++k)
            {
                if (!GetItemAt(k).IsSortDirty && comparison(item, GetItemAt(k)) <= 0)
                    break;
            }
 
            int index;
            GetRootAndIndex(this, out index);
            return new RBFinger<LiveShapingItem>() { Node = this, Offset = k, Index = index+k };
        }
 
 
        /* The next two methods - SearchLeft and SearchRight - are called when the item
            might belong to a different node.  I.e. it compares below the first clean item
            in the current node (or there is no first clean item), or it compares above
            the last clean item (or there is no last clean item).   Here's the picture for
            the "left" case.
                                                    Legend
                    [-----]                     +       starting node
                   /       \                    [----]  left-ancestor - needs search
                  *         0                   0       right-ancestor - doesn't need search
                           /                    *       unexplored left subtree
                       [-----]
                      /       \
                     *         +
                              /
                             *
            To find where the item belongs, we first walk up the tree pausing at
            each left-ancestor (so we visit them right-to-left).  If it has no clean
            items, we learn nothing - instead we add its left subtree * to a list
            of unexplored subtrees that we may search later.  More likely, it has clean
            items, and comparisons will tell us whether the item belongs to the ancestor
            itself, to its left, or to its right.  This constrains the search:
 
                itself  the item belongs to the ancestor - use binary search to find where
                left    the item can't belong to the unexplored trees - discard them
                right   the item can't belong any farther left - stop the upward tree walk
 
            When the upward walk stops without finding a home for the item, we start
            searching the unexplored subtrees, right-to-left.  To search a subtree,
            we first look at its root.  As above, the bad case is when the root has
            no clean items;  in that case we need to search both its subtrees, so we push
            them on a stack (the stack holds the unexplored roots in right-to-left
            order).   Here's a picture:
 
                    Stack                       *           Stack
                                               / \            R
                      *     ==> Pop *   ==>   L   R  ==>      L
                      x                                       x
 
            With better luck, the subtree root will have clean items, and comparisons
            will tell us where the item belongs with respect to the node:
 
                itself  use binary search to find where
                left    push the node's left child onto the stack
                right   push the node's right child onto the stack
 
            Throughout this search, we keep track of the rightmost node the item
            could belong to (the "found node").  Initially this is the original
            starting node, but it changes as we move left from a subtree root.
            If the stack empties without finding a home, we put the item into
            the "found node", to the left of its leftmost clean item.
 
            The "right" search is symmetric.  We explore right-ancestors, followed
            by unexplored subtrees in left-to-right order.
        */
 
        // find the item in the tree to my left.  If it's larger than the nearest clean
        // neighbor, return a finger to the given offset within this node
        RBFinger<LiveShapingItem> SearchLeft(LiveShapingItem item, int offset, Comparison<LiveShapingItem> comparison)
        {
            LiveShapingBlock foundBlock = this;
 
            List<LiveShapingBlock> list = new List<LiveShapingBlock>();  // subtrees to explore
            list.Add(LeftChildBlock);
 
            // phase 1, walk up the tree looking for the item in each left-parent
            LiveShapingBlock block, parent;
            int first, last, size;
            for (block=this, parent=block.ParentBlock; parent != null; block=parent, parent=block.ParentBlock)
            {
                if (parent.RightChildBlock == block)
                {
                    parent.GetFirstAndLastCleanItems(out first, out last, out size);
 
                    // find where the search item belongs relative to the clean items
                    if (first >= size)
                    {   // no clean items - add the left subtree for later exploration
                        list.Add(parent.LeftChildBlock);
                    }
                    else if (comparison(item, parent.GetItemAt(last)) > 0)
                    {   // item belongs to the right of parent - no need to climb higher
                        break;
                    }
                    else if (comparison(item, parent.GetItemAt(first)) >= 0)
                    {   // item belongs in the parent
                        return parent.LocalSearch(item, first+1, last, comparison);
                    }
                    else
                    {   // item belongs to the left of parent, thus also left of unexplored subtrees
                        list.Clear();
                        list.Add(parent.LeftChildBlock);
                        foundBlock = parent;
                        offset = first;
                    }
                }
            }
 
            // phase 2, item wasn't found in a left-parent, so it belongs in one of the
            // unexplored subtrees.   Search them right-to-left, hoping item didn't move far.
            Stack<LiveShapingBlock> stack = new Stack<LiveShapingBlock>(list);
            while (stack.Count > 0)
            {
                block = stack.Pop();
                if (block == null)
                    continue;
 
                block.GetFirstAndLastCleanItems(out first, out last, out size);
 
                if (first >= size)
                {   // no clean items - explore the subtrees
                    stack.Push(block.LeftChildBlock);
                    stack.Push(block.RightChildBlock);
                }
                else if (comparison(item, block.GetItemAt(last)) > 0)
                {   // item belongs to the right
                    stack.Clear();
                    stack.Push(block.RightChildBlock);
                }
                else if (comparison(item, block.GetItemAt(first)) >= 0)
                {   // item belongs in the current block
                    return block.LocalSearch(item, first+1, last, comparison);
                }
                else
                {   // item belongs to the left of the block, or possibly in it
                    foundBlock = block;
                    offset = first;
                    stack.Push(block.LeftChildBlock);
                }
            }
 
            // phase 3, item wasn't found within any block, so put it at the
            // edge of the "found" block
            int baseIndex;
            GetRootAndIndex(foundBlock, out baseIndex);
            return new RBFinger<LiveShapingItem>() { Node=foundBlock, Offset=offset, Index=baseIndex+offset };
        }
 
        // find the item in the tree to my right.  If it's smaller than the nearest clean
        // neighbor, return a finger to the given offset within this node
        RBFinger<LiveShapingItem> SearchRight(LiveShapingItem item, int offset, Comparison<LiveShapingItem> comparison)
        {
            LiveShapingBlock foundBlock = this;
 
            List<LiveShapingBlock> list = new List<LiveShapingBlock>();  // subtrees to explore
            list.Add(RightChildBlock);
 
            // phase 1, walk up the tree looking for the item in each right-parent
            LiveShapingBlock block, parent;
            int first, last, size;
            for (block=this, parent=block.ParentBlock; parent != null; block=parent, parent=block.ParentBlock)
            {
                if (parent.LeftChildBlock == block)
                {
                    parent.GetFirstAndLastCleanItems(out first, out last, out size);
 
                    // find where the search item belongs relative to the clean items
                    if (first >= size)
                    {   // no clean items - add the right subtree for later exploration
                        list.Add(parent.RightChildBlock);
                    }
                    else if (comparison(item, parent.GetItemAt(first)) < 0)
                    {   // item belongs to the left of parent - no need to climb higher
                        break;
                    }
                    else if (comparison(item, parent.GetItemAt(last)) <= 0)
                    {   // item belongs in the parent
                        return parent.LocalSearch(item, first+1, last, comparison);
                    }
                    else
                    {   // item belongs to the right of parent, thus also right of unexplored subtrees
                        list.Clear();
                        list.Add(parent.RightChildBlock);
                        foundBlock = parent;
                        offset = last+1;
                    }
                }
            }
 
            // phase 2, item wasn't found in a right-parent, so it belongs in one of the
            // unexplored subtrees.   Search them left-to-right, hoping item didn't move far.
            Stack<LiveShapingBlock> stack = new Stack<LiveShapingBlock>(list);
            while (stack.Count > 0)
            {
                block = stack.Pop();
                if (block == null)
                    continue;
 
                block.GetFirstAndLastCleanItems(out first, out last, out size);
 
                if (first >= size)
                {   // no clean items - explore the subtrees
                    stack.Push(block.RightChildBlock);
                    stack.Push(block.LeftChildBlock);
                }
                else if (comparison(item, block.GetItemAt(first)) < 0)
                {   // item belongs to the left
                    stack.Clear();
                    stack.Push(block.LeftChildBlock);
                }
                else if (comparison(item, block.GetItemAt(last)) <= 0)
                {   // item belongs in the current block
                    return block.LocalSearch(item, first+1, last, comparison);
                }
                else
                {   // item belongs to the right of the block, or possibly in it
                    foundBlock = block;
                    offset = last+1;
                    stack.Push(block.RightChildBlock);
                }
            }
 
            // phase 3, item wasn't found within any block, so put it at the
            // edge of the "found" block
            int baseIndex;
            GetRootAndIndex(foundBlock, out baseIndex);
            return new RBFinger<LiveShapingItem>() { Node=foundBlock, Offset=offset, Index=baseIndex+offset };
        }
 
        void GetFirstAndLastCleanItems(out int first, out int last, out int size)
        {
            size=Size;
            for (first=0; first<size; ++first)
            {
                if (!GetItemAt(first).IsSortDirty)
                    break;
            }
            for (last=size-1; last>first; --last)
            {
                if (!GetItemAt(last).IsSortDirty)
                    break;
            }
        }
 
        #if LiveShapingInstrumentation

        static internal void SetNodeSize(int nodeSize)
        {
            MaxSize = nodeSize;
        }
 
        static internal int _copies, _totalCopySize;
        #endif // LiveShapingInstrumentation
    }
}