之前看学长他们用过这个动态路由，但是以前也没有太注意，最近在学习框架的建立。第一次让我感受到了算法在写项目时候的应用，之前都觉得算法这个东西，就是刷题用的，在实战的时候很少用。今天学习这一块稍微有一点吃力，但是还是看懂了，很nice。

什么是动态路由呢

动态路由在开发的时候，就是说不是像原来写项目的时候，这个固定路由绑定固定的函数，而是变化的路由进行固定函数的绑定，这样就可以实现很多的功能。
动态路由的实例：/api/v1/:name
这里我们要知道的是，上面这个路由可以匹配很多的路由比如：
/api/v1/lzz /api/v1/ceshi ....等
这里第三个分隔开的字段，就是对name的赋值。这就是动态路由

实现动态路由需要准备什么

首先我们要用到的就是前缀树，这里我们看一下怎么实现前缀树。我们还是说明一下，比如说，在我们路由中我们可以通过/来分割节点，然后后面通过这些节点进行寻找正确的路由。、
上面的这个图就是展示了前缀树。然后下面我们就来实现一下这个前缀树。
首先定义前缀树的节点：

type node struct {
  pattern  string  //待匹配的路由
  part     string  //路由中的一部分
  children []*node //子节点
  isWild   bool //这里如果是*或者：开头的就是true
}

然后我们建立一个注册函数，一个查找函数

func (n *node) insert(pattern string, parts []string, height int) {
	//查看是不是最后一个，是的话就返回
	if len(parts) == height {
		n.pattern = pattern
		return
	}
	//取出路径中的一部分
	part := parts[height]
	//查看现在的树中是不是有这个节点，没有的话就进行创建
	child := n.matchChild(part)
	//下面是创建的流程。也就是创建
	if child == nil {
		//如果是动态的就会设置为true
		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
		n.children = append(n.children, child)
	}
	child.insert(pattern, parts, height+1)
}

查找函数：

func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		result := child.search(parts, height+1)
		if result != nil {
			return result
		}
	}

	return nil
}

上面两个函数中有两个关键的函数，就是对路由的匹配，这两个函数我还是看了很久才理解，也是在学习的时候出现的问题。

//创建节点插入的时候的判断函数
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

//查找路径
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}
	return nodes
}

两个函数的原理都是差不多的，传入需要判断的路径一部分，然后在节点里面去寻找是否有这个节点，然后找到了就返回，没有找到就返回nil，我认为的这两个函数，第一个就是判断有没有这个节点，如果没有就返回，然后建立新的节点进行存储，如果找到了就不做操作。
第二个函数，就是对没有部分的判断，然后进行一个添加。
前缀树完整的代码：

package gee

import (
	"fmt"
	"strings"
)

type node struct {
	pattern  string
	part     string
	children []*node
	isWild   bool
}

func (n *node) String() string {
	return fmt.Sprintf("node{pattern=%s, part=%s, isWild=%t}", n.pattern, n.part, n.isWild)
}

func (n *node) insert(pattern string, parts []string, height int) {
	//查看是不是最后一个，是的话就返回
	if len(parts) == height {
		n.pattern = pattern
		return
	}
	//取出路径中的一部分
	part := parts[height]
	//查看现在的树中是不是有这个节点，没有的话就进行创建
	child := n.matchChild(part)
	//下面是创建的流程。也就是创建
	if child == nil {
		//如果是动态的就会设置为true
		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
		n.children = append(n.children, child)
	}
	child.insert(pattern, parts, height+1)
}

//路由的查找
func (n *node) search(parts []string, height int) *node {
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		result := child.search(parts, height+1)
		if result != nil {
			return result
		}
	}

	return nil
}

func (n *node) travel(list *([]*node)) {
	if n.pattern != "" {
		*list = append(*list, n)
	}
	for _, child := range n.children {
		child.travel(list)
	}
}

//创建节点插入的时候的判断函数
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

//查找路径
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}
	return nodes
}