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

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

    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<UriTemplatePathPartiallyEquivalentSet> finalCompoundSegment; // matches e.g. "{var}.{var}"
        Dictionary<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet> finalLiteralSegment; // matches e.g. "segmentThatDoesntEndInSlash"
        UriTemplatePathPartiallyEquivalentSet finalVariableSegment; // matches e.g. "{var}"
        AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation> nextCompoundSegment; // all are AfterLiteral; matches e.g. "{var}.{var}/"
        Dictionary<UriTemplateLiteralPathSegment, UriTemplateTrieLocation> 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<KeyValuePair<UriTemplate, object>> keyValuePairs,
            bool allowDuplicateEquivalentUriTemplates)
        {
            // given a UTT at MakeReadOnly time, build the trie
            // note that root.onFailure == null;
            UriTemplateTrieNode root = new UriTemplateTrieNode(0);
            foreach (KeyValuePair<UriTemplate, object> kvp in keyValuePairs)
            {
                Add(root, kvp);
            }
            Validate(root, allowDuplicateEquivalentUriTemplates);
            return root;
        }

        public bool Match(UriTemplateLiteralPathSegment[] wireData, ICollection<UriTemplateTableMatchCandidate> candidates)
        {
            UriTemplateTrieLocation currentLocation = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.BeforeLiteral);
            return GetMatch(currentLocation, wireData, candidates);
        }

        static void Add(UriTemplateTrieNode root, KeyValuePair<UriTemplate, object> 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<IList<UriTemplateTrieLocation>> locationsSet, UriTemplateLiteralPathSegment[] wireData,
            ICollection<UriTemplateTableMatchCandidate> 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<UriTemplateTableMatchCandidate> 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<IList<UriTemplateTrieLocation>> 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<UriTemplateTrieLocation>.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<IList<UriTemplatePathPartiallyEquivalentSet>> 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<UriTemplatePathPartiallyEquivalentSet>.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<IList<UriTemplateTrieLocation>> 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<UriTemplateTrieNode> nodesQueue = new Queue<UriTemplateTrieNode>();

            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<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet> kvp in current.finalLiteralSegment)
                    {
                        Validate(kvp.Value, allowDuplicateEquivalentUriTemplates);
                    }
                }
                if (current.finalCompoundSegment != null)
                {
                    IList<IList<UriTemplatePathPartiallyEquivalentSet>> pesLists = current.finalCompoundSegment.Values;
                    for (int i = 0; i < pesLists.Count; i++)
                    {
                        if (!allowDuplicateEquivalentUriTemplates && (pesLists[i].Count > 1))
                        {
                            throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
                                SR.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<UriTemplateLiteralPathSegment, UriTemplateTrieLocation> 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<IList<UriTemplateTrieLocation>> 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(SR.GetString(
                                SR.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<UriTemplate, object> 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<UriTemplatePathPartiallyEquivalentSet>(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<UriTemplateTrieLocation>(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<T>(IDictionary<UriTemplateLiteralPathSegment, T> dictionary)
        {
            using (IEnumerator<T> valuesEnumerator = dictionary.Values.GetEnumerator())
            {
                valuesEnumerator.MoveNext();
                return valuesEnumerator.Current;
            }
        }

        void AddFinalCompoundSegment(UriTemplateCompoundPathSegment cps, KeyValuePair<UriTemplate, object> kvp)
        {
            Fx.Assert(cps != null, "must be - based on the segment nature");
            if (this.finalCompoundSegment == null)
            {
                this.finalCompoundSegment = new AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalentSet>();
            }
            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<UriTemplate, object> 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<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet>();
                }
                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>();
            }
            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<UriTemplateLiteralPathSegment, UriTemplateTrieLocation>();
                }
                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<IList<UriTemplateTrieLocation>> locationsSet;
            readonly UriTemplateTrieLocation singleLocation;

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

            public bool IsSingle
            {
                get
                {
                    return this.isSingle;
                }
            }
            public IList<IList<UriTemplateTrieLocation>> 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<T>
            where T : class
        {
            SortedList<UriTemplateCompoundPathSegment, Collection<CollectionItem>> items;

            public AscendingSortedCompoundSegmentsCollection()
            {
                this.items = new SortedList<UriTemplateCompoundPathSegment, Collection<AscendingSortedCompoundSegmentsCollection<T>.CollectionItem>>();
            }

            public IList<IList<T>> Values
            {
                get
                {
                    IList<IList<T>> results = new List<IList<T>>(this.items.Count);
                    for (int i = 0; i < this.items.Values.Count; i++)
                    {
                        results.Add(new List<T>(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<CollectionItem> subItems = new Collection<CollectionItem>();
                    subItems.Add(new CollectionItem(segment, value));
                    this.items.Add(segment, subItems);
                }
                else
                {
                    Collection<CollectionItem> 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<CollectionItem> 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<IList<T>> Find(UriTemplateLiteralPathSegment wireData)
            {
                IList<IList<T>> results = new List<IList<T>>();
                for (int i = 0; i < this.items.Values.Count; i++)
                {
                    List<T> 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<T>();
                            }
                            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<T> collection,
                UriTemplateLiteralPathSegment wireData, out IList<IList<T>> 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;
                    }
                }
            }
        }
    }
}