1package validation
 2
 3import (
 4	"fmt"
 5	"sort"
 6	"strconv"
 7	"strings"
 8)
 9
10func makeSuggestion(prefix string, options []string, input string) string {
11	var selected []string
12	distances := make(map[string]int)
13	for _, opt := range options {
14		distance := levenshteinDistance(input, opt)
15		threshold := max(len(input)/2, max(len(opt)/2, 1))
16		if distance < threshold {
17			selected = append(selected, opt)
18			distances[opt] = distance
19		}
20	}
21
22	if len(selected) == 0 {
23		return ""
24	}
25	sort.Slice(selected, func(i, j int) bool {
26		return distances[selected[i]] < distances[selected[j]]
27	})
28
29	parts := make([]string, len(selected))
30	for i, opt := range selected {
31		parts[i] = strconv.Quote(opt)
32	}
33	if len(parts) > 1 {
34		parts[len(parts)-1] = "or " + parts[len(parts)-1]
35	}
36	return fmt.Sprintf(" %s %s?", prefix, strings.Join(parts, ", "))
37}
38
39func levenshteinDistance(s1, s2 string) int {
40	column := make([]int, len(s1)+1)
41	for y := range s1 {
42		column[y+1] = y + 1
43	}
44	for x, rx := range s2 {
45		column[0] = x + 1
46		lastdiag := x
47		for y, ry := range s1 {
48			olddiag := column[y+1]
49			if rx != ry {
50				lastdiag++
51			}
52			column[y+1] = min(column[y+1]+1, min(column[y]+1, lastdiag))
53			lastdiag = olddiag
54		}
55	}
56	return column[len(s1)]
57}
58
59func min(a, b int) int {
60	if a < b {
61		return a
62	}
63	return b
64}
65
66func max(a, b int) int {
67	if a > b {
68		return a
69	}
70	return b
71}