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