Cleanup BoyerMoore (TheAlgorithms#4951)

prathameshpowar1910 · vil02 · web-flow · commit 574138c7a353 · 2023-10-31T09:07:59.000+01:00
* modify code to make use of java Optional class

* revert changes

* add java.util.Optional&lt;Integer&gt;

* add java.util.Optional

* refactors: make `findmajor` return `optional`

* refactors: make method name findMajor and split it

* refactors: change method name in tests

* Apply suggestions from code review

Co-authored-by: Piotr Idzik &lt;65706193+vil02@users.noreply.github.com&gt;

* change back to int

* fix: swap arguments

* tests: add some test cases

* refactor: add `isMajority` and avoid rounding

* style: use `var`

* style: swap arguments of `countOccurrences`

---------

Co-authored-by: vil02 &lt;vil02@o2.pl&gt;
Co-authored-by: Piotr Idzik &lt;65706193+vil02@users.noreply.github.com&gt;
diff --git a/src/main/java/com/thealgorithms/others/BoyerMoore.java b/src/main/java/com/thealgorithms/others/BoyerMoore.java
@@ -5,35 +5,50 @@
 https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm
  */
 package com.thealgorithms.others;
+import java.util.Optional;
 
 public final class BoyerMoore {
     private BoyerMoore() {
     }
 
-    public static int findmajor(final int[] a) {
+    public static Optional<Integer> findMajor(final int[] a) {
+        final var candidate = findCandidate(a);
+        final var count = countOccurrences(candidate, a);
+        if (isMajority(count, a.length)) {
+            return Optional.of(candidate);
+        }
+        return Optional.empty();
+    }
+
+    private static int findCandidate(final int[] a) {
         int count = 0;
-        int cand = -1;
+        int candidate = -1;
         for (final var k : a) {
             if (count == 0) {
-                cand = k;
+                candidate = k;
                 count = 1;
             } else {
-                if (k == cand) {
+                if (k == candidate) {
                     count++;
                 } else {
                     count--;
                 }
             }
         }
-        count = 0;
+        return candidate;
+    }
+
+    private static int countOccurrences(final int candidate, final int[] a) {
+        int count = 0;
         for (final var j : a) {
-            if (j == cand) {
+            if (j == candidate) {
                 count++;
             }
         }
-        if (count > (a.length / 2)) {
-            return cand;
-        }
-        return -1;
+        return count;
+    }
+
+    private static boolean isMajority(final int count, final int totalCount) {
+        return 2 * count > totalCount;
     }
 }
diff --git a/src/test/java/com/thealgorithms/others/BoyerMooreTest.java b/src/test/java/com/thealgorithms/others/BoyerMooreTest.java
@@ -11,12 +11,22 @@
 public class BoyerMooreTest {
 
     @ParameterizedTest
-    @MethodSource("inputStream")
-    void numberTests(int expected, int[] input) {
-        Assertions.assertEquals(expected, BoyerMoore.findmajor(input));
+    @MethodSource("inputStreamWithExistingMajority")
+    void checkWhenMajorityExists(int expected, int[] input) {
+        Assertions.assertEquals(expected, BoyerMoore.findMajor(input).get());
     }
 
-    private static Stream<Arguments> inputStream() {
-        return Stream.of(Arguments.of(5, new int[] {5, 5, 5, 2}), Arguments.of(10, new int[] {10, 10, 20}), Arguments.of(10, new int[] {10, 20, 10}), Arguments.of(10, new int[] {20, 10, 10}), Arguments.of(-1, new int[] {10, 10, 20, 20, 30, 30}), Arguments.of(4, new int[] {1, 4, 2, 4, 4, 5, 4}));
+    private static Stream<Arguments> inputStreamWithExistingMajority() {
+        return Stream.of(Arguments.of(5, new int[] {5, 5, 5, 2}), Arguments.of(10, new int[] {10, 10, 20}), Arguments.of(10, new int[] {10, 20, 10}), Arguments.of(10, new int[] {20, 10, 10}), Arguments.of(4, new int[] {1, 4, 2, 4, 4, 5, 4}), Arguments.of(-1, new int[] {-1}));
+    }
+
+    @ParameterizedTest
+    @MethodSource("inputStreamWithoutMajority")
+    void checkWhenMajorityExists(int[] input) {
+        Assertions.assertFalse(BoyerMoore.findMajor(input).isPresent());
+    }
+
+    private static Stream<Arguments> inputStreamWithoutMajority() {
+        return Stream.of(Arguments.of(new int[] {10, 10, 20, 20, 30, 30}), Arguments.of(new int[] {10, 20, 30, 40, 50}), Arguments.of(new int[] {1, 2}), Arguments.of(new int[] {}));
     }
 }
