UriTemplateTrieNode.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 / NetFx35 / System.ServiceModel.Web / System / UriTemplateTrieNode.cs / 4 / UriTemplateTrieNode.cs

                            //---------------------------------------------------------------- 
// Copyright (c) Microsoft Corporation.  All rights reserved.
//---------------------------------------------------------------

namespace System 
{
    using System.Collections.Generic; 
    using System.Collections.ObjectModel; 
    using System.ServiceModel;
    using System.ServiceModel.Web; 

    class UriTemplateTrieNode
    {
        int depth; // relative segment depth (root = 0) 
        UriTemplatePathPartiallyEquivalentSet endOfPath; // matches the non-existent segment at the end of a slash-terminated path
        AscendingSortedCompoundSegmentsCollection finalCompoundSegment; // matches e.g. "{var}.{var}" 
        Dictionary finalLiteralSegment; // matches e.g. "segmentThatDoesntEndInSlash" 
        UriTemplatePathPartiallyEquivalentSet finalVariableSegment; // matches e.g. "{var}"
        AscendingSortedCompoundSegmentsCollection nextCompoundSegment; // all are AfterLiteral; matches e.g. "{var}.{var}/" 
        Dictionary nextLiteralSegment; // all are BeforeLiteral; matches e.g. "path/"
        UriTemplateTrieLocation nextVariableSegment; // is BeforeLiteral; matches e.g. "{var}/"
        UriTemplateTrieLocation onFailure; // points to parent, at 'after me'
        UriTemplatePathPartiallyEquivalentSet star; // matches any "extra/path/segments" at the end 

        UriTemplateTrieNode(int depth) 
        { 
            this.depth = depth;
            this.nextLiteralSegment = null; 
            this.nextCompoundSegment = null;
            this.finalLiteralSegment = null;
            this.finalCompoundSegment = null;
            this.finalVariableSegment = new UriTemplatePathPartiallyEquivalentSet(depth + 1); 
            this.star = new UriTemplatePathPartiallyEquivalentSet(depth);
            this.endOfPath = new UriTemplatePathPartiallyEquivalentSet(depth); 
        } 

        public static UriTemplateTrieNode Make(IEnumerable> keyValuePairs, 
            bool allowDuplicateEquivalentUriTemplates)
        {
            // given a UTT at MakeReadOnly time, build the trie
            // note that root.onFailure == null; 
            UriTemplateTrieNode root = new UriTemplateTrieNode(0);
            foreach (KeyValuePair kvp in keyValuePairs) 
            { 
                Add(root, kvp);
            } 
            Validate(root, allowDuplicateEquivalentUriTemplates);
            return root;
        }
 
        public bool Match(UriTemplateLiteralPathSegment[] wireData, ICollection candidates)
        { 
            UriTemplateTrieLocation currentLocation = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.BeforeLiteral); 
            return GetMatch(currentLocation, wireData, candidates);
        } 

        static void Add(UriTemplateTrieNode root, KeyValuePair kvp)
        {
            // Currently UTT doesn't support teplates with ignoreTrailingSlash == true; thus we 
            //  don't care about supporting it in the trie as well.
            UriTemplateTrieNode current = root; 
            UriTemplate ut = kvp.Key; 
            bool needProcessingOnFinalNode = ((ut.segments.Count == 0) || ut.HasWildcard ||
                ut.segments[ut.segments.Count - 1].EndsWithSlash); 
            for (int i = 0; i < ut.segments.Count; ++i)
            {
                if (i >= ut.firstOptionalSegment)
                { 
                    current.endOfPath.Items.Add(kvp);
                } 
                UriTemplatePathSegment ps = ut.segments[i]; 
                if (!ps.EndsWithSlash)
                { 
                    Fx.Assert(i == ut.segments.Count - 1, "only the last segment can !EndsWithSlash");
                    Fx.Assert(!ut.HasWildcard, "path star cannot have !EndsWithSlash");
                    switch (ps.Nature)
                    { 
                        case UriTemplatePartType.Literal:
                            current.AddFinalLiteralSegment(ps as UriTemplateLiteralPathSegment, kvp); 
                            break; 

                        case UriTemplatePartType.Compound: 
                            current.AddFinalCompoundSegment(ps as UriTemplateCompoundPathSegment, kvp);
                            break;

                        case UriTemplatePartType.Variable: 
                            current.finalVariableSegment.Items.Add(kvp);
                            break; 
 
                        default:
                            Fx.Assert("Invalid value as PathSegment.Nature"); 
                            break;
                    }
                }
                else 
                {
                    Fx.Assert(ps.EndsWithSlash, "ps.EndsWithSlash"); 
                    switch (ps.Nature) 
                    {
                        case UriTemplatePartType.Literal: 
                            current = current.AddNextLiteralSegment(ps as UriTemplateLiteralPathSegment);
                            break;

                        case UriTemplatePartType.Compound: 
                            current = current.AddNextCompoundSegment(ps as UriTemplateCompoundPathSegment);
                            break; 
 
                        case UriTemplatePartType.Variable:
                            current = current.AddNextVariableSegment(); 
                            break;

                        default:
                            Fx.Assert("Invalid value as PathSegment.Nature"); 
                            break;
                    } 
                } 
            }
            if (needProcessingOnFinalNode) 
            {
                // if the last segment ended in a slash, there is still more to do
                if (ut.HasWildcard)
                { 
                    // e.g. "path1/path2/*"
                    current.star.Items.Add(kvp); 
                } 
                else
                { 
                    // e.g. "path1/path2/"
                    current.endOfPath.Items.Add(kvp);
                }
            } 
        }
 
        static bool CheckMultipleMatches(IList> locationsSet, UriTemplateLiteralPathSegment[] wireData, 
            ICollection candidates)
        { 
            bool result = false;
            for (int i = 0; ((i < locationsSet.Count) && !result); i++)
            {
                for (int j = 0; j < locationsSet[i].Count; j++) 
                {
                    if (GetMatch(locationsSet[i][j], wireData, candidates)) 
                    { 
                        result = true;
                    } 
                }
            }
            return result;
        } 
        static bool GetMatch(UriTemplateTrieLocation location, UriTemplateLiteralPathSegment[] wireData,
            ICollection candidates) 
        { 
            int initialDepth = location.node.depth;
            SingleLocationOrLocationsSet nextStep; 
            UriTemplatePathPartiallyEquivalentSet answer;
            do
            {
                if (TryMatch(wireData, location, out answer, out nextStep)) 
                {
                    if (answer != null) 
                    { 
                        for(int i = 0; i < answer.Items.Count; i++)
                        { 
                            candidates.Add(new UriTemplateTableMatchCandidate(answer.Items[i].Key, answer.SegmentsCount,
                                answer.Items[i].Value));
                        }
                    } 
                    return true;
                } 
                if (nextStep.IsSingle) 
                {
                    location = nextStep.SingleLocation; 
                }
                else
                {
                    Fx.Assert(nextStep.LocationsSet != null, "This should be set to a valid value by TryMatch"); 
                    if (CheckMultipleMatches(nextStep.LocationsSet, wireData, candidates))
                    { 
                        return true; 
                    }
                    location = GetFailureLocationFromLocationsSet(nextStep.LocationsSet); 
                }
            } while ((location != null) && (location.node.depth >= initialDepth));

            // we walked the whole trie down and found nothing 
            return false;
        } 
        static bool TryMatch(UriTemplateLiteralPathSegment[] wireUriSegments, UriTemplateTrieLocation currentLocation, 
            out UriTemplatePathPartiallyEquivalentSet success, out SingleLocationOrLocationsSet nextStep)
        { 
            // if returns true, success is set to answer
            // if returns false, nextStep is set to next place to look
            success = null;
            nextStep = new SingleLocationOrLocationsSet(); 

            if (wireUriSegments.Length <= currentLocation.node.depth) 
            { 
                Fx.Assert(wireUriSegments.Length == 0 || wireUriSegments[wireUriSegments.Length - 1].EndsWithSlash,
                    "we should not have traversed this deep into the trie unless the wire path ended in a slash"); 

                if (currentLocation.node.endOfPath.Items.Count != 0)
                {
                    // exact match of e.g. "path1/path2/" 
                    success = currentLocation.node.endOfPath;
                    return true; 
                } 
                else if (currentLocation.node.star.Items.Count != 0)
                { 
                    // inexact match of e.g. WIRE("path1/path2/") against TEMPLATE("path1/path2/*")
                    success = currentLocation.node.star;
                    return true;
                } 
                else
                { 
                    nextStep = new SingleLocationOrLocationsSet(currentLocation.node.onFailure); 
                    return false;
                } 
            }
            else
            {
                UriTemplateLiteralPathSegment curWireSeg = wireUriSegments[currentLocation.node.depth]; 
                bool considerLiteral = false;
                bool considerCompound = false; 
                bool considerVariable = false; 
                bool considerStar = false;
                switch (currentLocation.locationWithin) 
                {
                    case UriTemplateTrieIntraNodeLocation.BeforeLiteral:
                        considerLiteral = true;
                        considerCompound = true; 
                        considerVariable = true;
                        considerStar = true; 
                        break; 
                    case UriTemplateTrieIntraNodeLocation.AfterLiteral:
                        considerLiteral = false; 
                        considerCompound = true;
                        considerVariable = true;
                        considerStar = true;
                        break; 
                    case UriTemplateTrieIntraNodeLocation.AfterCompound:
                        considerLiteral = false; 
                        considerCompound = false; 
                        considerVariable = true;
                        considerStar = true; 
                        break;
                    case UriTemplateTrieIntraNodeLocation.AfterVariable:
                        considerLiteral = false;
                        considerCompound = false; 
                        considerVariable = false;
                        considerStar = true; 
                        break; 
                    default:
                        Fx.Assert("bad kind"); 
                        break;
                }
                if (curWireSeg.EndsWithSlash)
                { 
                    IList> compoundLocationsSet;
 
                    if (considerLiteral && currentLocation.node.nextLiteralSegment != null && 
                        currentLocation.node.nextLiteralSegment.ContainsKey(curWireSeg))
                    { 
                        nextStep = new SingleLocationOrLocationsSet(currentLocation.node.nextLiteralSegment[curWireSeg]);
                        return false;
                    }
                    else if (considerCompound && currentLocation.node.nextCompoundSegment != null && 
                        AscendingSortedCompoundSegmentsCollection.Lookup(currentLocation.node.nextCompoundSegment, curWireSeg, out compoundLocationsSet))
                    { 
                        nextStep = new SingleLocationOrLocationsSet(compoundLocationsSet); 
                        return false;
                    } 
                    else if (considerVariable && currentLocation.node.nextVariableSegment != null &&
                        !curWireSeg.IsNullOrEmpty())
                    {
                        nextStep = new SingleLocationOrLocationsSet(currentLocation.node.nextVariableSegment); 
                        return false;
                    } 
                    else if (considerStar && currentLocation.node.star.Items.Count != 0) 
                    {
                        // matches e.g. WIRE("path1/path2/path3") and TEMPLATE("path1/*") 
                        success = currentLocation.node.star;
                        return true;
                    }
                    else 
                    {
                        nextStep = new SingleLocationOrLocationsSet(currentLocation.node.onFailure); 
                        return false; 
                    }
                } 
                else
                {
                    IList> compoundPathEquivalentSets;
 
                    Fx.Assert(!curWireSeg.EndsWithSlash, "!curWireSeg.EndsWithSlash");
                    Fx.Assert(!curWireSeg.IsNullOrEmpty(), "!curWireSeg.IsNullOrEmpty()"); 
                    if (considerLiteral && currentLocation.node.finalLiteralSegment != null && 
                        currentLocation.node.finalLiteralSegment.ContainsKey(curWireSeg))
                    { 
                        // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/path2")
                        success = currentLocation.node.finalLiteralSegment[curWireSeg];
                        return true;
                    } 
                    else if (considerCompound && currentLocation.node.finalCompoundSegment != null &&
                        AscendingSortedCompoundSegmentsCollection.Lookup(currentLocation.node.finalCompoundSegment, curWireSeg, out compoundPathEquivalentSets)) 
                    { 
                        // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/p{var}th2")
                        // we should take only the highest order match! 
                        Fx.Assert(compoundPathEquivalentSets.Count >= 1, "Lookup is expected to return false otherwise");
                        Fx.Assert(compoundPathEquivalentSets[0].Count > 0, "Find shouldn't return empty sublists");
                        if (compoundPathEquivalentSets[0].Count == 1)
                        { 
                            success = compoundPathEquivalentSets[0][0];
                        } 
                        else 
                        {
                            success = new UriTemplatePathPartiallyEquivalentSet(currentLocation.node.depth + 1); 
                            for (int i = 0; i < compoundPathEquivalentSets[0].Count; i++)
                            {
                                success.Items.AddRange(compoundPathEquivalentSets[0][i].Items);
                            } 
                        }
                        return true; 
                    } 
                    else if (considerVariable && currentLocation.node.finalVariableSegment.Items.Count != 0)
                    { 
                        // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/{var}")
                        success = currentLocation.node.finalVariableSegment;
                        return true;
                    } 
                    else if (considerStar && currentLocation.node.star.Items.Count != 0)
                    { 
                        // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/*") 
                        success = currentLocation.node.star;
                        return true; 
                    }
                    else
                    {
                        nextStep = new SingleLocationOrLocationsSet(currentLocation.node.onFailure); 
                        return false;
                    } 
                } 
            }
        } 

        static UriTemplateTrieLocation GetFailureLocationFromLocationsSet(IList> locationsSet)
        {
            Fx.Assert(locationsSet != null, "Shouldn't be called on null set"); 
            Fx.Assert(locationsSet.Count > 0, "Shouldn't be called on empty set");
            Fx.Assert(locationsSet[0] != null, "Shouldn't be called on a set with null sub-lists"); 
            Fx.Assert(locationsSet[0].Count > 0, "Shouldn't be called on a set with empty sub-lists"); 

            return locationsSet[0][0].node.onFailure; 
        }

        static void Validate(UriTemplateTrieNode root, bool allowDuplicateEquivalentUriTemplates)
        { 
            // walk the entire tree, and ensure that each PathEquivalentSet is ok (no ambiguous queries),
            // verify thst compound segments didn't add potentialy multiple matchs; 
            // also Assert various data-structure invariants 
            Queue nodesQueue = new Queue();
 
            UriTemplateTrieNode current = root;
            while (true)
            {
                // validate all the PathEquivalentSets that live in this node 
                Validate(current.endOfPath, allowDuplicateEquivalentUriTemplates);
                Validate(current.finalVariableSegment, allowDuplicateEquivalentUriTemplates); 
                Validate(current.star, allowDuplicateEquivalentUriTemplates); 
                if (current.finalLiteralSegment != null)
                { 
                    foreach (KeyValuePair kvp in current.finalLiteralSegment)
                    {
                        Validate(kvp.Value, allowDuplicateEquivalentUriTemplates);
                    } 
                }
                if (current.finalCompoundSegment != null) 
                { 
                    IList> pesLists = current.finalCompoundSegment.Values;
                    for (int i = 0; i < pesLists.Count; i++) 
                    {
                        if (!allowDuplicateEquivalentUriTemplates && (pesLists[i].Count > 1))
                        {
                            throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR2.GetString( 
                                SR2.UTTDuplicate, pesLists[i][0].Items[0].Key.ToString(), pesLists[i][1].Items[0].Key.ToString())));
                        } 
                        for (int j = 0; j < pesLists[i].Count; j++) 
                        {
                            Validate(pesLists[i][j], allowDuplicateEquivalentUriTemplates); 
                        }
                    }
                }
                // deal with children of this node 
                if (current.nextLiteralSegment != null)
                { 
                    foreach (KeyValuePair kvp in current.nextLiteralSegment) 
                    {
                        Fx.Assert(kvp.Value.locationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-pointers should always point to a BeforeLiteral location"); 
                        Fx.Assert(kvp.Value.node.depth == current.depth + 1, "kvp.Value.node.depth == current.depth + 1");
                        Fx.Assert(kvp.Value.node.onFailure.node == current, "back pointer should point back to here");
                        Fx.Assert(kvp.Value.node.onFailure.locationWithin == UriTemplateTrieIntraNodeLocation.AfterLiteral, "back-pointer should be AfterLiteral");
                        nodesQueue.Enqueue(kvp.Value.node); 
                    }
                } 
                if (current.nextCompoundSegment != null) 
                {
                    IList> locations = current.nextCompoundSegment.Values; 
                    for (int i = 0; i < locations.Count; i++)
                    {
                        if (!allowDuplicateEquivalentUriTemplates && (locations[i].Count > 1))
                        { 
                            // In the future we might ease up the restrictions and verify if there is realy
                            // a potential multiple match here; for now we are throwing. 
                            UriTemplate firstTemplate = FindAnyUriTemplate(locations[i][0].node); 
                            UriTemplate secondTemplate = FindAnyUriTemplate(locations[i][1].node);
                            throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR2.GetString( 
                                SR2.UTTDuplicate, firstTemplate.ToString(), secondTemplate.ToString())));
                        }
                        for (int j = 0; j < locations[i].Count; j++)
                        { 
                            UriTemplateTrieLocation location = locations[i][j];
                            Fx.Assert(location.locationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-pointers should always point to a BeforeLiteral location"); 
                            Fx.Assert(location.node.depth == current.depth + 1, "kvp.Value.node.depth == current.depth + 1"); 
                            Fx.Assert(location.node.onFailure.node == current, "back pointer should point back to here");
                            Fx.Assert(location.node.onFailure.locationWithin == UriTemplateTrieIntraNodeLocation.AfterCompound, "back-pointer should be AfterCompound"); 
                            nodesQueue.Enqueue(location.node);
                        }
                    }
                } 
                if (current.nextVariableSegment != null)
                { 
                    Fx.Assert(current.nextVariableSegment.locationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-pointers should always point to a BeforeLiteral location"); 
                    Fx.Assert(current.nextVariableSegment.node.depth == current.depth + 1, "current.nextVariableSegment.node.depth == current.depth + 1");
                    Fx.Assert(current.nextVariableSegment.node.onFailure.node == current, "back pointer should point back to here"); 
                    Fx.Assert(current.nextVariableSegment.node.onFailure.locationWithin == UriTemplateTrieIntraNodeLocation.AfterVariable, "back-pointer should be AfterVariable");
                    nodesQueue.Enqueue(current.nextVariableSegment.node);
                }
                // move on to next bit of work 
                if (nodesQueue.Count == 0)
                { 
                    break; 
                }
                current = nodesQueue.Dequeue(); 
            }
        }
        static void Validate(UriTemplatePathPartiallyEquivalentSet pes, bool allowDuplicateEquivalentUriTemplates)
        { 
            // A set with 0 or 1 items is valid by definition
            if (pes.Items.Count < 2) 
            { 
                return;
            } 
            // Assert all paths are partially-equivalent
            for (int i = 0; i < pes.Items.Count - 1; ++i)
            {
                Fx.Assert(pes.Items[i].Key.IsPathPartiallyEquivalentAt(pes.Items[i + 1].Key, pes.SegmentsCount), 
                    "all elements of a PES must be path partially-equivalent");
            } 
            // We will check that the queries disambiguate only for templates, which are 
            //  matched completely at the segments count; templates, which are match at
            //  that point due to terminal defaults, will be ruled out. 
            UriTemplate[] a = new UriTemplate[pes.Items.Count];
            int arrayIndex = 0;
            foreach (KeyValuePair kvp in pes.Items)
            { 
                if (pes.SegmentsCount < kvp.Key.segments.Count)
                { 
                    continue; 
                }
                Fx.Assert(arrayIndex < a.Length, "We made enough room for all the items"); 
                a[arrayIndex++] = kvp.Key;
            }
            // Ensure that queries disambiguate (if needed) :
            if (arrayIndex > 0) 
            {
                UriTemplateHelpers.DisambiguateSamePath(a, 0, arrayIndex, allowDuplicateEquivalentUriTemplates); 
            } 
        }
 
        static UriTemplate FindAnyUriTemplate(UriTemplateTrieNode node)
        {
            while (node != null)
            { 
                if (node.endOfPath.Items.Count > 0)
                { 
                    return node.endOfPath.Items[0].Key; 
                }
                if (node.finalVariableSegment.Items.Count > 0) 
                {
                    return node.finalVariableSegment.Items[0].Key;
                }
                if (node.star.Items.Count > 0) 
                {
                    return node.star.Items[0].Key; 
                } 
                if (node.finalLiteralSegment != null)
                { 
                    UriTemplatePathPartiallyEquivalentSet pes =
                        GetAnyDictionaryValue(node.finalLiteralSegment);
                    Fx.Assert(pes.Items.Count > 0, "Otherwise, why creating the dictionary?");
                    return pes.Items[0].Key; 
                }
                if (node.finalCompoundSegment != null) 
                { 
                    UriTemplatePathPartiallyEquivalentSet pes = node.finalCompoundSegment.GetAnyValue();
                    Fx.Assert(pes.Items.Count > 0, "Otherwise, why creating the collection?"); 
                    return pes.Items[0].Key;
                }

                if (node.nextLiteralSegment != null) 
                {
                    UriTemplateTrieLocation location = 
                        GetAnyDictionaryValue(node.nextLiteralSegment); 
                    node = location.node;
                } 
                else if (node.nextCompoundSegment != null)
                {
                    UriTemplateTrieLocation location = node.nextCompoundSegment.GetAnyValue();
                    node = location.node; 
                }
                else if (node.nextVariableSegment != null) 
                { 
                    node = node.nextVariableSegment.node;
                } 
                else
                {
                    node = null;
                } 
            }
            Fx.Assert("How did we got here without finding a UriTemplate earlier?"); 
            return null; 
        }
        static T GetAnyDictionaryValue(IDictionary dictionary) 
        {
            using (IEnumerator valuesEnumerator = dictionary.Values.GetEnumerator())
            {
                valuesEnumerator.MoveNext(); 
                return valuesEnumerator.Current;
            } 
        } 

        void AddFinalCompoundSegment(UriTemplateCompoundPathSegment cps, KeyValuePair kvp) 
        {
            Fx.Assert(cps != null, "must be - based on the segment nature");
            if (this.finalCompoundSegment == null)
            { 
                this.finalCompoundSegment = new AscendingSortedCompoundSegmentsCollection();
            } 
            UriTemplatePathPartiallyEquivalentSet pes = this.finalCompoundSegment.Find(cps); 
            if (pes == null)
            { 
                pes = new UriTemplatePathPartiallyEquivalentSet(this.depth + 1);
                this.finalCompoundSegment.Add(cps, pes);
            }
            pes.Items.Add(kvp); 
        }
        void AddFinalLiteralSegment(UriTemplateLiteralPathSegment lps, KeyValuePair kvp) 
        { 
            Fx.Assert(lps != null, "must be - based on the segment nature");
            if (this.finalLiteralSegment != null && this.finalLiteralSegment.ContainsKey(lps)) 
            {
                this.finalLiteralSegment[lps].Items.Add(kvp);
            }
            else 
            {
                if (this.finalLiteralSegment == null) 
                { 
                    this.finalLiteralSegment = new Dictionary();
                } 
                UriTemplatePathPartiallyEquivalentSet pes = new UriTemplatePathPartiallyEquivalentSet(this.depth + 1);
                pes.Items.Add(kvp);
                this.finalLiteralSegment.Add(lps, pes);
            } 
        }
        UriTemplateTrieNode AddNextCompoundSegment(UriTemplateCompoundPathSegment cps) 
        { 
            Fx.Assert(cps != null, "must be - based on the segment nature");
            if (this.nextCompoundSegment == null) 
            {
                this.nextCompoundSegment = new AscendingSortedCompoundSegmentsCollection();
            }
            UriTemplateTrieLocation nextLocation = this.nextCompoundSegment.Find(cps); 
            if (nextLocation == null)
            { 
                UriTemplateTrieNode nextNode = new UriTemplateTrieNode(this.depth + 1); 
                nextNode.onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterCompound);
                nextLocation = new UriTemplateTrieLocation(nextNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral); 
                this.nextCompoundSegment.Add(cps, nextLocation);
            }
            return nextLocation.node;
        } 
        UriTemplateTrieNode AddNextLiteralSegment(UriTemplateLiteralPathSegment lps)
        { 
            Fx.Assert(lps != null, "must be - based on the segment nature"); 
            if (this.nextLiteralSegment != null && this.nextLiteralSegment.ContainsKey(lps))
            { 
                return this.nextLiteralSegment[lps].node;
            }
            else
            { 
                if (this.nextLiteralSegment == null)
                { 
                    this.nextLiteralSegment = new Dictionary(); 
                }
                UriTemplateTrieNode newNode = new UriTemplateTrieNode(this.depth + 1); 
                newNode.onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterLiteral);
                this.nextLiteralSegment.Add(lps, new UriTemplateTrieLocation(newNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral));
                return newNode;
            } 
        }
        UriTemplateTrieNode AddNextVariableSegment() 
        { 
            if (this.nextVariableSegment != null)
            { 
                return this.nextVariableSegment.node;
            }
            else
            { 
                UriTemplateTrieNode newNode = new UriTemplateTrieNode(this.depth + 1);
                newNode.onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterVariable); 
                this.nextVariableSegment = new UriTemplateTrieLocation(newNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral); 
                return newNode;
            } 
        }

        struct SingleLocationOrLocationsSet
        { 
            readonly bool isSingle;
            readonly IList> locationsSet; 
            readonly UriTemplateTrieLocation singleLocation; 

            public SingleLocationOrLocationsSet(UriTemplateTrieLocation singleLocation) 
            {
                this.isSingle = true;
                this.singleLocation = singleLocation;
                this.locationsSet = null; 
            }
            public SingleLocationOrLocationsSet(IList> locationsSet) 
            { 
                this.isSingle = false;
                this.singleLocation = null; 
                this.locationsSet = locationsSet;
            }

            public bool IsSingle 
            {
                get 
                { 
                    return this.isSingle;
                } 
            }
            public IList> LocationsSet
            {
                get 
                {
                    Fx.Assert(!this.isSingle, "!this.isSingle"); 
                    return this.locationsSet; 
                }
            } 
            public UriTemplateTrieLocation SingleLocation
            {
                get
                { 
                    Fx.Assert(this.isSingle, "this.isSingle");
                    return this.singleLocation; 
                } 
            }
        } 

        class AscendingSortedCompoundSegmentsCollection
            where T : class
        { 
            SortedList> items;
 
            public AscendingSortedCompoundSegmentsCollection() 
            {
                this.items = new SortedList.CollectionItem>>(); 
            }

            public IList> Values
            { 
                get
                { 
                    IList> results = new List>(this.items.Count); 
                    for (int i = 0; i < this.items.Values.Count; i++)
                    { 
                        results.Add(new List(this.items.Values[i].Count));
                        Fx.Assert(results.Count == i + 1, "We are adding item for each values collection");
                        for (int j = 0; j < this.items.Values[i].Count; j++)
                        { 
                            results[i].Add(this.items.Values[i][j].Value);
                            Fx.Assert(results[i].Count == j + 1, "We are adding item for each value in the collection"); 
                        } 
                        Fx.Assert(results[i].Count == this.items.Values[i].Count, "We were supposed to add an item for each value in the collection");
                    } 
                    Fx.Assert(results.Count == this.items.Values.Count, "We were supposed to add a sub-list for each values collection");
                    return results;
                }
            } 

            public void Add(UriTemplateCompoundPathSegment segment, T value) 
            { 
                int index = this.items.IndexOfKey(segment);
                if(index == -1) 
                {
                    Collection subItems = new Collection();
                    subItems.Add(new CollectionItem(segment, value));
                    this.items.Add(segment, subItems); 
                }
                else 
                { 
                    Collection subItems = this.items.Values[index];
                    subItems.Add(new CollectionItem(segment, value)); 
                }
            }

            public T Find(UriTemplateCompoundPathSegment segment) 
            {
                int index = this.items.IndexOfKey(segment); 
                if(index == -1) 
                {
                    return null; 
                }
                Collection subItems = this.items.Values[index];
                for(int i = 0; i < subItems.Count; i++)
                { 
                    if(subItems[i].Segment.IsEquivalentTo(segment, false))
                    { 
                        return subItems[i].Value; 
                    }
                } 
                return null;
            }
            public IList> Find(UriTemplateLiteralPathSegment wireData)
            { 
                IList> results = new List>();
                for (int i = 0; i < this.items.Values.Count; i++) 
                { 
                    List sameOrderResults = null;
                    for (int j = 0; j < this.items.Values[i].Count; j++) 
                    {
                        if (this.items.Values[i][j].Segment.IsMatch(wireData))
                        {
                            if (sameOrderResults == null) 
                            {
                                sameOrderResults = new List(); 
                            } 
                            sameOrderResults.Add(this.items.Values[i][j].Value);
                        } 
                    }
                    if (sameOrderResults != null)
                    {
                        results.Add(sameOrderResults); 
                    }
                } 
                return results; 
            }
 
            public T GetAnyValue()
            {
                if (this.items.Values.Count > 0)
                { 
                    Fx.Assert(this.items.Values[0].Count > 0, "We are not adding a sub-list unless there is at list one item");
                    return this.items.Values[0][0].Value; 
                } 
                else
                { 
                    return null;
                }
            }
 
            public static bool Lookup(AscendingSortedCompoundSegmentsCollection collection,
                UriTemplateLiteralPathSegment wireData, out IList> results) 
            { 
                results = collection.Find(wireData);
                return ((results != null) && (results.Count > 0)); 
            }

            struct CollectionItem
            { 
                UriTemplateCompoundPathSegment segment;
                T value; 
 
                public CollectionItem(UriTemplateCompoundPathSegment segment, T value)
                { 
                    this.segment = segment;
                    this.value = value;
                }
 
                public UriTemplateCompoundPathSegment Segment
                { 
                    get 
                    {
                        return this.segment; 
                    }
                }
                public T Value
                { 
                    get
                    { 
                        return this.value; 
                    }
                } 
            }
        }
    }
} 

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