FirstBatch.java

import java.util.Arrays;
import java.util.function.IntPredicate;
import java.util.stream.IntStream;

/**
 * A first batch of array algorithms demonstrating loops, two-pointer
 * techniques, and functional predicates.
 * <p>
 * Updated for Java 21+ with {@link IntPredicate} for flexible filtering,
 * streams where they improve clarity, and better naming throughout.
 *
 * @author Ilkka Kokkarinen
 */
public class FirstBatch {

 // -----------------------------------------------------------------------
 // Counting and collecting elements that satisfy a predicate.
 // Demonstrates: IntPredicate (functional interface), higher-order methods.
 //
 // The old version hardcoded an "isFunny" test. The modern version accepts
 // any IntPredicate, so callers choose the criterion:
 //
 // countMatching(a, n -> n % 3 == 0) // divisible by 3
 // countMatching(a, n -> isPrime(n)) // primes
 // countMatching(a, FirstBatch::isPrime) // same, method reference
 // -----------------------------------------------------------------------

 /**
 * Count how many elements in the array satisfy the given predicate.
 *
 * @param values the array to examine
 * @param predicate the condition to test each element against
 * @return the count of matching elements
 */
 public static int countMatching(int[] values, IntPredicate predicate) {
 int count = 0;
 for (int value : values) {
 if (predicate.test(value)) { count++; }
 }
 return count;
 }

 /**
 * Collect all elements satisfying the predicate into a new array.
 *
 * @param values the array to filter
 * @param predicate the condition to test each element against
 * @return a new array containing only the matching elements, in order
 */
 public static int[] collectMatching(int[] values, IntPredicate predicate) {
 // With streams, this is a clean one-liner. Under the hood it does
 // essentially the same two-pass (or buffer-and-trim) work.
 return Arrays.stream(values)
 .filter(predicate)
 .toArray();
 }

 // A sample predicate for demonstration purposes.
 public static boolean isDivisibleByThree(int n) {
 return n % 3 == 0;
 }

 // -----------------------------------------------------------------------
 // Selection sort — our first (and worst) sorting algorithm.
 // Demonstrates: nested loops, in-place swapping, finding a minimum.
 // -----------------------------------------------------------------------

 /**
 * Find the index of the smallest element in {@code array[from..to]}
 * (inclusive on both ends).
 */
 private static int indexOfMinimum(int[] array, int from, int to) {
 int minIndex = from;
 for (int i = from + 1; i <= to; i++) {
 if (array[i] < array[minIndex]) { minIndex = i; }
 }
 return minIndex;
 }

 /**
 * Sort the array in place using selection sort. Time complexity is
 * O(n²) regardless of input — there are far better algorithms, but
 * this one is easy to understand and prove correct.
 *
 * @param array the array to sort
 */
 public static void selectionSort(int[] array) {
 for (int i = 0; i < array.length - 1; i++) {
 int minIndex = indexOfMinimum(array, i, array.length - 1);
 // Swap array[i] with the smallest remaining element.
 int temp = array[i];
 array[i] = array[minIndex];
 array[minIndex] = temp;
 }
 }

 // -----------------------------------------------------------------------
 // Three two-pointer array algorithms of similar spirit.
 // Each walks through one or two sorted arrays in a single pass.
 // -----------------------------------------------------------------------

 /**
 * Interleave elements of two arrays: take one from {@code first}, one
 * from {@code second}, alternating. When one runs out, append the rest
 * of the other. (This is sometimes called a "riffle" or "zip".)
 *
 * @param first the first array
 * @param second the second array
 * @return the interleaved result
 */
 public static int[] zip(int[] first, int[] second) {
 var result = new int[first.length + second.length];
 int i = 0, dest = 0;
 while (i < first.length && i < second.length) {
 result[dest++] = first[i];
 result[dest++] = second[i];
 i++;
 }
 while (i < first.length) { result[dest++] = first[i++]; }
 while (i < second.length) { result[dest++] = second[i++]; }
 return result;
 }

 /**
 * Merge two sorted arrays into one sorted array. Both inputs must
 * already be sorted in ascending order. This is the key subroutine
 * of merge sort.
 *
 * @param first the first sorted array
 * @param second the second sorted array
 * @return a new sorted array containing all elements of both inputs
 */
 public static int[] merge(int[] first, int[] second) {
 var result = new int[first.length + second.length];
 int i = 0, j = 0, dest = 0;
 while (i < first.length && j < second.length) {
 if (first[i] <= second[j]) { result[dest++] = first[i++]; }
 else { result[dest++] = second[j++]; }
 }
 while (i < first.length) { result[dest++] = first[i++]; }
 while (j < second.length) { result[dest++] = second[j++]; }
 return result;
 }

 /**
 * Compute the intersection of two sorted arrays — elements that appear
 * in both. Both inputs must be sorted in ascending order. The result
 * preserves duplicates only if they appear in both arrays.
 *
 * @param first the first sorted array
 * @param second the second sorted array
 * @return a new sorted array of common elements
 */
 public static int[] intersection(int[] first, int[] second) {
 // IntStream.Builder avoids the two-pass approach (count then fill)
 // and the boxing overhead of ArrayList<Integer>.
 var builder = IntStream.builder();
 int i = 0, j = 0;
 while (i < first.length && j < second.length) {
 if (first[i] < second[j]) { i++; }
 else if (first[i] > second[j]) { j++; }
 else {
 builder.add(first[i]);
 i++;
 j++;
 }
 }
 return builder.build().toArray();
 }

 // -----------------------------------------------------------------------
 // Remove consecutive duplicates from a sorted array.
 // -----------------------------------------------------------------------

 /**
 * Return a new array with consecutive duplicates removed. The input
 * must be sorted so that equal elements are adjacent.
 *
 * @param sorted the sorted input array
 * @return a new array with duplicates removed
 */
 public static int[] removeDuplicates(int[] sorted) {
 if (sorted.length == 0) { return sorted; }
 // IntStream with a stateful filter is one option, but the explicit
 // approach is clearer and avoids concerns about stream ordering.
 // Single pass: write each element that differs from its predecessor.
 var result = new int[sorted.length]; // upper bound on size
 result[0] = sorted[0];
 int dest = 1;
 for (int i = 1; i < sorted.length; i++) {
 if (sorted[i] != sorted[i - 1]) {
 result[dest++] = sorted[i];
 }
 }
 return Arrays.copyOf(result, dest);
 }

 // -----------------------------------------------------------------------
 // Longest ascending run — a one-pass algorithm with state variables.
 // -----------------------------------------------------------------------

 /**
 * Find the length of the longest strictly ascending run in the array.
 * Demonstrates the pattern of maintaining "current" and "best so far"
 * state variables that are updated at each step.
 *
 * @param values the array to examine
 * @return the length of the longest ascending run (at least 1 if non-empty)
 */
 public static int longestAscending(int[] values) {
 if (values.length == 0) { return 0; }
 int currentRun = 1;
 int longestRun = 1;
 for (int i = 1; i < values.length; i++) {
 if (values[i] > values[i - 1]) {
 currentRun++;
 if (currentRun > longestRun) { longestRun = currentRun; }
 } else {
 currentRun = 1;
 }
 }
 return longestRun;
 }

 // -----------------------------------------------------------------------
 // Roman numeral encoding and decoding.
 // -----------------------------------------------------------------------

 // Parallel arrays: each Roman symbol paired with its decimal value.
 // Ordered from largest to smallest for the greedy encoding algorithm.
 private static final String[] ROMAN_SYMBOLS = {
 "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
 };
 private static final int[] ROMAN_VALUES = {
 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
 };

 /**
 * Encode a positive integer as a Roman numeral string.
 * Uses a greedy algorithm: repeatedly subtract the largest possible
 * Roman value and append its symbol.
 *
 * @param number the positive integer to encode (must be ≥ 1)
 * @return the Roman numeral representation
 * @throws IllegalArgumentException if number is less than 1
 */
 public static String romanEncode(int number) {
 if (number < 1) {
 throw new IllegalArgumentException("Cannot convert " + number + " to Roman");
 }
 var result = new StringBuilder();
 int symbolIndex = 0;
 while (number > 0) {
 while (number >= ROMAN_VALUES[symbolIndex]) {
 result.append(ROMAN_SYMBOLS[symbolIndex]);
 number -= ROMAN_VALUES[symbolIndex];
 }
 symbolIndex++;
 }
 return result.toString();
 }

 // For decoding, we only need the seven basic symbols and their values.
 private static final String BASIC_SYMBOLS = "MDCLXVI";
 private static final int[] BASIC_VALUES = {1000, 500, 100, 50, 10, 5, 1};

 /**
 * Decode a Roman numeral string to its integer value. Reads right to left:
 * if a symbol's value is less than the previous one, it is subtracted
 * (this handles cases like IV = 4 and IX = 9).
 *
 * @param roman the Roman numeral string (case-insensitive)
 * @return the decoded integer value
 * @throws IllegalArgumentException if the string contains invalid characters
 */
 public static int romanDecode(String roman) {
 roman = roman.toUpperCase();
 int result = 0;
 int previousValue = 0;
 // Process right to left so we can detect subtractive notation.
 for (int i = roman.length() - 1; i >= 0; i--) {
 int symbolIndex = BASIC_SYMBOLS.indexOf(roman.charAt(i));
 if (symbolIndex == -1) {
 throw new IllegalArgumentException(
 "Illegal Roman numeral character: " + roman.charAt(i));
 }
 int currentValue = BASIC_VALUES[symbolIndex];
 // Subtractive rule: IV means 5 - 1, not 5 + 1.
 result += (currentValue < previousValue) ? -currentValue : currentValue;
 previousValue = currentValue;
 }
 return result;
 }

 /**
 * Verify that encoding and decoding are perfect inverses for 1..4999.
 */
 public static boolean testRomanConversions() {
 return IntStream.rangeClosed(1, 4999)
 .allMatch(n -> romanDecode(romanEncode(n)) == n);
 }

 // -----------------------------------------------------------------------
 // Main method — exercise each example and display results.
 // -----------------------------------------------------------------------

 public static void main(String[] args) {

 // --- Predicate-based counting and collecting ---
 System.out.println("--- countMatching / collectMatching ---");
 int[] data = {3, 7, 9, 12, 15, 20, 21, 25, 30};
 System.out.printf("Data: %s%n", Arrays.toString(data));

 // Pass different predicates to the same method:
 IntPredicate divBy3 = FirstBatch::isDivisibleByThree;
 IntPredicate isEven = n -> n % 2 == 0;
 IntPredicate over15 = n -> n > 15;

 System.out.printf("Divisible by 3: count=%d, values=%s%n",
 countMatching(data, divBy3), Arrays.toString(collectMatching(data, divBy3)));
 System.out.printf("Even: count=%d, values=%s%n",
 countMatching(data, isEven), Arrays.toString(collectMatching(data, isEven)));
 System.out.printf("Greater than 15: count=%d, values=%s%n",
 countMatching(data, over15), Arrays.toString(collectMatching(data, over15)));

 // Predicates can also be composed with and/or/negate:
 IntPredicate divBy3AndEven = divBy3.and(isEven);
 System.out.printf("Div by 3 AND even: %s%n%n",
 Arrays.toString(collectMatching(data, divBy3AndEven)));

 // --- Selection sort ---
 System.out.println("--- selectionSort ---");
 int[] unsorted = {38, 27, 43, 3, 9, 82, 10};
 System.out.printf("Before: %s%n", Arrays.toString(unsorted));
 selectionSort(unsorted);
 System.out.printf("After: %s%n%n", Arrays.toString(unsorted));

 // --- Zip, merge, intersection ---
 System.out.println("--- zip / merge / intersection ---");
 int[] left = {1, 3, 5, 7, 9};
 int[] right = {2, 4, 6};
 System.out.printf("zip(%s, %s) = %s%n",
 Arrays.toString(left), Arrays.toString(right),
 Arrays.toString(zip(left, right)));
 System.out.printf("merge(%s, %s) = %s%n",
 Arrays.toString(left), Arrays.toString(right),
 Arrays.toString(merge(left, right)));
 int[] sorted1 = {1, 3, 5, 7, 9, 11};
 int[] sorted2 = {2, 3, 5, 8, 9, 13};
 System.out.printf("intersection(%s, %s) = %s%n%n",
 Arrays.toString(sorted1), Arrays.toString(sorted2),
 Arrays.toString(intersection(sorted1, sorted2)));

 // --- Remove duplicates ---
 System.out.println("--- removeDuplicates ---");
 int[] withDups = {1, 1, 2, 3, 3, 3, 4, 5, 5};
 System.out.printf("removeDuplicates(%s) = %s%n%n",
 Arrays.toString(withDups), Arrays.toString(removeDuplicates(withDups)));

 // --- Longest ascending run ---
 System.out.println("--- longestAscending ---");
 int[] sequence = {3, 5, 7, 2, 4, 6, 8, 10, 1};
 System.out.printf("longestAscending(%s) = %d%n%n",
 Arrays.toString(sequence), longestAscending(sequence));

 // --- Roman numerals ---
 System.out.println("--- Roman numerals ---");
 for (int n : new int[]{1, 4, 9, 42, 1999, 2025, 3888}) {
 String roman = romanEncode(n);
 int decoded = romanDecode(roman);
 System.out.printf("%4d → %-15s → %d%n", n, roman, decoded);
 }
 System.out.printf("%nRoundtrip test (1..4999): %s%n", testRomanConversions());
 }
}