import java.util.Arrays;

/**
 * Runnable companion for the Two Pointers concept article.
 * Arrays and strings must be non-null. Sorted methods require ascending input.
 */
public final class TwoPointerExamples {
    private TwoPointerExamples() {}

    public static boolean isPalindrome(String text) {
        int left = 0;                       // First unchecked character.
        int right = text.length() - 1;       // Last unchecked character.

        while (left < right) {              // A distinct mirrored pair remains.
            if (text.charAt(left) != text.charAt(right)) {
                return false;              // One mismatch disproves the palindrome.
            }
            left++;                        // This left character is now checked.
            right--;                       // Its mirrored partner is checked too.
        }
        return true;                       // All required pairs matched.
    }

    public static int[] findPair(int[] values, long target) {
        int left = 0;
        int right = values.length - 1;

        while (left < right) {                 // Never reuse the same index.
            long sum = (long) values[left] + values[right]; // Add without int overflow.

            if (sum == target) {
                return new int[] {left, right}; // Return one valid pair of indexes.
            }
            if (sum < target) {
                left++;                       // This smallest value cannot work.
            } else {
                right--;                      // This largest value cannot work.
            }
        }
        return new int[] {-1, -1};             // No pair of different indexes exists.
    }

    public static int removeDuplicates(int[] values) {
        if (values.length == 0) {
            return 0;                          // There is no first value to keep.
        }
        int write = 1;                         // values[0] is already kept.

        for (int read = 1; read < values.length; read++) {
            if (values[read] != values[write - 1]) { // Compare with the last kept value.
                values[write] = values[read];   // Put the new value in the valid prefix.
                write++;                       // Advance only when we keep a value.
            }
        }
        return write;                          // Next free index equals kept length.
    }

    public static int[] mergeSorted(int[] first, int[] second) {
        int[] result = new int[first.length + second.length];
        int i = 0;                             // Next unused value in first.
        int j = 0;                             // Next unused value in second.
        int write = 0;                         // Next output position.

        while (i < first.length && j < second.length) { // Both values must exist.
            if (first[i] <= second[j]) {        // Prefer first on a tie.
                result[write++] = first[i++];   // Copy, then advance source and output.
            } else {
                result[write++] = second[j++];
            }
        }
        while (i < first.length) {              // second may have run out first.
            result[write++] = first[i++];
        }
        while (j < second.length) {             // first may have run out first.
            result[write++] = second[j++];
        }
        return result;
    }

    public static final class ListNode {
        public final int value;
        public ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }

    public static ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) { // A two-link move is safe.
            slow = slow.next;                      // One link per round.
            fast = fast.next.next;                 // Two links per round.
        }
        return slow;                               // null for an empty list.
    }

    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) { // Stop if the list has an end.
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {                    // Same node object, not equal values.
                return true;
            }
        }
        return false;                              // fast reached the end.
    }

    public static int expandLength(String text, int left, int right) {
        while (left >= 0 && right < text.length() // Both boundary characters exist.
                && text.charAt(left) == text.charAt(right)) {
            left--;                              // Try the next outer pair.
            right++;
        }
        return right - left - 1;                  // Last valid range: left+1..right-1.
    }

    public static void main(String[] args) {
        System.out.println("level is a palindrome: " + isPalindrome("level"));
        System.out.println("apple is a palindrome: " + isPalindrome("apple"));
        int[] values = {1, 2, 6, 9, 12, 15, 17};
        System.out.println("Pair indexes for 24: " + Arrays.toString(findPair(values, 24)));
        int[] repeated = {1, 1, 2, 2, 3};
        int length = removeDuplicates(repeated);
        System.out.println("Unique prefix: " + Arrays.toString(Arrays.copyOf(repeated, length)));
        System.out.println("Merged: " + Arrays.toString(mergeSorted(
                new int[] {1, 4, 6, 9, 10}, new int[] {9, 10, 16, 22, 30})));
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println("Middle: " + middleNode(head).value);
        System.out.println("Has a cycle: " + hasCycle(head));
        head.next.next.next.next.next = head.next; // Deliberately create a cycle.
        System.out.println("Has a cycle after linking tail to node 2: " + hasCycle(head));
        System.out.println("Odd expansion length: " + expandLength("level", 2, 2));
        System.out.println("Even expansion length: " + expandLength("abba", 1, 2));
    }
}
