1 /*
2  * Copyright (C) 2022 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 /**
20  * This class represents the matrix used in the Levenshtein distance algorithm, together with the
21  * algorithm itself which operates on the matrix.
22  *
23  * We also track of the individual operations applied to transform the source string into the target
24  * string so we can trace the path taken through the matrix afterwards, in order to perform the
25  * formatting as required.
26  */
27 class LevenshteinDistance(source: Array<Token?>?, target: Array<Token?>?) {
28   private val mSource: Array<Token?>?
29   private val mTarget: Array<Token?>?
30   private val mEditTypeTable: Array<IntArray>
31   private val mDistanceTable: Array<IntArray>
32 
33   /**
34    * Implementation of Levenshtein distance algorithm.
35    *
36    * @return The Levenshtein distance.
37    */
calculatenull38   fun calculate(): Int {
39     val src = mSource
40     val trg = mTarget
41     val sourceLen = src!!.size
42     val targetLen = trg!!.size
43     val distTab = mDistanceTable
44     val editTab = mEditTypeTable
45     for (s in 1..sourceLen) {
46       val sourceToken = src[s - 1]
47       for (t in 1..targetLen) {
48         val targetToken = trg[t - 1]
49         val cost = if (sourceToken?.prefixOf(targetToken) == true) 0 else 1
50         var distance = distTab[s - 1][t] + 1
51         var type: Int = EDIT_DELETE
52         var d = distTab[s][t - 1]
53         if (d + 1 < distance) {
54           distance = d + 1
55           type = EDIT_INSERT
56         }
57         d = distTab[s - 1][t - 1]
58         if (d + cost < distance) {
59           distance = d + cost
60           type = if (cost == 0) EDIT_UNCHANGED else EDIT_REPLACE
61         }
62         distTab[s][t] = distance
63         editTab[s][t] = type
64       }
65     }
66     return distTab[sourceLen][targetLen]
67   }
68 
69   /**
70    * Gets the list of operations which were applied to each target token; [.calculate] must have
71    * been called on this object before using this method.
72    * @return A list of [EditOperation]s indicating the origin of each token in the target string.
73    * The position of the token indicates the position in the source string of the token that was
74    * unchanged/replaced, or the position in the source after which a target token was inserted.
75    */
76   val targetOperations: Array<EditOperation?>
77     get() {
78       val trgLen = mTarget!!.size
79       val ops = arrayOfNulls<EditOperation>(trgLen)
80       var targetPos = trgLen
81       var sourcePos = mSource!!.size
82       val editTab = mEditTypeTable
83       while (targetPos > 0) {
84         val editType = editTab[sourcePos][targetPos]
85         when (editType) {
86           EDIT_DELETE -> sourcePos--
87           EDIT_INSERT -> {
88             targetPos--
89             ops[targetPos] = EditOperation(editType, sourcePos)
90           }
91           EDIT_UNCHANGED,
92           EDIT_REPLACE -> {
93             targetPos--
94             sourcePos--
95             ops[targetPos] = EditOperation(editType, sourcePos)
96           }
97         }
98       }
99       return ops
100     }
101 
102   class EditOperation(val type: Int, val position: Int)
103   class Token(private val mContainer: CharArray, val mStart: Int, val mEnd: Int) : CharSequence {
104     @get:Override
105     override val length: Int
106       get() = mEnd - mStart
107 
108     @Override
toStringnull109     override fun toString(): String {
110       // used in tests only.
111       return subSequence(0, length)
112     }
113 
prefixOfnull114     fun prefixOf(that: Token?): Boolean {
115       val len = length
116       if (len > that!!.length) return false
117       val thisStart = mStart
118       val thatStart: Int = that.mStart
119       val thisContainer = mContainer
120       val thatContainer: CharArray = that.mContainer
121       for (i in 0 until len) {
122         if (thisContainer[thisStart + i] != thatContainer[thatStart + i]) {
123           return false
124         }
125       }
126       return true
127     }
128 
getnull129     override fun get(index: Int): Char {
130       return mContainer[index + mStart]
131     }
132 
subSequencenull133     override fun subSequence(startIndex: Int, endIndex: Int): String {
134       return String(mContainer, mStart + startIndex, length)
135     }
136   }
137 
138   companion object {
139     const val EDIT_DELETE = 0
140     const val EDIT_INSERT = 1
141     const val EDIT_REPLACE = 2
142     const val EDIT_UNCHANGED = 3
143   }
144 
145   init {
146     val sourceSize = source!!.size
147     val targetSize = target!!.size
<lambda>null148     val editTab = Array(sourceSize + 1) { IntArray(targetSize + 1) }
<lambda>null149     val distTab = Array(sourceSize + 1) { IntArray(targetSize + 1) }
150     editTab[0][0] = EDIT_UNCHANGED
151     distTab[0][0] = 0
inull152     for (i in 1..sourceSize) {
153       editTab[i][0] = EDIT_DELETE
154       distTab[i][0] = i
155     }
inull156     for (i in 1..targetSize) {
157       editTab[0][i] = EDIT_INSERT
158       distTab[0][i] = i
159     }
160     mEditTypeTable = editTab
161     mDistanceTable = distTab
162     mSource = source
163     mTarget = target
164   }
165 }
166