#738 Router with a Segment Trie

A router with thousands of routes can't test every pattern on each navigation. Store patterns in a trie of segments and search it instead.

Implement Router: add(pattern) registers a pattern. match(path) returns { pattern, params } for the most specific matching pattern, or null. Matching uses the usual rules (segments split on / with empty pieces ignored; plain segments must be equal; :name matches one segment and captures it, decoded with decodeURIComponent; a final * matches the rest, even nothing, captured joined by / under "*").

Most specific means: compare candidates segment by segment from the left; at the first position where their kinds differ, plain beats :param beats *, and a pattern that has ended beats one with a * there. If two patterns have the same kinds everywhere, the one added first wins.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new Router(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Input: ["Router","add","add","add","match","match","match"]
[[],["/users/:id"],["/users/new"],["/*"],["/users/new"],["/users/9"],["/about/team"]]
Output: [null,null,null,null,{"pattern":"/users/new","params":{}},{"pattern":"/users/:id","params":{"id":"9"}},{"pattern":"/*","params":{"*":"about/team"}}]

Constraints

• Up to 10^4 calls; patterns and paths are up to 200 characters.
• * only appears as the last segment of a pattern.