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