content: /*
   * 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.apache.calcite.materialize;
  
  import org.apache.calcite.plan.RelOptTable;
  import org.apache.calcite.util.graph.AttributedDirectedGraph;
  import org.apache.calcite.util.graph.DefaultEdge;
  import org.apache.calcite.util.mapping.IntPair;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.Ordering;
  
  import org.checkerframework.checker.initialization.qual.NotOnlyInitialized;
  import org.checkerframework.checker.initialization.qual.UnderInitialization;
  import org.checkerframework.checker.nullness.qual.Nullable;
  
  import java.util.List;
  import java.util.Objects;
  
  import static java.util.Objects.requireNonNull;
  
  /** Edge in the join graph.
   *
   * <p>It is directed: the "parent" must be the "many" side containing the
   * foreign key, and the "target" is the "one" side containing the primary
   * key. For example, EMP &rarr; DEPT.
   *
   * <p>When created via
   * {@link LatticeSpace#addEdge(LatticeTable, LatticeTable, List)}
   * it is unique within the {@link LatticeSpace}. */
  class Step extends DefaultEdge {
    final List<IntPair> keys;
  
    /** String representation of {@link #keys}. Computing the string requires a
     * {@link LatticeSpace}, so we pre-compute it before construction. */
    final String keyString;
  
    private Step(LatticeTable source, LatticeTable target,
        List<IntPair> keys, String keyString) {
      super(source, target);
      this.keys = ImmutableList.copyOf(keys);
      this.keyString = requireNonNull(keyString, "keyString");
      assert IntPair.ORDERING.isStrictlyOrdered(keys); // ordered and unique
    }
  
    /** Creates a Step. */
    static Step create(LatticeTable source, LatticeTable target,
        List<IntPair> keys, LatticeSpace space) {
      final StringBuilder b = new StringBuilder();
      for (IntPair key : keys) {
        b.append(' ')
            .append(space.fieldName(source, key.source))
            .append(':')
            .append(space.fieldName(target, key.target));
      }
      return new Step(source, target, keys, b.toString());
    }
  
    @Override public int hashCode() {
      return Objects.hash(source, target, keys);
    }
  
    @Override public boolean equals(@Nullable Object obj) {
      return this == obj
          || obj instanceof Step
          && ((Step) obj).source.equals(source)
          && ((Step) obj).target.equals(target)
          && ((Step) obj).keys.equals(keys);
    }
  
    @Override public String toString() {
      return "Step(" + source + ", " + target + "," + keyString + ")";
    }
  
    LatticeTable source() {
      return (LatticeTable) source;
    }
  
    LatticeTable target() {
      return (LatticeTable) target;
    }
  
    boolean isBackwards(SqlStatisticProvider statisticProvider) {
      final RelOptTable sourceTable = source().t;
      final List<Integer> sourceColumns = IntPair.left(keys);
      final RelOptTable targetTable = target().t;
      final List<Integer> targetColumns = IntPair.right(keys);
      final boolean noDerivedSourceColumns =
          sourceColumns.stream().allMatch(i ->
              i < sourceTable.getRowType().getFieldCount());
      final boolean noDerivedTargetColumns =
          targetColumns.stream().allMatch(i ->
              i < targetTable.getRowType().getFieldCount());
      final boolean forwardForeignKey = noDerivedSourceColumns
          && noDerivedTargetColumns
          && statisticProvider.isForeignKey(sourceTable, sourceColumns,
              targetTable, targetColumns)
          && statisticProvider.isKey(targetTable, targetColumns);
      final boolean backwardForeignKey = noDerivedSourceColumns
          && noDerivedTargetColumns
          && statisticProvider.isForeignKey(targetTable, targetColumns,
              sourceTable, sourceColumns)
          && statisticProvider.isKey(sourceTable, sourceColumns);
      if (backwardForeignKey != forwardForeignKey) {
        return backwardForeignKey;
      }
      // Tie-break if it's a foreign key in neither or both directions
      return compare(sourceTable, sourceColumns, targetTable, targetColumns) < 0;
    }
  
    /** Arbitrarily compares (table, columns). */
    private static int compare(RelOptTable table1, List<Integer> columns1,
        RelOptTable table2, List<Integer> columns2) {
      int c = Ordering.natural().<String>lexicographical()
          .compare(table1.getQualifiedName(), table2.getQualifiedName());
      if (c == 0) {
        c = Ordering.natural().<Integer>lexicographical()
            .compare(columns1, columns2);
      }
      return c;
    }
  
    /** Temporary method. We should use (inferred) primary keys to figure out
     * the direction of steps. */
    @SuppressWarnings("unused")
    private static double cardinality(SqlStatisticProvider statisticProvider,
        LatticeTable table) {
      return statisticProvider.tableCardinality(table.t);
    }
  
    /** Creates {@link Step} instances. */
    static class Factory implements AttributedDirectedGraph.AttributedEdgeFactory<
        LatticeTable, Step> {
      private final @NotOnlyInitialized LatticeSpace space;
  
      @SuppressWarnings("type.argument.type.incompatible")
      Factory(@UnderInitialization LatticeSpace space) {
        this.space = requireNonNull(space, "space");
      }
  
      @Override public Step createEdge(LatticeTable source, LatticeTable target) {
        throw new UnsupportedOperationException();
      }
  
      @Override public Step createEdge(LatticeTable source, LatticeTable target,
          Object... attributes) {
        @SuppressWarnings("unchecked") final List<IntPair> keys =
            (List) attributes[0];
        return Step.create(source, target, keys, space);
      }
    }
  }
  