/*
 * Copyright (C) 2017 The Guava Authors
 *
 * 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.
 */

package com.google.common.graph;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.graph.GraphConstants.ENDPOINTS_MISMATCH;

import com.google.common.base.Function;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterators;
import com.google.common.collect.Sets;
import com.google.common.collect.UnmodifiableIterator;
import com.google.common.math.IntMath;
import com.google.common.primitives.Ints;
import java.util.AbstractSet;
import java.util.Set;
import org.checkerframework.checker.nullness.qual.Nullable;

This class provides a skeletal implementation of BaseGraph. 
The methods implemented in this class should not be overridden unless the subclass admits a
more efficient implementation.
Author:
James Sexton
Type parameters:
<N> – Node parameter type/**
 * This class provides a skeletal implementation of {@link BaseGraph}.
 *
 * <p>The methods implemented in this class should not be overridden unless the subclass admits a
 * more efficient implementation.
 *
 * @author James Sexton
 * @param <N> Node parameter type
 */
abstract class AbstractBaseGraph<N> implements BaseGraph<N> {

  
Returns the number of edges in this graph; used to calculate the size of edges(). This implementation requires O(|N|) time. Classes extending this one may manually keep track of the number of edges as the graph is updated, and override this method for better performance. /**
   * Returns the number of edges in this graph; used to calculate the size of {@link #edges()}. This
   * implementation requires O(|N|) time. Classes extending this one may manually keep track of the
   * number of edges as the graph is updated, and override this method for better performance.
   */
  protected long edgeCount() {
    long degreeSum = 0L;
    for (N node : nodes()) {
      degreeSum += degree(node);
    }
    // According to the degree sum formula, this is equal to twice the number of edges.
    checkState((degreeSum & 1) == 0);
    return degreeSum >>> 1;
  }

  
An implementation of BaseGraph.edges() defined in terms of BaseGraph.nodes() and BaseGraph.successors(Object). /**
   * An implementation of {@link BaseGraph#edges()} defined in terms of {@link #nodes()} and {@link
   * #successors(Object)}.
   */
  @Override
  public Set<EndpointPair<N>> edges() {
    return new AbstractSet<EndpointPair<N>>() {
      @Override
      public UnmodifiableIterator<EndpointPair<N>> iterator() {
        return EndpointPairIterator.of(AbstractBaseGraph.this);
      }

      @Override
      public int size() {
        return Ints.saturatedCast(edgeCount());
      }

      @Override
      public boolean remove(Object o) {
        throw new UnsupportedOperationException();
      }

      // Mostly safe: We check contains(u) before calling successors(u), so we perform unsafe
      // operations only in weird cases like checking for an EndpointPair<ArrayList> in a
      // Graph<LinkedList>.
      @SuppressWarnings("unchecked")
      @Override
      public boolean contains(@Nullable Object obj) {
        if (!(obj instanceof EndpointPair)) {
          return false;
        }
        EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
        return isOrderingCompatible(endpointPair)
            && nodes().contains(endpointPair.nodeU())
            && successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV());
      }
    };
  }

  @Override
  public Set<EndpointPair<N>> incidentEdges(N node) {
    checkNotNull(node);
    checkArgument(nodes().contains(node), "Node %s is not an element of this graph.", node);
    return IncidentEdgeSet.of(this, node);
  }

  @Override
  public int degree(N node) {
    if (isDirected()) {
      return IntMath.saturatedAdd(predecessors(node).size(), successors(node).size());
    } else {
      Set<N> neighbors = adjacentNodes(node);
      int selfLoopCount = (allowsSelfLoops() && neighbors.contains(node)) ? 1 : 0;
      return IntMath.saturatedAdd(neighbors.size(), selfLoopCount);
    }
  }

  @Override
  public int inDegree(N node) {
    return isDirected() ? predecessors(node).size() : degree(node);
  }

  @Override
  public int outDegree(N node) {
    return isDirected() ? successors(node).size() : degree(node);
  }

  @Override
  public boolean hasEdgeConnecting(N nodeU, N nodeV) {
    checkNotNull(nodeU);
    checkNotNull(nodeV);
    return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
  }

  @Override
  public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
    checkNotNull(endpoints);
    if (!isOrderingCompatible(endpoints)) {
      return false;
    }
    N nodeU = endpoints.nodeU();
    N nodeV = endpoints.nodeV();
    return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
  }

  
Throws IllegalArgumentException if the ordering of endpoints is not compatible with the directionality of this graph. /**
   * Throws {@code IllegalArgumentException} if the ordering of {@code endpoints} is not compatible
   * with the directionality of this graph.
   */
  protected final void validateEndpoints(EndpointPair<?> endpoints) {
    checkNotNull(endpoints);
    checkArgument(isOrderingCompatible(endpoints), ENDPOINTS_MISMATCH);
  }

  protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) {
    return endpoints.isOrdered() || !this.isDirected();
  }

  private abstract static class IncidentEdgeSet<N> extends AbstractSet<EndpointPair<N>> {
    protected final N node;
    protected final BaseGraph<N> graph;

    public static <N> IncidentEdgeSet<N> of(BaseGraph<N> graph, N node) {
      return graph.isDirected() ? new Directed<>(graph, node) : new Undirected<>(graph, node);
    }

    private IncidentEdgeSet(BaseGraph<N> graph, N node) {
      this.graph = graph;
      this.node = node;
    }

    @Override
    public boolean remove(Object o) {
      throw new UnsupportedOperationException();
    }

    private static final class Directed<N> extends IncidentEdgeSet<N> {

      private Directed(BaseGraph<N> graph, N node) {
        super(graph, node);
      }

      @Override
      public UnmodifiableIterator<EndpointPair<N>> iterator() {
        return Iterators.unmodifiableIterator(
            Iterators.concat(
                Iterators.transform(
                    graph.predecessors(node).iterator(),
                    new Function<N, EndpointPair<N>>() {
                      @Override
                      public EndpointPair<N> apply(N predecessor) {
                        return EndpointPair.ordered(predecessor, node);
                      }
                    }),
                Iterators.transform(
                    // filter out 'node' from successors (already covered by predecessors, above)
                    Sets.difference(graph.successors(node), ImmutableSet.of(node)).iterator(),
                    new Function<N, EndpointPair<N>>() {
                      @Override
                      public EndpointPair<N> apply(N successor) {
                        return EndpointPair.ordered(node, successor);
                      }
                    })));
      }

      @Override
      public int size() {
        return graph.inDegree(node)
            + graph.outDegree(node)
            - (graph.successors(node).contains(node) ? 1 : 0);
      }

      @Override
      public boolean contains(@Nullable Object obj) {
        if (!(obj instanceof EndpointPair)) {
          return false;
        }

        EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
        if (!endpointPair.isOrdered()) {
          return false;
        }

        Object source = endpointPair.source();
        Object target = endpointPair.target();
        return (node.equals(source) && graph.successors(node).contains(target))
            || (node.equals(target) && graph.predecessors(node).contains(source));
      }
    }

    private static final class Undirected<N> extends IncidentEdgeSet<N> {
      private Undirected(BaseGraph<N> graph, N node) {
        super(graph, node);
      }

      @Override
      public UnmodifiableIterator<EndpointPair<N>> iterator() {
        return Iterators.unmodifiableIterator(
            Iterators.transform(
                graph.adjacentNodes(node).iterator(),
                new Function<N, EndpointPair<N>>() {
                  @Override
                  public EndpointPair<N> apply(N adjacentNode) {
                    return EndpointPair.unordered(node, adjacentNode);
                  }
                }));
      }

      @Override
      public int size() {
        return graph.adjacentNodes(node).size();
      }

      @Override
      public boolean contains(@Nullable Object obj) {
        if (!(obj instanceof EndpointPair)) {
          return false;
        }

        EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
        if (endpointPair.isOrdered()) {
          return false;
        }
        Set<N> adjacent = graph.adjacentNodes(node);
        Object nodeU = endpointPair.nodeU();
        Object nodeV = endpointPair.nodeV();

        return (node.equals(nodeV) && adjacent.contains(nodeU))
            || (node.equals(nodeU) && adjacent.contains(nodeV));
      }
    }
  }
}