/*

    Suggested solutions to exam TDA548 2017-10-26

*/

    // --------- 1 --------------  (4p)

    See lecture notes


    // --------- 2 --------------   (2p)

    int result = add(div(sub(7, 6), 5), 4);  // Type error, will not compile

    Reason: Result from div (double) can't be implicitly casted to int (add param's are int)

    NOTE: sub returns int but implicit cast to double (for div param) is ok.

    // --------- 3 -------------------  (4p)

    double sqrt(double n) {
        double xi = n;
        for (int i = 0; i < 5; i++) {
            double xiPlus1 = 0.5 * (xi + n / xi);
            xi = xiPlus1;
        }
        return xi;
    }

    // --------- 4 -------------------   (12p)

    // Other solutions possible
    int[] insert(int arr[], int[] elems, int position) {
        int[] tmp = new int[arr.length + elems.length];
        int k = 0;
        int n = 0;
        for (int i = 0; i < tmp.length; i++) {
            if (position <= i && i < position + elems.length) {
                if (!contains(arr, elems[n])) {
                    tmp[i] = elems[n];
                }
                n++;
            } else {
                tmp[i] = arr[k];
                k++;
            }
        }
        return removeZero(tmp);
    }

    // Func. decomp
    boolean contains(int[] arr, int elem) {
        for (int i : arr) {
            if (i == elem) {
                return true;
            }
        }
        return false;
    }

    // Func. decomp
    int[] removeZero(int[] arr) {
        int count = 0;
        for (int i : arr) {
            if (i == 0) {
                count++;
            }
        }
        int[] tmp = new int[arr.length - count];
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
               tmp[k] = arr[i];
                k++;
            }
        }
        return tmp;
    }


    // -------- 5 ---------       (6p)

    int maxNesting(String str) {
        int open = 0;
        int close = 0;
        int max = 0;
        int tmp = 0;
        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                open++;
                tmp++;
                if (tmp > max) {
                    max = tmp;
                }
            } else if (ch == ')') {
                close++;
                tmp--;
                if( close > open){
                    return -1;
                }
            } else {
                // Skip other chars
            }
        }
        if (open != close) {
            return -1;
        } else {
            return max;
        }
    }

    // -------- 6 ---------  (6p)

    // See link to image, on page close tho this link


    // ------- 7 -----------

   public class Cell {                              //(3)
        private int row;
        private int col;
        private String content;

        public Cell(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public void incCol() {
            col++;
        }

        public int getCol() {
            return col;
        }
    }


    public class Sheet {                                      //(4p)
        private final List cells = new ArrayList();
        private int maxRow;
        private int maxCol;

        public Sheet(int maxRow, int maxCol) {
            this.maxRow = maxRow;
            this.maxCol = maxCol;

            for (int row = 0; row < maxRow; row++) {
                for (int col = 0; col < maxCol; col++) {
                    cells.add(new Cell(row, col));
                }
            }
        }

        public void insertColumn(int colNumber) {           // (5p)
            for (Cell c : cells) {
                if (c.getCol() >= colNumber) {
                    c.incCol();
                }
            }
            for (int i = 0; i < maxRow; i++) {
                cells.add(new Cell(i, colNumber));
            }
            maxCol++;
        }
    }

    // ------- 8 ----------- (8p)
    // NOTE: There are no cycles in the graph

    int distance(int n, int m) {
        List l1 = getSeq(n);
        List l2 = getSeq(m);
        for (Integer i : l1) {
            if (l2.contains(i)) {
                return l1.indexOf(i) + l2.indexOf(i);
            }
        }
        return -1;
    }

    List getSeq(int n) {
        List seq = new ArrayList<>();
        while (n > 1) {
            seq.add(n);
            if (n % 2 == 0) {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
        }
        seq.add(1);
        return seq;
    }

    // ------- 9 ----------- (6p)

    b1.eqals(b2) will return true because Books equals() called.
    Method used equals by value.

    Method contains() uses equals() when searching for an object.
    For this to work the equals method must be overridden.
    Books equals is NOT overridden because method head differs, param
    should be Object. So NO overriding, we'll get overloading
    (i.e. Book has two equals). Because not overridden, Objects equals
     will be called i.e. equality by reference (==) used.
     Book b1 and b2 not same object, so false, not found.

        // This will not override Object's equals wrong parameter type
        public boolean equals(Book b) {
            if (b == this) {
                return true;
            }
            if (b == null) {
                return false;
            }
            return b.isbn.equals(isbn);
        }

        // This is the way it should be
        public boolean equals(Object b) {
            if (b == this) {
                return true;
            }
            if (b == null || b.getClass() != getClass()) {
                return false;
            }
            return ((Book)b).isbn.equals(isbn);
        }

}