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
17package com.android.quicksearchbox.util;
18
19import com.android.quicksearchbox.util.LevenshteinDistance.EditOperation;
20import com.android.quicksearchbox.util.LevenshteinDistance.Token;
21
22import android.test.AndroidTestCase;
23import android.test.suitebuilder.annotation.SmallTest;
24
25/**
26 * Tests for class {@link LevenshteinDistance}.
27 */
28@SmallTest
29public 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