java-diff-utils
diff --git a/‎java-diff-utils/src/main/java/com/github/difflib/algorithm/myers/IntIntMap.java‎
Lines changed: 104 additions & 0 deletions b/‎java-diff-utils/src/main/java/com/github/difflib/algorithm/myers/IntIntMap.java‎
Lines changed: 104 additions & 0 deletions
@@ -0,0 +1,104 @@
+/*
+ * Copyright 2024 java-diff-utils.
+ *
+ * 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
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * 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.
+ */
+package com.github.difflib.algorithm.myers;
+
+/**
+ * A simple open-addressing hash map for int -> int mappings.
+ * Avoids boxing overhead of HashMap&lt;Integer, Integer&gt;.
+ */
+final class IntIntMap {
+    private int[] keys;
+    private int[] values;
+    private boolean[] allocated;
+    private int size;
+    private int capacity;
+    private int threshold;
+
+    IntIntMap(int initialCapacity) {
+        capacity = 1;
+        while (capacity < initialCapacity) {
+            capacity = capacity << 1;
+        }
+        keys = new int[capacity];
+        values = new int[capacity];
+        allocated = new boolean[capacity];
+        threshold = (int) (capacity * 0.75);
+    }
+
+    void put(int key, int value) {
+        if (size >= threshold) {
+            resize();
+        }
+
+        int idx = findInsertIndex(key);
+        if (!allocated[idx]) {
+            allocated[idx] = true;
+            keys[idx] = key;
+            size++;
+        }
+        values[idx] = value;
+    }
+
+    int get(int key) {
+        int idx = findIndex(key);
+        if (idx == -1) {
+            return 0; // default value
+        }
+        return values[idx];
+    }
+
+    private int findIndex(int key) {
+        int idx = key & (capacity - 1);
+        while (allocated[idx]) {
+            if (keys[idx] == key) {
+                return idx;
+            }
+            idx = (idx + 1) & (capacity - 1);
+        }
+        return -1;
+    }
+
+    private int findInsertIndex(int key) {
+        int idx = key & (capacity - 1);
+        while (allocated[idx]) {
+            if (keys[idx] == key) {
+                return idx;
+            }
+            idx = (idx + 1) & (capacity - 1);
+        }
+        return idx;
+    }
+
+    private void resize() {
+        int[] oldKeys = keys;
+        int[] oldValues = values;
+        boolean[] oldAllocated = allocated;
+        int oldCapacity = capacity;
+
+        capacity = capacity << 1;
+        threshold = (int) (capacity * 0.75);
+        keys = new int[capacity];
+        values = new int[capacity];
+        allocated = new boolean[capacity];
+        size = 0;
+
+        for (int i = 0; i < oldCapacity; i++) {
+            if (oldAllocated[i]) {
+                put(oldKeys[i], oldValues[i]);
+            }
+        }
+    }
+}