FixedTextBuilder.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / wpf / src / Framework / System / Windows / Documents / FixedTextBuilder.cs / 1 / FixedTextBuilder.cs

                            //---------------------------------------------------------------------------- 
// 
//      Copyright (C) 2004 by Microsoft Corporation.  All rights reserved.
// 
// 
// Description:
//      FixedTextBuilder contains heuristics to map fixed document elements 
//      into stream of flow text 
//
// History: 
//      02/10/2004 - Zhenbin Xu (ZhenbinX) - Created.
//
//---------------------------------------------------------------------------
 
namespace System.Windows.Documents
{ 
    using MS.Internal.Documents; 
    using System.Windows.Controls;      // UIElementCollection
    using System.Windows.Media; 
    using System.Windows.Media.Imaging;
    using System.Windows.Markup;
    using System.Windows.Shapes;       // Glyphs
    using System.Windows.Automation; 
    using System.Windows.Documents.DocumentStructures;
    using System; 
    using System.Collections; 
    using System.Collections.Generic;
    using System.Diagnostics; 
    using System.Globalization;
    using System.Text;
    using System.IO;
    using System.Xml; 
    using Path=System.Windows.Shapes.Path;
 
    using MS.Utility; 

    //===================================================================== 
    /// 
    /// FixedTextBuilder contains heuristics to map fixed document elements
    /// into stream of flow text.
    ///  
    internal sealed class FixedTextBuilder
    { 
        //------------------------------------------------------------------- 
        //
        // Consts 
        //
        //----------------------------------------------------------------------
        #region Const
        internal const char FLOWORDER_SEPARATOR = ' '; 
        #endregion Const
 
 

        //------------------------------------------------------------------- 
        //
        // Statics
        //
        //---------------------------------------------------------------------- 
        #region Statics
 
        // A list of CultureInfo that are always adjacent 
        internal static CultureInfo[] AdjacentLanguage =
        { 
            new CultureInfo("zh-CHS"),      // Chinese Simplified
            new CultureInfo("zh-CHT"),      // Chinese Traditional
            new CultureInfo("zh-HK"),       // Chinese Hong Kong SAR
            new CultureInfo("zh-MO"),       // Chinese Macau SAR 
            new CultureInfo("zh-CN"),       // Chinese China
            new CultureInfo("zh-SG"),       // Chinese Singapore 
            new CultureInfo("zh-TW"),       // Chinese `Taiwan 
            new CultureInfo("ja-JP"),       // Japanese
            new CultureInfo("ko-KR"),       // Korean 
            new CultureInfo("th-TH")        // Thai
        };

 
        internal static bool AlwaysAdjacent(CultureInfo ci)
        { 
            foreach (CultureInfo cultureInfo in AdjacentLanguage) 
            {
                if (ci.Equals(cultureInfo)) 
                {
                    return true;
                }
            } 
            return false;
        } 
 

 
        // obtained via Unicode 3.0 book: C0 Controls and Basic Latin.
        //    0x002D/0x00AD and their related characters.
        //
        // NOTE it is okay to not getting accurate list as long as 
        // we deal with common cases since this is used in heuristic
        // algorithm! 
        internal static char[] HyphenSet = 
        {
            '\x002D',     // Hyphen-Minus 
            '\x2010',     // Hyphen
            '\x2011',     // Non-breaking Hyphen
            '\x2012',     // Figure-dash
            '\x2013',     // En-dash 
            '\x2212',     // Minus Sign
            '\x00AD'      // Soft-Hyphen 
        }; 

        internal static bool IsHyphen(char target) 
        {
            foreach (char hyphen in HyphenSet)
            {
                if (hyphen == target) 
                {
                    return true; 
                } 
            }
            return false; 
        }

        // Space that was used in the heuristic algorithm.
        internal static bool IsSpace(char target) 
        {
            // Only the regular space character is considered 
            // space. 
            return (target == '\x0020');
        } 
        #endregion Statics


        //-------------------------------------------------------------------- 
        //
        // Connstructors 
        // 
        //---------------------------------------------------------------------
 
        #region Constructors
        internal FixedTextBuilder(FixedTextContainer container)
        {
            _container = container; 
            _Init();
        } 
        #endregion Constructors 

        //-------------------------------------------------------------------- 
        //
        // Public Methods
        //
        //--------------------------------------------------------------------- 

        //------------------------------------------------------------------- 
        // 
        // Public Properties
        // 
        //---------------------------------------------------------------------

        //--------------------------------------------------------------------
        // 
        // Public Events
        // 
        //--------------------------------------------------------------------- 

        //-------------------------------------------------------------------- 
        //
        // Internal Methods
        //
        //---------------------------------------------------------------------- 

        #region Internal Methods 
 
        //-------------------------------------------------------------------
        // Virtualization 
        //----------------------------------------------------------------------

        // Add virtual FlowNode to represent the page
        internal void AddVirtualPage() 
        {
#if DEBUG 
            DocumentsTrace.FixedTextOM.Builder.Trace(string.Format("AppendVirtualPage {0}", _pageStructures.Count)); 
#endif
            FixedPageStructure pageStructure = new FixedPageStructure(_pageStructures.Count); 
#if DEBUG
            pageStructure.FixedTextBuilder = this;
#endif
            _pageStructures.Add(pageStructure); 

            // Insert the virtural FlowNode into the Flow Order. 
            _fixedFlowMap.FlowOrderInsertBefore(_fixedFlowMap.FlowEndEdge, pageStructure.FlowStart); 

        } 


        //-------------------------------------------------------------------
        // Devirtualizing flow structure 
        //---------------------------------------------------------------------
 
        // Making sure a page is devirtualized 
        // All function that takes FixedNode as parameter and asks for FlowPosition
        // related content should call this functions first!!! 
        internal bool EnsureTextOMForPage(int pageIndex)
        {
            Debug.Assert(!_IsBoundaryPage(pageIndex));
            FixedPageStructure pageStructure = _pageStructures[pageIndex]; 
            if (!pageStructure.Loaded)
            { 
                EventTrace.NormalTraceEvent(EventTraceGuidId.DRXENSUREOMGUID, EventType.StartEvent); 

                FixedPage page = _container.FixedDocument.SyncGetPage(pageIndex, false); 

                if (page == null)
                    return false;
 
                Size pageSize = _container.FixedDocument.ComputePageSize(page);
 
                page.Measure(pageSize); 
                page.Arrange(new Rect(new Point(0, 0), pageSize));
 
                Debug.Assert(page != null);
                Debug.Assert(page.IsInitialized);

                bool constructSOM = true; 
                StoryFragments sf = page.GetPageStructure();
                if (sf != null) 
                { 
                    constructSOM = false;
                    FixedDSBuilder fb = new FixedDSBuilder(page, sf); 
                    pageStructure.FixedDSBuilder = fb;
                }

                if (constructSOM) 
                {
                    FixedSOMPageConstructor pageConstructor = new FixedSOMPageConstructor(page, pageIndex); 
                    pageStructure.PageConstructor = pageConstructor; 
                    pageStructure.FixedSOMPage = pageConstructor.FixedSOMPage;
                } 

                DocumentsTrace.FixedTextOM.Builder.Trace(string.Format("_EnsureTextOMForPage Loading..."));
                _CreateFixedMappingAndElementForPage(pageStructure, page, constructSOM);
 
#if DEBUG
                // 
                // Note: this debug verification is expensive. I have moved this code from FixedFlowMap.cs 
                // to reduce the rate is is called. Now it is called after each page is constructed and might
                // still have effect on long documents and scrolling in page per stream case. 
                //
                //FixedFlowMap.DebugVerifyMapping(true);
#endif
                EventTrace.NormalTraceEvent(EventTraceGuidId.DRXENSUREOMGUID, EventType.EndEvent); 

                return true; 
            } 

#if DEBUG 
            FixedPage fixedPage = _container.FixedDocument.SyncGetPage(pageIndex, false);
            fixedPage.FixedPageStructure = pageStructure;
#endif
            return false; 
        }
 
        //------------------------------------------------------------------- 
        // Fixed Document
        //---------------------------------------------------------------------- 

        // This could return null if FixedNode is an artificial boundary node
        internal FixedPage GetFixedPage(FixedNode node)
        { 
            FixedDocument doc = _container.FixedDocument;
            return doc.SyncGetPageWithCheck(node.Page); 
        } 

        // This could return null if FixedNode is an artificial boundary node 
        internal Glyphs GetGlyphsElement(FixedNode node)
        {
            FixedPage page = GetFixedPage(node);
            if (page != null) 
            {
                return page.GetGlyphsElement(node); 
            } 
            return null;
        } 


        //-------------------------------------------------------------------
        // Hit Testing / Keyboard Navigation 
        //----------------------------------------------------------------------
 
        // Given a fixed node, find its next/previous line 
        // count:
        //      in   # of lines desired 
        //      out  # of lines remaining
        // Return null if no next line
        internal FixedNode[] GetNextLine(FixedNode currentNode, bool forward, ref int count)
        { 
            if (_IsBoundaryPage(currentNode.Page))
            { 
                return null; 
            }
 
            EnsureTextOMForPage(currentNode.Page);
            FixedPageStructure ps = _pageStructures[currentNode.Page];

            if (_IsStartVisual(currentNode[1])) 
            {
                FixedNode[] firstLine = ps.FirstLine; 
                if (firstLine == null) 
                {
                    return null; 
                }
                currentNode = firstLine[0];
                count--;
            } 
            else if (_IsEndVisual(currentNode[1]))
            { 
                FixedNode[] lastLine = ps.LastLine; 
                if (lastLine == null)
                { 
                    return null;
                }
                currentNode = lastLine[0];
                count--; 
            }
 
            FixedSOMTextRun run = _fixedFlowMap.MappingGetFixedSOMElement(currentNode, 0) as FixedSOMTextRun; 

            if (run == null) 
            {
                return null;
            }
 
            int lineIndex = run.LineIndex;
 
            return ps.GetNextLine(lineIndex, forward, ref count); 
        }
 

        // Given a fixed node
        // Return null is cannot get line
        internal FixedNode[] GetLine(int pageIndex, Point pt) 
        {
            EnsureTextOMForPage(pageIndex); 
            return _pageStructures[pageIndex].FindSnapToLine(pt); 
        }
 
        // Find first line on page
        internal FixedNode[] GetFirstLine(int pageIndex)
        {
            EnsureTextOMForPage(pageIndex); 
            return _pageStructures[pageIndex].FirstLine;
        } 
 
        //-----------------------------------------------
        // Fixed nodes ==>  FlowPosition 
        //-----------------------------------------------

        // Find out flow offset given fixed position
        internal FlowPosition CreateFlowPosition(FixedPosition fixedPosition) 
        {
            // make sure page has been loaded 
            EnsureTextOMForPage(fixedPosition.Page); 

            FixedSOMElement element = _fixedFlowMap.MappingGetFixedSOMElement(fixedPosition.Node, fixedPosition.Offset); 
            if (element != null)
            {
                FlowNode flow = element.FlowNode;
                int fixedOffset = fixedPosition.Offset; 
                FixedSOMTextRun run = element as FixedSOMTextRun;
                if (run != null && run.IsReversed) 
                { 
                    fixedOffset  = run.EndIndex - run.StartIndex - fixedOffset;
                } 
                int offset = element.OffsetInFlowNode + fixedOffset - element.StartIndex;
                return new FlowPosition(_container, flow, offset);
            }
            return null; 
        }
 
 
        internal FlowPosition GetPageStartFlowPosition(int pageIndex)
        { 
            EnsureTextOMForPage(pageIndex);

            FlowNode fn = _pageStructures[pageIndex].FlowStart;
            // Remove this assert once we start supporting element across page bounary 
            Debug.Assert(fn.Type == FlowNodeType.Start);
            return new FlowPosition(_container, fn, 0); 
        } 

 
        internal FlowPosition GetPageEndFlowPosition(int pageIndex)
        {
            EnsureTextOMForPage(pageIndex);
 
            // Remove this assert once we start supporting element across page bounary
            FlowNode fn = _pageStructures[pageIndex].FlowEnd; 
            return new FlowPosition(_container, fn, 1); 
        }
 
        //-----------------------------------------------
        // FlowPosition ==>  Fixed Nodes
        //-----------------------------------------------
 
        // This function can handle flow nodes that are mapped to fixed nodes (Object or Run type) and start and end nodes
        internal bool GetFixedPosition(FlowPosition position, LogicalDirection textdir, out FixedPosition fixedp) 
        { 
            // Currently broken on empty page and on start/end flow nodes!
            // Init out parameter 
            fixedp = new FixedPosition(FixedFlowMap.FixedStartEdge, 0);

            int flowOffset;
            FlowNode flow; 

            position.GetFlowNode(textdir, out flow, out flowOffset); 
            FixedSOMElement[] fixes = flow.FixedSOMElements; 
            if (fixes == null)
            { 
                return false;
            }

            int loIndex = 0, hiIndex = fixes.Length - 1; 
            while (hiIndex > loIndex)
            { 
                int index = (hiIndex + loIndex + 1) >> 1; // middle, round up -- guarantee hiIndex >= index > loIndex 
                if (fixes[index].OffsetInFlowNode > flowOffset)
                { 
                    hiIndex = index - 1;
                }
                else
                { 
                    loIndex = index;
                } 
            } 

            FixedSOMElement element = fixes[loIndex]; 
            FixedSOMTextRun run;

            if (loIndex > 0 &&
                textdir == LogicalDirection.Backward && 
                element.OffsetInFlowNode == flowOffset)
            { 
                //check if we should really be in the prior element 
                FixedSOMElement last = fixes[loIndex - 1];
                int offsetInLast = flowOffset - last.OffsetInFlowNode + last.StartIndex; 

                if (offsetInLast == last.EndIndex)
                {
                    run = last as FixedSOMTextRun; 
                    if (run != null && run.IsReversed)
                    { 
                        offsetInLast = run.EndIndex - run.StartIndex - offsetInLast; 

                    } 
                    fixedp = new FixedPosition(last.FixedNode, offsetInLast);
                    return true;
                }
            } 

            run = element as FixedSOMTextRun; 
            int fixedOffset  = flowOffset - element.OffsetInFlowNode + element.StartIndex; 
            if (run != null && run.IsReversed)
            { 
                fixedOffset = run.EndIndex - run.StartIndex - fixedOffset;

            }
            fixedp = new FixedPosition(element.FixedNode, fixedOffset); 
            return true;
 
        } 

 
        // Find out fixed node given flow positions
        internal bool GetFixedNodesForFlowRange(FlowPosition pStart,
                                                            FlowPosition pEnd,
                                                            out FixedSOMElement[] somElements, 
                                                            out int firstElementStart,
                                                            out int lastElementEnd) 
        { 
            Debug.Assert(pStart.CompareTo(pEnd) < 0);
            somElements = null; 
            firstElementStart = 0;
            lastElementEnd = 0;

            FlowNode[] flowNodes; 
            int charStart = 0;
            int charEnd = -1; 
 
            int offsetStart;
            int offsetEnd; 

            pStart.GetFlowNodes(pEnd, out flowNodes, out offsetStart, out offsetEnd);
            if (flowNodes.Length <= 0)
            { 
                return false;
            } 
 
            ArrayList ar = new ArrayList();
            FlowNode flowStart  = flowNodes[0]; 
            FlowNode flowEnd    = flowNodes[flowNodes.Length - 1];

            foreach (FlowNode flowScan in flowNodes)
            { 
                int skipBefore = 0;
                int stopAt     = Int32.MaxValue; 
                if (flowScan == flowStart) 
                {
                    skipBefore = offsetStart; 
                }

                if (flowScan == flowEnd)
                { 
                    stopAt = offsetEnd;
                } 
 
                if (flowScan.Type == FlowNodeType.Object)
                { 
                    FixedSOMElement[] fixes = flowScan.FixedSOMElements;
                    Debug.Assert(fixes.Length == 1);
                    ar.Add(fixes[0]);
                } 

                if (flowScan.Type == FlowNodeType.Run) 
                { 
                    FixedSOMElement[] fixes = flowScan.FixedSOMElements;
                    foreach (FixedSOMElement element in fixes) 
                    {
                        int startIndex = element.OffsetInFlowNode;
                        if (startIndex >= stopAt)
                        { 
                            break;
                        } 
 
                        int endIndex = startIndex + element.EndIndex - element.StartIndex;
                        if (endIndex <= skipBefore) 
                        {
                            continue;
                        }
 
                        ar.Add(element);
 
                        if (skipBefore >= startIndex && flowScan == flowStart) 
                        {
                            charStart = element.StartIndex + skipBefore - startIndex; 
                        }

                        if (stopAt <= endIndex && flowScan == flowEnd)
                        { 
                            charEnd = element.StartIndex + stopAt - startIndex;
                            break; 
                        } 
                        else if (stopAt == endIndex + 1)
                        { 
                            charEnd = element.EndIndex; //in case this ends at beginning of next node
                        }

                    } 
                }//endofifrun
            }//endofforeach FlowNode 
 
            // This array could be empty! (Maybe...)  Broken if it is.
            somElements = (FixedSOMElement[])ar.ToArray(typeof(FixedSOMElement)); 
            if (somElements.Length == 0)
            {
                return false;
            } 

            if (flowStart.Type == FlowNodeType.Object) 
            {   // Image 
                firstElementStart = offsetStart;
            } 
            else
            {
                firstElementStart = charStart;
            } 
            if (flowEnd.Type == FlowNodeType.Object)
            { 
                lastElementEnd = offsetEnd; 
            }
            else 
            {
                lastElementEnd = charEnd;
            }
 
            return true;
        } 
 
        //-----------------------------------------------
        // FlowPosition ==>  Flow Content 
        //-----------------------------------------------

        // Helper function to retrieve text from FixedNodes that are mapped
        // to a flow run represented by a FlowPosition. 
        internal string GetFlowText(FlowNode flowNode)
        { 
            Debug.Assert(flowNode.Type == FlowNodeType.Run); 

            StringBuilder sb = new StringBuilder(); 
            FixedSOMElement[] fixes = flowNode.FixedSOMElements;
            Debug.Assert(flowNode.Type == FlowNodeType.Run);
            Debug.Assert(fixes != null);
 
            foreach (FixedSOMTextRun element in fixes)
            { 
                sb.Append(element.Text); 
            }
            return sb.ToString(); 
        }

        internal static bool MostlyRTL(string s)
        { 
            int RTL = 0;
            int LTR = 0; 
            foreach (char c in s) 
            {
                if (_IsRTL(c)) 
                {
                    RTL++;
                }
                else if (c != ' ') 
                {
                    LTR++; 
                } 
            }
 
            return (RTL > 0) && (LTR == 0 || (RTL / LTR >= 2));
        }

        //Decides whether two lines specified by line heights and a vertical distance between them is considered on the same line 
        //verticalDistance needs to be passed as top of line2 - top of line 1
        internal static bool IsSameLine(double verticalDistance, double fontSize1, double fontSize2) 
        { 
            // According to spec for rubber band selection, to adjacent Glyphs are on same line if they have 50% overlap
            double smallSize = (fontSize1 < fontSize2) ? fontSize1 : fontSize2; 
            double overlap = (verticalDistance > 0) ? (fontSize1 - verticalDistance) : (fontSize2 + verticalDistance);
            return overlap / smallSize > .5;
        }
 
        //------------------------------------------------------------------------------
        // Design Note (ZhenbinX - 2004/11/15) - Heuristic to test if two FixedSOMTextRun adjacent 
        // in geometry for the purpose of adding additional separator into non-adjacent runs. 
        // This algorithm bias toward NOT adding separator. The reason is artifically breaking
        // a word is more annoying than missing a space between words. 
        //
        // The following steps are applied in order:
        // 1. If the two TextRun belong to two different languages, they are not
        //    adjacent. (A separator is needed) 
        // 2. If the TextRun belongs to a language that does not use space as separator,
        //    they are always adjacent. (Need additional input about Bidi and complext 
        //    script here. Currently NOT adjacent). 
        // 3. If the two TextRuns belong to two different lines, they are NOT adjacent
        //    unless the end of the previous GlyphRun is HYPHEN. 
        // 3. For TextRuns on the same line:
        //    a. If the last character of the previous run is SPACE, they are adjacent.
        //    b. If they are in different Bidi embedding level, they are NOT adjacent.
        //    c. If the distance between their InkBoundingBox is greater than 1/4 of 
        //       the BoundingBox of the preceeding GlyphRun, they are NOT adjacent.
        //       (This can be tweaked to use step function in the future!). 
        // All others are adjacent Glyphs! 
        //
        //----------------------------------------------------------------------------- 
        internal static bool IsNonContiguous(CultureInfo ciPrev,
                                                    CultureInfo ciCurrent,
                                                    bool isSidewaysPrev,
                                                    bool isSidewaysCurrent, 
                                                    string strPrev,
                                                    string strCurrent, 
                                                    GlyphComparison comparison) 

        { 
            if (ciPrev != ciCurrent)
            {
                return true;
            } 
            if (AlwaysAdjacent(ciPrev))
            { 
                return false; 
            }
 

            if (isSidewaysPrev != isSidewaysCurrent)
            {
                return true;  // not adjacent 
            }
 
            if (strPrev.Length == 0 || strCurrent.Length == 0) 
            {
                return false;  // adjacent 
            }

            if (!isSidewaysPrev)
            {   // Horizontal Lines 
                int textLength = strPrev.Length;
                char lastChar = strPrev[textLength - 1]; 
 
                if (IsSpace(lastChar))
                { 
                    return false;       // adjacent
                }

                if (comparison == GlyphComparison.DifferentLine || 
                    comparison == GlyphComparison.Unknown)
                { 
                    // Different Line 
                    if (!IsHyphen(lastChar))
                    { 
                        return true;   // non adjacent
                    }
                }
                else 
                {
                    return comparison != GlyphComparison.Adjacent; 
                } 
            }
            return false;   // Default is adjacent 
        }


        #endregion Internal Methods 

 
        //-------------------------------------------------------------------- 
        //
        // Internal Properties 
        //
        //---------------------------------------------------------------------
        #region Internal Properties
        internal FixedFlowMap FixedFlowMap 
        {
            get 
            { 
                return _fixedFlowMap;
            } 
        }
#if DEBUG
        internal FixedTextContainer FixedTextContainer
        { 
            get
            { 
                return _container; 
            }
        } 
#endif

        #endregion Internal Propeties
 
        //-------------------------------------------------------------------
        // 
        // Private Methods 
        //
        //--------------------------------------------------------------------- 

        #region Private Methods

        //-------------------------------------------------------------------- 
        // Initilization
        //--------------------------------------------------------------------- 
        private void _Init() 
        {
            // Initialize Id 
            _nextScopeId  = FixedFlowMap.FlowOrderScopeIdStart;

            // Create empty mapping
            _fixedFlowMap = new FixedFlowMap(); 

            // 
            _pageStructures  = new List(); 
        }
 
        //--------------------------------------------------------------------
        // Heuristics
        //
        // Design Note (ZhenbinX): 
        //      Page boundary is artificially represented by a pair
        //      of FixedNodes. Start of Page uses int.MinValue as 
        //      its glyphs index, while End of Page uses int.MaxValue 
        //      as its glyphs index.  All users of FixedNode needs
        //      to be aware of such articifical index and special case 
        //      so that the "fake" glyphs indice are not used to access
        //      children.  One should always use FixedPage.GetGlyphs
        //      instead of using FixedPage's logical children collection
        //      directly, and should always check for possible null return. 
        //
        //      The page boundaries, however, are mapped to a FlowNodeType.Run 
        //      instead of any other FlowNodeType.  This is to be 
        //      consistent with the general principal that non-run type
        //      FlowNode has no corresponding FixedNode. 
        //
        //      Each FlowNode, if it is of type FlowNodeType.Run, contains
        //      a cookie that is the run length.
        //---------------------------------------------------------------------- 

        // Helper function for efficient creation of FixedNode used during pre-order walking. 
        // current index is @ childIndex 
        // depending on nesting level, the prefix can be hold at
        //      1. no prefix (level1) 
        //      2. level1Index
        //      3. pathPrefix.
        //
        FixedNode _NewFixedNode(int pageIndex, int nestingLevel, int level1Index, int[] pathPrefix, int childIndex) 
        {
            if (nestingLevel == 1) 
            { 
                return FixedNode.Create(pageIndex, nestingLevel, childIndex, -1, null);
            } 
            else if (nestingLevel == 2)
            {
                return FixedNode.Create(pageIndex, nestingLevel, level1Index, childIndex, null);
            } 
            else
            { 
                // For deeply nested path, we need to append current childIndex to a pathPrefix 
                // to form the entire childPath.
                Debug.Assert(pathPrefix != null); 
                int[] newPath = new int[pathPrefix.Length + 1];
                pathPrefix.CopyTo(newPath, 0);
                newPath[newPath.Length - 1] = childIndex;
                return FixedNode.Create(pageIndex, nestingLevel, -1, -1, newPath); 
            }
        } 
 

        // Helper function to get Paths with ImageBrushes 
        private bool _IsImage(object o)
        {
            System.Windows.Shapes.Path p = o as System.Windows.Shapes.Path;
            if (p != null) 
            {
                return p.Fill is ImageBrush && p.Data != null; 
            } 
            return o is Image;
        } 


        private bool _IsNonContiguous(FixedSOMTextRun prevRun, FixedSOMTextRun currentRun, GlyphComparison comparison)
        { 
            Debug.Assert(prevRun != null);
            Debug.Assert(currentRun != null); 
 
            if (prevRun.FixedNode == currentRun.FixedNode)
            { 
                return currentRun.StartIndex != prevRun.EndIndex;
            }

            return IsNonContiguous(prevRun.CultureInfo, 
                                    currentRun.CultureInfo,
                                    prevRun.IsSideways, 
                                    currentRun.IsSideways, 
                                    prevRun.Text,
                                    currentRun.Text, 
                                    comparison);

        }
 
        private GlyphComparison _CompareGlyphs(Glyphs glyph1, Glyphs glyph2)
        { 
            GlyphComparison comparison = GlyphComparison.DifferentLine; 
            if (glyph1 == glyph2)
            { 
                comparison = GlyphComparison.SameLine;
            }
            else if (glyph1 != null && glyph2 != null)
            { 
                GlyphRun run1 = glyph1.ToGlyphRun();
                GlyphRun run2 = glyph2.ToGlyphRun(); 
                if (run1 != null && run2 != null) 
                {
                    Rect box1 = run1.ComputeAlignmentBox(); 
                    box1.Offset(glyph1.OriginX, glyph1.OriginY);
                    Rect box2 = run2.ComputeAlignmentBox();
                    box2.Offset(glyph2.OriginX, glyph2.OriginY);
 
                    bool LTR1 = ((glyph1.BidiLevel & 1) == 0);
                    bool LTR2 = ((glyph2.BidiLevel & 1) == 0); 
 
                    GeneralTransform transform = glyph2.TransformToVisual(glyph1);
                    Point prevPt = LTR1 ? box1.TopRight : box1.TopLeft; 
                    Point currentPt = LTR2 ? box2.TopLeft : box2.TopRight;
                    if (transform != null)
                    {
                        transform.TryTransform(currentPt, out currentPt); 
                    }
 
                    if (IsSameLine(currentPt.Y - prevPt.Y, box1.Height, box2.Height)) 
                    {
                        comparison = GlyphComparison.SameLine; 
                        if (LTR1 == LTR2)
                        {
                            double xDistance = Math.Abs(currentPt.X - prevPt.X);
                            double maxHeight = Math.Max(box1.Height, box2.Height); 

                            if (xDistance / maxHeight < .05) 
                            { 
                                comparison = GlyphComparison.Adjacent;
                            } 
                        }
                    }
                }
            } 
            return comparison;
        } 
 
        // Apply heuristics
        // Create FlowNode structure 
        // Create Fixed to Flow mapping
        // Create FixedElement
        private void _CreateFixedMappingAndElementForPage(FixedPageStructure pageStructure, FixedPage page, bool constructSOM)
        { 
            List fixedNodes = new List();
            _GetFixedNodes(pageStructure, 
                           page.Children, 
                           1,
                           -1, 
                           null,
                           constructSOM,
                           fixedNodes,
                           Matrix.Identity); 

            FlowModelBuilder flowBuilder = new FlowModelBuilder(this, pageStructure, page); 
            flowBuilder.FindHyperlinkPaths(page); 

            if (constructSOM) 
            {
                pageStructure.FixedSOMPage.MarkupOrder = fixedNodes;
                pageStructure.ConstructFixedSOMPage(fixedNodes);
 

                _CreateFlowNodes(pageStructure.FixedSOMPage, flowBuilder); 
                pageStructure.PageConstructor = null; 
            }
            else 
            {
                pageStructure.FixedDSBuilder.ConstructFlowNodes(flowBuilder, fixedNodes);
            }
 
            flowBuilder.FinishMapping();
 
#if DEBUG 
            pageStructure.FixedNodes = fixedNodes;
            //flowBuilder.DumpToFile("FlowDump_Page_" + pageStructure.PageIndex.ToString() + ".xml"); 
#endif


 
        }
 
        private void _GetFixedNodes( 
                                    FixedPageStructure pageStructure,
                                    IEnumerable oneLevel, 
                                    int nestingLevel,       // the level of nesting
                                    int level1Index,        // if nesting level == 2, this is leve1 1 index
                                    int[] pathPrefix,   // if nesting level > 2, this is used to represent prefix, otherwise it is null
                                    bool constructLines, 
                                    List fixedNodes, // start empty, nodes will be added to this list
                                    Matrix transform 
                                    ) 
        {
            int pageIndex = pageStructure.PageIndex; 

            DocumentsTrace.FixedTextOM.Builder.Trace(string.Format("_FlowOrderAnalysis P{0}-L[{0}]", pageIndex, nestingLevel));

            int currentScopeId = _NewScopeId(); 

            // Create per run fixed nodes 
            IFrameworkInputElement namedNode; 

            int childIndex = 0; 
            IEnumerator elements = oneLevel.GetEnumerator();
            while (elements.MoveNext())
            {
                if (!constructLines) 
                {
                    namedNode = elements.Current as IFrameworkInputElement; 
                    if (namedNode != null && namedNode.Name != null && namedNode.Name.Length != 0) 
                    {
                        pageStructure.FixedDSBuilder.BuildNameHashTable(namedNode.Name, 
                                    elements.Current as UIElement,
                                    fixedNodes.Count);
                    }
                } 

                if (_IsImage(elements.Current) || 
                    (elements.Current is Glyphs && (elements.Current as Glyphs).MeasurementGlyphRun != null)) 
                {
                    fixedNodes.Add( 
                        _NewFixedNode(pageIndex, nestingLevel, level1Index, pathPrefix, childIndex)
                                            );
                    // GlyphRuns are non contiguous due to Image
                } 
                else if (constructLines && elements.Current is Path)
                { 
                    pageStructure.PageConstructor.ProcessPath(elements.Current as Path, transform); 
                }
                else if (elements.Current is Canvas) 
                {
                    Transform localTransform = Transform.Identity;

                    // Drill down to next level 
                    IEnumerable children;
 
                    Canvas canvas = elements.Current as Canvas; 

                    children       = canvas.Children; 
                    localTransform = canvas.RenderTransform;

                    if (localTransform == null)
                    { 
                        localTransform = Transform.Identity;
                    } 
 
                    if (children != null)
                    { 
                        int[] newPathPrefix = null;
                        if (nestingLevel >= 2)
                        {
                            // anything more than two level deep, we need to use path array 
                            if (nestingLevel == 2)
                            { 
                                Debug.Assert(pathPrefix == null); 
                                Debug.Assert(level1Index >= 0);
                                newPathPrefix = new int[2]; 
                                newPathPrefix[0] = level1Index;
                            }
                            else
                            { 
                                newPathPrefix = new int[pathPrefix.Length + 1];
                                pathPrefix.CopyTo(newPathPrefix, 0); 
                            } 
                            // Append the childIndex to newPathPrefix.
                            Debug.Assert(newPathPrefix != null); 
                            newPathPrefix[newPathPrefix.Length - 1] = childIndex;
                        }
#if DEBUG
                        else 
                        {
                            Debug.Assert(pathPrefix == null && newPathPrefix == null); 
                        } 
#endif
                        _GetFixedNodes( 
                                pageStructure,
                                children,
                                (nestingLevel + 1), // go to next nesting level
                                (nestingLevel == 1 ? childIndex : -1), // use this index if we are going from 1 to 2 
                                newPathPrefix,         // otherwise use this path prefix
                                constructLines, 
                                fixedNodes, 
                                transform * localTransform.Value
                                ); 

                    }//endofElementIsCanvas
                }
 
                childIndex++;
            } 
        } 

        private void _CreateFlowNodes(FixedSOMPage somPage, FlowModelBuilder flowBuilder) 
        {
            flowBuilder.AddStartNode(FixedElement.ElementType.Section);
            somPage.SetRTFProperties(flowBuilder.FixedElement);
 
            foreach (FixedSOMContainer container in somPage.SemanticBoxes)
            { 
                _CreateFlowNodes(container, flowBuilder); 
            }
 
            //Add the remaining hyperlinks at the end of the page
            flowBuilder.AddLeftoverHyperlinks();

            flowBuilder.AddEndNode(); 
        }
 
 

 
        //We will need to have a special case for an empty page
        private void _CreateFlowNodes(FixedSOMContainer node, FlowModelBuilder flowBuilder)
        {
            FixedElement.ElementType[] elementsForNode = node.ElementTypes; 
            foreach (FixedElement.ElementType type in elementsForNode)
            { 
                flowBuilder.AddStartNode(type); 
                node.SetRTFProperties(flowBuilder.FixedElement);
            } 


            List children = node.SemanticBoxes;
 
            foreach (FixedSOMSemanticBox box in children)
            { 
                if (box is FixedSOMElement) 
                {
                    flowBuilder.AddElement((FixedSOMElement)box); 
                }
                else if (box is FixedSOMContainer)
                {
                    _CreateFlowNodes((FixedSOMContainer)box, flowBuilder); 
                }
                else 
                { 
                    Debug.Assert(false);
                } 
            }

            foreach (FixedElement.ElementType type in elementsForNode)
            { 
                flowBuilder.AddEndNode();
            } 
        } 

 

        //-------------------------------------------------------------------
        // Fixed Document
        //---------------------------------------------------------------------- 

        private bool _IsStartVisual(int visualIndex) 
        { 
            return visualIndex == FixedFlowMap.FixedOrderStartVisual;
        } 

        private bool _IsEndVisual(int visualIndex)
        {
            return visualIndex == FixedFlowMap.FixedOrderEndVisual; 
        }
 
        private bool _IsBoundaryPage(int pageIndex) 
        {
            return (   pageIndex == FixedFlowMap.FixedOrderStartPage 
                    || pageIndex == FixedFlowMap.FixedOrderEndPage
                    );
        }
 
        // Advance the scope ID -- called when a new flow scope is needed.
        // the scope ID is used to identify the flow scope in flow order. 
        // 
        // For instance:
        //        
        // All Id =1 consists of one scope while Id=2 opens a new scope (in this case a nested scope).
        //
        private int _NewScopeId()
        { 
            return _nextScopeId++;
        } 
 

        private static bool _IsRTL(char c) 
        {
            /*return (c > 0x590 && c < 0x780) ||
                (c >= 0xFB1D && c <= 0xFDFD) ||
                (c >= 0xFE70 && c <= 0xFEFC);*/ 
            return (c >= 0x5D0 && c <= 0x60B) ||
                (c == 0x60D) || 
                (c >= 0x61B && c <= 0x64A) || 
                (c >= 0x66D && c <= 0x6D5 && c != 0x670) ||
                (c == 0x6DD) || (c == 0x6E5) || (c == 0x6E6) || 
                (c == 0x6EE) || (c == 0x6EF) ||
                (c >= 0x6FA && c <= 0x70D) ||
                (c == 0x710) || (c >= 0x712 && c <= 0x72F) ||
                (c >= 0x74D && c <= 0x7A5) || (c == 0x7B1) || 
                (c == 0xFB1D) || (c >= 0xFB1F && c <= 0xFD3D && c != 0xFB29) ||
                (c >= 0xFD50 && c <= 0xFDFC) || (c >= 0xFE70 && c <= 0xFEFC); 
 
        }
 
#if DEBUG
        private static bool _IsCombiningMark(char c)
        {
            return (c > 0x590 && c < 0x5BE) || 
                (c > 0x5BE && c < 0x5C8 && _cTable[c - 0x5BF]) ||
                (c >= 0x610 && c <= 0x615) || 
                (c >= 0x64B && c <= 0x65E) || c == 0x670 || 
                (c >= 0x6D6 && c <= 0x6ED && _cTable[c - 0x6CE])
                || c == 0x711 || (c >= 0x730 && c <= 0x74A) || 
                c == 0xFB1D;
        }

 
        /*private static Brush _ChooseDebugColor(Glyphs g)
        { 
            foreach (char c in g.UnicodeString) 
            {
                if (c >= 0xFB1D) 
                {
                    return Brushes.Red;
                }
                else if (_IsCombiningMark(c)) 
                {
                    return Brushes.Blue; 
                } 
            }
            return Brushes.Green; 
        }*/
#endif

        #endregion Private Methods 

        //------------------------------------------------------------------- 
        // 
        // Private Properties
        // 
        //---------------------------------------------------------------------

        #region Private Properties
        #endregion Private Properties 

        //------------------------------------------------------------------- 
        // 
        // Private Fields
        // 
        //----------------------------------------------------------------------

        #region Private Fields
        private readonly FixedTextContainer _container;     // page container 
        private List  _pageStructures; // contain all FixedPageStructure for each page.
        private int _nextScopeId;                           // Next FlowNode ScopeId 
        private FixedFlowMap _fixedFlowMap; 
        private static bool[] _cTable = new bool[] { true, //0x5BF   //Combining marks table
                false, true, true, false, // 0x5C0 - 3 
                true, true, false, true, //0x5C4
                true, true, //0x6D6 - 7
                true, true, true, true, //0x6D8 - B
                true, false, false, true, //C - F 
                true, true, true, true, //0x6E0 - 3
                true, false, false, true, //0x6E4 - 7 
                true, false, true, true, //0x6E8 - B 
                true, true //C, D
            }; 
        #endregion Private Fields

        //-------------------------------------------------------------------
        // 
        // Private Class
        // 
        //-------------------------------------------------------------------- 

        #region Private Class 
        internal sealed class FlowModelBuilder
        {
            private sealed class LogicalHyperlink
            { 
                public LogicalHyperlink(Uri uri, Geometry geom, UIElement uiElement)
                { 
                    _uiElement = uiElement; 
                    _uri = uri;
                    _geometry = geom; 
                    _boundingRect = geom.Bounds; //Get bounding rect
                    _used = false;
                }
 
                public Uri Uri
                { 
                    get 
                    {
                        return _uri; 
                    }
                }

                public Geometry Geometry 
                {
                    get 
                    { 
                        return _geometry;
                    } 
                }

                public Rect BoundingRect
                { 
                    get
                    { 
                        return _boundingRect; 
                    }
                } 

                public UIElement UIElement
                {
                    get 
                    {
                        return _uiElement; 
                    } 
                }
 
                public bool Used
                {
                    get
                    { 
                        return _used;
                    } 
                    set 
                    {
                        _used = value; 
                    }
                }

 
                private UIElement _uiElement;
                private Uri _uri; 
                private Geometry _geometry; 
                private Rect _boundingRect;
                private bool _used; 
            }

            private sealed class LogicalHyperlinkContainer : IEnumerable
            { 
                public LogicalHyperlinkContainer()
                { 
                    _hyperlinks = new List(); 

                } 

                IEnumerator IEnumerable.GetEnumerator()
                {
                    return _hyperlinks.GetEnumerator(); 
                }
 
                IEnumerator IEnumerable.GetEnumerator() 
                {
                    return _hyperlinks.GetEnumerator(); 
                }

                public void AddLogicalHyperlink(Uri uri, Geometry geometry, UIElement uiElement)
                { 
                    LogicalHyperlink hyperlink = new LogicalHyperlink(uri, geometry, uiElement);
                    _hyperlinks.Add(hyperlink); 
                } 

                //Returns a Uri that is associated with a SOMElement if there is one 
                //Also returns the actual UIElement as an output variable if a Path with NavigateUri
                //is used to make this SOMElement look like an actual hyperlink
                public Uri GetUri(FixedSOMElement element, FixedPage p, out UIElement shadowElement)
                { 
                    shadowElement = null;
                    UIElement e = p.GetElement(element.FixedNode) as UIElement; 
                    if (e == null) 
                    {
                        Debug.Assert(false); 
                        return null;
                    }
                    LogicalHyperlink logicalHyperlink = null;
                    Uri relUri = FixedPage.GetNavigateUri(e); 
                    if (relUri == null && _hyperlinks.Count > 0)
                    { 
                        Transform t = e.TransformToAncestor(p) as Transform; 
                        Geometry g;
                        if (e is Glyphs) 
                        {
                            GlyphRun run = ((Glyphs)e).ToGlyphRun();
                            Rect designRect = run.ComputeAlignmentBox();
                            designRect.Offset(run.BaselineOrigin.X, run.BaselineOrigin.Y); 

                            g = new RectangleGeometry(designRect); 
                        } 
                        else if (e is Path)
                        { 
                            g = ((Path)e).Data;
                        }
                        else
                        { 
                            Debug.Assert(e is Image);
                            Image im = (Image)e; 
                            g = new RectangleGeometry(new Rect(0, 0, im.Width, im.Height)); 
                        }
                        logicalHyperlink = _GetHyperlinkFromGeometry(g, t); 
                        if (logicalHyperlink != null)
                        {
                            relUri = logicalHyperlink.Uri;
                            shadowElement = logicalHyperlink.UIElement; 
                        }
                    } 
                    if (relUri == null) 
                    {
                        return null; 
                    }

                    return FixedPage.GetLinkUri(p, relUri);
                } 

 
                //Marks the hyperlink associated with a specific UIElement as "used" 
                public void MarkAsUsed(UIElement uiElement)
                { 
                    for (int i=0; i<_hyperlinks.Count; i++)
                    {
                        LogicalHyperlink hyperlink = _hyperlinks[i];
                        if (hyperlink.UIElement == uiElement) 
                        {
                            hyperlink.Used = true; 
                            break; 
                        }
                    } 
                }

                private LogicalHyperlink _GetHyperlinkFromGeometry(Geometry geom, Transform t)
                { 
                    Geometry g = geom;
 
                    if (t != null && !t.Value.IsIdentity) 
                    {
                        g = PathGeometry.CreateFromGeometry(geom); 
                        g.Transform = t;
                    }

                    double minArea = g.GetArea() * .99; 
                    Rect r = g.Bounds;
 
                    for (int i = 0; i < _hyperlinks.Count; i++) 
                    {
                        // do fast rect overlap before doing more expensive geometric comparison 
                        if (r.IntersectsWith(_hyperlinks[i].BoundingRect))
                        {
                            Geometry combined = Geometry.Combine(g, _hyperlinks[i].Geometry, GeometryCombineMode.Intersect, Transform.Identity);
                            if (combined.GetArea() > minArea) 
                            {
                                return _hyperlinks[i]; 
                            } 
                        }
                    } 

                    return null;
                }
 
                private List _hyperlinks;
 
            } 

            public FlowModelBuilder(FixedTextBuilder builder, FixedPageStructure pageStructure, FixedPage page) 
            {
                _builder = builder;
                _container = builder._container;
                _pageIndex = pageStructure.PageIndex; 
                _textRuns = new List();
                _flowNodes = new List(); 
                _fixedNodes = new List(); 
                _nodesInLine = new List();
                _lineResults = new List(); 
                _endNodes = new Stack();
                _fixedElements = new Stack();
                _mapping = builder._fixedFlowMap;
                _pageStructure = pageStructure; 
                _currentFixedElement = _container.ContainerElement;
                _lineLayoutBox = Rect.Empty; 
                _logicalHyperlinkContainer = new LogicalHyperlinkContainer(); 
                _fixedPage = page;
#if DEBUG 
                _dumpDoc = new XmlDocument();
                _currentDumpNode = _dumpDoc.CreateElement("FlowModel");
                _dumpDoc.AppendChild(_currentDumpNode);
#endif 

            } 
 

            public void FindHyperlinkPaths(FrameworkElement elem) 
            {
                //we are only interested in hyperlinks created by putting Path on top of a Gyphs element

                Debug.Assert(elem is FixedPage || elem is Canvas); 
                IEnumerable children = LogicalTreeHelper.GetChildren(elem);
 
                foreach (UIElement child in children) 
                {
                    Canvas canvas = child as Canvas; 
                    if (canvas != null)
                    {
                        FindHyperlinkPaths(canvas);
                    } 

                    if (!(child is Path) || ((Path)child).Fill is ImageBrush) 
                    { 
                        // ignore these, these are content
                        continue; 
                    }

                    Uri navUri = FixedPage.GetNavigateUri(child);
 
                    if (navUri != null && ((Path)child).Data != null)
                    { 
                        Transform trans = child.TransformToAncestor(_fixedPage) as Transform; 

                        Geometry geom = ((Path)child).Data; 
                        if (trans != null && !trans.Value.IsIdentity)
                        {
                            geom = PathGeometry.CreateFromGeometry(geom);
                            geom.Transform = trans; 
                        }
                        _logicalHyperlinkContainer.AddLogicalHyperlink(navUri, geom, child); 
                    } 
                }
            } 

            public void AddLeftoverHyperlinks()
            {
 
                foreach (LogicalHyperlink hyperlink in _logicalHyperlinkContainer)
                { 
                    if (!hyperlink.Used) 
                    {
                        _AddStartNode(FixedElement.ElementType.Paragraph); 
                        _AddStartNode(FixedElement.ElementType.Hyperlink);
                        _currentFixedElement.SetValue(Hyperlink.NavigateUriProperty, hyperlink.Uri);
                        _currentFixedElement.SetValue(FixedElement.HelpTextProperty, (String) (hyperlink.UIElement.GetValue(AutomationProperties.HelpTextProperty)));
                        _currentFixedElement.SetValue(FixedElement.NameProperty, (String) (hyperlink.UIElement.GetValue(AutomationProperties.NameProperty))); 
                        _AddEndNode();
                        _AddEndNode(); 
                    } 
                }
            } 
            //Use this for start tags
            public void AddStartNode(FixedElement.ElementType type)
            {
                _FinishTextRun(true); 
                _FinishHyperlink();
                _AddStartNode(type); 
            } 

            public void AddEndNode() 
            {
                _FinishTextRun(false);
                _FinishHyperlink();
                _AddEndNode(); 
            }
            //Use this for images and text runs -- generates necessary flow nodes 
            public void AddElement(FixedSOMElement element) 
            {
                FixedPage page = _builder.GetFixedPage(element.FixedNode); 
                UIElement shadowHyperlink;
                Uri navUri = _logicalHyperlinkContainer.GetUri(element, page, out shadowHyperlink);
                if (element is FixedSOMTextRun)
                { 
                    // Will add code to get font info for rich copy here
                    FixedSOMTextRun run = element as FixedSOMTextRun; 
                    bool createNewRun = (_currentRun == null) || (!run.HasSameRichProperties(_currentRun)) 
                        || navUri != _currentNavUri || (navUri != null && navUri.ToString() != _currentNavUri.ToString());
 
                    if (createNewRun)
                    {
                        if (_currentRun != null)
                        { 
                            //Close existing inline tag
                            FixedSOMFixedBlock parent = run.FixedBlock; 
 
                            FixedSOMTextRun lastRun = _textRuns[_textRuns.Count - 1];
 
                            Glyphs currentRunGlyph = _builder.GetGlyphsElement(lastRun.FixedNode);
                            Glyphs glyphs = _builder.GetGlyphsElement(run.FixedNode);

                            GlyphComparison comparison = _builder._CompareGlyphs(currentRunGlyph, glyphs); 

                            bool addSpace = false; 
                            if (_builder._IsNonContiguous(lastRun, run, comparison)) 
                            {
                                addSpace = true; 
                            }

                            _FinishTextRun(addSpace);
                        } 

                        _SetHyperlink(navUri, run.FixedNode, shadowHyperlink); 
                        //Open new Run tag and set RTF props 

                        _AddStartNode(FixedElement.ElementType.Run); 
                        run.SetRTFProperties(_currentFixedElement);
                        _currentRun = run;
                    }
 
                    _textRuns.Add((FixedSOMTextRun)element);
                    if (_fixedNodes.Count == 0 || _fixedNodes[_fixedNodes.Count - 1] != element.FixedNode) 
                    { 
                        _fixedNodes.Add(element.FixedNode);
                    } 
                }
                else if (element is FixedSOMImage)
                {
                    FixedSOMImage image = (FixedSOMImage)element; 
                    _FinishTextRun(true);
                    _SetHyperlink(navUri, image.FixedNode, shadowHyperlink); 
 
                    _AddStartNode(FixedElement.ElementType.InlineUIContainer);
 
                    FlowNode flowImageNode = new FlowNode(_NewScopeId(), FlowNodeType.Object, null);
                    // Create a new FixedElement to represent this new node.
                    _container.OnNewFlowElement(_currentFixedElement,
                                    FixedElement.ElementType.Object, 
                                    new FlowPosition(_container, flowImageNode, 0),
                                    new FlowPosition(_container, flowImageNode, 1), 
                                    image.Source, 
                                    _pageIndex
                                    ); 


                    _flowNodes.Add(flowImageNode);
 
                    // Do fixed/flow mapping for image
                    element.FlowNode = flowImageNode; 
                    flowImageNode.FixedSOMElements = new FixedSOMElement[] { element }; 
                    _mapping.AddFixedElement(element);
                    // Do we need this? 
                    _fixedNodes.Add(element.FixedNode);

                    //copy automation properties
                    FixedElement fElement = (FixedElement)flowImageNode.Cookie; 
                    fElement.SetValue(FixedElement.NameProperty, image.Name);
                    fElement.SetValue(FixedElement.HelpTextProperty, image.HelpText); 
 
                    _AddEndNode();
                } 
                else
                {
                    Debug.Assert(false);
                } 
            }
 
            public void FinishMapping() 
            {
                _FinishLine(); 
                _mapping.MappingReplace(_pageStructure.FlowStart, _flowNodes);
                _pageStructure.SetFlowBoundary(_flowNodes[0], _flowNodes[_flowNodes.Count-1]);
                _pageStructure.SetupLineResults(_lineResults.ToArray());
            } 

#if DEBUG 
            public void DumpToFile(string file) 
            {
                //_dumpDoc.Save(file); 
                StringWriter writer = new StringWriter();
                _dumpDoc.Save(writer);
            }
 
            private void DumpFlowNode(FlowNode node)
            { 
                FixedElement element = node.Cookie as FixedElement; 
                if (element != null)
                { 
                    XmlElement newDumpNode = _dumpDoc.CreateElement(element.Type.Name);
                    newDumpNode.SetAttribute("id", node.ScopeId.ToString());
                    _currentDumpNode.AppendChild(newDumpNode);
                    _currentDumpNode = newDumpNode; 
                }
                else 
                { 
                    //Run
                    int nodeLength = (int) node.Cookie; 
                    _currentDumpNode.SetAttribute("Cookie", nodeLength.ToString());
                    FixedSOMElement[] somElems = node.FixedSOMElements;
                    if (somElems!=null)
                    { 
                        StringBuilder strBuilder = new StringBuilder();
                        foreach (FixedSOMElement somElem in somElems) 
                        { 
                            FixedSOMTextRun run = somElem as FixedSOMTextRun;
                            if (run != null) 
                            {
                                strBuilder.Append(run.Text);
                            }
                        } 
                        _currentDumpNode.InnerText = strBuilder.ToString();
                    } 
                } 

            } 
#endif

            private void _AddStartNode(FixedElement.ElementType type)
            { 
                FlowNode startNode = new FlowNode(_NewScopeId(), FlowNodeType.Start, _pageIndex);
                FlowNode endNode = new FlowNode(_NewScopeId(), FlowNodeType.End, _pageIndex); 
                // add fixed element 
                _container.OnNewFlowElement(_currentFixedElement, //_container.ContainerElement,
                type, 
                new FlowPosition(_container, (FlowNode)startNode, 1),
                new FlowPosition(_container, (FlowNode)endNode, 0),
                null,
                _pageIndex 
                );
                // Create fixed element 
                _fixedElements.Push(_currentFixedElement); 
                _currentFixedElement = (FixedElement)startNode.Cookie;
                _flowNodes.Add(startNode); 
                _endNodes.Push(endNode);
#if DEBUG
                DumpFlowNode(startNode);
#endif 

 
            } 

            private void _AddEndNode() 
            {
                _flowNodes.Add((FlowNode)_endNodes.Pop());
                _currentFixedElement = (FixedElement)_fixedElements.Pop();
#if DEBUG 
                _currentDumpNode = (XmlElement) _currentDumpNode.ParentNode;
#endif 
            } 

            private void _FinishTextRun(bool addSpace) 
            {
                if (_textRuns.Count > 0)
                {
                    int textRunLength = 0; 
                    FixedSOMTextRun run = null;
                    for (int i=0; i<_textRuns.Count; i++) 
                    { 
                        run = _textRuns[i];
                        Glyphs glyphs = _builder.GetGlyphsElement(run.FixedNode); 
                        GlyphComparison comparison = _builder._CompareGlyphs(_lastGlyphs, glyphs);

                        if (comparison == GlyphComparison.DifferentLine)
                        { 
                            _FinishLine();
                        } 
 
                        _lastGlyphs = glyphs;
 
                        _lineLayoutBox.Union(run.BoundingRect);
                        run.LineIndex = _lineResults.Count;
                        if (_nodesInLine.Count == 0 || _nodesInLine[_nodesInLine.Count - 1] != run.FixedNode)
                        { 
                            _nodesInLine.Add(run.FixedNode);
                        } 
 
                        textRunLength += run.EndIndex - run.StartIndex;
                        Debug.Assert(run.EndIndex - run.StartIndex == run.Text.Length); 

                        if (i>0 && _builder._IsNonContiguous(_textRuns[i-1], run, comparison))
                        {
                            _textRuns[i-1].Text = _textRuns[i-1].Text + " "; 
                            textRunLength++;
                        } 
                    } 
                    if (addSpace && run.Text.Length>0 && !run.Text.EndsWith(" ", StringComparison.Ordinal) && !IsHyphen(run.Text[run.Text.Length - 1]))
                    { 
                        run.Text = run.Text + " ";
                        textRunLength ++;
                    }
 
                    if (textRunLength != 0)
                    { 
                        FlowNode flowNodeRun = new FlowNode(_NewScopeId(), FlowNodeType.Run, textRunLength); 
                        // Add list of text runs to flow node
                        flowNodeRun.FixedSOMElements = _textRuns.ToArray(); 

                        int offset = 0;

                        foreach (FixedSOMTextRun textRun in _textRuns) 
                        {
                            textRun.FlowNode = flowNodeRun; 
                            textRun.OffsetInFlowNode = offset; 
                            _mapping.AddFixedElement(textRun);
 
                            offset += textRun.Text.Length;
                        }

                        //Debug.Assert(offset == textRunLength); 

                        _flowNodes.Add(flowNodeRun); 
#if DEBUG 
                        DumpFlowNode(flowNodeRun);
#endif 

                        // clear the list
                        _textRuns.Clear();
 
                    }
 
                } 

                //Close the inline tag if any 
                if (_currentRun != null)
                {
                    _AddEndNode();
                    _currentRun = null; 
                }
 
            } 

            private void _FinishHyperlink() 
            {
                if (_currentNavUri != null)
                {
                    _AddEndNode(); //  
                    _currentNavUri = null;
                } 
            } 

            private void _SetHyperlink(Uri navUri, FixedNode node, UIElement shadowHyperlink) 
            {
                if (navUri != _currentNavUri || (navUri != null && navUri.ToString() != _currentNavUri.ToString()))
                {
                    if (_currentNavUri != null) 
                    {
                        _AddEndNode(); //  
                    } 

                    if (navUri != null) 
                    {
                        _AddStartNode(FixedElement.ElementType.Hyperlink);
                        _currentFixedElement.SetValue(Hyperlink.NavigateUriProperty, navUri);
                        UIElement uiElement = _fixedPage.GetElement(node) as UIElement; 
                        Debug.Assert(uiElement != null);
                        if (uiElement != null) 
                        { 
                            _currentFixedElement.SetValue(FixedElement.HelpTextProperty, (String) (uiElement.GetValue(AutomationProperties.HelpTextProperty)));
                            _currentFixedElement.SetValue(FixedElement.NameProperty, (String) (uiElement.GetValue(AutomationProperties.NameProperty))); 
                            if (shadowHyperlink != null)
                            {
                                _logicalHyperlinkContainer.MarkAsUsed(shadowHyperlink);
                            } 
                        }
                    } 
 
                    _currentNavUri = navUri;
                } 
            }

            private void _FinishLine()
            { 
                if (_nodesInLine.Count > 0)
                { 
                    FixedLineResult newLineResult = new FixedLineResult(_nodesInLine.ToArray(), _lineLayoutBox); 
                    Debug.Assert(newLineResult != null);
 
                    _lineResults.Add(newLineResult);

                    _nodesInLine.Clear();
                    _lineLayoutBox = Rect.Empty; 
                }
            } 
 
            private int _NewScopeId()
            { 
                return _builder._nextScopeId++;
            }

            public FixedElement FixedElement 
            {
                get 
                { 
                    return _currentFixedElement;
                } 
            }

            private int _pageIndex;
            private FixedTextContainer _container; 
            private FixedTextBuilder _builder;
            private List _textRuns; 
            private List _flowNodes; 
            private List _fixedNodes;
            private List _nodesInLine; 
            private List _lineResults;
            private Rect _lineLayoutBox;
            private Stack _endNodes;
            private Stack _fixedElements; 
            private FixedElement _currentFixedElement;
            private FixedFlowMap _mapping; 
            private FixedPageStructure _pageStructure; 
            private Glyphs _lastGlyphs;
            private FixedSOMTextRun _currentRun; 
            private LogicalHyperlinkContainer _logicalHyperlinkContainer;
            private FixedPage _fixedPage;
            private Uri _currentNavUri;
#if DEBUG 
            private XmlDocument _dumpDoc;
            private XmlElement _currentDumpNode; 
#endif 

        } 


        internal enum GlyphComparison
        { 
            DifferentLine,
            SameLine, 
            Adjacent, //also on same line 
            Unknown
        } 

        #endregion
    }
} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// Copyright (c) Microsoft Corporation. All rights reserved.
//---------------------------------------------------------------------------- 
// 
//      Copyright (C) 2004 by Microsoft Corporation.  All rights reserved.
// 
// 
// Description:
//      FixedTextBuilder contains heuristics to map fixed document elements 
//      into stream of flow text 
//
// History: 
//      02/10/2004 - Zhenbin Xu (ZhenbinX) - Created.
//
//---------------------------------------------------------------------------
 
namespace System.Windows.Documents
{ 
    using MS.Internal.Documents; 
    using System.Windows.Controls;      // UIElementCollection
    using System.Windows.Media; 
    using System.Windows.Media.Imaging;
    using System.Windows.Markup;
    using System.Windows.Shapes;       // Glyphs
    using System.Windows.Automation; 
    using System.Windows.Documents.DocumentStructures;
    using System; 
    using System.Collections; 
    using System.Collections.Generic;
    using System.Diagnostics; 
    using System.Globalization;
    using System.Text;
    using System.IO;
    using System.Xml; 
    using Path=System.Windows.Shapes.Path;
 
    using MS.Utility; 

    //===================================================================== 
    /// 
    /// FixedTextBuilder contains heuristics to map fixed document elements
    /// into stream of flow text.
    ///  
    internal sealed class FixedTextBuilder
    { 
        //------------------------------------------------------------------- 
        //
        // Consts 
        //
        //----------------------------------------------------------------------
        #region Const
        internal const char FLOWORDER_SEPARATOR = ' '; 
        #endregion Const
 
 

        //------------------------------------------------------------------- 
        //
        // Statics
        //
        //---------------------------------------------------------------------- 
        #region Statics
 
        // A list of CultureInfo that are always adjacent 
        internal static CultureInfo[] AdjacentLanguage =
        { 
            new CultureInfo("zh-CHS"),      // Chinese Simplified
            new CultureInfo("zh-CHT"),      // Chinese Traditional
            new CultureInfo("zh-HK"),       // Chinese Hong Kong SAR
            new CultureInfo("zh-MO"),       // Chinese Macau SAR 
            new CultureInfo("zh-CN"),       // Chinese China
            new CultureInfo("zh-SG"),       // Chinese Singapore 
            new CultureInfo("zh-TW"),       // Chinese `Taiwan 
            new CultureInfo("ja-JP"),       // Japanese
            new CultureInfo("ko-KR"),       // Korean 
            new CultureInfo("th-TH")        // Thai
        };

 
        internal static bool AlwaysAdjacent(CultureInfo ci)
        { 
            foreach (CultureInfo cultureInfo in AdjacentLanguage) 
            {
                if (ci.Equals(cultureInfo)) 
                {
                    return true;
                }
            } 
            return false;
        } 
 

 
        // obtained via Unicode 3.0 book: C0 Controls and Basic Latin.
        //    0x002D/0x00AD and their related characters.
        //
        // NOTE it is okay to not getting accurate list as long as 
        // we deal with common cases since this is used in heuristic
        // algorithm! 
        internal static char[] HyphenSet = 
        {
            '\x002D',     // Hyphen-Minus 
            '\x2010',     // Hyphen
            '\x2011',     // Non-breaking Hyphen
            '\x2012',     // Figure-dash
            '\x2013',     // En-dash 
            '\x2212',     // Minus Sign
            '\x00AD'      // Soft-Hyphen 
        }; 

        internal static bool IsHyphen(char target) 
        {
            foreach (char hyphen in HyphenSet)
            {
                if (hyphen == target) 
                {
                    return true; 
                } 
            }
            return false; 
        }

        // Space that was used in the heuristic algorithm.
        internal static bool IsSpace(char target) 
        {
            // Only the regular space character is considered 
            // space. 
            return (target == '\x0020');
        } 
        #endregion Statics


        //-------------------------------------------------------------------- 
        //
        // Connstructors 
        // 
        //---------------------------------------------------------------------
 
        #region Constructors
        internal FixedTextBuilder(FixedTextContainer container)
        {
            _container = container; 
            _Init();
        } 
        #endregion Constructors 

        //-------------------------------------------------------------------- 
        //
        // Public Methods
        //
        //--------------------------------------------------------------------- 

        //------------------------------------------------------------------- 
        // 
        // Public Properties
        // 
        //---------------------------------------------------------------------

        //--------------------------------------------------------------------
        // 
        // Public Events
        // 
        //--------------------------------------------------------------------- 

        //-------------------------------------------------------------------- 
        //
        // Internal Methods
        //
        //---------------------------------------------------------------------- 

        #region Internal Methods 
 
        //-------------------------------------------------------------------
        // Virtualization 
        //----------------------------------------------------------------------

        // Add virtual FlowNode to represent the page
        internal void AddVirtualPage() 
        {
#if DEBUG 
            DocumentsTrace.FixedTextOM.Builder.Trace(string.Format("AppendVirtualPage {0}", _pageStructures.Count)); 
#endif
            FixedPageStructure pageStructure = new FixedPageStructure(_pageStructures.Count); 
#if DEBUG
            pageStructure.FixedTextBuilder = this;
#endif
            _pageStructures.Add(pageStructure); 

            // Insert the virtural FlowNode into the Flow Order. 
            _fixedFlowMap.FlowOrderInsertBefore(_fixedFlowMap.FlowEndEdge, pageStructure.FlowStart); 

        } 


        //-------------------------------------------------------------------
        // Devirtualizing flow structure 
        //---------------------------------------------------------------------
 
        // Making sure a page is devirtualized 
        // All function that takes FixedNode as parameter and asks for FlowPosition
        // related content should call this functions first!!! 
        internal bool EnsureTextOMForPage(int pageIndex)
        {
            Debug.Assert(!_IsBoundaryPage(pageIndex));
            FixedPageStructure pageStructure = _pageStructures[pageIndex]; 
            if (!pageStructure.Loaded)
            { 
                EventTrace.NormalTraceEvent(EventTraceGuidId.DRXENSUREOMGUID, EventType.StartEvent); 

                FixedPage page = _container.FixedDocument.SyncGetPage(pageIndex, false); 

                if (page == null)
                    return false;
 
                Size pageSize = _container.FixedDocument.ComputePageSize(page);
 
                page.Measure(pageSize); 
                page.Arrange(new Rect(new Point(0, 0), pageSize));
 
                Debug.Assert(page != null);
                Debug.Assert(page.IsInitialized);

                bool constructSOM = true; 
                StoryFragments sf = page.GetPageStructure();
                if (sf != null) 
                { 
                    constructSOM = false;
                    FixedDSBuilder fb = new FixedDSBuilder(page, sf); 
                    pageStructure.FixedDSBuilder = fb;
                }

                if (constructSOM) 
                {
                    FixedSOMPageConstructor pageConstructor = new FixedSOMPageConstructor(page, pageIndex); 
                    pageStructure.PageConstructor = pageConstructor; 
                    pageStructure.FixedSOMPage = pageConstructor.FixedSOMPage;
                } 

                DocumentsTrace.FixedTextOM.Builder.Trace(string.Format("_EnsureTextOMForPage Loading..."));
                _CreateFixedMappingAndElementForPage(pageStructure, page, constructSOM);
 
#if DEBUG
                // 
                // Note: this debug verification is expensive. I have moved this code from FixedFlowMap.cs 
                // to reduce the rate is is called. Now it is called after each page is constructed and might
                // still have effect on long documents and scrolling in page per stream case. 
                //
                //FixedFlowMap.DebugVerifyMapping(true);
#endif
                EventTrace.NormalTraceEvent(EventTraceGuidId.DRXENSUREOMGUID, EventType.EndEvent); 

                return true; 
            } 

#if DEBUG 
            FixedPage fixedPage = _container.FixedDocument.SyncGetPage(pageIndex, false);
            fixedPage.FixedPageStructure = pageStructure;
#endif
            return false; 
        }
 
        //------------------------------------------------------------------- 
        // Fixed Document
        //---------------------------------------------------------------------- 

        // This could return null if FixedNode is an artificial boundary node
        internal FixedPage GetFixedPage(FixedNode node)
        { 
            FixedDocument doc = _container.FixedDocument;
            return doc.SyncGetPageWithCheck(node.Page); 
        } 

        // This could return null if FixedNode is an artificial boundary node 
        internal Glyphs GetGlyphsElement(FixedNode node)
        {
            FixedPage page = GetFixedPage(node);
            if (page != null) 
            {
                return page.GetGlyphsElement(node); 
            } 
            return null;
        } 


        //-------------------------------------------------------------------
        // Hit Testing / Keyboard Navigation 
        //----------------------------------------------------------------------
 
        // Given a fixed node, find its next/previous line 
        // count:
        //      in   # of lines desired 
        //      out  # of lines remaining
        // Return null if no next line
        internal FixedNode[] GetNextLine(FixedNode currentNode, bool forward, ref int count)
        { 
            if (_IsBoundaryPage(currentNode.Page))
            { 
                return null; 
            }
 
            EnsureTextOMForPage(currentNode.Page);
            FixedPageStructure ps = _pageStructures[currentNode.Page];

            if (_IsStartVisual(currentNode[1])) 
            {
                FixedNode[] firstLine = ps.FirstLine; 
                if (firstLine == null) 
                {
                    return null; 
                }
                currentNode = firstLine[0];
                count--;
            } 
            else if (_IsEndVisual(currentNode[1]))
            { 
                FixedNode[] lastLine = ps.LastLine; 
                if (lastLine == null)
                { 
                    return null;
                }
                currentNode = lastLine[0];
                count--; 
            }
 
            FixedSOMTextRun run = _fixedFlowMap.MappingGetFixedSOMElement(currentNode, 0) as FixedSOMTextRun; 

            if (run == null) 
            {
                return null;
            }
 
            int lineIndex = run.LineIndex;
 
            return ps.GetNextLine(lineIndex, forward, ref count); 
        }
 

        // Given a fixed node
        // Return null is cannot get line
        internal FixedNode[] GetLine(int pageIndex, Point pt) 
        {
            EnsureTextOMForPage(pageIndex); 
            return _pageStructures[pageIndex].FindSnapToLine(pt); 
        }
 
        // Find first line on page
        internal FixedNode[] GetFirstLine(int pageIndex)
        {
            EnsureTextOMForPage(pageIndex); 
            return _pageStructures[pageIndex].FirstLine;
        } 
 
        //-----------------------------------------------
        // Fixed nodes ==>  FlowPosition 
        //-----------------------------------------------

        // Find out flow offset given fixed position
        internal FlowPosition CreateFlowPosition(FixedPosition fixedPosition) 
        {
            // make sure page has been loaded 
            EnsureTextOMForPage(fixedPosition.Page); 

            FixedSOMElement element = _fixedFlowMap.MappingGetFixedSOMElement(fixedPosition.Node, fixedPosition.Offset); 
            if (element != null)
            {
                FlowNode flow = element.FlowNode;
                int fixedOffset = fixedPosition.Offset; 
                FixedSOMTextRun run = element as FixedSOMTextRun;
                if (run != null && run.IsReversed) 
                { 
                    fixedOffset  = run.EndIndex - run.StartIndex - fixedOffset;
                } 
                int offset = element.OffsetInFlowNode + fixedOffset - element.StartIndex;
                return new FlowPosition(_container, flow, offset);
            }
            return null; 
        }
 
 
        internal FlowPosition GetPageStartFlowPosition(int pageIndex)
        { 
            EnsureTextOMForPage(pageIndex);

            FlowNode fn = _pageStructures[pageIndex].FlowStart;
            // Remove this assert once we start supporting element across page bounary 
            Debug.Assert(fn.Type == FlowNodeType.Start);
            return new FlowPosition(_container, fn, 0); 
        } 

 
        internal FlowPosition GetPageEndFlowPosition(int pageIndex)
        {
            EnsureTextOMForPage(pageIndex);
 
            // Remove this assert once we start supporting element across page bounary
            FlowNode fn = _pageStructures[pageIndex].FlowEnd; 
            return new FlowPosition(_container, fn, 1); 
        }
 
        //-----------------------------------------------
        // FlowPosition ==>  Fixed Nodes
        //-----------------------------------------------
 
        // This function can handle flow nodes that are mapped to fixed nodes (Object or Run type) and start and end nodes
        internal bool GetFixedPosition(FlowPosition position, LogicalDirection textdir, out FixedPosition fixedp) 
        { 
            // Currently broken on empty page and on start/end flow nodes!
            // Init out parameter 
            fixedp = new FixedPosition(FixedFlowMap.FixedStartEdge, 0);

            int flowOffset;
            FlowNode flow; 

            position.GetFlowNode(textdir, out flow, out flowOffset); 
            FixedSOMElement[] fixes = flow.FixedSOMElements; 
            if (fixes == null)
            { 
                return false;
            }

            int loIndex = 0, hiIndex = fixes.Length - 1; 
            while (hiIndex > loIndex)
            { 
                int index = (hiIndex + loIndex + 1) >> 1; // middle, round up -- guarantee hiIndex >= index > loIndex 
                if (fixes[index].OffsetInFlowNode > flowOffset)
                { 
                    hiIndex = index - 1;
                }
                else
                { 
                    loIndex = index;
                } 
            } 

            FixedSOMElement element = fixes[loIndex]; 
            FixedSOMTextRun run;

            if (loIndex > 0 &&
                textdir == LogicalDirection.Backward && 
                element.OffsetInFlowNode == flowOffset)
            { 
                //check if we should really be in the prior element 
                FixedSOMElement last = fixes[loIndex - 1];
                int offsetInLast = flowOffset - last.OffsetInFlowNode + last.StartIndex; 

                if (offsetInLast == last.EndIndex)
                {
                    run = last as FixedSOMTextRun; 
                    if (run != null && run.IsReversed)
                    { 
                        offsetInLast = run.EndIndex - run.StartIndex - offsetInLast; 

                    } 
                    fixedp = new FixedPosition(last.FixedNode, offsetInLast);
                    return true;
                }
            } 

            run = element as FixedSOMTextRun; 
            int fixedOffset  = flowOffset - element.OffsetInFlowNode + element.StartIndex; 
            if (run != null && run.IsReversed)
            { 
                fixedOffset = run.EndIndex - run.StartIndex - fixedOffset;

            }
            fixedp = new FixedPosition(element.FixedNode, fixedOffset); 
            return true;
 
        } 

 
        // Find out fixed node given flow positions
        internal bool GetFixedNodesForFlowRange(FlowPosition pStart,
                                                            FlowPosition pEnd,
                                                            out FixedSOMElement[] somElements, 
                                                            out int firstElementStart,
                                                            out int lastElementEnd) 
        { 
            Debug.Assert(pStart.CompareTo(pEnd) < 0);
            somElements = null; 
            firstElementStart = 0;
            lastElementEnd = 0;

            FlowNode[] flowNodes; 
            int charStart = 0;
            int charEnd = -1; 
 
            int offsetStart;
            int offsetEnd; 

            pStart.GetFlowNodes(pEnd, out flowNodes, out offsetStart, out offsetEnd);
            if (flowNodes.Length <= 0)
            { 
                return false;
            } 
 
            ArrayList ar = new ArrayList();
            FlowNode flowStart  = flowNodes[0]; 
            FlowNode flowEnd    = flowNodes[flowNodes.Length - 1];

            foreach (FlowNode flowScan in flowNodes)
            { 
                int skipBefore = 0;
                int stopAt     = Int32.MaxValue; 
                if (flowScan == flowStart) 
                {
                    skipBefore = offsetStart; 
                }

                if (flowScan == flowEnd)
                { 
                    stopAt = offsetEnd;
                } 
 
                if (flowScan.Type == FlowNodeType.Object)
                { 
                    FixedSOMElement[] fixes = flowScan.FixedSOMElements;
                    Debug.Assert(fixes.Length == 1);
                    ar.Add(fixes[0]);
                } 

                if (flowScan.Type == FlowNodeType.Run) 
                { 
                    FixedSOMElement[] fixes = flowScan.FixedSOMElements;
                    foreach (FixedSOMElement element in fixes) 
                    {
                        int startIndex = element.OffsetInFlowNode;
                        if (startIndex >= stopAt)
                        { 
                            break;
                        } 
 
                        int endIndex = startIndex + element.EndIndex - element.StartIndex;
                        if (endIndex <= skipBefore) 
                        {
                            continue;
                        }
 
                        ar.Add(element);
 
                        if (skipBefore >= startIndex && flowScan == flowStart) 
                        {
                            charStart = element.StartIndex + skipBefore - startIndex; 
                        }

                        if (stopAt <= endIndex && flowScan == flowEnd)
                        { 
                            charEnd = element.StartIndex + stopAt - startIndex;
                            break; 
                        } 
                        else if (stopAt == endIndex + 1)
                        { 
                            charEnd = element.EndIndex; //in case this ends at beginning of next node
                        }

                    } 
                }//endofifrun
            }//endofforeach FlowNode 
 
            // This array could be empty! (Maybe...)  Broken if it is.
            somElements = (FixedSOMElement[])ar.ToArray(typeof(FixedSOMElement)); 
            if (somElements.Length == 0)
            {
                return false;
            } 

            if (flowStart.Type == FlowNodeType.Object) 
            {   // Image 
                firstElementStart = offsetStart;
            } 
            else
            {
                firstElementStart = charStart;
            } 
            if (flowEnd.Type == FlowNodeType.Object)
            { 
                lastElementEnd = offsetEnd; 
            }
            else 
            {
                lastElementEnd = charEnd;
            }
 
            return true;
        } 
 
        //-----------------------------------------------
        // FlowPosition ==>  Flow Content 
        //-----------------------------------------------

        // Helper function to retrieve text from FixedNodes that are mapped
        // to a flow run represented by a FlowPosition. 
        internal string GetFlowText(FlowNode flowNode)
        { 
            Debug.Assert(flowNode.Type == FlowNodeType.Run); 

            StringBuilder sb = new StringBuilder(); 
            FixedSOMElement[] fixes = flowNode.FixedSOMElements;
            Debug.Assert(flowNode.Type == FlowNodeType.Run);
            Debug.Assert(fixes != null);
 
            foreach (FixedSOMTextRun element in fixes)
            { 
                sb.Append(element.Text); 
            }
            return sb.ToString(); 
        }

        internal static bool MostlyRTL(string s)
        { 
            int RTL = 0;
            int LTR = 0; 
            foreach (char c in s) 
            {
                if (_IsRTL(c)) 
                {
                    RTL++;
                }
                else if (c != ' ') 
                {
                    LTR++; 
                } 
            }
 
            return (RTL > 0) && (LTR == 0 || (RTL / LTR >= 2));
        }

        //Decides whether two lines specified by line heights and a vertical distance between them is considered on the same line 
        //verticalDistance needs to be passed as top of line2 - top of line 1
        internal static bool IsSameLine(double verticalDistance, double fontSize1, double fontSize2) 
        { 
            // According to spec for rubber band selection, to adjacent Glyphs are on same line if they have 50% overlap
            double smallSize = (fontSize1 < fontSize2) ? fontSize1 : fontSize2; 
            double overlap = (verticalDistance > 0) ? (fontSize1 - verticalDistance) : (fontSize2 + verticalDistance);
            return overlap / smallSize > .5;
        }
 
        //------------------------------------------------------------------------------
        // Design Note (ZhenbinX - 2004/11/15) - Heuristic to test if two FixedSOMTextRun adjacent 
        // in geometry for the purpose of adding additional separator into non-adjacent runs. 
        // This algorithm bias toward NOT adding separator. The reason is artifically breaking
        // a word is more annoying than missing a space between words. 
        //
        // The following steps are applied in order:
        // 1. If the two TextRun belong to two different languages, they are not
        //    adjacent. (A separator is needed) 
        // 2. If the TextRun belongs to a language that does not use space as separator,
        //    they are always adjacent. (Need additional input about Bidi and complext 
        //    script here. Currently NOT adjacent). 
        // 3. If the two TextRuns belong to two different lines, they are NOT adjacent
        //    unless the end of the previous GlyphRun is HYPHEN. 
        // 3. For TextRuns on the same line:
        //    a. If the last character of the previous run is SPACE, they are adjacent.
        //    b. If they are in different Bidi embedding level, they are NOT adjacent.
        //    c. If the distance between their InkBoundingBox is greater than 1/4 of 
        //       the BoundingBox of the preceeding GlyphRun, they are NOT adjacent.
        //       (This can be tweaked to use step function in the future!). 
        // All others are adjacent Glyphs! 
        //
        //----------------------------------------------------------------------------- 
        internal static bool IsNonContiguous(CultureInfo ciPrev,
                                                    CultureInfo ciCurrent,
                                                    bool isSidewaysPrev,
                                                    bool isSidewaysCurrent, 
                                                    string strPrev,
                                                    string strCurrent, 
                                                    GlyphComparison comparison) 

        { 
            if (ciPrev != ciCurrent)
            {
                return true;
            } 
            if (AlwaysAdjacent(ciPrev))
            { 
                return false; 
            }
 

            if (isSidewaysPrev != isSidewaysCurrent)
            {
                return true;  // not adjacent 
            }
 
            if (strPrev.Length == 0 || strCurrent.Length == 0) 
            {
                return false;  // adjacent 
            }

            if (!isSidewaysPrev)
            {   // Horizontal Lines 
                int textLength = strPrev.Length;
                char lastChar = strPrev[textLength - 1]; 
 
                if (IsSpace(lastChar))
                { 
                    return false;       // adjacent
                }

                if (comparison == GlyphComparison.DifferentLine || 
                    comparison == GlyphComparison.Unknown)
                { 
                    // Different Line 
                    if (!IsHyphen(lastChar))
                    { 
                        return true;   // non adjacent
                    }
                }
                else 
                {
                    return comparison != GlyphComparison.Adjacent; 
                } 
            }
            return false;   // Default is adjacent 
        }


        #endregion Internal Methods 

 
        //-------------------------------------------------------------------- 
        //
        // Internal Properties 
        //
        //---------------------------------------------------------------------
        #region Internal Properties
        internal FixedFlowMap FixedFlowMap 
        {
            get 
            { 
                return _fixedFlowMap;
            } 
        }
#if DEBUG
        internal FixedTextContainer FixedTextContainer
        { 
            get
            { 
                return _container; 
            }
        } 
#endif

        #endregion Internal Propeties
 
        //-------------------------------------------------------------------
        // 
        // Private Methods 
        //
        //--------------------------------------------------------------------- 

        #region Private Methods

        //-------------------------------------------------------------------- 
        // Initilization
        //--------------------------------------------------------------------- 
        private void _Init() 
        {
            // Initialize Id 
            _nextScopeId  = FixedFlowMap.FlowOrderScopeIdStart;

            // Create empty mapping
            _fixedFlowMap = new FixedFlowMap(); 

            // 
            _pageStructures  = new List(); 
        }
 
        //--------------------------------------------------------------------
        // Heuristics
        //
        // Design Note (ZhenbinX): 
        //      Page boundary is artificially represented by a pair
        //      of FixedNodes. Start of Page uses int.MinValue as 
        //      its glyphs index, while End of Page uses int.MaxValue 
        //      as its glyphs index.  All users of FixedNode needs
        //      to be aware of such articifical index and special case 
        //      so that the "fake" glyphs indice are not used to access
        //      children.  One should always use FixedPage.GetGlyphs
        //      instead of using FixedPage's logical children collection
        //      directly, and should always check for possible null return. 
        //
        //      The page boundaries, however, are mapped to a FlowNodeType.Run 
        //      instead of any other FlowNodeType.  This is to be 
        //      consistent with the general principal that non-run type
        //      FlowNode has no corresponding FixedNode. 
        //
        //      Each FlowNode, if it is of type FlowNodeType.Run, contains
        //      a cookie that is the run length.
        //---------------------------------------------------------------------- 

        // Helper function for efficient creation of FixedNode used during pre-order walking. 
        // current index is @ childIndex 
        // depending on nesting level, the prefix can be hold at
        //      1. no prefix (level1) 
        //      2. level1Index
        //      3. pathPrefix.
        //
        FixedNode _NewFixedNode(int pageIndex, int nestingLevel, int level1Index, int[] pathPrefix, int childIndex) 
        {
            if (nestingLevel == 1) 
            { 
                return FixedNode.Create(pageIndex, nestingLevel, childIndex, -1, null);
            } 
            else if (nestingLevel == 2)
            {
                return FixedNode.Create(pageIndex, nestingLevel, level1Index, childIndex, null);
            } 
            else
            { 
                // For deeply nested path, we need to append current childIndex to a pathPrefix 
                // to form the entire childPath.
                Debug.Assert(pathPrefix != null); 
                int[] newPath = new int[pathPrefix.Length + 1];
                pathPrefix.CopyTo(newPath, 0);
                newPath[newPath.Length - 1] = childIndex;
                return FixedNode.Create(pageIndex, nestingLevel, -1, -1, newPath); 
            }
        } 
 

        // Helper function to get Paths with ImageBrushes 
        private bool _IsImage(object o)
        {
            System.Windows.Shapes.Path p = o as System.Windows.Shapes.Path;
            if (p != null) 
            {
                return p.Fill is ImageBrush && p.Data != null; 
            } 
            return o is Image;
        } 


        private bool _IsNonContiguous(FixedSOMTextRun prevRun, FixedSOMTextRun currentRun, GlyphComparison comparison)
        { 
            Debug.Assert(prevRun != null);
            Debug.Assert(currentRun != null); 
 
            if (prevRun.FixedNode == currentRun.FixedNode)
            { 
                return currentRun.StartIndex != prevRun.EndIndex;
            }

            return IsNonContiguous(prevRun.CultureInfo, 
                                    currentRun.CultureInfo,
                                    prevRun.IsSideways, 
                                    currentRun.IsSideways, 
                                    prevRun.Text,
                                    currentRun.Text, 
                                    comparison);

        }
 
        private GlyphComparison _CompareGlyphs(Glyphs glyph1, Glyphs glyph2)
        { 
            GlyphComparison comparison = GlyphComparison.DifferentLine; 
            if (glyph1 == glyph2)
            { 
                comparison = GlyphComparison.SameLine;
            }
            else if (glyph1 != null && glyph2 != null)
            { 
                GlyphRun run1 = glyph1.ToGlyphRun();
                GlyphRun run2 = glyph2.ToGlyphRun(); 
                if (run1 != null && run2 != null) 
                {
                    Rect box1 = run1.ComputeAlignmentBox(); 
                    box1.Offset(glyph1.OriginX, glyph1.OriginY);
                    Rect box2 = run2.ComputeAlignmentBox();
                    box2.Offset(glyph2.OriginX, glyph2.OriginY);
 
                    bool LTR1 = ((glyph1.BidiLevel & 1) == 0);
                    bool LTR2 = ((glyph2.BidiLevel & 1) == 0); 
 
                    GeneralTransform transform = glyph2.TransformToVisual(glyph1);
                    Point prevPt = LTR1 ? box1.TopRight : box1.TopLeft; 
                    Point currentPt = LTR2 ? box2.TopLeft : box2.TopRight;
                    if (transform != null)
                    {
                        transform.TryTransform(currentPt, out currentPt); 
                    }
 
                    if (IsSameLine(currentPt.Y - prevPt.Y, box1.Height, box2.Height)) 
                    {
                        comparison = GlyphComparison.SameLine; 
                        if (LTR1 == LTR2)
                        {
                            double xDistance = Math.Abs(currentPt.X - prevPt.X);
                            double maxHeight = Math.Max(box1.Height, box2.Height); 

                            if (xDistance / maxHeight < .05) 
                            { 
                                comparison = GlyphComparison.Adjacent;
                            } 
                        }
                    }
                }
            } 
            return comparison;
        } 
 
        // Apply heuristics
        // Create FlowNode structure 
        // Create Fixed to Flow mapping
        // Create FixedElement
        private void _CreateFixedMappingAndElementForPage(FixedPageStructure pageStructure, FixedPage page, bool constructSOM)
        { 
            List fixedNodes = new List();
            _GetFixedNodes(pageStructure, 
                           page.Children, 
                           1,
                           -1, 
                           null,
                           constructSOM,
                           fixedNodes,
                           Matrix.Identity); 

            FlowModelBuilder flowBuilder = new FlowModelBuilder(this, pageStructure, page); 
            flowBuilder.FindHyperlinkPaths(page); 

            if (constructSOM) 
            {
                pageStructure.FixedSOMPage.MarkupOrder = fixedNodes;
                pageStructure.ConstructFixedSOMPage(fixedNodes);
 

                _CreateFlowNodes(pageStructure.FixedSOMPage, flowBuilder); 
                pageStructure.PageConstructor = null; 
            }
            else 
            {
                pageStructure.FixedDSBuilder.ConstructFlowNodes(flowBuilder, fixedNodes);
            }
 
            flowBuilder.FinishMapping();
 
#if DEBUG 
            pageStructure.FixedNodes = fixedNodes;
            //flowBuilder.DumpToFile("FlowDump_Page_" + pageStructure.PageIndex.ToString() + ".xml"); 
#endif


 
        }
 
        private void _GetFixedNodes( 
                                    FixedPageStructure pageStructure,
                                    IEnumerable oneLevel, 
                                    int nestingLevel,       // the level of nesting
                                    int level1Index,        // if nesting level == 2, this is leve1 1 index
                                    int[] pathPrefix,   // if nesting level > 2, this is used to represent prefix, otherwise it is null
                                    bool constructLines, 
                                    List fixedNodes, // start empty, nodes will be added to this list
                                    Matrix transform 
                                    ) 
        {
            int pageIndex = pageStructure.PageIndex; 

            DocumentsTrace.FixedTextOM.Builder.Trace(string.Format("_FlowOrderAnalysis P{0}-L[{0}]", pageIndex, nestingLevel));

            int currentScopeId = _NewScopeId(); 

            // Create per run fixed nodes 
            IFrameworkInputElement namedNode; 

            int childIndex = 0; 
            IEnumerator elements = oneLevel.GetEnumerator();
            while (elements.MoveNext())
            {
                if (!constructLines) 
                {
                    namedNode = elements.Current as IFrameworkInputElement; 
                    if (namedNode != null && namedNode.Name != null && namedNode.Name.Length != 0) 
                    {
                        pageStructure.FixedDSBuilder.BuildNameHashTable(namedNode.Name, 
                                    elements.Current as UIElement,
                                    fixedNodes.Count);
                    }
                } 

                if (_IsImage(elements.Current) || 
                    (elements.Current is Glyphs && (elements.Current as Glyphs).MeasurementGlyphRun != null)) 
                {
                    fixedNodes.Add( 
                        _NewFixedNode(pageIndex, nestingLevel, level1Index, pathPrefix, childIndex)
                                            );
                    // GlyphRuns are non contiguous due to Image
                } 
                else if (constructLines && elements.Current is Path)
                { 
                    pageStructure.PageConstructor.ProcessPath(elements.Current as Path, transform); 
                }
                else if (elements.Current is Canvas) 
                {
                    Transform localTransform = Transform.Identity;

                    // Drill down to next level 
                    IEnumerable children;
 
                    Canvas canvas = elements.Current as Canvas; 

                    children       = canvas.Children; 
                    localTransform = canvas.RenderTransform;

                    if (localTransform == null)
                    { 
                        localTransform = Transform.Identity;
                    } 
 
                    if (children != null)
                    { 
                        int[] newPathPrefix = null;
                        if (nestingLevel >= 2)
                        {
                            // anything more than two level deep, we need to use path array 
                            if (nestingLevel == 2)
                            { 
                                Debug.Assert(pathPrefix == null); 
                                Debug.Assert(level1Index >= 0);
                                newPathPrefix = new int[2]; 
                                newPathPrefix[0] = level1Index;
                            }
                            else
                            { 
                                newPathPrefix = new int[pathPrefix.Length + 1];
                                pathPrefix.CopyTo(newPathPrefix, 0); 
                            } 
                            // Append the childIndex to newPathPrefix.
                            Debug.Assert(newPathPrefix != null); 
                            newPathPrefix[newPathPrefix.Length - 1] = childIndex;
                        }
#if DEBUG
                        else 
                        {
                            Debug.Assert(pathPrefix == null && newPathPrefix == null); 
                        } 
#endif
                        _GetFixedNodes( 
                                pageStructure,
                                children,
                                (nestingLevel + 1), // go to next nesting level
                                (nestingLevel == 1 ? childIndex : -1), // use this index if we are going from 1 to 2 
                                newPathPrefix,         // otherwise use this path prefix
                                constructLines, 
                                fixedNodes, 
                                transform * localTransform.Value
                                ); 

                    }//endofElementIsCanvas
                }
 
                childIndex++;
            } 
        } 

        private void _CreateFlowNodes(FixedSOMPage somPage, FlowModelBuilder flowBuilder) 
        {
            flowBuilder.AddStartNode(FixedElement.ElementType.Section);
            somPage.SetRTFProperties(flowBuilder.FixedElement);
 
            foreach (FixedSOMContainer container in somPage.SemanticBoxes)
            { 
                _CreateFlowNodes(container, flowBuilder); 
            }
 
            //Add the remaining hyperlinks at the end of the page
            flowBuilder.AddLeftoverHyperlinks();

            flowBuilder.AddEndNode(); 
        }
 
 

 
        //We will need to have a special case for an empty page
        private void _CreateFlowNodes(FixedSOMContainer node, FlowModelBuilder flowBuilder)
        {
            FixedElement.ElementType[] elementsForNode = node.ElementTypes; 
            foreach (FixedElement.ElementType type in elementsForNode)
            { 
                flowBuilder.AddStartNode(type); 
                node.SetRTFProperties(flowBuilder.FixedElement);
            } 


            List children = node.SemanticBoxes;
 
            foreach (FixedSOMSemanticBox box in children)
            { 
                if (box is FixedSOMElement) 
                {
                    flowBuilder.AddElement((FixedSOMElement)box); 
                }
                else if (box is FixedSOMContainer)
                {
                    _CreateFlowNodes((FixedSOMContainer)box, flowBuilder); 
                }
                else 
                { 
                    Debug.Assert(false);
                } 
            }

            foreach (FixedElement.ElementType type in elementsForNode)
            { 
                flowBuilder.AddEndNode();
            } 
        } 

 

        //-------------------------------------------------------------------
        // Fixed Document
        //---------------------------------------------------------------------- 

        private bool _IsStartVisual(int visualIndex) 
        { 
            return visualIndex == FixedFlowMap.FixedOrderStartVisual;
        } 

        private bool _IsEndVisual(int visualIndex)
        {
            return visualIndex == FixedFlowMap.FixedOrderEndVisual; 
        }
 
        private bool _IsBoundaryPage(int pageIndex) 
        {
            return (   pageIndex == FixedFlowMap.FixedOrderStartPage 
                    || pageIndex == FixedFlowMap.FixedOrderEndPage
                    );
        }
 
        // Advance the scope ID -- called when a new flow scope is needed.
        // the scope ID is used to identify the flow scope in flow order. 
        // 
        // For instance:
        //        
        // All Id =1 consists of one scope while Id=2 opens a new scope (in this case a nested scope).
        //
        private int _NewScopeId()
        { 
            return _nextScopeId++;
        } 
 

        private static bool _IsRTL(char c) 
        {
            /*return (c > 0x590 && c < 0x780) ||
                (c >= 0xFB1D && c <= 0xFDFD) ||
                (c >= 0xFE70 && c <= 0xFEFC);*/ 
            return (c >= 0x5D0 && c <= 0x60B) ||
                (c == 0x60D) || 
                (c >= 0x61B && c <= 0x64A) || 
                (c >= 0x66D && c <= 0x6D5 && c != 0x670) ||
                (c == 0x6DD) || (c == 0x6E5) || (c == 0x6E6) || 
                (c == 0x6EE) || (c == 0x6EF) ||
                (c >= 0x6FA && c <= 0x70D) ||
                (c == 0x710) || (c >= 0x712 && c <= 0x72F) ||
                (c >= 0x74D && c <= 0x7A5) || (c == 0x7B1) || 
                (c == 0xFB1D) || (c >= 0xFB1F && c <= 0xFD3D && c != 0xFB29) ||
                (c >= 0xFD50 && c <= 0xFDFC) || (c >= 0xFE70 && c <= 0xFEFC); 
 
        }
 
#if DEBUG
        private static bool _IsCombiningMark(char c)
        {
            return (c > 0x590 && c < 0x5BE) || 
                (c > 0x5BE && c < 0x5C8 && _cTable[c - 0x5BF]) ||
                (c >= 0x610 && c <= 0x615) || 
                (c >= 0x64B && c <= 0x65E) || c == 0x670 || 
                (c >= 0x6D6 && c <= 0x6ED && _cTable[c - 0x6CE])
                || c == 0x711 || (c >= 0x730 && c <= 0x74A) || 
                c == 0xFB1D;
        }

 
        /*private static Brush _ChooseDebugColor(Glyphs g)
        { 
            foreach (char c in g.UnicodeString) 
            {
                if (c >= 0xFB1D) 
                {
                    return Brushes.Red;
                }
                else if (_IsCombiningMark(c)) 
                {
                    return Brushes.Blue; 
                } 
            }
            return Brushes.Green; 
        }*/
#endif

        #endregion Private Methods 

        //------------------------------------------------------------------- 
        // 
        // Private Properties
        // 
        //---------------------------------------------------------------------

        #region Private Properties
        #endregion Private Properties 

        //------------------------------------------------------------------- 
        // 
        // Private Fields
        // 
        //----------------------------------------------------------------------

        #region Private Fields
        private readonly FixedTextContainer _container;     // page container 
        private List  _pageStructures; // contain all FixedPageStructure for each page.
        private int _nextScopeId;                           // Next FlowNode ScopeId 
        private FixedFlowMap _fixedFlowMap; 
        private static bool[] _cTable = new bool[] { true, //0x5BF   //Combining marks table
                false, true, true, false, // 0x5C0 - 3 
                true, true, false, true, //0x5C4
                true, true, //0x6D6 - 7
                true, true, true, true, //0x6D8 - B
                true, false, false, true, //C - F 
                true, true, true, true, //0x6E0 - 3
                true, false, false, true, //0x6E4 - 7 
                true, false, true, true, //0x6E8 - B 
                true, true //C, D
            }; 
        #endregion Private Fields

        //-------------------------------------------------------------------
        // 
        // Private Class
        // 
        //-------------------------------------------------------------------- 

        #region Private Class 
        internal sealed class FlowModelBuilder
        {
            private sealed class LogicalHyperlink
            { 
                public LogicalHyperlink(Uri uri, Geometry geom, UIElement uiElement)
                { 
                    _uiElement = uiElement; 
                    _uri = uri;
                    _geometry = geom; 
                    _boundingRect = geom.Bounds; //Get bounding rect
                    _used = false;
                }
 
                public Uri Uri
                { 
                    get 
                    {
                        return _uri; 
                    }
                }

                public Geometry Geometry 
                {
                    get 
                    { 
                        return _geometry;
                    } 
                }

                public Rect BoundingRect
                { 
                    get
                    { 
                        return _boundingRect; 
                    }
                } 

                public UIElement UIElement
                {
                    get 
                    {
                        return _uiElement; 
                    } 
                }
 
                public bool Used
                {
                    get
                    { 
                        return _used;
                    } 
                    set 
                    {
                        _used = value; 
                    }
                }

 
                private UIElement _uiElement;
                private Uri _uri; 
                private Geometry _geometry; 
                private Rect _boundingRect;
                private bool _used; 
            }

            private sealed class LogicalHyperlinkContainer : IEnumerable
            { 
                public LogicalHyperlinkContainer()
                { 
                    _hyperlinks = new List(); 

                } 

                IEnumerator IEnumerable.GetEnumerator()
                {
                    return _hyperlinks.GetEnumerator(); 
                }
 
                IEnumerator IEnumerable.GetEnumerator() 
                {
                    return _hyperlinks.GetEnumerator(); 
                }

                public void AddLogicalHyperlink(Uri uri, Geometry geometry, UIElement uiElement)
                { 
                    LogicalHyperlink hyperlink = new LogicalHyperlink(uri, geometry, uiElement);
                    _hyperlinks.Add(hyperlink); 
                } 

                //Returns a Uri that is associated with a SOMElement if there is one 
                //Also returns the actual UIElement as an output variable if a Path with NavigateUri
                //is used to make this SOMElement look like an actual hyperlink
                public Uri GetUri(FixedSOMElement element, FixedPage p, out UIElement shadowElement)
                { 
                    shadowElement = null;
                    UIElement e = p.GetElement(element.FixedNode) as UIElement; 
                    if (e == null) 
                    {
                        Debug.Assert(false); 
                        return null;
                    }
                    LogicalHyperlink logicalHyperlink = null;
                    Uri relUri = FixedPage.GetNavigateUri(e); 
                    if (relUri == null && _hyperlinks.Count > 0)
                    { 
                        Transform t = e.TransformToAncestor(p) as Transform; 
                        Geometry g;
                        if (e is Glyphs) 
                        {
                            GlyphRun run = ((Glyphs)e).ToGlyphRun();
                            Rect designRect = run.ComputeAlignmentBox();
                            designRect.Offset(run.BaselineOrigin.X, run.BaselineOrigin.Y); 

                            g = new RectangleGeometry(designRect); 
                        } 
                        else if (e is Path)
                        { 
                            g = ((Path)e).Data;
                        }
                        else
                        { 
                            Debug.Assert(e is Image);
                            Image im = (Image)e; 
                            g = new RectangleGeometry(new Rect(0, 0, im.Width, im.Height)); 
                        }
                        logicalHyperlink = _GetHyperlinkFromGeometry(g, t); 
                        if (logicalHyperlink != null)
                        {
                            relUri = logicalHyperlink.Uri;
                            shadowElement = logicalHyperlink.UIElement; 
                        }
                    } 
                    if (relUri == null) 
                    {
                        return null; 
                    }

                    return FixedPage.GetLinkUri(p, relUri);
                } 

 
                //Marks the hyperlink associated with a specific UIElement as "used" 
                public void MarkAsUsed(UIElement uiElement)
                { 
                    for (int i=0; i<_hyperlinks.Count; i++)
                    {
                        LogicalHyperlink hyperlink = _hyperlinks[i];
                        if (hyperlink.UIElement == uiElement) 
                        {
                            hyperlink.Used = true; 
                            break; 
                        }
                    } 
                }

                private LogicalHyperlink _GetHyperlinkFromGeometry(Geometry geom, Transform t)
                { 
                    Geometry g = geom;
 
                    if (t != null && !t.Value.IsIdentity) 
                    {
                        g = PathGeometry.CreateFromGeometry(geom); 
                        g.Transform = t;
                    }

                    double minArea = g.GetArea() * .99; 
                    Rect r = g.Bounds;
 
                    for (int i = 0; i < _hyperlinks.Count; i++) 
                    {
                        // do fast rect overlap before doing more expensive geometric comparison 
                        if (r.IntersectsWith(_hyperlinks[i].BoundingRect))
                        {
                            Geometry combined = Geometry.Combine(g, _hyperlinks[i].Geometry, GeometryCombineMode.Intersect, Transform.Identity);
                            if (combined.GetArea() > minArea) 
                            {
                                return _hyperlinks[i]; 
                            } 
                        }
                    } 

                    return null;
                }
 
                private List _hyperlinks;
 
            } 

            public FlowModelBuilder(FixedTextBuilder builder, FixedPageStructure pageStructure, FixedPage page) 
            {
                _builder = builder;
                _container = builder._container;
                _pageIndex = pageStructure.PageIndex; 
                _textRuns = new List();
                _flowNodes = new List(); 
                _fixedNodes = new List(); 
                _nodesInLine = new List();
                _lineResults = new List(); 
                _endNodes = new Stack();
                _fixedElements = new Stack();
                _mapping = builder._fixedFlowMap;
                _pageStructure = pageStructure; 
                _currentFixedElement = _container.ContainerElement;
                _lineLayoutBox = Rect.Empty; 
                _logicalHyperlinkContainer = new LogicalHyperlinkContainer(); 
                _fixedPage = page;
#if DEBUG 
                _dumpDoc = new XmlDocument();
                _currentDumpNode = _dumpDoc.CreateElement("FlowModel");
                _dumpDoc.AppendChild(_currentDumpNode);
#endif 

            } 
 

            public void FindHyperlinkPaths(FrameworkElement elem) 
            {
                //we are only interested in hyperlinks created by putting Path on top of a Gyphs element

                Debug.Assert(elem is FixedPage || elem is Canvas); 
                IEnumerable children = LogicalTreeHelper.GetChildren(elem);
 
                foreach (UIElement child in children) 
                {
                    Canvas canvas = child as Canvas; 
                    if (canvas != null)
                    {
                        FindHyperlinkPaths(canvas);
                    } 

                    if (!(child is Path) || ((Path)child).Fill is ImageBrush) 
                    { 
                        // ignore these, these are content
                        continue; 
                    }

                    Uri navUri = FixedPage.GetNavigateUri(child);
 
                    if (navUri != null && ((Path)child).Data != null)
                    { 
                        Transform trans = child.TransformToAncestor(_fixedPage) as Transform; 

                        Geometry geom = ((Path)child).Data; 
                        if (trans != null && !trans.Value.IsIdentity)
                        {
                            geom = PathGeometry.CreateFromGeometry(geom);
                            geom.Transform = trans; 
                        }
                        _logicalHyperlinkContainer.AddLogicalHyperlink(navUri, geom, child); 
                    } 
                }
            } 

            public void AddLeftoverHyperlinks()
            {
 
                foreach (LogicalHyperlink hyperlink in _logicalHyperlinkContainer)
                { 
                    if (!hyperlink.Used) 
                    {
                        _AddStartNode(FixedElement.ElementType.Paragraph); 
                        _AddStartNode(FixedElement.ElementType.Hyperlink);
                        _currentFixedElement.SetValue(Hyperlink.NavigateUriProperty, hyperlink.Uri);
                        _currentFixedElement.SetValue(FixedElement.HelpTextProperty, (String) (hyperlink.UIElement.GetValue(AutomationProperties.HelpTextProperty)));
                        _currentFixedElement.SetValue(FixedElement.NameProperty, (String) (hyperlink.UIElement.GetValue(AutomationProperties.NameProperty))); 
                        _AddEndNode();
                        _AddEndNode(); 
                    } 
                }
            } 
            //Use this for start tags
            public void AddStartNode(FixedElement.ElementType type)
            {
                _FinishTextRun(true); 
                _FinishHyperlink();
                _AddStartNode(type); 
            } 

            public void AddEndNode() 
            {
                _FinishTextRun(false);
                _FinishHyperlink();
                _AddEndNode(); 
            }
            //Use this for images and text runs -- generates necessary flow nodes 
            public void AddElement(FixedSOMElement element) 
            {
                FixedPage page = _builder.GetFixedPage(element.FixedNode); 
                UIElement shadowHyperlink;
                Uri navUri = _logicalHyperlinkContainer.GetUri(element, page, out shadowHyperlink);
                if (element is FixedSOMTextRun)
                { 
                    // Will add code to get font info for rich copy here
                    FixedSOMTextRun run = element as FixedSOMTextRun; 
                    bool createNewRun = (_currentRun == null) || (!run.HasSameRichProperties(_currentRun)) 
                        || navUri != _currentNavUri || (navUri != null && navUri.ToString() != _currentNavUri.ToString());
 
                    if (createNewRun)
                    {
                        if (_currentRun != null)
                        { 
                            //Close existing inline tag
                            FixedSOMFixedBlock parent = run.FixedBlock; 
 
                            FixedSOMTextRun lastRun = _textRuns[_textRuns.Count - 1];
 
                            Glyphs currentRunGlyph = _builder.GetGlyphsElement(lastRun.FixedNode);
                            Glyphs glyphs = _builder.GetGlyphsElement(run.FixedNode);

                            GlyphComparison comparison = _builder._CompareGlyphs(currentRunGlyph, glyphs); 

                            bool addSpace = false; 
                            if (_builder._IsNonContiguous(lastRun, run, comparison)) 
                            {
                                addSpace = true; 
                            }

                            _FinishTextRun(addSpace);
                        } 

                        _SetHyperlink(navUri, run.FixedNode, shadowHyperlink); 
                        //Open new Run tag and set RTF props 

                        _AddStartNode(FixedElement.ElementType.Run); 
                        run.SetRTFProperties(_currentFixedElement);
                        _currentRun = run;
                    }
 
                    _textRuns.Add((FixedSOMTextRun)element);
                    if (_fixedNodes.Count == 0 || _fixedNodes[_fixedNodes.Count - 1] != element.FixedNode) 
                    { 
                        _fixedNodes.Add(element.FixedNode);
                    } 
                }
                else if (element is FixedSOMImage)
                {
                    FixedSOMImage image = (FixedSOMImage)element; 
                    _FinishTextRun(true);
                    _SetHyperlink(navUri, image.FixedNode, shadowHyperlink); 
 
                    _AddStartNode(FixedElement.ElementType.InlineUIContainer);
 
                    FlowNode flowImageNode = new FlowNode(_NewScopeId(), FlowNodeType.Object, null);
                    // Create a new FixedElement to represent this new node.
                    _container.OnNewFlowElement(_currentFixedElement,
                                    FixedElement.ElementType.Object, 
                                    new FlowPosition(_container, flowImageNode, 0),
                                    new FlowPosition(_container, flowImageNode, 1), 
                                    image.Source, 
                                    _pageIndex
                                    ); 


                    _flowNodes.Add(flowImageNode);
 
                    // Do fixed/flow mapping for image
                    element.FlowNode = flowImageNode; 
                    flowImageNode.FixedSOMElements = new FixedSOMElement[] { element }; 
                    _mapping.AddFixedElement(element);
                    // Do we need this? 
                    _fixedNodes.Add(element.FixedNode);

                    //copy automation properties
                    FixedElement fElement = (FixedElement)flowImageNode.Cookie; 
                    fElement.SetValue(FixedElement.NameProperty, image.Name);
                    fElement.SetValue(FixedElement.HelpTextProperty, image.HelpText); 
 
                    _AddEndNode();
                } 
                else
                {
                    Debug.Assert(false);
                } 
            }
 
            public void FinishMapping() 
            {
                _FinishLine(); 
                _mapping.MappingReplace(_pageStructure.FlowStart, _flowNodes);
                _pageStructure.SetFlowBoundary(_flowNodes[0], _flowNodes[_flowNodes.Count-1]);
                _pageStructure.SetupLineResults(_lineResults.ToArray());
            } 

#if DEBUG 
            public void DumpToFile(string file) 
            {
                //_dumpDoc.Save(file); 
                StringWriter writer = new StringWriter();
                _dumpDoc.Save(writer);
            }
 
            private void DumpFlowNode(FlowNode node)
            { 
                FixedElement element = node.Cookie as FixedElement; 
                if (element != null)
                { 
                    XmlElement newDumpNode = _dumpDoc.CreateElement(element.Type.Name);
                    newDumpNode.SetAttribute("id", node.ScopeId.ToString());
                    _currentDumpNode.AppendChild(newDumpNode);
                    _currentDumpNode = newDumpNode; 
                }
                else 
                { 
                    //Run
                    int nodeLength = (int) node.Cookie; 
                    _currentDumpNode.SetAttribute("Cookie", nodeLength.ToString());
                    FixedSOMElement[] somElems = node.FixedSOMElements;
                    if (somElems!=null)
                    { 
                        StringBuilder strBuilder = new StringBuilder();
                        foreach (FixedSOMElement somElem in somElems) 
                        { 
                            FixedSOMTextRun run = somElem as FixedSOMTextRun;
                            if (run != null) 
                            {
                                strBuilder.Append(run.Text);
                            }
                        } 
                        _currentDumpNode.InnerText = strBuilder.ToString();
                    } 
                } 

            } 
#endif

            private void _AddStartNode(FixedElement.ElementType type)
            { 
                FlowNode startNode = new FlowNode(_NewScopeId(), FlowNodeType.Start, _pageIndex);
                FlowNode endNode = new FlowNode(_NewScopeId(), FlowNodeType.End, _pageIndex); 
                // add fixed element 
                _container.OnNewFlowElement(_currentFixedElement, //_container.ContainerElement,
                type, 
                new FlowPosition(_container, (FlowNode)startNode, 1),
                new FlowPosition(_container, (FlowNode)endNode, 0),
                null,
                _pageIndex 
                );
                // Create fixed element 
                _fixedElements.Push(_currentFixedElement); 
                _currentFixedElement = (FixedElement)startNode.Cookie;
                _flowNodes.Add(startNode); 
                _endNodes.Push(endNode);
#if DEBUG
                DumpFlowNode(startNode);
#endif 

 
            } 

            private void _AddEndNode() 
            {
                _flowNodes.Add((FlowNode)_endNodes.Pop());
                _currentFixedElement = (FixedElement)_fixedElements.Pop();
#if DEBUG 
                _currentDumpNode = (XmlElement) _currentDumpNode.ParentNode;
#endif 
            } 

            private void _FinishTextRun(bool addSpace) 
            {
                if (_textRuns.Count > 0)
                {
                    int textRunLength = 0; 
                    FixedSOMTextRun run = null;
                    for (int i=0; i<_textRuns.Count; i++) 
                    { 
                        run = _textRuns[i];
                        Glyphs glyphs = _builder.GetGlyphsElement(run.FixedNode); 
                        GlyphComparison comparison = _builder._CompareGlyphs(_lastGlyphs, glyphs);

                        if (comparison == GlyphComparison.DifferentLine)
                        { 
                            _FinishLine();
                        } 
 
                        _lastGlyphs = glyphs;
 
                        _lineLayoutBox.Union(run.BoundingRect);
                        run.LineIndex = _lineResults.Count;
                        if (_nodesInLine.Count == 0 || _nodesInLine[_nodesInLine.Count - 1] != run.FixedNode)
                        { 
                            _nodesInLine.Add(run.FixedNode);
                        } 
 
                        textRunLength += run.EndIndex - run.StartIndex;
                        Debug.Assert(run.EndIndex - run.StartIndex == run.Text.Length); 

                        if (i>0 && _builder._IsNonContiguous(_textRuns[i-1], run, comparison))
                        {
                            _textRuns[i-1].Text = _textRuns[i-1].Text + " "; 
                            textRunLength++;
                        } 
                    } 
                    if (addSpace && run.Text.Length>0 && !run.Text.EndsWith(" ", StringComparison.Ordinal) && !IsHyphen(run.Text[run.Text.Length - 1]))
                    { 
                        run.Text = run.Text + " ";
                        textRunLength ++;
                    }
 
                    if (textRunLength != 0)
                    { 
                        FlowNode flowNodeRun = new FlowNode(_NewScopeId(), FlowNodeType.Run, textRunLength); 
                        // Add list of text runs to flow node
                        flowNodeRun.FixedSOMElements = _textRuns.ToArray(); 

                        int offset = 0;

                        foreach (FixedSOMTextRun textRun in _textRuns) 
                        {
                            textRun.FlowNode = flowNodeRun; 
                            textRun.OffsetInFlowNode = offset; 
                            _mapping.AddFixedElement(textRun);
 
                            offset += textRun.Text.Length;
                        }

                        //Debug.Assert(offset == textRunLength); 

                        _flowNodes.Add(flowNodeRun); 
#if DEBUG 
                        DumpFlowNode(flowNodeRun);
#endif 

                        // clear the list
                        _textRuns.Clear();
 
                    }
 
                } 

                //Close the inline tag if any 
                if (_currentRun != null)
                {
                    _AddEndNode();
                    _currentRun = null; 
                }
 
            } 

            private void _FinishHyperlink() 
            {
                if (_currentNavUri != null)
                {
                    _AddEndNode(); //  
                    _currentNavUri = null;
                } 
            } 

            private void _SetHyperlink(Uri navUri, FixedNode node, UIElement shadowHyperlink) 
            {
                if (navUri != _currentNavUri || (navUri != null && navUri.ToString() != _currentNavUri.ToString()))
                {
                    if (_currentNavUri != null) 
                    {
                        _AddEndNode(); //  
                    } 

                    if (navUri != null) 
                    {
                        _AddStartNode(FixedElement.ElementType.Hyperlink);
                        _currentFixedElement.SetValue(Hyperlink.NavigateUriProperty, navUri);
                        UIElement uiElement = _fixedPage.GetElement(node) as UIElement; 
                        Debug.Assert(uiElement != null);
                        if (uiElement != null) 
                        { 
                            _currentFixedElement.SetValue(FixedElement.HelpTextProperty, (String) (uiElement.GetValue(AutomationProperties.HelpTextProperty)));
                            _currentFixedElement.SetValue(FixedElement.NameProperty, (String) (uiElement.GetValue(AutomationProperties.NameProperty))); 
                            if (shadowHyperlink != null)
                            {
                                _logicalHyperlinkContainer.MarkAsUsed(shadowHyperlink);
                            } 
                        }
                    } 
 
                    _currentNavUri = navUri;
                } 
            }

            private void _FinishLine()
            { 
                if (_nodesInLine.Count > 0)
                { 
                    FixedLineResult newLineResult = new FixedLineResult(_nodesInLine.ToArray(), _lineLayoutBox); 
                    Debug.Assert(newLineResult != null);
 
                    _lineResults.Add(newLineResult);

                    _nodesInLine.Clear();
                    _lineLayoutBox = Rect.Empty; 
                }
            } 
 
            private int _NewScopeId()
            { 
                return _builder._nextScopeId++;
            }

            public FixedElement FixedElement 
            {
                get 
                { 
                    return _currentFixedElement;
                } 
            }

            private int _pageIndex;
            private FixedTextContainer _container; 
            private FixedTextBuilder _builder;
            private List _textRuns; 
            private List _flowNodes; 
            private List _fixedNodes;
            private List _nodesInLine; 
            private List _lineResults;
            private Rect _lineLayoutBox;
            private Stack _endNodes;
            private Stack _fixedElements; 
            private FixedElement _currentFixedElement;
            private FixedFlowMap _mapping; 
            private FixedPageStructure _pageStructure; 
            private Glyphs _lastGlyphs;
            private FixedSOMTextRun _currentRun; 
            private LogicalHyperlinkContainer _logicalHyperlinkContainer;
            private FixedPage _fixedPage;
            private Uri _currentNavUri;
#if DEBUG 
            private XmlDocument _dumpDoc;
            private XmlElement _currentDumpNode; 
#endif 

        } 


        internal enum GlyphComparison
        { 
            DifferentLine,
            SameLine, 
            Adjacent, //also on same line 
            Unknown
        } 

        #endregion
    }
} 

// 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