1 /*
2  * Copyright (C) 2010 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.quicksearchbox.util;
18 
19 import com.android.quicksearchbox.util.LevenshteinDistance.EditOperation;
20 import com.android.quicksearchbox.util.LevenshteinDistance.Token;
21 
22 import android.test.AndroidTestCase;
23 import android.test.suitebuilder.annotation.SmallTest;
24 
25 /**
26  * Tests for class {@link LevenshteinDistance}.
27  */
28 @SmallTest
29 public class LevenshteinDistanceTest extends AndroidTestCase {
30     // to make the tests less verbose:
31     private static final int INSERT = LevenshteinDistance.EDIT_INSERT;
32     private static final int DELETE = LevenshteinDistance.EDIT_DELETE;
33     private static final int REPLACE = LevenshteinDistance.EDIT_REPLACE;
34     private static final int UNCHANGED = LevenshteinDistance.EDIT_UNCHANGED;
35 
verifyTargetOperations(String[] source, String[] target, int[] expectedOps, int expectedDistance)36     private void verifyTargetOperations(String[] source, String[] target, int[] expectedOps,
37             int expectedDistance) {
38 
39         Token[] sourceTokens = makeTokens(source);
40         Token[] targetTokens = makeTokens(target);
41 
42         assertEquals("test error", target.length, expectedOps.length);
43         LevenshteinDistance distance = new LevenshteinDistance(sourceTokens, targetTokens);
44 
45         assertEquals(expectedDistance, distance.calculate());
46         EditOperation[] ops = distance.getTargetOperations();
47         assertEquals(expectedOps.length, ops.length);
48         for (int i = 0; i < ops.length; ++i) {
49             assertEquals("Token " + i + " '" + target[i] + "' has wrong operation",
50                     expectedOps[i], ops[i].getType());
51             if (expectedOps[i] == UNCHANGED) {
52                 assertEquals(source[ops[i].getPosition()], target[i]);
53             } else if (expectedOps[i] == REPLACE) {
54                 assertFalse(source[ops[i].getPosition()].equals(target[i]));
55             }
56         }
57     }
58 
makeTokens(String[] strings)59     private Token[] makeTokens(String[] strings) {
60         Token[] tokens = new Token[strings.length];
61         for (int i = 0; i < strings.length; i++) {
62             String str = strings[i];
63             tokens[i] = new Token(str.toCharArray(), 0, str.length());
64         }
65         return tokens;
66     }
67 
testGetTargetOperationsEmptySource()68     public void testGetTargetOperationsEmptySource() {
69         verifyTargetOperations(
70                 new String[]{},
71                 new String[]{},
72                 new int[]{},
73                 0);
74 
75         verifyTargetOperations(
76                 new String[]{},
77                 new String[]{"goo", "ball"},
78                 new int[]{INSERT, INSERT},
79                 2);
80     }
81 
testGetTargetOperationsEmptyTarget()82     public void testGetTargetOperationsEmptyTarget() {
83         verifyTargetOperations(
84                 new String[]{"delete"},
85                 new String[]{},
86                 new int[]   {},
87                 1);
88 
89         verifyTargetOperations(
90                 new String[]{"delete", "me"},
91                 new String[]{},
92                 new int[]   {},
93                 2);
94     }
95 
testGetTargetOperationsReplacement()96     public void testGetTargetOperationsReplacement() {
97         verifyTargetOperations(
98                 new String[]{"dennis"},
99                 new String[]{"gnasher"},
100                 new int[]   {REPLACE},
101                 1);
102 
103         verifyTargetOperations(
104                 new String[]{"angry", "viking"},
105                 new String[]{"happy", "kitten"},
106                 new int[]   {REPLACE, REPLACE},
107                 2);
108     }
109 
testGetTargetOperationsUnchanged()110     public void testGetTargetOperationsUnchanged() {
111         verifyTargetOperations(
112                 new String[]{"tweedledee"},
113                 new String[]{"tweedledee"},
114                 new int[]   {UNCHANGED},
115                 0);
116 
117         verifyTargetOperations(
118                 new String[]{"tweedledee", "tweedledum"},
119                 new String[]{"tweedledee", "tweedledum"},
120                 new int[]   {UNCHANGED,     UNCHANGED},
121                 0);
122     }
123 
testGetTargetOperationsDuplicateTokens()124     public void testGetTargetOperationsDuplicateTokens() {
125         String rhubarb = "rhubarb";
126         verifyTargetOperations(
127                 new String[]{rhubarb},
128                 new String[]{rhubarb,   rhubarb},
129                 new int[]   {UNCHANGED, INSERT},
130                 1);
131 
132         verifyTargetOperations(
133                 new String[]{rhubarb,   rhubarb},
134                 new String[]{rhubarb,   rhubarb},
135                 new int[]   {UNCHANGED, UNCHANGED},
136                 0);
137 
138         verifyTargetOperations(
139                 new String[]{rhubarb,   rhubarb},
140                 new String[]{rhubarb,   rhubarb,   rhubarb},
141                 new int[]   {UNCHANGED, UNCHANGED, INSERT},
142                 1);
143     }
144 
145 }
146