# routes #

Routes are stored using a radix tree. This doc should help explain
what's going on in radixtree.go.

A radix tree is a data structure which facilitates efficient lookups
of values which are indexed by strings. In our case, we're trying to
look up the name of a URI path, so the values are names and the lookup
keys are paths.

Radix trees work by by storing string prefixes that lead to their
children. It's easiest to explain this with an example. If we want to
store, say, what part of speech (verb, noun, adjective, etc) some
words are, we could do it with a radix tree like this:

```
input
  hang: verb
  hanger: noun
  hinge: noun
  house: noun
  hollow: adjective
  holler: verb
```
  
radix tree:

```
h
  ang - verb
    er - noun
  inge - noun
  o
    use - noun
    ll
      ow - adjective
      er - verb
      ```
      
To look up a value, like "hollow", you traverse the tree starting
at the root and matching characters. Here's an example lookup:


"hollow" starts with "h", so we enter at the root. We examine each
of the children of h, finding which one shares the most leading
characters with the remainder of hollow, which is "ollow":

  - ang vs ollow: 0 chars
  - inge vs ollow: 0 chars
  - o vs ollow: 1 char

o is the winner, so we move into o, and repeat the process with "llow":
  - use vs llow: 0 chars
  - ll vs llow: 2 chars

ll wins. Finally, we compare against "ow":
  - ow vs ow: 2 chars
  - er vs ow: 0 chars
ow wins, and there are no characters remaining, so we are done. We inspect
the value stored at this final node - it is 'adjective', so we return that.


## Wildcards ##

In the particular implementation of a tree for routes, the radix tree
has an added wrinkle: it supports wildcards. We're matching URL paths,
which often include data segments, so some data in the tree can match
anything:


input:
```
  /api/channel/*/info.json: #channel-info
  /api/chat/moderator:      #chat-mod
  /api/kraken/viewer.json:  #kraken-viewer
  /api/kraken/chat.json:    #kraken-chat
  /admin/edit/*.*:          #active-admin-edit-with-format
  /admin/edit/*:            #active-admin-edit
  /*:                       #404
```
  
tree:
  ```
  /
    * - #404
    api/
      ch
        annel/
          *
            /info.json - #channel-info
        at/moderator - #chat-mod
      kraken/
        viewer.json - #kraken-viewer
        chat.json   - #kraken-chat
    admin/edit/
      *
        .
          * - #active-admin-edit

```

### Lookups with wildcards ###

Wildcards make traversal much more complex because multiple paths
might match. Imagine, for example, /channel/* and /*/* both being
paths. /channel/foo would match both of those. So, we explore every
candidate path, and then need to return the path which matches "best."
In this implementation, the "best" match is simply the one that was
added to the tree first - that's done with the `prio` struct attribute
on `node`. Higher prio values are considered better matches.


Additionally, there's some trickiness in how to compute the "remaining
string" after passing through a wildcard. With simple prefixes, it was
easy - you just chop of len(prefix) characters from the front of the
input string. But with the wilcards, it's not obvious how many
characters you should remove from the front. Instead, you have to test
every child of the wildcard, finding the index of the subchild's
prefix in the entire remaining string. If the subchild's prefix is
present, then its a candidate, so you have to try traversing down it
to find any matches.


