Home | History | Annotate | Download | only in util 
      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 
     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 
     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 
     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 
     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 
     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 
    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 
    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