1//  Copyright (c) 2017 Couchbase, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// 		http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package levenshtein
16
17import "unicode/utf8"
18
19// dynamicLevenshtein is the rune-based automaton, which is used
20// during the building of the ut8-aware byte-based automaton
21type dynamicLevenshtein struct {
22	query    string
23	distance uint
24}
25
26func (d *dynamicLevenshtein) start() []int {
27	runeCount := utf8.RuneCountInString(d.query)
28	rv := make([]int, runeCount+1)
29	for i := 0; i < runeCount+1; i++ {
30		rv[i] = i
31	}
32	return rv
33}
34
35func (d *dynamicLevenshtein) isMatch(state []int) bool {
36	last := state[len(state)-1]
37	if uint(last) <= d.distance {
38		return true
39	}
40	return false
41}
42
43func (d *dynamicLevenshtein) canMatch(state []int) bool {
44	distance := int(d.distance)
45	for _, v := range state {
46		if v <= distance {
47			return true
48		}
49	}
50	return false
51}
52
53func (d *dynamicLevenshtein) accept(state []int, r *rune) []int {
54	next := make([]int, 0, len(d.query)+1)
55	next = append(next, state[0]+1)
56	i := 0
57	for _, c := range d.query {
58		var cost int
59		if r == nil || c != *r {
60			cost = 1
61		}
62		v := min(min(next[i]+1, state[i+1]+1), state[i]+cost)
63		next = append(next, min(v, int(d.distance)+1))
64		i++
65	}
66	return next
67}
68
69func min(a, b int) int {
70	if a < b {
71		return a
72	}
73	return b
74}
75