## Ex. Implementing Dynamic Routing

<!-- Learn how to enhance the TrieRouter class to support dynamic routing and handle variable URL paths effectively with Node.js. Also, understand the significance of dynamic routing in building flexible and scalable server applications. -->

When we're building a server application, dynamic routing is an essential feature for creating flexible and scalable applications. To fully grasp its significance and how we can enhance our router to support dynamic routes like `/users/:id`, let's delve into the concept of dynamic routing.

### Why Dynamic Routing?

At its core, dynamic routing refers to the ability of a web application (not just server) to handle requests to URLs that are not predetermined but rather, are defined by patterns. It allows developers to create routes that can match a range of URL structures, often using parameters. For instance, a URL like `/users/:user_id` can handle requests for any user ID, where `:user_id` is a variable part of the URL.

#### Flexibility

Dynamic routing introduces a level of flexibility that static routing cannot match. As applications grow and become more complex, new routes often need to be added. With dynamic routing, you can handle a vast number of routes with just a few route patterns, making the application more scalable and easier to maintain. For example, imagine having to define a route for every kind of asset your website serves.

You may do something like this

```js
// images
app.get("/static/imgs/img1.png", img_handler);
app.get("/static/imgs/img2.png", img_handler);
app.get("/static/imgs/img3.png", img_handler);
app.get("/static/imgs/img4.png", img_handler);

// javascript
app.get("/static/js/main.js", script_handler);
app.get("/static/js/third_party.js", script_handler);

/** And so on**/
```

This is quite tedious, and you cannot expect an application like this to scale. What if we had a dynamic route to serve all the assets?

```js
app.get("/static/img/:image_file_name", img_handler);
app.get("/static/js/:javascript_file_name", img_handler);
```

This is somewhat better than the previous.

> However, this is still not the best way to handle assets. You may have subdirectories - i.e `/img/compressed/webps/img.webp`. You will get a route not found while doing the method above. To solve this issue, we have a concept of wildcards. You don't need to worry about wildcards just yet. We'll cover them in an upcoming challenge.

#### Better User Experience

Dynamic routes allow for creating more personalized user experiences. For example, in a blog application, a dynamic route like `/posts/:postId` can display a specific post based on the ID in the URL. This approach makes it straightforward to link to specific content, improving the navigability and user engagement.

#### Better Developer Experience

By using dynamic routes, developers of our framework can avoid the tedium of defining every possible URL path in their application. This not only saves time but also reduces the risk of errors. A single dynamic route can replace dozens, if not hundreds, of static routes, streamlining the development process.

#### Better SEO

Dynamic routing can also contribute to better Search Engine Optimization (SEO). With the ability to generate clean and meaningful URLs (e.g., `/game/dota2` instead of `/game?uid=dota2`), dynamic routes make URLs more understandable to both users and search engines, potentially improving search rankings.

### Anatomy of a dynamic route

A dynamic route follows a structure where certain parts of the URL path are variable, known as dynamic segments.

```bash
/[Static Path Segment]/[Dynamic Segment]/[More Static or Dynamic Segments]
```

Example URL: https://github.com/:user_id/repos

1. Static Path Segment: 'repos'

   - A fixed part of the URL path that doesn't change.

2. Dynamic Segment: `:user_id`

   - A variable part of the URL. The `user_id` can be any value, representing a specific user.

### Challenge: Enhance the `TrieRouter` Class to Support Dynamic Routing

In this challenge, we will modify the existing `TrieRouter` class to support dynamic routing. Dynamic routes are identified by segments of the URL that begin with a colon (`:`), allowing for variable parameters in the route paths. This enhancement will enable the router to extract these dynamic parameters and make them accessible to the corresponding route handler.

#### Requirements

1. **Dynamic Route Identification**: Modify the `#addRoute` method to recognize dynamic route segments (e.g., `/users/:userId`) and store them appropriately within the `RouteNode`.

2. **Parameter Extraction**: Update the `findRoute` method to extract dynamic parameters from the URL path and return them alongside the route handler.

3. **Data Structure Update**: Enhance the `RouteNode` class to include a property for storing dynamic parameter names.

4. **Error Handling**: Ensure that the router continues to validate paths and handlers, throwing appropriate errors for malformed paths or invalid HTTP methods.

#### More Details

1. **Dynamic Parameter Storage**: In the `RouteNode` class, add a `params` property to store the names of dynamic parameters for each route.

2. **Route Addition Logic**: In the `#addRoute` method, check if a segment starts with a colon (`:`). If it does, treat it as a dynamic parameter and store its name in the `params` array of the current node.

3. **Route Finding Logic**: In the `findRoute` method, when a dynamic segment is encountered, extract the corresponding value from the URL and store it somewhere for later use.

4. **Example**:
   - Input: `"/users/:userId"`
   - Output: When the path `"/users/123"` is requested, the router should return `{ params: { userId: '123' }, handler: <handler_function> }`.

#### Solution

Here’s the updated implementation of the `TrieRouter` class with dynamic routing capabilities:

```js
const HTTP_METHODS = {
  GET: "GET",
  POST: "POST",
  PUT: "PUT",
  DELETE: "DELETE",
  PATCH: "PATCH",
  HEAD: "HEAD",
  OPTIONS: "OPTIONS",
  CONNECT: "CONNECT",
  TRACE: "TRACE",
};

class RouteNode {
  constructor() {
    this.children = new Map();
    this.handler = new Map();
    this.params = [];
  }
}

class TrieRouter {
  constructor() {
    this.root = new RouteNode();
  }

  #verifyParams(path, method, handler) {
    if (typeof path !== "string" || path[0] !== "/") throw new Error("Malformed path provided.");
    if (typeof handler !== "function") throw new Error("Handler should be a function");
    if (!HTTP_METHODS[method]) throw new Error("Invalid HTTP Method");
  }

  #addRoute(path, method, handler) {
    this.#verifyParams(path, method, handler);

    let currentNode = this.root;
    let routeParts = path.split("/").filter(Boolean);
    let dynamicParams = [];

    for (const segment of routeParts) {
      if (segment.includes(" ")) throw new Error("Malformed `path` parameter");

      const isDynamic = segment[0] === ":";
      const key = isDynamic ? ":" : segment.toLowerCase();

      if (isDynamic) {
        dynamicParams.push(segment.substring(1));
      }

      if (!currentNode.children.has(key)) {
        currentNode.children.set(key, new RouteNode());
      }

      currentNode = currentNode.children.get(key);
    }

    currentNode.handler.set(method, handler);
    currentNode.params = dynamicParams;
  }

  findRoute(path, method) {
    let segments = path.split("/").filter(Boolean);
    let currentNode = this.root;
    let extractedParams = [];

    for (let idx = 0; idx < segments.length; idx++) {
      const segment = segments[idx];

      let childNode = currentNode.children.get(segment.toLowerCase());
      if (childNode) {
        currentNode = childNode;
      } else if ((childNode = currentNode.children.get(":"))) {
        extractedParams.push(segment);
        currentNode = childNode;
      } else {
        return null;
      }
    }

    let params = Object.create(null);

    for (let idx = 0; idx < extractedParams.length; idx++) {
      let key = currentNode.params[idx];
      let value = extractedParams[idx];

      params[key] = value;
    }

    return {
      params,
      handler: currentNode.handler.get(method),
    };
  }

  get(path, handler) {
    this.#addRoute(path, HTTP_METHODS.GET, handler);
  }

  post(path, handler) {
    this.#addRoute(path, HTTP_METHODS.POST, handler);
  }

  put(path, handler) {
    this.#addRoute(path, HTTP_METHODS.PUT, handler);
  }

  delete(path, handler) {
    this.#addRoute(path, HTTP_METHODS.DELETE, handler);
  }

  patch(path, handler) {
    this.#addRoute(path, HTTP_METHODS.PATCH, handler);
  }

  head(path, handler) {
    this.#addRoute(path, HTTP_METHODS.HEAD, handler);
  }

  options(path, handler) {
    this.#addRoute(path, HTTP_METHODS.OPTIONS, handler);
  }

  connect(path, handler) {
    this.#addRoute(path, HTTP_METHODS.CONNECT, handler);
  }

  trace(path, handler) {
    this.#addRoute(path, HTTP_METHODS.TRACE, handler);
  }

  printTree(node = this.root, indentation = 0) {
    const indent = "-".repeat(indentation);

    node.children.forEach((childNode, segment) => {
      console.log(`${indent}(${segment}) Dynamic: ${childNode.params}`);
      this.printTree(childNode, indentation + 1);
    });
  }
}
```

Let's go through the updated code and understand the changes made to support dynamic routing in the `TrieRouter`.

#### Explanation

```js
class RouteNode {
  constructor() {
    this.children = new Map();
    this.handler = new Map();

    // Initialize an array to store dynamic parameter names
    this.params = [];
  }
}
```

In the `RouteNode` class, we added a `params` array to store the names of dynamic parameters. This allows us to keep track of which segments of the route are dynamic (e.g., `:userId`) and helps in extracting their values when a matching route is found.

> Note, we're going to store the `params` on the leaf node of the route. This is because the dynamic parameters are only relevant when we reach the end of the route.

```js
class TrieRouter {
  constructor() {
    // Create a root node upon TrieRouter instantiation
    this.root = new RouteNode();
  }
}
```

The `TrieRouter` constructor remains unchanged, still initializing a `root` node that serves as the entry point for route management.

```js
#verifyParams(path, method, handler) {
  if (typeof path !== "string" || path[0] !== "/") throw new Error("Malformed path provided.");
  if (typeof handler !== "function") throw new Error("Handler should be a function");
  if (!HTTP_METHODS[method]) throw new Error("Invalid HTTP Method");
}
```

We introduced a new private method `#verifyParams` to validate the parameters passed to the `addRoute` method. This method checks that the `path` is a valid string starting with a slash, that the `handler` is a function, and that the `method` is a valid HTTP method. This way we separate the validation logic from the main route handling logic.

```js
#addRoute(path, method, handler) {
  this.#verifyParams(path, method, handler);

  let currentNode = this.root;
  let routeParts = path.split("/").filter(Boolean);
  let dynamicParams = [];
}
```

In the `#addRoute` method, we call `#verifyParams` to validate the inputs. We also initialize an array `dynamicParams` to keep track of any dynamic segments in the route.

```js
for (const segment of routeParts) {
  if (segment.includes(" ")) throw new Error("Malformed `path` parameter");

  const isDynamic = segment[0] === ":";
  const key = isDynamic ? ":" : segment.toLowerCase();

  if (isDynamic) {
    dynamicParams.push(segment.substring(1));
  }
```

As we iterate through each segment of the route, we check if it is dynamic by looking for a leading colon (`:`). If it is dynamic, we store the parameter name (without the colon) in the `dynamicParams` array. We also determine the key to use in the `children` Map: if it's dynamic, we use `":"` as the key; otherwise, we convert the segment to lowercase.

```js
if (!currentNode.children.has(key)) {
  currentNode.children.set(key, new RouteNode());
}
```

If a child node for the current segment does not exist, we create a new `RouteNode` and add it to the `children` Map of the current node.

```js
currentNode.handler.set(method, handler);
currentNode.params = dynamicParams;
```

After processing all segments, we set the handler for the route in the `handler` Map and store the dynamic parameters in the `params` array of the current node.

```js
findRoute(path, method) {
  let segments = path.split("/").filter(Boolean);
  let currentNode = this.root;
  let extractedParams = [];

  ...
}
```

In the `findRoute` method, we initialize an array `extractedParams` to store values for any dynamic parameters. Note that we store the "keys" of the dynamic parameter in the `addRoute` method and the "values" in the `findRoute` method.

```js
for (let idx = 0; idx < segments.length; idx++) {
  const segment = segments[idx];

  let childNode = currentNode.children.get(segment.toLowerCase());
  if (childNode) {
    currentNode = childNode;
  } else if ((childNode = currentNode.children.get(":"))) {
    extractedParams.push(segment);
    currentNode = childNode;
  } else {
    return null;
  }
}
```

As we iterate through the segments, we first check for a direct match in the `children` Map. If no match is found, we check for a dynamic route (using the `":"` key). If we find a dynamic route, we push the current segment's value into `extractedParams`.

Note the syntax `(childNode = currentNode.children.get(":"))`. This is a common pattern in JavaScript to both check if a value is truthy and assign it to a variable in a single line. So,

```js
let x = obj.get("key");
if (x) {
  // do something with x
}
```

can be written as

```js
if ((x = obj.get("key"))) {
  // do something with x
}
```

Now, moving on to extracting the dynamic parameters:

```js
let params = Object.create(null);

for (let idx = 0; idx < extractedParams.length; idx++) {
  let key = currentNode.params[idx];
  let value = extractedParams[idx];

  params[key] = value;
}
```

After traversing the route, we create an object `params` to store the extracted dynamic parameters. We loop through `extractedParams` and map each value to its corresponding key from `currentNode.params`.

```js
return {
  params,
  handler: currentNode.handler.get(method),
};
```

Finally, we return an object containing the extracted parameters and the corresponding handler for the route.

#### Testing the implementation

I've also updated the `printTree` method to include dynamic parameters in the output. You can use this method to visualize the trie structure and verify that dynamic routes are correctly stored.

```js
const trieRouter = new TrieRouter();
trieRouter.get("/users/:id/hello/there/:some/:hello", function get1() {});
trieRouter.post("/users/:some/hello/there/:id/none", function post1() {});

console.log("Printing Tree:");
trieRouter.printTree();

console.log("Finding Handlers:");

console.log(trieRouter.findRoute("/users/e/hello/there/2/3", HTTP_METHODS.GET));
console.log(trieRouter.findRoute("/users/1/hello/there/2/none", HTTP_METHODS.GET));
console.log(trieRouter.findRoute("/users", HTTP_METHODS.PUT));
console.log(trieRouter.findRoute("/users", HTTP_METHODS.TRACE));
```

This outputs:

```curl
Printing Tree:
(users) Dynamic:
-(:) Dynamic:
--(hello) Dynamic:
---(there) Dynamic:
----(:) Dynamic:
-----(:) Dynamic: id,some,hello
-----(none) Dynamic: some,id

Finding Handlers:
{
  params: [Object: null prototype] { id: 'e', some: '2', hello: '3' },
  handler: [Function: get1]
}
{
  params: [Object: null prototype] { some: '1', id: '2' },
  handler: undefined
}
{ params: [Object: null prototype] {}, handler: undefined }
{ params: [Object: null prototype] {}, handler: undefined }
```

That's it! We now have a `TrieRouter` that supports dynamic routing, allowing us to define routes with variable segments and extract their values when a route is matched.

### Visualisation of our `TrieRouter` structure

Suppose we have the following routes:

```js
trieRouter.get("/users/:id", function get1() {});
trieRouter.get("/users/:id/ban", function get1() {});
trieRouter.get("/:some/hello", function post2() {});
trieRouter.get("/:name/student", function get3() {});
```

The trie structure would look like this:

![](/assets/imgs/dynamic_router_trie.webp)

### Summary

In this challenge, we successfully enhanced the `TrieRouter` class to support dynamic routing. The router can now handle routes with dynamic parameters, extract their values from the URL, and provide them to the corresponding route handler. This functionality is essential for building flexible and scalable web applications.
