func stringMapFromPairs(err string, pairs ...string) map[string]string {
	size := len(pairs)
	if size%2 != 0 {
		panic(fmt.Sprintf(err, pairs))
	}
	m := make(map[string]string, size/2)
	for i := 0; i < size; i += 2 {
		m[pairs[i]] = pairs[i+1]
	}
	return m
}
stringMapFromPairs converts variadic string parameters to a string map.
package mux
import (
	"bytes"
	"errors"
	"fmt"
	"http"
	"path"
	"regexp"
	"strings"
	"url"
	"gorilla.googlecode.com/hg/gorilla/context"
)
const (
	errRouteName string = "Duplicated route name: %q."
	errVarName   string = "Duplicated route variable name: %q."
	errUnbalancedBraces string = "Unbalanced curly braces in route template: %q."
	errBadTemplatePart  string = "Missing name or pattern in route template: %q."
	errMissingRouteVar string = "Missing route variable: %q."
	errBadRouteVar     string = "Route variable doesn't match: got %q, expected %q."
	errMissingHost     string = "Route doesn't have a host."
	errMissingPath     string = "Route doesn't have a path."
	errEmptyHost       string = "Host() requires a non-zero string, got %q."
	errEmptyPath       string = "Path() requires a non-zero string that starts with a slash, got %q."
	errEmptyPathPrefix string = "PathPrefix() requires a non-zero string that starts with a slash, got %q."
	errEmptyHeaders string = "Headers() requires at least a pair of parameters."
	errEmptyMethods string = "Methods() requires at least one parameter."
	errEmptyQueries string = "Queries() requires at least a pair of parameters."
	errEmptySchemes string = "Schemes() requires at least one parameter."
	errOddHeaders   string = "Headers() requires an even number of parameters, got %v."
	errOddQueries   string = "Queries() requires an even number of parameters, got %v."
	errOddURLPairs  string = "URL() requires an even number of parameters, got %v."
)
type RouteVars map[string]string
var ctx = new(context.Namespace)
func Vars(request *http.Request) RouteVars {
	rv := ctx.Get(request)
	if rv != nil {
		return rv.(RouteVars)
	}
	return nil
}
var routeCtx = new(context.Namespace)
func CurrentRoute(request *http.Request) *Route {
	rv := routeCtx.Get(request)
	if rv != nil {
		return rv.(*Route)
	}
	return nil
}
type Router struct {
	Routes []*Route
	NamedRoutes map[string]*Route
	rootRouter *Router
	NotFoundHandler http.Handler
	redirectSlash bool
}
func (r *Router) root() *Router {
	if r.rootRouter == nil {
		return r
	}
	return r.rootRouter
}
func (r *Router) Match(request *http.Request) (match *RouteMatch, ok bool) {
	for _, route := range r.Routes {
		if match, ok = route.Match(request); ok {
			return
		}
	}
	return
}
func (r *Router) ServeHTTP(writer http.ResponseWriter, request *http.Request) {
	if p := cleanPath(request.URL.Path); p != request.URL.Path {
		writer.Header().Set("Location", p)
		writer.WriteHeader(http.StatusMovedPermanently)
		return
	}
	var handler http.Handler
	if match, ok := r.Match(request); ok {
		handler = match.Handler
	}
	if handler == nil {
		if r.NotFoundHandler == nil {
			r.NotFoundHandler = http.NotFoundHandler()
		}
		handler = r.NotFoundHandler
	}
	defer context.DefaultContext.Clear(request)
	handler.ServeHTTP(writer, request)
}
func (r *Router) AddRoute(route *Route) *Router {
	if r.Routes == nil {
		r.Routes = make([]*Route, 0)
	}
	route.router = r
	r.Routes = append(r.Routes, route)
	return r
}
func (r *Router) RedirectSlash(value bool) *Router {
	r.redirectSlash = value
	return r
}
func (r *Router) NewRoute() *Route {
	route := newRoute()
	route.redirectSlash = r.redirectSlash
	r.AddRoute(route)
	return route
}
func (r *Router) Handle(path string, handler http.Handler) *Route {
	return r.NewRoute().Handle(path, handler)
}
func (r *Router) HandleFunc(path string, handler func(http.ResponseWriter,
	*http.Request)) *Route {
	return r.NewRoute().HandleFunc(path, handler)
}
type Route struct {
	router *Router
	handler http.Handler
	matchers []*routeMatcher
	hostTemplate *parsedTemplate
	pathTemplate *parsedTemplate
	redirectSlash bool
	name string
}
func newRoute() *Route {
	return &Route{
		matchers: make([]*routeMatcher, 0),
	}
}
func (r *Route) Clone() *Route {
	matchers := make([]*routeMatcher, len(r.matchers))
	copy(matchers, r.matchers)
	return &Route{
		router:        r.router,
		handler:       r.handler,
		matchers:      matchers,
		hostTemplate:  r.hostTemplate,
		pathTemplate:  r.pathTemplate,
		redirectSlash: r.redirectSlash,
	}
}
func (r *Route) Match(req *http.Request) (*RouteMatch, bool) {
	var hostMatches, pathMatches []string
	if r.hostTemplate != nil {
		hostMatches = r.hostTemplate.Regexp.FindStringSubmatch(req.URL.Host)
		if hostMatches == nil {
			return nil, false
		}
	}
	var redirectURL string
	if r.pathTemplate != nil {
		pathMatches = r.pathTemplate.Regexp.FindStringSubmatch(req.URL.Path)
		if pathMatches == nil {
			return nil, false
		} else if r.redirectSlash {
			p1 := strings.HasSuffix(req.URL.Path, "/")
			p2 := strings.HasSuffix(r.pathTemplate.Template, "/")
			if p1 != p2 {
				ru, _ := url.Parse(req.URL.String())
				if p1 {
					ru.Path = ru.Path[:len(ru.Path)-1]
				} else {
					ru.Path = ru.Path + "/"
				}
				redirectURL = ru.String()
			}
		}
	}
	var match *RouteMatch
	if r.matchers != nil {
		for _, matcher := range r.matchers {
			if rv, ok := (*matcher).Match(req); !ok {
				return nil, false
			} else if rv != nil {
				match = rv
				break
			}
		}
	}
	vars := make(RouteVars)
	if hostMatches != nil {
		for k, v := range r.hostTemplate.VarsN {
			vars[v] = hostMatches[k+1]
		}
	}
	if pathMatches != nil {
		for k, v := range r.pathTemplate.VarsN {
			vars[v] = pathMatches[k+1]
		}
	}
	if match == nil {
		match = &RouteMatch{Route: r, Handler: r.handler}
	}
	if redirectURL != "" {
		match.Handler = http.RedirectHandler(redirectURL, 301)
	}
	ctx.Set(req, vars)
	routeCtx.Set(req, match.Route)
	return match, true
}
func (r *Route) NewRouter() *Router {
	router := &Router{
		Routes:     make([]*Route, 0),
		rootRouter: r.router.root(),
	}
	r.addMatcher(router)
	return router
}
func (r *Route) URL(pairs ...string) (rv *url.URL) {
	rv, _ = r.URLDebug(pairs...)
	return
}
func (r *Route) URLDebug(pairs ...string) (rv *url.URL, err error) {
	var scheme, host, path string
	values := stringMapFromPairs(errOddURLPairs, pairs...)
	if r.hostTemplate != nil {
		scheme = "http"
		if host, err = reverseRoute(r.hostTemplate, values); err != nil {
			return
		}
	}
	if r.pathTemplate != nil {
		if path, err = reverseRoute(r.pathTemplate, values); err != nil {
			return
		}
	}
	rv = &url.URL{
		Scheme: scheme,
		Host:   host,
		Path:   path,
	}
	return
}
func (r *Route) URLHost(pairs ...string) (rv *url.URL) {
	rv, _ = r.URLHostDebug(pairs...)
	return
}
func (r *Route) URLHostDebug(pairs ...string) (rv *url.URL, err error) {
	if r.hostTemplate == nil {
		err = muxError(errMissingHost)
		return
	}
	var host string
	values := stringMapFromPairs(errOddURLPairs, pairs...)
	if host, err = reverseRoute(r.hostTemplate, values); err != nil {
		return
	} else {
		rv = &url.URL{
			Scheme: "http",
			Host:   host,
		}
	}
	return
}
func (r *Route) URLPath(pairs ...string) (rv *url.URL) {
	rv, _ = r.URLPathDebug(pairs...)
	return
}
func (r *Route) URLPathDebug(pairs ...string) (rv *url.URL, err error) {
	if r.pathTemplate == nil {
		err = muxError(errMissingPath)
		return
	}
	var path string
	values := stringMapFromPairs(errOddURLPairs, pairs...)
	if path, err = reverseRoute(r.pathTemplate, values); err != nil {
		return
	} else {
		rv = &url.URL{
			Path: path,
		}
	}
	return
}
func reverseRoute(tpl *parsedTemplate, values map[string]string) (rv string, err error) {
	var value string
	var ok bool
	urlValues := make([]interface{}, len(tpl.VarsN))
	for k, v := range tpl.VarsN {
		if value, ok = values[v]; !ok {
			err = muxError(errMissingRouteVar, v)
			return
		}
		urlValues[k] = value
	}
	rv = fmt.Sprintf(tpl.Reverse, urlValues...)
	if !tpl.Regexp.MatchString(rv) {
		for k, v := range tpl.VarsN {
			if !tpl.VarsR[k].MatchString(values[v]) {
				err = muxError(errBadRouteVar, values[v],
					tpl.VarsR[k].String())
				return
			}
		}
	}
	return
}
func (r *Route) Handler(handler http.Handler) *Route {
	r.handler = handler
	return r
}
func (r *Route) HandlerFunc(handler func(http.ResponseWriter,
	*http.Request)) *Route {
	return r.Handler(http.HandlerFunc(handler))
}
func (r *Route) Handle(path string, handler http.Handler) *Route {
	return r.Path(path).Handler(handler)
}
func (r *Route) HandleFunc(path string, handler func(http.ResponseWriter,
	*http.Request)) *Route {
	return r.Path(path).Handler(http.HandlerFunc(handler))
}
func (r *Route) Name(name string) *Route {
	router := r.router.root()
	if router.NamedRoutes == nil {
		router.NamedRoutes = make(map[string]*Route)
	}
	r.name = name
	router.NamedRoutes[name] = r
	return r
}
func (r *Route) GetName() string {
	return r.name
}
func (r *Route) RedirectSlash(value bool) *Route {
	r.redirectSlash = value
	return r
}
func (r *Route) addMatcher(m routeMatcher) *Route {
	r.matchers = append(r.matchers, &m)
	return r
}
func (r *Route) Headers(pairs ...string) *Route {
	headers := stringMapFromPairs(errOddHeaders, pairs...)
	if len(headers) == 0 {
		panic(errEmptyHeaders)
	}
	return r.addMatcher(&headerMatcher{headers: headers})
}
func (r *Route) Host(template string) *Route {
	if template == "" {
		panic(fmt.Sprintf(errEmptyHost, template))
	}
	tpl := &parsedTemplate{Template: template}
	err := parseTemplate(tpl, "[^.]+", false, false,
		variableNames(r.pathTemplate))
	if err != nil {
		panic(err)
	}
	r.hostTemplate = tpl
	return r
}
func (r *Route) Matcher(matcherFunc MatcherFunc) *Route {
	return r.addMatcher(&customMatcher{matcherFunc: matcherFunc})
}
func (r *Route) Methods(methods ...string) *Route {
	if len(methods) == 0 {
		panic(errEmptyMethods)
	}
	for k, v := range methods {
		methods[k] = strings.ToUpper(v)
	}
	return r.addMatcher(&methodMatcher{methods: methods})
}
func (r *Route) Path(template string) *Route {
	if template == "" || template[0] != '/' {
		panic(fmt.Sprintf(errEmptyPath, template))
	}
	tpl := &parsedTemplate{Template: template}
	err := parseTemplate(tpl, "[^/]+", false, r.redirectSlash,
		variableNames(r.hostTemplate))
	if err != nil {
		panic(err)
	}
	r.pathTemplate = tpl
	return r
}
func (r *Route) PathPrefix(template string) *Route {
	if template == "" || template[0] != '/' {
		panic(fmt.Sprintf(errEmptyPathPrefix, template))
	}
	tpl := &parsedTemplate{Template: template}
	err := parseTemplate(tpl, "[^/]+", true, false,
		variableNames(r.hostTemplate))
	if err != nil {
		panic(err)
	}
	r.pathTemplate = tpl
	return r
}
func (r *Route) Queries(pairs ...string) *Route {
	queries := stringMapFromPairs(errOddQueries, pairs...)
	if len(queries) == 0 {
		panic(errEmptyQueries)
	}
	return r.addMatcher(&queryMatcher{queries: queries})
}
func (r *Route) Schemes(schemes ...string) *Route {
	if len(schemes) == 0 {
		panic(errEmptySchemes)
	}
	for k, v := range schemes {
		schemes[k] = strings.ToLower(v)
	}
	return r.addMatcher(&schemeMatcher{schemes: schemes})
}
type RouteMatch struct {
	Route   *Route
	Handler http.Handler
}
type MatcherFunc func(*http.Request) bool
type routeMatcher interface {
	Match(*http.Request) (*RouteMatch, bool)
}
type customMatcher struct {
	matcherFunc MatcherFunc
}
func (m *customMatcher) Match(request *http.Request) (*RouteMatch, bool) {
	return nil, m.matcherFunc(request)
}
type headerMatcher struct {
	headers map[string]string
}
func (m *headerMatcher) Match(request *http.Request) (*RouteMatch, bool) {
	return nil, matchMap(m.headers, request.Header, true)
}
type methodMatcher struct {
	methods []string
}
func (m *methodMatcher) Match(request *http.Request) (*RouteMatch, bool) {
	return nil, matchInArray(m.methods, request.Method)
}
type queryMatcher struct {
	queries map[string]string
}
func (m *queryMatcher) Match(request *http.Request) (*RouteMatch, bool) {
	return nil, matchMap(m.queries, request.URL.Query(), false)
}
type schemeMatcher struct {
	schemes []string
}
func (m *schemeMatcher) Match(request *http.Request) (*RouteMatch, bool) {
	return nil, matchInArray(m.schemes, request.URL.Scheme)
}
type parsedTemplate struct {
	Template string
	Regexp *regexp.Regexp
	Reverse string
	VarsN []string
	VarsR []*regexp.Regexp
}
func parseTemplate(tpl *parsedTemplate, defaultPattern string, prefix bool,
	redirectSlash bool, names *[]string) error {
	template := tpl.Template
	endSlash := false
	if redirectSlash && strings.HasSuffix(template, "/") {
		template = template[:len(template)-1]
		endSlash = true
	}
	idxs, err := getBraceIndices(template)
	if err != nil {
		return err
	}
	var raw, name, patt string
	var end int
	var parts []string
	pattern := bytes.NewBufferString("^")
	reverse := bytes.NewBufferString("")
	size := len(idxs)
	tpl.VarsN = make([]string, size/2)
	tpl.VarsR = make([]*regexp.Regexp, size/2)
	for i := 0; i < size; i += 2 {
		raw = template[end:idxs[i]]
		end = idxs[i+1]
		parts = strings.SplitN(template[idxs[i]+1:end-1], ":", 2)
		name = parts[0]
		if len(parts) == 1 {
			patt = defaultPattern
		} else {
			patt = parts[1]
		}
		if name == "" || patt == "" {
			return muxError(errBadTemplatePart, template[idxs[i]:end])
		}
		if names != nil {
			if matchInArray(*names, name) {
				return muxError(errVarName, name)
			}
			*names = append(*names, name)
		}
		fmt.Fprintf(pattern, "%s(%s)", regexp.QuoteMeta(raw), patt)
		fmt.Fprintf(reverse, "%s%%s", raw)
		tpl.VarsN[i/2] = name
		if reg, err := regexp.Compile(fmt.Sprintf("^%s$", patt)); err != nil {
			return err
		} else {
			tpl.VarsR[i/2] = reg
		}
	}
	raw = template[end:]
	pattern.WriteString(regexp.QuoteMeta(raw))
	if redirectSlash {
		pattern.WriteString("[/]?")
	}
	if !prefix {
		pattern.WriteString("$")
	}
	reverse.WriteString(raw)
	if endSlash {
		reverse.WriteString("/")
	}
	reg, err := regexp.Compile(pattern.String())
	if err != nil {
		return err
	}
	tpl.Regexp = reg
	tpl.Reverse = reverse.String()
	return nil
}
func getBraceIndices(s string) ([]int, error) {
	var level, idx int
	idxs := make([]int, 0)
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case '{':
			if level++; level == 1 {
				idx = i
			}
		case '}':
			if level--; level == 0 {
				idxs = append(idxs, idx, i+1)
			} else if level < 0 {
				return nil, muxError(errUnbalancedBraces, s)
			}
		}
	}
	if level != 0 {
		return nil, muxError(errUnbalancedBraces, s)
	}
	return idxs, nil
}
func muxError(msg string, vars ...interface{}) error {
	return errors.New(fmt.Sprintf(msg, vars...))
}
func cleanPath(p string) string {
	if p == "" {
		return "/"
	}
	if p[0] != '/' {
		p = "/" + p
	}
	np := path.Clean(p)
	if p[len(p)-1] == '/' && np != "/" {
		np += "/"
	}
	return np
}