import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

/**
 * Computes the Transitive Closure of a random set using Warshall's Algorithm.
 * @author William John Holden
 * @version 1.1
  */
public class Warshall {
    
    public static void main(String[] args) {
        Integer pairs = 5, max = 5;
        Set s = null;
        try {
            if (args.length == 2) {
                pairs = Integer.parseInt(args[0]);
                max = Integer.parseInt(args[1]);
                s = randomSetFactory(pairs, max);
            } else if (args.length > 2 && args.length % 2 == 0) {
                s = new TreeSet<>();
                for (int i = 0; i < args.length; i = i + 2) {
                    Integer x = Integer.parseInt(args[i]);
                    Integer y = Integer.parseInt(args[i + 1]);
                    s.add(new OrderedPair(x, y));
                }
            } else if (args.length > 0 && args.length % 2 == 1) {
                System.err.println("Provide no arguments, specify "
                        + "number of pairs and maximum value, or an even "
                        + "number of space-separated integers.");
                System.exit(-1);
            } else {
                s = randomSetFactory(pairs, max);
            }
        } catch (NumberFormatException e) {
            System.err.println(e);
            System.exit(-1);
        }
        
        System.out.println("Original Relation (" + s.size() + ") = " + s);
        Matrix m = new Matrix(s);

        if (m.isIdentity())
            System.out.println(" - is an identity (aka diagonal) relation");
        if (m.isUniversal())
            System.out.println(" - is a universal relation");
        System.out.println(String.format(" - is%s reflexive",
                m.isReflexive() ? "" : " not"));
        System.out.println(String.format(" - is%s symmetrical",
                m.isSymmetric()? "" : " not"));
        System.out.println(String.format(" - is%s antisymmetrical",
                m.isAntiSymmetric() ? "" : " not"));
        System.out.println(String.format(" - is%s transitive",
                m.isTransitive() ? "" : " not"));
        if (m.isEquivalence())
            System.out.println(" - is an equivalence relation");
        if (m.isPartialOrder())
            System.out.println(" - is a partial order relation");

        System.out.println("Universal Set (" + m.getUniversal().size() + ") = "
                + m.getUniversal());
        System.out.println("Matrix representation:");
        System.out.println(m);
        
        if (!m.isTransitive()) {
            Matrix w = m.warshall();
            Set ws = w.toSet();
            System.out.println("Matrix after Warshall's Algorithm:");
            System.out.println(w);
            System.out.println("Transitive Closure (" + ws.size() + ") = " + 
                    ws);
        }
    }
    
    private static Set randomSetFactory (int pairs, int max) {
        SecureRandom random = new SecureRandom();
        Set<OrderedPair> r = new TreeSet<>();
        for (int i = 0 ; i < pairs ; i++) {
            OrderedPair p;
            p = new OrderedPair(Math.abs(random.nextInt() % max),
                    Math.abs(random.nextInt() % max));
            r.add(p);
        }
        return r;
    }

    private static class OrderedPair implements Comparable {

        @Override
        public String toString() {
            return "(" + this.x + ',' + this.y + ')';
        }
        public Integer x;
        public Integer y;

        public OrderedPair() {
            this.x = 0;
            this.y = 0;
        }
        
        public OrderedPair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof OrderedPair) {
                return ((Objects.equals(((OrderedPair) obj).x, this.x)) &&
                        (Objects.equals(((OrderedPair) obj).y, this.y)));
            }
            return false;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 89 * hash + this.x;
            hash = 89 * hash + this.y;
            return hash;
        }

        @Override
        public int compareTo(Object obj) {
            if (obj instanceof OrderedPair) {
                if ((Objects.equals(((OrderedPair) obj).x, this.x))) {
                    return (this.y.compareTo(((OrderedPair) obj).y));
                }
                return (this.x.compareTo(((OrderedPair) obj).x));
            }
            return 0;
        }
    }
    
    private static class Matrix {

        @Override
        public int hashCode() {
            int hash = 3;
            hash = 53 * hash + Arrays.deepHashCode(this.m);
            hash = 53 * hash + Objects.hashCode(this.universal);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Matrix other = (Matrix) obj;
            if (!Arrays.deepEquals(this.m, other.m)) {
                return false;
            }
            if (!Objects.equals(this.universal, other.universal)) {
                return false;
            }
            return true;
        }

        private int m [][], w [][];
        private final Set universal;
        
        public Matrix (int m[][], Set universal) {
            this.m = m;
            this.universal = universal;
        }
        
        public Matrix (Set<OrderedPair> r) {
            this.universal = universal(r);
            List u = universalSortedIndexedList(universal);
            
            m = new int[universal.size()][universal.size()];
           
            for (OrderedPair p : r) {
                m[u.indexOf(p.x)][u.indexOf(p.y)] = 1;
            }
        }
        
        private Set universal (Set<OrderedPair> r) {
            Set<Integer> u = new TreeSet<>();
            for (OrderedPair p : r) {
                u.add(p.x);
                u.add(p.y);
            }
            return u;
        }
        
        private List universalSortedIndexedList (Set universal) {
            List<?> u;
            u = new ArrayList<>(universal);
            return u;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int i = 0 ; i < m.length ; i++) {
                if (i > 0)
                    sb.append(" ");
                sb.append("[");
                for (int j = 0 ; j < m.length ; j++) {
                    if (j > 0)
                        sb.append(" ");
                    sb.append(m[i][j]);
                }
                sb.append("]");
                if (i < m.length - 1) {
                    sb.append("\n");
                }
            }
            sb.append("]");
            return sb.toString();
        }

        public Set getUniversal() {
            return universal;
        }
        
        public Matrix warshall () {
            List<Integer> p, q;
            
            // cache the result so subsequent calls to this function go fast
            if (w != null) {
                return new Matrix(w, universal);
            }
            
            // Surprise! The clone method is not a deep copy for 2D arrays.
            w = new int[m.length][];
            for (int k = 0 ; k < m.length ; k++) {
                w[k] = Arrays.copyOf(m[k], m[k].length);
            }
            
            for (int i = 0 ; i < w.length ; i++) {
                p = new ArrayList<>();
                q = new ArrayList<>();
                
                // find 1's in column first (p-values)
                for (int column = 0 ; column < w.length ; column++) {
                    if (w[column][i] > 0) {
                        p.add(column);
                    }
                }
                
                // find 1's in row (q-values)
                for (int row = 0 ; row < w.length ; row++) {
                    if (w[i][row] > 0) {
                        q.add(row);
                    }
                }
                
                // add transitive pairs to closure
                for (Integer x : p) {
                    for (int y : q) {
                        w[x][y] = 1;
                    }
                }
            }

            return new Matrix(w, universal);
        }
        
        public Set toSet () {
            Set<OrderedPair> set = new TreeSet<>();
            List<Integer> u = universalSortedIndexedList(universal);
            for (int i = 0 ; i < m.length ; i++) {
                for (int j = 0 ; j < m.length ; j++) {
                    if (m[i][j] > 0) {
                        set.add(new OrderedPair(u.get(i), u.get(j)));
                    }
                }
            }
            return set;
        }
        
        public boolean isReflexive () {
            for (int i = 0 ; i < universal.size() ; i++) {
                if (m[i][i] == 0)
                    return false;
            }
            return true;
        }
        
        public boolean isSymmetric () {
            for (int row = 0 ; row < universal.size() ; row++) {
                for (int column = 0 ; column < universal.size() ; column++) {
                    if (row == column)
                        ; // skip
                    else if (m[row][column] != m[column][row]) {
                        return false;
                    }
                }
            }
            return true;
        }
        
        public boolean isAntiSymmetric () {
            for (int row = 0 ; row < universal.size() ; row++) {
                for (int column = 0 ; column < universal.size() ; column++) {
                    if (row == column)
                        ; // skip
                    else if (m[row][column] + m[column][row] > 1) {
                        return false;
                    }
                }
            }
            return true;
        }
        
        public boolean isIdentity () {
            for (int row = 0 ; row < universal.size() ; row++) {
                for (int column = 0 ; column < universal.size() ; column++) {
                    if (row == column && m[row][column] != 1)
                        return false;
                    if (row != column && m[row][column] != 0) {
                        return false;
                    }
                }
            }
            return true;
        }
        
        public boolean isUniversal () {
            for (int row = 0 ; row < universal.size() ; row++) {
                for (int column = 0 ; column < universal.size() ; column++) {
                    if (m[row][column] != 1)
                        return false;
                }
            }
            return true;
        }
        
        public boolean isTransitive () {
            Matrix w = warshall();
            return this.equals(w);
        }
        
        public boolean isEquivalence () {
            return (isReflexive() & isSymmetric() & isTransitive());
        }
        
        public boolean isPartialOrder () {
            return (isReflexive() & isAntiSymmetric() & isTransitive());
        }
    }
}