/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2011-2020 Broad Institute, Aiden Lab, Rice University, Baylor College of Medicine
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *  THE SOFTWARE.
 */

package juicebox.tools.utils.juicer.arrowhead.connectedcomponents;

import java.awt.*;
import java.util.List;
import java.util.Queue;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * Implementation of 2-pass algorithm for finding connected components
 */
public class BinaryConnectedComponents {

    // unique labels for components, start at 0
    private static Integer nextLabel = 0;

    /**
     * @param image
     * @param threshold
     * @return list of connected components in image
     */
    public synchronized static List<Set<Point>> detection(double[][] image, double threshold) {
        int r = image.length;
        int c = image[0].length;

        // pixel label matrix
        int[][] labels = new int[r][c];

        List<IndexNode> indices = new ArrayList<>();
        indices.add(new IndexNode(-1));
        nextLabel = 1;

        // 1st pass
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (image[i][j] > threshold) {
                    processNeighbors(labels, indices, i, j, Math.max(i - 1, 0), Math.min(i + 1, r - 1), Math.max(j - 1, 0), Math.min(j + 1, c - 1));
                }
            }
        }
        return processLabeledIndices(indices);
    }

    /**
     * 2nd pass of algorithm
     *
     * @param indices
     * @return connected components
     */
    private static List<Set<Point>> processLabeledIndices(List<IndexNode> indices) {
        List<Set<Point>> components = new ArrayList<>();
        for (int i = 1; i < nextLabel; i++) {
            IndexNode current = indices.get(i);
            if (current.hasNotBeenIndexed()) {
                Set<Point> points = new HashSet<>(current.getMatrixIndices());
                Queue<IndexNode> queue = new LinkedBlockingQueue<>(current.getConnectedNodes());
                current.index();

                while (!queue.isEmpty()) {
                    IndexNode node = queue.poll();
                    if (node.hasNotBeenIndexed()) {
                        points.addAll(node.getMatrixIndices());
                        node.index();
                        for (IndexNode node2 : node.getConnectedNodes()) {
                            if (node2.hasNotBeenIndexed())
                                queue.add(node2);
                        }
                    }
                }
                components.add(points);
            }
        }
        return components;
    }

    /**
     * Label the neighbors of the pixel
     *
     * @param labels
     * @param indices
     * @param i
     * @param j
     * @param left
     * @param right
     * @param top
     * @param bottom
     */
    private static void processNeighbors(int[][] labels, List<IndexNode> indices, int i, int j,
                                         int left, int right, int top, int bottom) {

        // 8 - point connectivity
        int[][] neighborLabels = getSubMatrix(labels, left, right, top, bottom);

        // 0 - means none found
        Set<Integer> allPosVals = positiveValues(neighborLabels);

        int lowestLabel = 0;
        if (allPosVals.size() > 0)
            lowestLabel = Collections.min(new ArrayList<>(allPosVals));

        if (lowestLabel <= 0) {
            lowestLabel = nextLabel;
            indices.add(new IndexNode(lowestLabel));
            nextLabel++;
        }

        labels[i][j] = lowestLabel;
        IndexNode current = indices.get(lowestLabel);
        current.addPoint(new Point(i, j));

        for (Integer k : allPosVals) {
            IndexNode other = indices.get(k);
            other.addConnections(current);
            current.addConnections(other);
        }

    }

    private static int[][] getSubMatrix(int[][] matrix, int left, int right, int top, int bottom) {
        int[][] subMatrix = new int[right - left + 1][bottom - top + 1];
        for (int i = 0; i < subMatrix.length; i++) {
            System.arraycopy(matrix[left + i], top, subMatrix[i], 0, subMatrix[0].length);
        }
        return subMatrix;
    }

    private static Set<Integer> positiveValues(int[][] matrix) {
        Set<Integer> values = new HashSet<>();
        for (int[] row : matrix) {
            for (int val : row) {
                if (val > 0) {
                    values.add(val);
                }
            }
        }
        return values;
    }
}
