QueryPrefixOp.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ WCF / WCF / 3.5.30729.1 / untmp / Orcas / SP / ndp / cdf / src / WCF / ServiceModel / System / ServiceModel / Dispatcher / QueryPrefixOp.cs / 1 / QueryPrefixOp.cs

                            //------------------------------------------------------------ 
// Copyright (c) Microsoft Corporation.  All rights reserved.
//-----------------------------------------------------------
namespace System.ServiceModel.Dispatcher
{ 
    using System.Collections;
    using System.ServiceModel.Channels; 
    using System.Collections.Generic; 
    using System.Text;
    using System.Diagnostics; 

    internal class TrieSegmentComparer : IComparer
    {
        public int Compare(TrieSegment t1, TrieSegment t2) 
        {
            return ((int)t1.FirstChar) - ((int)t2.FirstChar); 
        } 

        public bool Equals(TrieSegment t1, TrieSegment t2) 
        {
            return t1.FirstChar == t2.FirstChar;
        }
 
        public int GetHashCode(TrieSegment t)
        { 
            return t.GetHashCode(); 
        }
    } 

    internal class TrieSegmentKeyComparer : IItemComparer
    {
        public int Compare(char c, TrieSegment t) 
        {
            return ((int)c) - ((int)t.FirstChar); 
        } 
    }
 
    internal class TrieSegment
    {
        static readonly TrieSegmentKeyComparer SegKeyComparer = new TrieSegmentKeyComparer();
 
        SortedBuffer children;
        QueryBranch data; 
        TrieSegment parent; // segment's parent 
        char segmentFirstChar; // this segment's first character
        string segmentTail; // this segment's tail 
        int segmentLength;

        internal TrieSegment() : this(char.MinValue)
        { 
        }
 
        internal TrieSegment(char firstChar) : this(firstChar, string.Empty) 
        {
        } 

        internal TrieSegment(char firstChar, string segmentTail)
        {
            DiagnosticUtility.DebugAssert(null != segmentTail, ""); 
            this.SetSegment(firstChar, segmentTail);
            this.children = new SortedBuffer(); 
        } 

        internal TrieSegment(string sourceSegment, int offset, int length) 
        {
            DiagnosticUtility.DebugAssert(null != sourceSegment && length > 0, "");
            this.SetSegmentString(sourceSegment, offset, length);
            this.children = new SortedBuffer(); 
        }
 
        internal bool CanMerge 
        {
            get 
            {
                return (null == this.data && 1 == this.children.Count);
            }
        } 

        internal bool CanPrune 
        { 
            get
            { 
                return (null == this.data && 0 == this.children.Count);
            }
        }
#if NO 
        internal int ChildCount
        { 
            get 
            {
                return this.children.Count; 
            }
        }
#endif
        internal void CollectXPathFilters(ICollection filters) 
        {
            if(this.data != null) 
            { 
                (this.data).Branch.CollectXPathFilters(filters);
            } 

            for(int i = 0; i < this.children.Count; ++i)
            {
                this.children[i].CollectXPathFilters(filters); 
            }
        } 
 
        internal QueryBranch Data
        { 
            get
            {
                return this.data;
            } 
            set
            { 
                this.data = value; 
            }
        } 

        internal char FirstChar
        {
            get 
            {
                return this.segmentFirstChar; 
            } 
        }
 
        internal bool HasChildren
        {
            get
            { 
                return (this.children.Count > 0);
            } 
        } 

        internal int Length 
        {
            get
            {
                //return (this.segmentFirstChar == char.MinValue) ? 0 : this.segmentTail.Length + 1; 
                return this.segmentLength;
            } 
        } 
#if NO
        internal string Tail 
        {
            get
            {
                return this.segmentTail; 
            }
        } 
#endif 
        internal TrieSegment AddChild(TrieSegment segment)
        { 
            DiagnosticUtility.DebugAssert(null != segment, "");

            this.children.Insert(segment);
            segment.parent = this; 

            return segment; 
        } 
#if NO
        internal TrieSegment[] CopyChildren() 
        {
            return this.children.ToArray();
        }
#endif 
        internal int FindDivergence(string compareString, int offset, int length)
        { 
            DiagnosticUtility.DebugAssert(null != compareString && length > 0, ""); 

            if (compareString[offset] != this.segmentFirstChar) 
            {
                return 0;
            }
 
            --length;
            ++offset; 
 
            int charCount = (length <= this.segmentTail.Length) ? length : this.segmentTail.Length;
            for (int iSegment = 0, iCompare = offset; iSegment < charCount; ++iSegment, ++iCompare) 
            {
                if (compareString[iCompare] != this.segmentTail[iSegment])
                {
                    return iSegment + 1; 
                }
            } 
 
            if (length < this.segmentTail.Length)
            { 
                return length + 1;
            }

            return -1; 
        }
 
        internal TrieSegment GetChild(int index) 
        {
            DiagnosticUtility.DebugAssert(this.HasChildren, ""); 
            return this.children[index];
        }

        ///  
        /// Return the index of the child such that matchString == the string segment stored at that child
        /// i.e. matchString[0] == child.segmentFirstChar and matchString[1 -> length] == child.segmentTail[0 -> length] 
        ///  
        internal int GetChildPosition(string matchString, int offset, int length)
        { 
            DiagnosticUtility.DebugAssert(null != matchString, "");

            if (this.HasChildren)
            { 
                char matchChar = matchString[offset];
                int tailLength = length - 1; 
                int tailOffset = offset + 1; 
                int index = this.children.IndexOfKey(matchChar, SegKeyComparer);
                if(index >= 0) 
                {
                    TrieSegment child = this.children[index];
                    if (tailLength >= child.segmentTail.Length && (0 == child.segmentTail.Length || 0 == string.CompareOrdinal(matchString, tailOffset, child.segmentTail, 0, child.segmentTail.Length)))
                    { 
                        return index;
                    } 
                } 
            }
            return -1; 
        }

        /// 
        /// Return the index of the child such that child.segmentFirstChar == ch 
        /// 
        internal int GetChildPosition(char ch) 
        { 
            return this.children.IndexOfKey(ch, SegKeyComparer);
        } 

        internal int IndexOf(TrieSegment segment)
        {
            return this.children.IndexOf(segment); 
        }
 
        internal void MergeChild(TrieSegment segment) 
        {
            int childIndex = this.IndexOf(segment); 
            if (childIndex > -1)
            {
                this.MergeChild(childIndex);
            } 
        }
 
        ///  
        /// If the child node has no data associated with it and but one child of its own, it can be
        /// merged with the child, reducing the path by 1 
        /// 
        internal void MergeChild(int childIndex)
        {
            DiagnosticUtility.DebugAssert(this.HasChildren, ""); 

            TrieSegment child = this.children[childIndex]; 
            if (child.CanMerge) 
            {
                TrieSegment grandchild = child.children[0]; 

                StringBuilder newTail = new StringBuilder();
                newTail.Append(child.segmentTail);
                newTail.Append(grandchild.segmentFirstChar); 
                newTail.Append(grandchild.segmentTail);
 
                grandchild.SetSegment(child.segmentFirstChar, newTail.ToString()); 
                grandchild.parent = this;
 
                this.children.Exchange(child, grandchild);
                child.parent = null;
            }
        } 

        internal void Remove() 
        { 
            if (null != this.parent)
            { 
                this.parent.RemoveChild(this);
            }
        }
 
        /// 
        /// Remove the child == segment, and prune the tree 
        ///  
        void RemoveChild(TrieSegment segment)
        { 
            DiagnosticUtility.DebugAssert(null != segment, "");
            int childIndex = this.IndexOf(segment);
            if (childIndex >= 0)
            { 
                this.RemoveChild(childIndex, true);
            } 
        } 

        ///  
        /// Remove the child at index childIndex.
        /// If fixupTree is true, traverse back up the tree, removing prunable nodes or merging mergable nodes
        /// as appropriate
        ///  
        internal void RemoveChild(int childIndex, bool fixupTree)
        { 
            DiagnosticUtility.DebugAssert(this.HasChildren && childIndex >= 0, ""); 

            TrieSegment child = this.children[childIndex]; 

            child.parent = null;
            this.children.RemoveAt(childIndex);
 
            if (0 == this.children.Count)
            { 
                if (fixupTree && this.CanPrune) 
                {
                    this.Remove(); 
                }
            }
            else
            { 
                if (fixupTree && this.CanMerge && null != this.parent)
                { 
                    this.parent.MergeChild(this); 
                }
            } 
        }

        void SetSegment(char firstChar, string segmentTail)
        { 
            this.segmentFirstChar = firstChar;
            this.segmentTail = segmentTail; 
            this.segmentLength = firstChar == char.MinValue ? 0 : 1 + segmentTail.Length; 
        }
 
        void SetSegmentString(string segmentString, int offset, int length)
        {
            this.segmentFirstChar = segmentString[offset];
            if (length > 1) 
            {
                this.segmentTail = segmentString.Substring(offset + 1, length - 1); 
            } 
            else
            { 
                this.segmentTail = string.Empty;
            }
            this.segmentLength = length;
        } 

        TrieSegment SplitAt(int charIndex) 
        { 
            DiagnosticUtility.DebugAssert(charIndex > 0, "");
 
            TrieSegment newSegment;
            if (1 == charIndex)
            {
                newSegment = new TrieSegment(this.segmentFirstChar); 
            }
            else 
            { 
                DiagnosticUtility.DebugAssert(this.segmentTail.Length > 0, "");
                newSegment = new TrieSegment(this.segmentFirstChar, this.segmentTail.Substring(0, charIndex - 1)); 
            }
            --charIndex;
            this.SetSegmentString(this.segmentTail, charIndex, this.segmentTail.Length - charIndex);
            newSegment.AddChild(this); 
            return newSegment;
        } 
 
        internal TrieSegment SplitChild(int childIndex, int charIndex)
        { 
            DiagnosticUtility.DebugAssert(this.HasChildren, "");

            TrieSegment child = this.children[childIndex];
            this.children.Remove(child); 
            TrieSegment newChild = child.SplitAt(charIndex);
            this.children.Insert(newChild); 
            newChild.parent = this; 
            return newChild;
        } 

        internal void Trim()
        {
            this.children.Trim(); 
            for(int i = 0; i < this.children.Count; ++i)
            { 
                this.children[i].Trim(); 
            }
        } 
    }

    internal struct TrieTraverser
    { 
        int length;
        int offset; 
        string prefix; 
        TrieSegment rootSegment;
        TrieSegment segment; 
        int segmentIndex;

        internal TrieTraverser(TrieSegment root, string prefix)
        { 
            DiagnosticUtility.DebugAssert(null != root && null != prefix, "");
            this.prefix = prefix; 
            this.rootSegment = root; 
            this.segment = null;
            this.segmentIndex = -1; 
            this.offset = 0;
            this.length = prefix.Length;
        }
 
        /// 
        /// What length of segment that matched 
        ///  
        internal int Length
        { 
            get
            {
                return this.length;
            } 
        }
 
        ///  
        /// The offset within the original segment where the matching part of the source string began
        ///  
        internal int Offset
        {
            get
            { 
                return this.offset;
            } 
        } 

        ///  
        /// The traverser is currently at this segment node
        /// 
        internal TrieSegment Segment
        { 
            get
            { 
                return this.segment; 
            }
            set 
            {
                DiagnosticUtility.DebugAssert(null != value, "");
                this.segment = value;
            } 
        }
 
        internal int SegmentIndex 
        {
            get 
            {
                return this.segmentIndex;
            }
        } 

        ///  
        /// Traverse the prefix tree 
        /// 
        internal bool MoveNext() 
        {
            if (null != this.segment)
            {
                int segmentLength = this.segment.Length; 
                this.offset += segmentLength;
                this.length -= segmentLength; 
 
                if (this.length > 0)
                { 
                    this.segmentIndex = this.segment.GetChildPosition(this.prefix, this.offset, this.length);
                    if (this.segmentIndex > -1)
                    {
                        this.segment = this.segment.GetChild(this.segmentIndex); 
                        return true;
                    } 
                } 
                else
                { 
                    this.segmentIndex = -1;
                }
                this.segment = null;
            } 
            else if (null != this.rootSegment)
            { 
                this.segment = this.rootSegment; 
                this.rootSegment = null;
                return true; 
            }
            return false;
        }
 
        /// 
        /// Traverse the prefix tree.. using only the first character of each segment to jump from 
        /// segment to segment 
        /// 
        internal bool MoveNextByFirstChar() 
        {
            if (null != this.segment)
            {
                int segmentLength = this.segment.Length; 
                this.offset += segmentLength;
                this.length -= segmentLength; 
 
                if (this.length > 0)
                { 
                    this.segmentIndex = this.segment.GetChildPosition(this.prefix[this.offset]);
                    if (this.segmentIndex > -1)
                    {
                        this.segment = this.segment.GetChild(this.segmentIndex); 
                        return true;
                    } 
                } 
                else
                { 
                    this.segmentIndex = -1;
                }
                this.segment = null;
            } 
            else if (null != this.rootSegment)
            { 
                this.segment = this.rootSegment; 
                this.rootSegment = null;
                return true; 
            }

            return false;
        } 
    }
 
 
    internal class Trie
    { 
        TrieSegment root; // prefix tree root
        bool hasDescendants;

        internal Trie() 
        {
            this.hasDescendants = false; 
        } 

        bool HasDescendants 
        {
            get
            {
                //return (null != this.root && this.root.ChildCount > 0); 
                return this.hasDescendants;
            } 
        } 
#if NO
        internal bool IsEmpty 
        {
            get
            {
                return (null == this.root || (null == this.root.Data && 0 == this.root.ChildCount)); 
            }
        } 
#endif 
        internal TrieSegment this[string prefix]
        { 
            get
            {
                return this.Find(prefix);
            } 
        }
 
        ///  
        /// Tree root segment
        ///  
        internal TrieSegment Root
        {
            get
            { 
                this.EnsureRoot();
                return this.root; 
            } 
        }
 
        internal TrieSegment Add(string newPrefix)
        {
            if (newPrefix.Length <= 0)
            { 
                return this.Root;
            } 
 
            this.EnsureRoot();
            TrieTraverser traverser = new TrieTraverser(this.root, newPrefix); // struct 
            TrieSegment parent;
            int indexDivergence;
            while (true)
            { 
                parent = traverser.Segment;
                if (traverser.MoveNextByFirstChar()) 
                { 
                    // There is a child segment that starts with the same character as the remainder of newPrefix
                    // We have a shared segment 
                    // How much does newPrefix share with the current segment? Find the point at which they diverge
                    if (null != parent && -1 != (indexDivergence = traverser.Segment.FindDivergence(newPrefix, traverser.Offset, traverser.Length)))
                    {
                        // Segments diverge at character # 'indexDivergence'. newPrefix will share the segment upto 
                        // that character. Beyond that character, we will now have 2 child segments:
                        // - one for the portion of the current segment that diverged 
                        // - one for the portion of the new segment that diverged 

                        // Split the current segment into a shared part and a child containing the remainder of the segment.. 
                        traverser.Segment = parent.SplitChild(traverser.SegmentIndex, indexDivergence);
                    }
                }
                else 
                {
                    if (traverser.Length <= 0) 
                    { 
                        // The entire new prefix has been added to the tree
                        break; 
                    }
                    // No existing segment to share. Add a new one
                    traverser.Segment = parent.AddChild(new TrieSegment(newPrefix, traverser.Offset, traverser.Length));
                } 
            }
 
            this.hasDescendants = true; 

            return parent; 
        }

        void EnsureRoot()
        { 
            if (null == this.root)
            { 
                this.root = new TrieSegment(); 
            }
        } 

        TrieSegment Find(string prefix)
        {
            DiagnosticUtility.DebugAssert(null != prefix, ""); 

            if (0 == prefix.Length) 
            { 
                return this.Root;
            } 

            if (!this.HasDescendants)
            {
                return null; 
            }
 
            TrieTraverser traverser = new TrieTraverser(this.root, prefix); // struct 
            TrieSegment foundSegment = null;
            while (traverser.MoveNext()) 
            {
                foundSegment = traverser.Segment;
            }
            if (traverser.Length > 0) 
            {
                // We haven't used up the entire prefix in this search. Clearly, we didn't find the matching node 
                return null; 
            }
            return foundSegment; 
        }

        void PruneRoot()
        { 
            if (null != this.root && this.root.CanPrune)
            { 
                this.root = null; 
            }
        } 

        internal void Remove(string segment)
        {
            DiagnosticUtility.DebugAssert(null != segment, ""); 

            TrieSegment trieSegment = this[segment]; 
            if (null == trieSegment) 
            {
                return; 
            }

            if (trieSegment.HasChildren)
            { 
                trieSegment.Data = null;
                return; 
            } 

            if (trieSegment == this.root) 
            {
                // Remove the entire tree!
                this.root = null;
                this.hasDescendants = false; 
                return;
            } 
 
            trieSegment.Remove();
            this.PruneRoot(); 
        }

        internal void Trim()
        { 
            this.root.Trim();
        } 
    } 

    internal class StringPrefixOpcode : LiteralRelationOpcode 
    {
        string literal;

        internal StringPrefixOpcode(string literal) 
            : base(OpcodeID.StringPrefix)
        { 
            DiagnosticUtility.DebugAssert(null != literal, ""); 
            this.literal = literal;
        } 
#if NO
        internal override ValueDataType DataType
        {
            get 
            {
                return ValueDataType.String; 
            } 
        }
#endif 
        internal override object Literal
        {
            get
            { 
                return this.literal;
            } 
        } 

        internal override void Add(Opcode op) 
        {
            StringPrefixOpcode prefixOp = op as StringPrefixOpcode;
            if (null == prefixOp)
            { 
                base.Add(op);
                return; 
            } 

            DiagnosticUtility.DebugAssert(null != this.prev, ""); 

            StringPrefixBranchOpcode branch = new StringPrefixBranchOpcode();
            this.prev.Replace(this, branch);
            branch.Add(this); 
            branch.Add(prefixOp);
        } 
 
        internal override bool Equals(Opcode op)
        { 
            if (base.Equals (op))
            {
                StringPrefixOpcode prefixOp = (StringPrefixOpcode) op;
                return (prefixOp.literal == this.literal); 
            }
 
            return false; 
        }
 
        internal override Opcode Eval(ProcessingContext context)
        {
            StackFrame arg = context.TopArg;
            if (1 == arg.Count) 
            {
                DiagnosticUtility.DebugAssert(context.Values[arg.basePtr].IsType(ValueDataType.String), ""); 
 
                string target = context.Values[arg.basePtr].String;
                context.Values[arg.basePtr].Boolean = target.StartsWith(this.literal, StringComparison.Ordinal); 
            }
            else
            {
                for (int i = arg.basePtr; i <= arg.endPtr; ++i) 
                {
                    DiagnosticUtility.DebugAssert(context.Values[i].IsType(ValueDataType.String), ""); 
                    string target = context.Values[i].String; 
                    context.Values[i].Boolean = target.StartsWith(this.literal, StringComparison.Ordinal);
                } 
            }

            return this.next;
        } 
    }
 
    internal class TrieBranchIndex : QueryBranchIndex 
    {
        int count; 
        Trie trie;

        internal TrieBranchIndex()
        { 
            this.count = 0;
            this.trie = new Trie(); 
        } 

        internal override int Count 
        {
            get
            {
                return this.count; 
            }
        } 
 
        internal override QueryBranch this[object key]
        { 
            get
            {
                TrieSegment segment = this.trie[(string) key];
                if (null != segment) 
                {
                    return segment.Data; 
                } 
                return null;
            } 
            set
            {
                DiagnosticUtility.DebugAssert(null != key, "");
                TrieSegment segment = this.trie.Add((string) key); 
                DiagnosticUtility.DebugAssert(null != segment, "");
                this.count++; 
                segment.Data = value; 
            }
        } 

        internal override void CollectXPathFilters(ICollection filters)
        {
            this.trie.Root.CollectXPathFilters(filters); 
        }
 
#if NO 
        internal override IEnumerator GetEnumerator()
        { 
            //return new TrieBreadthFirstEnum(this.trie);
            throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new NotImplementedException("TODO"));
        }
#endif 

        void Match(int valIndex, string segment, QueryBranchResultSet results) 
        { 
            TrieTraverser traverser = new TrieTraverser(this.trie.Root, segment);
            while (traverser.MoveNext()) 
            {
                object segmentData = traverser.Segment.Data;
                if (null != segmentData)
                { 
                    results.Add((QueryBranch) segmentData, valIndex);
                } 
            } 
        }
 
        internal override void Match(int valIndex, ref Value val, QueryBranchResultSet results)
        {
            if (ValueDataType.Sequence == val.Type)
            { 
                NodeSequence sequence = val.Sequence;
                for (int i = 0; i < sequence.Count; ++i) 
                { 
                    this.Match(valIndex, sequence.Items[i].StringValue(), results);
                } 
            }
            else
            {
                this.Match(valIndex, val.String, results); 
            }
        } 
 
        internal override void Remove(object key)
        { 
            this.trie.Remove((string) key);
            this.count--;
        }
 
        internal override void Trim()
        { 
            this.trie.Trim(); 
        }
    } 

    internal class StringPrefixBranchOpcode : QueryConditionalBranchOpcode
    {
        internal StringPrefixBranchOpcode() 
            : base(OpcodeID.StringPrefixBranch, new TrieBranchIndex())
        { 
        } 
    }
} 

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