package com.rustem.simplecrudapplication.model;

public class Main {
    public static void main(String[] args) {
        MyLinkedList<Object> myList = new MyLinkedList<>();

        for (int i = 0; i < 5_000_000; i++) {
            myList.add(i);
        }
        System.out.println("Закончили" + "\n");

        myList.lastNode.setNextN(myList.head.nextN.nextN.nextN.nextN.nextN.nextN.nextN.nextN.nextN.nextN); // возвращаем цикл на 10-ый элемент

        new Thread(() -> {
            long t1 = System.currentTimeMillis();
            System.out.println(myList.hasLoopN(myList.head) ? "Цикл есть" : "Цикла нет");
            long t2 = System.currentTimeMillis();
            System.out.println("Время на поиск цикла с шагом 1/N: " + (t2 - t1));
        }).start();

        new Thread(() -> {
            long t3 = System.currentTimeMillis();
            System.out.println(myList.hasLoop2(myList.head) ? "Цикл есть" : "Цикла нет");
            long t4 = System.currentTimeMillis();
            System.out.println("Время на поиск цикла с шагом 1/2: " + (t4 - t3));
        }).start();
    }
}

class Node<E> {
    E index;
    Node<E> nextN;

    void setNextN(Node<E> nextN) {
        this.nextN = nextN;
    }
}

class MyLinkedList<E> {
    Node<E> head;
    Node<E> lastNode;
    private int size;
    private int step2;
    private int step1;

    public int size() {
        return size;
    }

    /**
     * Возвращает элемент в указанной позиции в этом списке
     *
     * @param index индекс возвращаемого элемента
     * @return элемент в указанной позиции в этом списке
     */
    public E get(int index) {
        checkElementIndex(index);
        return node(index).index;
    }

    void printNodes() {
        Node<E> n = head;
        while (n != null) {
            System.out.print(n.index + " ");
            n = n.nextN;
        }
        System.out.println();
    }

    /**
     * Добавляет указанный элемент в конец списка.
     *
     * @param element элемент, который будет добавлен в этот список
     */
    void add(E element) {
        size++;
        Node<E> n = new Node<>();
        n.index = element;
        if (lastNode == null) {
            head = n;
            lastNode = n;
        } else {
            lastNode.nextN = n;
            lastNode = n;
        }
    }

    /**
     * первый метод проверяющий на зацикленность
     *
     * @param first первый элемент ноды
     */
    boolean hasLoopN(Node first) {
        if (first == null)
            return false;

        Node slow;
        Node fast;

        slow = fast = first;

        while (true) {

            slow = slow.nextN;

            if (fast.nextN != null) {
                fast = fast.nextN.nextN.nextN.nextN.nextN.nextN.nextN;
                step1++;
            } else {
                return false;
            }

            if (slow == null || fast == null) {
                return false;
            }

            if (slow == fast) {
                System.out.println("Количество итераций: " + step1);
                return true;
            }
        }
    }

    boolean hasLoop2(Node first) {
        if (first == null)
            return false;

        Node slow;
        Node fast;

        slow = fast = first;

        while (true) {

            slow = slow.nextN;

            if (fast.nextN != null) {
                fast = fast.nextN.nextN;
                step2++;
            } else {
                return false;
            }

            if (slow == null || fast == null) {
                return false;
            }

            if (slow == fast) {
                System.out.println("Количество итераций: " + step2);
                return true;
            }
        }
    }

    /**
     * Возвращает узел по указанному индексу.
     */
    private Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < size) {
            Node<E> x = head;
            for (int i = 0; i < index; i++)
                x = x.nextN;
            return x;
        }
        return null;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * Является ли аргумент индексом созданного элемента.
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }
}