1// Copyright (c) 2014 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 search 16 17import ( 18 "testing" 19) 20 21func TestLevenshteinDistance(t *testing.T) { 22 23 tests := []struct { 24 a string 25 b string 26 dist int 27 }{ 28 { 29 "water", 30 "atec", 31 2, 32 }, 33 { 34 "water", 35 "aphex", 36 4, 37 }, 38 } 39 40 for _, test := range tests { 41 actual := LevenshteinDistance(test.a, test.b) 42 if actual != test.dist { 43 t.Errorf("expected %d, got %d for %s and %s", test.dist, actual, test.a, test.b) 44 } 45 } 46} 47 48func TestLevenshteinDistanceMax(t *testing.T) { 49 50 tests := []struct { 51 a string 52 b string 53 max int 54 dist int 55 exceeded bool 56 }{ 57 { 58 a: "water", 59 b: "atec", 60 max: 1, 61 dist: 1, 62 exceeded: true, 63 }, 64 { 65 a: "water", 66 b: "christmas", 67 max: 3, 68 dist: 3, 69 exceeded: true, 70 }, 71 { 72 a: "water", 73 b: "water", 74 max: 1, 75 dist: 0, 76 exceeded: false, 77 }, 78 } 79 80 for _, test := range tests { 81 actual, exceeded := LevenshteinDistanceMax(test.a, test.b, test.max) 82 if actual != test.dist || exceeded != test.exceeded { 83 t.Errorf("expected %d %t, got %d %t for %s and %s", test.dist, test.exceeded, actual, exceeded, test.a, test.b) 84 } 85 } 86} 87 88// 5 terms that are less than 2 89// 5 terms that are more than 2 90var benchmarkTerms = []string{ 91 "watex", 92 "aters", 93 "wayer", 94 "wbter", 95 "yater", 96 "christmas", 97 "waterwaterwater", 98 "watcatdogfish", 99 "q", 100 "couchbase", 101} 102 103func BenchmarkLevenshteinDistance(b *testing.B) { 104 a := "water" 105 for i := 0; i < b.N; i++ { 106 for _, t := range benchmarkTerms { 107 LevenshteinDistance(a, t) 108 } 109 } 110} 111 112func BenchmarkLevenshteinDistanceMax(b *testing.B) { 113 a := "water" 114 for i := 0; i < b.N; i++ { 115 for _, t := range benchmarkTerms { 116 LevenshteinDistanceMax(a, t, 2) 117 } 118 } 119} 120