Code convention

valaphee · Apr 8, 2022 · 2bb93e1 · 2bb93e1
1 parent 875bb89
commit 2bb93e1
Showing 1 changed file with 28 additions and 57 deletions.
diff --git a/src/main/kotlin/com/valaphee/protod/util/KnuthMorrisPratt.kt b/src/main/kotlin/com/valaphee/protod/util/KnuthMorrisPratt.kt
@@ -1,75 +1,46 @@
-package com.valaphee.protod.util
-
-/**
- * For each i in [0, length), this function computes
- * the length of the longest suffix of a substring of pattern from 0 to i
- * that is also a prefix of the pattern itself.
- */
-private fun computePrefixFunction(pattern: ByteArray): IntArray {
-    val resultTable = IntArray(pattern.size)
-
-    var matches = 0
-    for (i in 1..pattern.size - 1) {
-        while (matches > 0 && pattern[matches] != pattern[i]) {
-            matches = resultTable[matches]
-        }
-
-        if (pattern[matches] == pattern[i]) {
-            matches++
-        }
-        resultTable[i] = matches
-    }
-
-    return resultTable
-}
-
-/**
- * Returns a list of indices where the pattern occurs in this String. This method
- * searches character by character and thus does not support regular expressions
- * as input for the pattern.
+/*
+ * Copyright (c) 2021-2022, Valaphee.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
  *
- * @param [pattern] The pattern to look for in this String. Regular expressions
- *                 are not supported
- * @param [ignoreCase] If true, characters are matched even if one is upper and the other is
- *                 lower case
+ *     http://www.apache.org/licenses/LICENSE-2.0
  *
- * @return A list of indices where the supplied [pattern] starts in the text.
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
  */
-public fun ByteArray.occurrencesOf(pattern: ByteArray): Sequence<Int> {
 
-    if (isEmpty() || pattern.isEmpty()) {
-        return emptySequence()
-    }
-
-    if (pattern.size == 1) {
-        return indices.asSequence().filter { this[it].equals(pattern[0]) }
-    }
+package com.valaphee.protod.util
 
-    // Non-trivial pattern matching, perform computation
-    // using Knuth-Morris-Pratt
+fun ByteArray.occurrencesOf(pattern: ByteArray): Sequence<Int> {
+    if (isEmpty() || pattern.isEmpty()) return emptySequence()
+    if (pattern.size == 1) return indices.asSequence().filter { this[it] == pattern[0] }
 
-    val prefixFunction = computePrefixFunction(pattern)
+    val resultTable = IntArray(pattern.size)
+    var matches = 0
+    for (i in 1 until pattern.size) {
+        while (matches > 0 && pattern[matches] != pattern[i]) matches = resultTable[matches]
+        if (pattern[matches] == pattern[i]) matches++
+        resultTable[i] = matches
+    }
 
     var i = 0
-    var matches = 0
+    var matches0 = 0
     return generateSequence {
         while (i < size) {
-            while (matches > 0 && !pattern[matches].equals(this[i])) {
-                matches = prefixFunction[matches - 1]
-            }
-
-            if (pattern[matches].equals(this[i])) {
-                matches++
-            }
-            if (matches == pattern.size) {
-                matches = prefixFunction[matches - 1]
+            while (matches0 > 0 && pattern[matches0] != this[i]) matches0 = resultTable[matches0 - 1]
+            if (pattern[matches0] == this[i]) matches0++
+            if (matches0 == pattern.size) {
+                matches0 = resultTable[matches0 - 1]
                 i++
                 return@generateSequence i - pattern.size
             }
-
             i++
         }
-
         return@generateSequence null
     }
 }