ReadOnlyTernaryTree.cs source code in C# .NET

Source code for the .NET framework in C#

                        
Code:

                         / 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Xml / System / Xml / Core / ReadOnlyTernaryTree.cs / 1305376 / ReadOnlyTernaryTree.cs
                        

                        
                            //------------------------------------------------------------------------------ 
// 
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// [....] 
//-----------------------------------------------------------------------------
 
using System; 
using System.IO;
using System.Diagnostics; 

namespace System.Xml {

    // Array index to indicate the meaning of the each byte. 
    internal enum TernaryTreeByte  {characterByte = 0, leftTree = 1, rightTree = 2, data = 3};
 
    // 
    // XSL HTML output method properties
    // 
    // Keep the first four bits in [....], so that the element and attribute mask operation can be combined.
    internal enum ElementProperties : uint {DEFAULT = 0, URI_PARENT = 1, BOOL_PARENT = 2, NAME_PARENT = 4, EMPTY = 8, NO_ENTITIES = 16, HEAD = 32,  BLOCK_WS = 64, HAS_NS = 128}
    internal enum AttributeProperties : uint {DEFAULT = 0, URI = 1, BOOLEAN = 2, NAME = 4}
 

    /** 
     * TernaryTreeRO 
     * -------------
     * 
     * Ternary tree implementation used to make fast dictionary lookups in pre-generated
     * ternary trees.
     *
     * Note: Only strings composed of ASCII characters can exist in the tree. 
     */
    ///  
    internal class TernaryTreeReadOnly { 

        byte []  nodeBuffer; 

        //define the array positions

 
        /// 
        public TernaryTreeReadOnly(byte [] nodeBuffer) { 
            this.nodeBuffer = nodeBuffer; 
        }
 
        /*  ---------------------------------------------------------------------------
            findStringI()

            Find a Unicode string in the ternary tree and return the data byte it's 
            mapped to.  Find is case-insensitive.
        */ 
        ///  
        public byte FindCaseInsensitiveString(String stringToFind) {
 
            //Debug.Assert(wszFind != null && wszFind.Length != 0);

            int stringPos = 0, nodePos = 0;
            int charToFind, charInTheTree; 
            byte [] node = nodeBuffer;
 
            charToFind = stringToFind[stringPos]; 

            if (charToFind > 'z') return 0;                    // Ternary tree only stores ASCII strings 
            if (charToFind >= 'a') charToFind -= ('a' - 'A');     // Normalize to upper case

            while (true) {
                int pos = nodePos * 4; 

                charInTheTree = node[pos + (int)TernaryTreeByte.characterByte]; 
                //Console.WriteLine("charToFind: {0},charInTheTree: {1}, nodePos: {2}", charToFind, charInTheTree, nodePos); 

                if (charToFind < charInTheTree) { 

                    // If input character is less than the tree character, take the left branch
                    if (node[pos + (int)TernaryTreeByte.leftTree] == 0x0) {
                        break; 
                    }
                    nodePos = nodePos + node[pos + (int)TernaryTreeByte.leftTree]; 
 
                } else if (charToFind > charInTheTree) {
                    // If input character is greater than the tree character, take the right branch 
                    if (node[pos + (int)TernaryTreeByte.rightTree] == 0x0)
                        break;
                    nodePos = nodePos + node[pos + (int)TernaryTreeByte.rightTree];
 
                } else {
                    // If input character is equal to the tree character, take the equal branch 
                    if (charToFind == 0) 
                        return node[pos + (int)TernaryTreeByte.data];
 
                    // The offset for the equal branch is always one
                    ++nodePos;

                    // Move to the next input character 
                    ++stringPos;
                    if (stringPos == stringToFind.Length) { 
                        charToFind = 0; 
                    }
                    else { 
                        charToFind = stringToFind[stringPos];
                        if (charToFind > 'z') return 0;                     // Ternary tree only stores ASCII strings
                        if (charToFind >= 'a') charToFind -= ('a' - 'A');   // Normalize to upper case
                    } 
                }
            } 
 
            // Return default
            return 0; 
        }
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------------------ 
// 
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// [....] 
//-----------------------------------------------------------------------------
 
using System; 
using System.IO;
using System.Diagnostics; 

namespace System.Xml {

    // Array index to indicate the meaning of the each byte. 
    internal enum TernaryTreeByte  {characterByte = 0, leftTree = 1, rightTree = 2, data = 3};
 
    // 
    // XSL HTML output method properties
    // 
    // Keep the first four bits in [....], so that the element and attribute mask operation can be combined.
    internal enum ElementProperties : uint {DEFAULT = 0, URI_PARENT = 1, BOOL_PARENT = 2, NAME_PARENT = 4, EMPTY = 8, NO_ENTITIES = 16, HEAD = 32,  BLOCK_WS = 64, HAS_NS = 128}
    internal enum AttributeProperties : uint {DEFAULT = 0, URI = 1, BOOLEAN = 2, NAME = 4}
 

    /** 
     * TernaryTreeRO 
     * -------------
     * 
     * Ternary tree implementation used to make fast dictionary lookups in pre-generated
     * ternary trees.
     *
     * Note: Only strings composed of ASCII characters can exist in the tree. 
     */
    ///  
    internal class TernaryTreeReadOnly { 

        byte []  nodeBuffer; 

        //define the array positions

 
        /// 
        public TernaryTreeReadOnly(byte [] nodeBuffer) { 
            this.nodeBuffer = nodeBuffer; 
        }
 
        /*  ---------------------------------------------------------------------------
            findStringI()

            Find a Unicode string in the ternary tree and return the data byte it's 
            mapped to.  Find is case-insensitive.
        */ 
        ///  
        public byte FindCaseInsensitiveString(String stringToFind) {
 
            //Debug.Assert(wszFind != null && wszFind.Length != 0);

            int stringPos = 0, nodePos = 0;
            int charToFind, charInTheTree; 
            byte [] node = nodeBuffer;
 
            charToFind = stringToFind[stringPos]; 

            if (charToFind > 'z') return 0;                    // Ternary tree only stores ASCII strings 
            if (charToFind >= 'a') charToFind -= ('a' - 'A');     // Normalize to upper case

            while (true) {
                int pos = nodePos * 4; 

                charInTheTree = node[pos + (int)TernaryTreeByte.characterByte]; 
                //Console.WriteLine("charToFind: {0},charInTheTree: {1}, nodePos: {2}", charToFind, charInTheTree, nodePos); 

                if (charToFind < charInTheTree) { 

                    // If input character is less than the tree character, take the left branch
                    if (node[pos + (int)TernaryTreeByte.leftTree] == 0x0) {
                        break; 
                    }
                    nodePos = nodePos + node[pos + (int)TernaryTreeByte.leftTree]; 
 
                } else if (charToFind > charInTheTree) {
                    // If input character is greater than the tree character, take the right branch 
                    if (node[pos + (int)TernaryTreeByte.rightTree] == 0x0)
                        break;
                    nodePos = nodePos + node[pos + (int)TernaryTreeByte.rightTree];
 
                } else {
                    // If input character is equal to the tree character, take the equal branch 
                    if (charToFind == 0) 
                        return node[pos + (int)TernaryTreeByte.data];
 
                    // The offset for the equal branch is always one
                    ++nodePos;

                    // Move to the next input character 
                    ++stringPos;
                    if (stringPos == stringToFind.Length) { 
                        charToFind = 0; 
                    }
                    else { 
                        charToFind = stringToFind[stringPos];
                        if (charToFind > 'z') return 0;                     // Ternary tree only stores ASCII strings
                        if (charToFind >= 'a') charToFind -= ('a' - 'A');   // Normalize to upper case
                    } 
                }
            } 
 
            // Return default
            return 0; 
        }
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.

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