פעולות לבגרות

public class Helpy
{
    // -------------------------------------------------------------
    //                      ARRAY
    //create a new arr: {type}[] myIntArray = new {type}[3];
    //
    //
    // כדי לשנות למינימום צריך לשנות את הסימן
    // מוצא את ה אינדקס של האיבר הכי גדול
    public static int maxI(int[] arr) {
        int max = arr[0];
        for (int i=1;i<arr.length;i++) {
            if (max<arr[i]) max = arr[i];
        }
        for (int i=1;i<arr.length;i++) {
            if (max == arr[i])  return (i);

        }
        return (1234);
    }

    public static int[] copyArr(int[]arr) {
        int[]copyArr = new int[arr.length];
        for (int i=0; i<arr.length; i++) {
            copyArr[i] = arr[i];
        }
        return copyArr;
    }


    // בודק אם בסדר מסוים כדי לשנות סדר צריך לשנות את הסימן
    public static boolean inOrder(int[]arr) {
        for (int i = 0; i <arr.length-1;i++) {
            if (arr[i]<arr[i+1]) return (false);}
        return (true);}
    // מחליף בין 2 איברים
    public static void change (int[] arr,int x , int y ) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

    // מסדר
    public static void arrange ( int[] arr) {



    // left - big   right - small
        int counter = 0;
        for (int i = 1; i <arr.length;i++) {
            counter++;
            if (i==arr.length-1) i=1;
            if (arr[i]<arr[i+1]) change(arr,i,i+1);
            if (arr[i]>arr[i-1]) change(arr,i,i-1);

            if (inOrder(arr)) break;
            hhjhjk

        }
        System.out.println(counter);
        }






    //  ------------------------------------------------------------
    //                      LIST / NODE
    //create new node: Node <Integer> name = new Node<Integer>
    //

    // מעתיק node
    public static Node<Integer> copyList(Node<Integer> l) {
        Node<Integer> newList = null;
        while(l != null){
            newList = new Node<Integer>(l.getValue(), newList);
            l = l.getNext();
        }
        return newList;
    }

    //list length
    public static int listLength(Node<Integer> l) {
        int m = 1;
        while (l.hasNext()) {
            m++;
            l = l.getNext();
        }
        return m;
    }

    //מוסיף לרשימה ערך
    public static void addToList(Node<Integer> list, int n){
        Node<Integer> node = new Node<Integer>(n);
        while (list.hasNext()){
            list = list.getNext();
        }
        list.setNext(node);
    }
    // לוקח איבר מחזרים אם קיים ברשימה
    public static boolean existInList(Node<Integer> l, int n){
        Node<Integer> pos = l;
        while (pos != null)
        {
            if (pos.getValue() == n)
                return true;
            pos = pos.getNext();
        }
        return false;}
        // סכום רשימה

    public static int sumList(Node<Integer> l){
        int sum = 0;
        Node<Integer> first = l;
        while (first != null)
        {
            sum += first.getValue();
            first = first.getNext();
        }
        return sum;
    }

    public static int placeInList(Node<Integer> node, int value) {
        //       טענת כניסה: הפעולה מקבלת שרשרת חוליות של מספרים שלמים ומספר שלם
        //       טענת יציאה: הפעולה מחזירה את המקום של המספר השלם בשרשרת. אם הוא לא קיים יוחזר הערך 1
        //       סיבוכיות זמן ריצה: O(n)
        Node<Integer> p = node;
        int i=0;
        while (p!=null){
            if (p.getValue()==value)
                return i;
            i++;
            p=p.getNext();
        }
        return -1;
    }



    public static <T> Node<T> removeNodeFromList(Node<T> list, Node<T> p) {
        //       p טענת כניסה: הפעולה מקבלת שרשרת חוליות וחוליה להסרה
        //       טענת יציאה: הפעולה מסירה את החוליה מהשרשרת
        //       סיבוכיות זמן ריצה: O(n)
        if (list.getValue() == p.getValue()) {
            list = list.getNext();
            return list;
        }
        else {
            Node<T> prev = list;
            while (prev!= null && prev.hasNext()) {
                if (prev.getNext().getValue()==p.getValue())
                    prev.setNext(prev.getNext().getNext());
                prev = prev.getNext();
            }
            return list;
        }
    }

    public static Node<Integer> insertSortedList(Node<Integer> l, int x) {
        //       טענת כניסה: הפעולה מקבלת שרשרת חוליות ממויינת ומספר שלם
        //       טענת יציאה: הפעולה מכניסה באופן ממויין את המספר לשרשרת
        //       סיבוכיות זמן ריצה: O(n)
        if (l==null) {
            l = new Node<Integer>(x);
            return l;
        }
        Node<Integer> p = l, p1 = l.getNext();
        Node<Integer> tmp = new Node<Integer>(x);
        if (x<l.getValue()) {
            tmp.setNext(l);
            l=tmp;
            return l;
        }
        while (p1!=null && p1.getValue()<x){
            p = p1;
            p1 = p1.getNext();
        }
        tmp.setNext(p1);
        p.setNext(tmp);
        return l;
    }

    public static Node<Integer> sortList(Node<Integer> l) {
        //       טענת כניסה: הפעולה מקבלת שרשרת חוליות של מספרים שלמים
        //       טענת יציאה: הפעולה ממיינת את השרשרת בסדר עולה
        //       סיבוכיות זמן ריצה: O(n^2)
        Node<Integer> l1 = null, p=l;
        int x;
        while (p!=null) {
            x = p.getValue();
            l1 = insertSortedList(l1, x);  // !
            p = p.getNext();
        }
        return l;
    }

    // בודק כמה פעמים מספר מופיע ברשימה
    public static int howMuchInList(Node<Integer> l, int n){
        int count = 0;
        Node<Integer> pos = l;
        while (pos != null)
        {
            if (pos.getValue() == n)
                count++;
            pos = pos.getNext();
        }
        return count;
    }
    // איבר הכי גדול ברשימה
    public static int MaxList(Node<Integer>l) {
        int max = l.getValue();
        while (l != null) {
            if (l.getValue() > max)
                max = l.getValue();
            l = l.getNext();
        }
        return max;
    }
    // מעביר רשימה למחסנית
    public static Stack<Integer> listToStuck(Node<Integer> l){
        Stack<Integer> s = new Stack<Integer>();
        while(l.hasNext())
        {
            s.push(l.getValue());
            l = l.getNext();
        }
        return s;
    }


    // בודק אם הסדרה מסודרת בסדר עולה או יורד מסויים
    public static int difference(int num1, int num2) {
        return (num1-num2);
    }


    public static boolean chain(Node<Integer>n)  {
        int old_num=n.getValue();
        int old_sum =difference(old_num,n.getNext().getValue());
        while (n.hasNext()) {
            n=n.getNext();
            int num=n.getValue();
            int  sum = difference(old_num,num);
            if (sum!=old_sum) return (false);
            old_num=num;
            old_sum = sum;}
        return (true);
    }




    //     ------------------------------------------------------------
    //                          STACK

    //מעתיק מחסנית
    public static <T> Stack<T> copyStack(Stack<T>s ) {
        Stack <T> newS = new Stack<T>();
        Stack <T> tmp = new Stack<T>();
        while(!s.isEmpty())
            tmp.push(s.pop());
        while (!tmp.isEmpty())
        { newS.push(tmp.top()); s.push(tmp.pop()); }
        return (newS);

    }



    // הופך מחסנית
    public static Stack<Integer> flipStack(Stack<Integer> s){
        Stack<Integer> newS = new Stack<Integer>();
        Stack<Integer> tmp = copyStack(s); //!
        while (!tmp.isEmpty())
            newS.push(tmp.pop());
        return newS;
    }
    // בודק אם איבר קיים ברשימה
    public static boolean isExistStack(Stack<Integer> s, int n)
    {
        Stack<Integer> sCopy = copyStack(s); //!
        while (!sCopy.isEmpty())
            if (sCopy.pop() == n)
                return true;
        return false;
    }
    // בודק אם איבר קיים בצורה רקורסיבית
    public static boolean isExistStackRec(Stack<Integer> s, int n)
    {
        if (s.isEmpty())
            return false;
        int x = s.pop();
        boolean exists = (x == n || isExistStackRec(s, n));
        s.push(x); //לאחר הקריאה הרקורסיבית, האיבר שנשלף נדחף בחזרה אל תוך המחסנית
        return exists;
    }
    // סכום stack
    public static int sumStack(Stack<Integer> s)
    {
        int sum = 0;
        Stack<Integer> sCopy = copyStack(s); //!
        while (!sCopy.isEmpty())
            sum += sCopy.pop();
        return sum;
    }
    // אורך של המחסנית
    public static int lengthStack(Stack<Integer> s)
    {
        int length = 0;
        Stack<Integer> sCopy = copyStack(s); //!
        while (!sCopy.isEmpty())
        {
            length++;
            sCopy.pop();
        }
        return length;
    }
    // חותך חלק עליון של stack
    public static Stack<Integer> cutUpperStack(Stack<Integer> s){
        Stack<Integer> temp = new Stack<Integer>();
        Stack<Integer> newS = new Stack<Integer>();

        temp = copyStack(s);
        int length = lengthStack(s);
        for (int i=0; i<length/2; i++) {
            newS.push(temp.pop());

        }
        return newS;
    }
        // חותך חלק תחתון של מחסנית
    public static Stack<Integer> cutLowerStack(Stack<Integer> s){
        Stack<Integer> temp = new Stack<Integer>();
        Stack<Integer> newS = new Stack<Integer>();

        temp = copyStack(s);
        temp = flipStack(temp);
        int length = lengthStack(s);
        for (int i=0; i<length/2; i++) {
            newS.push(temp.pop());

        }
        return newS;
    }
    // כמה פעמים איבר מופיע במחסנית
    public static int howManyStack(Stack<Integer> s, int n)
    {
        int count = 0;
        Stack<Integer> tmp = copyStack(s); //!
        while (!tmp.isEmpty())
            if (tmp.pop() == n)
                count++;
        return count;
    }
    // מוחק איבר אחרון במחסנית
    public static void removeLastStack(Stack<Integer> s){
        flipStack(s);
        s.pop();
        flipStack(s);

    }
    // מוחק איבר ממחסנית
    public static void removeFromStack(Stack<Integer> s, int n)
    {
        Stack<Integer> tmp = flipStack(s);
        while (!s.isEmpty())
            s.pop();
        while (!tmp.isEmpty())
        {
            int x = tmp.pop();
            if (x != n)
                s.push(x);
        }
    }

    public static int maxStack(Stack<Integer> s) {
        //       טענת כניסה: הפעולה מקבלת מחסנית מכל סוג שניתן להשוואה // (
        //       טענת יציאה: הפעולה מחזירה את האיבר הגדול ביותר, או את האיבר שמגיע אחרון במילון //
        //       סיבוכיות זמן ריצה: O(n)
        Stack<Integer> temp = copyStack(s);
        int max = temp.top();
        while (!temp.isEmpty()) {
            if (temp.top() > max)
                max = temp.top();
            temp.pop();
        }
        return max;
    }

    public static void sortStack(Stack<Integer> s) {
        //       טענת כניסה: הפעולה מקבלת מחסנית
        //       טענת יציאה: הפעולה ממיינת את המחסנית כך שהערכים הגדולים נמצאים למטה
        //        O(n^2)
        Stack <Integer> s1 = new Stack<Integer>();
        Stack <Integer> s2 = new Stack<Integer>();
        while(!s.isEmpty()) {
            if (s1.isEmpty()) s1.push(s.pop());
            else {
                while(!s1.isEmpty() && s.top() < s1.top())
                    s2.push(s1.pop());
                s1.push(s.pop());
                while (!s2.isEmpty()) s1.push(s2.pop());
            }
        }
        while(!s1.isEmpty()) s.push (s1.pop());
    }

    //   ------------------------------------------------------------
    //                      QUEUE


    // מעתיק תור
    public static <T> Queue<T> copyQueue(Queue<T> q)
    {
        Queue<T> newQ = new Queue<T>();
        Queue<T> tmp = new Queue<T>();
        while (!q.isEmpty())
        {
            newQ.insert(q.head());
            tmp.insert(q.remove());
        }
        while (!tmp.isEmpty())
            q.insert(tmp.remove());
        return newQ;
    }
    // בודק אם איבר קיים בתור
    public static boolean existInQueue(Queue<Integer> q, int n)
    {
        Queue<Integer> qCopy = copyQueue(q); //!
        while (!qCopy.isEmpty())
            if (qCopy.remove() == n)
                return true;
        return false;
    }
    // מחזיר סכום של ה q
    public static int sumQueue(Queue<Integer> q)
    {
        int sum = 0;
        Queue<Integer> qCopy = copyQueue(q); //!
        while (!qCopy.isEmpty())
            sum += qCopy.remove();
        return sum;
    }
    // מחזיר אורך תור
    public static int lengthQueue(Queue<Integer> q)
    {
        int length = 0;
        Queue<Integer> qCopy = copyQueue(q); //!
        while (!qCopy.isEmpty())
        {
            length++;
            qCopy.remove();
        }
        return length;
    }

    // מחזיר כמה המספר מופיע בתור
    public static int howManyQueue(Queue<Integer> q, int n)
    {
        int count = 0;
        Queue<Integer> tmp = copyQueue(q); //!
        while (!tmp.isEmpty())
            if (tmp.remove() == n)
                count++;
        return count;
    }

    // מוחק מהתור איבר
    public static void removeFromQueue(Queue<Integer> q, int n)
    {
        Queue<Integer> tmp = copyQueue(q); //!
        while (!q.isEmpty())
            q.remove();
        while (!tmp.isEmpty())
        {
            int x = tmp.remove();
            if (x != n)
                q.insert(x);
        }
    }



    // בודק אם התור עולה
    public static boolean QGoesUp(Queue<Integer> q) {
        Queue<Integer> a = copyQueue(q); // change the sign if u want it to go down
        int old_q = a.remove();
        while (!a.isEmpty()) {
            int q1 = a.remove();

            if (old_q>q1) return (false);
            old_q=q1;

        }
        return (true);
    }
    // מחזיר את האיבר הכי גדול או קטן בטור
    //1 הכי גדול
    //-1 בשביל הכי קטן
    /// מחזריר אינדקס
    public static int getMaxOrLowQ(Queue<Integer>q,int sign) {
        Queue<Integer>q1 =copyQueue(q);
        int mon=q1.remove();
        while (q1.isEmpty()) {
            if (sign==1)mon=(Math.max(mon,q1.remove()));
            if (sign==-1)mon=(Math.min(mon,q1.remove()));
        }
        q1 =copyQueue(q);
        int c=0;
        // מחזיר אינדקס
        //
        while (q1.isEmpty()) {
            int x=q1.remove();
            c=c++;
            if (x==mon);
                return (c);
        }
        return (c);
    }


    public static void flipQueue(Queue<Integer> q) {
        Stack <Integer> temp = new Stack<Integer>();
        while (!q.isEmpty())
            temp.push(q.remove());
        while(!temp.isEmpty())
            q.insert(temp.pop());
    }

    // מסדר תור לפי גודל
    public static void sortQueue(Queue<Integer> q) {
        Queue<Integer> temp;
        temp = copyQueue(q);

        while(!q.isEmpty()) // Empty Queue
            q.remove();

        while (!temp.isEmpty()) { // Insert from high to low
            int max = maxQueue(temp), howMany = howManyQueue(temp, max);
            for (int i=0; i<howMany; i++)
                q.insert(max);
            removeFromQueue(temp, max);
        }
    }

    public static boolean isSorted(Queue<Integer> q) {
        // Checks if the queue is sorted high --> low
        Queue<Integer> a = copyQueue(q);
        int old_q = a.remove();
        while (!a.isEmpty()) {
            int q1 = a.remove();
            if (old_q>q1)
                return false;
            old_q=q1;
        }
        return true;}




    //   ------------------------------------------------------------
    //                          BINNODE


    // מעתיק עץ
    public static BinNode<Integer> copyTree(BinNode<Integer> bt)
    {
        if (bt == null)
            return null;
        BinNode<Integer> left = copyTree(bt.getLeft());
        BinNode<Integer> right = copyTree(bt.getRight());
        return new BinNode<Integer>(left, bt.getValue(), right); //להחליף ימין ושמאל לקבלת עץ מראה
    }
    // קיים בעץ
    public static boolean isExistTree(BinNode<Integer> bt, int n)
    {
        if (bt == null)
            return false;
        return (bt.getValue() == n || isExistTree(bt.getLeft(), n) || isExistTree(bt.getRight(), n));
    }


    // סכום עץ
    public static int sumTree(BinNode<Integer> bt)
    {
        if (bt == null)
            return 0;
        return bt.getValue() + sumTree(bt.getLeft()) + sumTree(bt.getRight());
    }


    // אין בנים (עלה)
    public static boolean isLeaf(BinNode<Integer> bt)
    {
        return (bt.getLeft() == null && bt.getRight() == null);
    }
    //
    public static void printPreOrder(BinNode<Integer> bt)
    {
        if (bt != null)
        {
            System.out.println(bt.getValue());
            printPreOrder(bt.getLeft());
            printPreOrder(bt.getRight());
        }
    }

    public static void printInOrder(BinNode<Integer> bt)
    {
        if (bt != null)
        {
            printInOrder(bt.getLeft());
            System.out.println(bt.getValue());
            printInOrder(bt.getRight());
        }
    }

    public static void printPostOrder(BinNode<Integer> bt)
    {
        if (bt != null)
        {
            printPostOrder(bt.getLeft());
            printPostOrder(bt.getRight());
            System.out.println(bt.getValue());
        }
    }

    public static void printByLevels(BinNode<Integer> t) {
        //       טענת כניסה: הפעולה מקבלת עץ בינארי של מספרים שלמים
        //       טענת יציאה: הפעולה מדפיסה את ערכי הצמתים בעץ לפי הרמה שלהם - כל צמתי העץ ברמה כלשהי יודפסו
        //       אחד אחרי השני
        //       סיבוכיות זמן ריצה: O(n)
        Queue<BinNode<Integer>> q = new Queue<BinNode<Integer>>();
        q.insert(t);
        while (!q.isEmpty()) {
            BinNode<Integer> current = q.remove();
            System.out.println(current.getValue());
            if (current.getLeft() != null)
                q.insert(current.getLeft());
            if (current.getRight() != null)
                q.insert(current.getRight());
        }
    }

    public static void printValuesInLevel(BinNode<Integer> t, int k) {
        //      טענת כניסה: הפעולה מקבלת עץ בינארי ומספר שלם k
        //      טענת יציאה: הפעולה מדפיסה את הערכים בעץ ברמה k
        //      סיבוכיות זמן ריצה: O(n) //
        if (t==null)
            System.out.println("null");
        if (k==0)
            System.out.print(t.getValue()+" ");
        if (k>0) {
            printValuesInLevel(t.getLeft(), k-1);
            printValuesInLevel(t.getRight(), k-1);
        }
    }
    // סופר כמה איברים יש
    public static int countNodes(BinNode<Integer> bt)
    {
        if (bt == null)
            return 0;
        return 1 + countNodes(bt.getLeft()) + countNodes(bt.getRight());
    }
    // סופר עלים
    public static int countLeaves(BinNode<Integer> bt)
    {
        if (bt == null)
            return 0;
        if (isLeaf(bt)) //!
            return 1;
        return countLeaves(bt.getLeft()) + countLeaves(bt.getRight());
    }
    // סופר את הגובה של העץ המקסימלי
    public static int height(BinNode<Integer> bt)
    {
        if (bt == null)
            return -1;
        return 1 + Math.max(height(bt.getLeft()), height(bt.getRight()));
    }
 // מוצא ערך מקסימלי בעץ
    public static int maxValue(BinNode<Integer> bt)
    {
        if (isLeaf(bt)) //!
            return bt.getValue();
        int maxLeft = maxValue(bt.getLeft());
        int maxRight = maxValue(bt.getRight());
        return Math.max(bt.getValue(), Math.max(maxLeft, maxRight));
    }
    // מחזיר את הערך שמעל האיבר
    public static BinNode<Integer> getFather(BinNode<Integer> source, BinNode<Integer> son)
    {
        if (source == null)
            return null;
        if (source.getLeft() == son || source.getRight() == son)
            return source;
        BinNode<Integer> left = getFather(source.getLeft(), son);
        if (left != null)
            return left;
        return getFather(source.getRight(), son);
    }

    //מדפיס איברים בעץ
    public static int howManyTree(BinNode<Integer> bt, int n)
    {
        if (bt == null)
            return 0;
        if (bt.getValue() == n)
            return 1 + howManyTree(bt.getLeft(), n) + howManyTree(bt.getRight(), n);
        return howManyTree(bt.getLeft(), n) + howManyTree(bt.getRight(), n);
    }

    // מדפיס מספר איברים בכל רמה
    public static int nodesInLevel(BinNode<Integer> bt, int level)  // Level 0 = first (root)
    {
        if (bt == null)
            return 0;
        if (level == 0)
            return 1;
        return nodesInLevel(bt.getLeft(), level - 1) + nodesInLevel(bt.getRight(), level - 1);
    }
    // מוחק איבר מעץ
    public static BinNode <Integer> RemoveFromBin(BinNode<Integer> p, int num)
    {
        BinNode <Integer>temp;
        while (p !=null && p.hasRight()) {
            if (num==p.getRight().getValue()){
                temp=p.getRight().getRight();
                p.setRight(temp);
                temp=null;
            }
            else p=p.getRight();
        }
        return p;
    }


    public static boolean isBST(BinNode<Integer> bt)
    {
        if (bt == null)
            return true;
        if (bt.getLeft() != null && bt.getLeft().getValue() >= bt.getValue())
            return false;
        if (bt.getRight() != null && bt.getRight().getValue() < bt.getValue())
            return false;
        return isBST(bt.getLeft()) && isBST(bt.getRight());
    }
    // טענת כניסה: הפעולה מקבלת עץ בינארי של מספרים שלמים ומספר שלם
    // טענת יציאה: הפעולה מוסיפה את המספר שהתקבל לעץ החיפוש הבינארי
    public static void addToBST(BinNode<Integer> bt, int n)
    {
        if (bt.getLeft() == null && n < bt.getValue())
            bt.setLeft(new BinNode<Integer>(n));
        else if (bt.getRight() == null && n >= bt.getValue())
            bt.setRight(new BinNode<Integer>(n));
        else if (n < bt.getValue())
            addToBST(bt.getLeft(), n);
        else addToBST(bt.getRight(), n);
    }

}