router,path matching with trie WIP

router.ts

///<reference path="optional.ts"/>
/*
 Path template:
 getSegments() PathSegment[]
 getTrailingSegment() TrailingSegment
 parse(path): {[paramName: string]: string}
 generate({[paramName: string]: string}): string

 Path template set:
 matches(path): string
 getTemplate(pathName: string): PathTemplate
 findAmbiguous(): AmbiguousPathTemplates

 AmbiguousPathTemplates:
 template1
 template2
 ambiguousPath

 /some/path/:id:number/test
 /some/other/:id/pepe
 /some/another/:name:string/test
 /some/withRegex/:id:[0-8]{4}/
 * */
module Paths {

    import checkArgument = Preconditions.checkArgument;
    import StringMap = Collections.StringMap;
    import ArrayIterator = Collections.ArrayIterator;
    import IllegalStateException = Preconditions.IllegalStateException;
    import Iterator = Collections.Iterator;
    export type Path = Array<string>

    export type ParameterValues = {[name: string]:string};

    enum MatcherKind {
        LITERAL, WILDCARD
    }
    class SegmentTemplate {
        constructor(public kind:MatcherKind, public literal:string, public name:string) {
        }

        matches(segment:string) {
            switch (this.kind) {
                case MatcherKind.LITERAL:
                    return (this.name === segment);
                case MatcherKind.WILDCARD:
                    return true;
            }
        }
    }

    export class PathPattern {

        constructor(private segmentTemplates:SegmentTemplate[]) {
        }

        getSegments():SegmentTemplate[] {
            return this.segmentTemplates.slice();
        }

        static fromTemplate(template:string):PathPattern {
            var segments = pathToSegments(template);
            var matchers:SegmentTemplate[] = [];
            segments.forEach((segment) => {
                if (segment.length > 0 && segment[0] === ':') {
                    matchers.push(new SegmentTemplate(MatcherKind.WILDCARD, null, segment.slice(1)));
                } else {
                    matchers.push(new SegmentTemplate(MatcherKind.WILDCARD, segment, null));
                }
            });
            return new PathPattern(matchers);
        }

        matchesPath(path:Path):boolean {
            if (path.length != this.segmentTemplates.length) {
                return false;
            }
            for (var i = 0; i < this.segmentTemplates.length; i++) {
                if (!this.segmentTemplates[i].matches(path[i])) {
                    return false;
                }
            }
            return true;
        }

        matchesSegment(segment:string, position:number):boolean {
            checkArgument(position < this.segmentTemplates.length);
            return this.segmentTemplates[position].matches(segment);
        }

        parse(path:Path):{[name: string]:string} {
            var parameterValues:{[name: string]:string} = {};
            checkArgument(this.matchesPath(path));
            for (var i = 0; i < path.length; i++) {
                var template = this.segmentTemplates[i];
                if (template.kind === MatcherKind.WILDCARD) {
                    parameterValues[template.name] = path[i];
                }
            }
            return parameterValues;
        }

        generate(parameters:{[name: string]:string}):Path {
            var path:Path = [];
            for (let template of this.segmentTemplates) {
                switch (template.kind) {
                    case MatcherKind.LITERAL:
                        path.push(template.literal);
                        break;
                    case MatcherKind.WILDCARD:
                        path.push(checkNotNull(parameters[template.name]));
                        break;
                }
            }
            return path;
        }

    }
    export class Named<T> {
        constructor(public name:string, public pattern:T) {
            checkNotNull(name);
            checkNotNull(pattern);
        }
    }

    export class PathPatternTrie {
        public literalBranches:StringMap<PathPatternTrie>;
        public wildcardBranch:Optional<PathPatternTrie>;
        public leaf:Optional<Named<PathPattern>>;

        constructor() {
            this.literalBranches = new StringMap<PathPatternTrie>();
            this.wildcardBranch = Optional.absent<PathPatternTrie>();
            this.leaf = Optional.absent<Named<PathPattern>>();
        }

        register(namedPathPattern:Named<PathPattern>):void {
            checkNotNull(namedPathPattern);
            var segments = new ArrayIterator<SegmentTemplate>(namedPathPattern.pattern.getSegments());
            this.registerWalk(namedPathPattern, segments);
        }

        private registerWalk(namedPattern:Named<PathPattern>, segments:ArrayIterator<SegmentTemplate>):void {
            if (segments.hasNext()) {
                var segment = segments.next();
                switch (segment.kind) {
                    case MatcherKind.LITERAL:
                        var follow = this.literalBranches.casProvider(segment.literal, () => new PathPatternTrie());
                        return follow.registerWalk(namedPattern, segments);
                    case MatcherKind.WILDCARD:
                        this.wildcardBranch = this.wildcardBranch.orProvider(() => new PathPatternTrie);
                        return this.wildcardBranch.get().registerWalk(namedPattern, segments);
                    default:
                        throw new IllegalStateException();
                }
            } else if (this.leaf.isPresent()) {
                throw new RouteConflict(namedPattern, this.leaf.get());
            } else {
                this.leaf = Optional.of(namedPattern);
            }
        }

        match(path:Path):Optional<Named<PathPattern>> {
            checkNotNull(path);
            var segments = new ArrayIterator<string>(path);
            return this.matchWalk(segments);
        }

        private matchWalk(segments:ArrayIterator<string>):Optional<Named<PathPattern>> {
            if (segments.hasNext()) {
                var segment = segments.next();
                //first try literals
                //then try wildcard;
                //
            } else {
                return this.leaf;
            }
        }

    }
    class RouteConflict extends Error {
        constructor(private route1:Named<PathPattern>, private route2:Named<PathPattern>) {
            super();
        }

        toString():string {
            return 'Route conflict between \n' + this.route1.toString() + '\n' + this.route2.toString();
        }
    }
    
    /** return a path without leading or trailing slashes */
    function stripPath(path:string):string {
        return path.replace(/^\/+|\/+$/g, '');
    }

    /* return an array of path segments. Expects a path without leading and trailing slashes */
    function splitPath(path:string):string[] {
        return path.split(/\/+/);
    }

    function pathToSegments(path:string):string[] {
        var stripped = stripPath(path);
        return splitPath(stripped);

    }
}