Creating URL Routing: Episode 2

bmf-san Algorithms, Data Structures ja
#HTTP#URL Routing#Tree Structure#Router

Overview

Creating URL Routing: Episode 1 continuation.

I managed to create a working version and published it as a package named packagist - ahi-router.

Changes from Episode 1

In Episode 1, I attempted to create routing by adopting a tree structure for the data structure.

In libraries optimized for performance, it seems common to prepare logic for generating tree structures and implement optimized search algorithms. However, writing the logic to generate a tree structure seemed time-consuming, so I decided to focus on improving the search part instead.

Previously, the routing definition data structure was:

But I redefined it as:

The changes include:

  • Unified the structure into a single root to form a proper tree structure.
    • A root node is a node without a parent node. It is the topmost node in a tree structure, and there can be at most one root node in a tree structure. - Wikipedia - Tree Structure (Data Structure)
    • In other words, the previous version was not technically a tree structure but a pseudo-tree structure.
  • Introduced an identifier called END_POINT.
    • While the name END_POINT may not be ideal, it was introduced to clearly distinguish it from the root node.

Previously, I tried to manage everything with functions, but it was challenging. Switching to an object-oriented approach made the implementation smoother. The changes to the data structure also contributed to easier implementation.

Implementation

The time complexity is roughly O(n), so as n (route definitions) increases, the computational complexity increases proportionally, making it a suboptimal algorithm.

Thoughts

If I were to build this properly, I should definitely study tree traversal algorithms. I had a hunch about this, but I’ve learned my lesson.

I feel like I’ve come to appreciate the importance of algorithms. (Just my two cents.)

I don’t usually write such convoluted code, so this was a good mental exercise. (I think doing such exercises occasionally to get used to algorithms is a good idea.)

Even some major routing libraries seem to use regular expressions or non-optimized algorithms, so I’d like to continue studying various implementations and algorithms and eventually try implementing routing again.

Source Code and Package

References