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 android.test.AndroidTestCase;
20 
21 import androidx.test.filters.SmallTest;
22 
23 import com.android.quicksearchbox.util.LevenshteinDistance.EditOperation;
24 import com.android.quicksearchbox.util.LevenshteinDistance.Token;
25 
26 /**
27  * Tests for class {@link LevenshteinDistance}.
28  */
29 @SmallTest
30 public class LevenshteinDistanceTest extends AndroidTestCase {
31     // to make the tests less verbose:
32     private static final int INSERT = LevenshteinDistance.EDIT_INSERT;
33     private static final int DELETE = LevenshteinDistance.EDIT_DELETE;
34     private static final int REPLACE = LevenshteinDistance.EDIT_REPLACE;
35     private static final int UNCHANGED = LevenshteinDistance.EDIT_UNCHANGED;
36 
verifyTargetOperations(String[] source, String[] target, int[] expectedOps, int expectedDistance)37     private void verifyTargetOperations(String[] source, String[] target, int[] expectedOps,
38             int expectedDistance) {
39 
40         Token[] sourceTokens = makeTokens(source);
41         Token[] targetTokens = makeTokens(target);
42 
43         assertEquals("test error", target.length, expectedOps.length);
44         LevenshteinDistance distance = new LevenshteinDistance(sourceTokens, targetTokens);
45 
46         assertEquals(expectedDistance, distance.calculate());
47         EditOperation[] ops = distance.getTargetOperations();
48         assertEquals(expectedOps.length, ops.length);
49         for (int i = 0; i < ops.length; ++i) {
50             assertEquals("Token " + i + " '" + target[i] + "' has wrong operation",
51                     expectedOps[i], ops[i].getType());
52             if (expectedOps[i] == UNCHANGED) {
53                 assertEquals(source[ops[i].getPosition()], target[i]);
54             } else if (expectedOps[i] == REPLACE) {
55                 assertFalse(source[ops[i].getPosition()].equals(target[i]));
56             }
57         }
58     }
59 
makeTokens(String[] strings)60     private Token[] makeTokens(String[] strings) {
61         Token[] tokens = new Token[strings.length];
62         for (int i = 0; i < strings.length; i++) {
63             String str = strings[i];
64             tokens[i] = new Token(str.toCharArray(), 0, str.length());
65         }
66         return tokens;
67     }
68 
testGetTargetOperationsEmptySource()69     public void testGetTargetOperationsEmptySource() {
70         verifyTargetOperations(
71                 new String[]{},
72                 new String[]{},
73                 new int[]{},
74                 0);
75 
76         verifyTargetOperations(
77                 new String[]{},
78                 new String[]{"goo", "ball"},
79                 new int[]{INSERT, INSERT},
80                 2);
81     }
82 
testGetTargetOperationsEmptyTarget()83     public void testGetTargetOperationsEmptyTarget() {
84         verifyTargetOperations(
85                 new String[]{"delete"},
86                 new String[]{},
87                 new int[]   {},
88                 1);
89 
90         verifyTargetOperations(
91                 new String[]{"delete", "me"},
92                 new String[]{},
93                 new int[]   {},
94                 2);
95     }
96 
testGetTargetOperationsReplacement()97     public void testGetTargetOperationsReplacement() {
98         verifyTargetOperations(
99                 new String[]{"dennis"},
100                 new String[]{"gnasher"},
101                 new int[]   {REPLACE},
102                 1);
103 
104         verifyTargetOperations(
105                 new String[]{"angry", "viking"},
106                 new String[]{"happy", "kitten"},
107                 new int[]   {REPLACE, REPLACE},
108                 2);
109     }
110 
testGetTargetOperationsUnchanged()111     public void testGetTargetOperationsUnchanged() {
112         verifyTargetOperations(
113                 new String[]{"tweedledee"},
114                 new String[]{"tweedledee"},
115                 new int[]   {UNCHANGED},
116                 0);
117 
118         verifyTargetOperations(
119                 new String[]{"tweedledee", "tweedledum"},
120                 new String[]{"tweedledee", "tweedledum"},
121                 new int[]   {UNCHANGED,     UNCHANGED},
122                 0);
123     }
124 
testGetTargetOperationsDuplicateTokens()125     public void testGetTargetOperationsDuplicateTokens() {
126         String rhubarb = "rhubarb";
127         verifyTargetOperations(
128                 new String[]{rhubarb},
129                 new String[]{rhubarb,   rhubarb},
130                 new int[]   {UNCHANGED, INSERT},
131                 1);
132 
133         verifyTargetOperations(
134                 new String[]{rhubarb,   rhubarb},
135                 new String[]{rhubarb,   rhubarb},
136                 new int[]   {UNCHANGED, UNCHANGED},
137                 0);
138 
139         verifyTargetOperations(
140                 new String[]{rhubarb,   rhubarb},
141                 new String[]{rhubarb,   rhubarb,   rhubarb},
142                 new int[]   {UNCHANGED, UNCHANGED, INSERT},
143                 1);
144     }
145 
146 }
147