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