/*
 * Copyright 2019-2020 The Polypheny Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * This file incorporates code covered by the following terms:
 *
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to you under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.polypheny.db.util.graph;


import com.google.common.collect.Ordering;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;


/**
 * Default implementation of {@link DirectedGraph}.
 *
 * @param <V> Vertex type
 * @param <E> Edge type
 */
public class DefaultDirectedGraph<V, E extends DefaultEdge> implements DirectedGraph<V, E> {

    final Set<E> edges = new LinkedHashSet<>();
    final Map<V, VertexInfo<V, E>> vertexMap = new LinkedHashMap<>();
    final EdgeFactory<V, E> edgeFactory;


    /**
     * Creates a graph.
     */
    public DefaultDirectedGraph( EdgeFactory<V, E> edgeFactory ) {
        this.edgeFactory = edgeFactory;
    }


    public static <V> DefaultDirectedGraph<V, DefaultEdge> create() {
        return create( DefaultEdge.factory() );
    }


    public static <V, E extends DefaultEdge> DefaultDirectedGraph<V, E> create( EdgeFactory<V, E> edgeFactory ) {
        return new DefaultDirectedGraph<>( edgeFactory );
    }


    public String toStringUnordered() {
        return "graph(vertices: " + vertexMap.keySet() + ", edges: " + edges + ")";
    }


    @Override
    public String toString() {
        @SuppressWarnings("unchecked") final Ordering<V> vertexOrdering = (Ordering) Ordering.usingToString();
        @SuppressWarnings("unchecked") final Ordering<E> edgeOrdering = (Ordering) Ordering.usingToString();
        return toString( vertexOrdering, edgeOrdering );
    }


    /**
     * Returns the string representation of this graph, using the given orderings to ensure that the output order of vertices and edges is deterministic.
     */
    private String toString( Ordering<V> vertexOrdering, Ordering<E> edgeOrdering ) {
        return "graph(vertices: " + vertexOrdering.sortedCopy( vertexMap.keySet() ) + ", edges: " + edgeOrdering.sortedCopy( edges ) + ")";
    }


    @Override
    public boolean addVertex( V vertex ) {
        if ( vertexMap.containsKey( vertex ) ) {
            return false;
        } else {
            vertexMap.put( vertex, new VertexInfo<>() );
            return true;
        }
    }


    @Override
    public Set<E> edgeSet() {
        return Collections.unmodifiableSet( edges );
    }


    @Override
    public E addEdge( V vertex, V targetVertex ) {
        final VertexInfo<V, E> info = vertexMap.get( vertex );
        if ( info == null ) {
            throw new IllegalArgumentException( "no vertex " + vertex );
        }
        final VertexInfo<V, E> info2 = vertexMap.get( targetVertex );
        if ( info2 == null ) {
            throw new IllegalArgumentException( "no vertex " + targetVertex );
        }
        final E edge = edgeFactory.createEdge( vertex, targetVertex );
        if ( edges.add( edge ) ) {
            info.outEdges.add( edge );
            return edge;
        } else {
            return null;
        }
    }


    @Override
    public E getEdge( V source, V target ) {
        // REVIEW: could instead use edges.get(new DefaultEdge(source, target))
        final VertexInfo<V, E> info = vertexMap.get( source );
        for ( E outEdge : info.outEdges ) {
            if ( outEdge.target.equals( target ) ) {
                return outEdge;
            }
        }
        return null;
    }


    @Override
    public boolean removeEdge( V source, V target ) {
        final VertexInfo<V, E> info = vertexMap.get( source );
        List<E> outEdges = info.outEdges;
        for ( int i = 0, size = outEdges.size(); i < size; i++ ) {
            E edge = outEdges.get( i );
            if ( edge.target.equals( target ) ) {
                outEdges.remove( i );
                edges.remove( edge );
                return true;
            }
        }
        return false;
    }


    @Override
    public Set<V> vertexSet() {
        return vertexMap.keySet();
    }


    @Override
    public void removeAllVertices( Collection<V> collection ) {
        vertexMap.keySet().removeAll( collection );
        for ( VertexInfo<V, E> info : vertexMap.values() ) {
            //noinspection SuspiciousMethodCalls
            info.outEdges.removeIf( next -> collection.contains( next.target ) );
        }
    }


    @Override
    public List<E> getOutwardEdges( V source ) {
        return vertexMap.get( source ).outEdges;
    }


    @Override
    public List<E> getInwardEdges( V target ) {
        final ArrayList<E> list = new ArrayList<>();
        for ( VertexInfo<V, E> info : vertexMap.values() ) {
            for ( E edge : info.outEdges ) {
                if ( edge.target.equals( target ) ) {
                    list.add( edge );
                }
            }
        }
        return list;
    }


    final V source( E edge ) {
        //noinspection unchecked
        return (V) edge.source;
    }


    final V target( E edge ) {
        //noinspection unchecked
        return (V) edge.target;
    }


    /**
     * Information about an edge.
     *
     * @param <V> Vertex type
     * @param <E> Edge type
     */
    static class VertexInfo<V, E> {

        public List<E> outEdges = new ArrayList<>();
    }
}

