/*
 * Copyright (C) 2008 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.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.Collections2.transform;
import static com.google.common.collect.Iterators.transform;
import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
import static java.util.Collections.unmodifiableCollection;
import static java.util.Collections.unmodifiableMap;
import static java.util.Collections.unmodifiableSet;
import static java.util.Collections.unmodifiableSortedMap;
import static java.util.Collections.unmodifiableSortedSet;

import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.J2ktIncompatible;
import com.google.common.base.Function;
import com.google.common.base.Supplier;
import com.google.common.collect.Table.Cell;
import java.io.Serializable;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.Spliterator;
import java.util.function.BinaryOperator;
import java.util.stream.Collector;
import org.jspecify.annotations.Nullable;

/**
 * Provides static methods that involve a {@code Table}.
 *
 * <p>See the Guava User Guide article on <a href=
 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#tables">{@code Tables}</a>.
 *
 * @author Jared Levy
 * @author Louis Wasserman
 * @since 7.0
 */
@GwtCompatible
public final class Tables {
  private Tables() {}

  /**
   * Returns a {@link Collector} that accumulates elements into a {@code Table} created using the
   * specified supplier, whose cells are generated by applying the provided mapping functions to the
   * input elements. Cells are inserted into the generated {@code Table} in encounter order.
   *
   * <p>If multiple input elements map to the same row and column, an {@code IllegalStateException}
   * is thrown when the collection operation is performed.
   *
   * <p>To collect to an {@link ImmutableTable}, use {@link ImmutableTable#toImmutableTable}.
   *
   * @since 21.0
   */
  public static <
          T extends @Nullable Object,
          R extends @Nullable Object,
          C extends @Nullable Object,
          V,
          I extends Table<R, C, V>>
      Collector<T, ?, I> toTable(
          java.util.function.Function<? super T, ? extends R> rowFunction,
          java.util.function.Function<? super T, ? extends C> columnFunction,
          java.util.function.Function<? super T, ? extends V> valueFunction,
          java.util.function.Supplier<I> tableSupplier) {
    return TableCollectors.<T, R, C, V, I>toTable(
        rowFunction, columnFunction, valueFunction, tableSupplier);
  }

  /**
   * Returns a {@link Collector} that accumulates elements into a {@code Table} created using the
   * specified supplier, whose cells are generated by applying the provided mapping functions to the
   * input elements. Cells are inserted into the generated {@code Table} in encounter order.
   *
   * <p>If multiple input elements map to the same row and column, the specified merging function is
   * used to combine the values. Like {@link
   * java.util.stream.Collectors#toMap(java.util.function.Function, java.util.function.Function,
   * BinaryOperator, java.util.function.Supplier)}, this Collector throws a {@code
   * NullPointerException} on null values returned from {@code valueFunction}, and treats nulls
   * returned from {@code mergeFunction} as removals of that row/column pair.
   *
   * @since 21.0
   */
  public static <
          T extends @Nullable Object,
          R extends @Nullable Object,
          C extends @Nullable Object,
          V,
          I extends Table<R, C, V>>
      Collector<T, ?, I> toTable(
          java.util.function.Function<? super T, ? extends R> rowFunction,
          java.util.function.Function<? super T, ? extends C> columnFunction,
          java.util.function.Function<? super T, ? extends V> valueFunction,
          BinaryOperator<V> mergeFunction,
          java.util.function.Supplier<I> tableSupplier) {
    return TableCollectors.<T, R, C, V, I>toTable(
        rowFunction, columnFunction, valueFunction, mergeFunction, tableSupplier);
  }

  /**
   * Returns an immutable cell with the specified row key, column key, and value.
   *
   * <p>The returned cell is serializable.
   *
   * @param rowKey the row key to be associated with the returned cell
   * @param columnKey the column key to be associated with the returned cell
   * @param value the value to be associated with the returned cell
   */
  public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      Cell<R, C, V> immutableCell(
          @ParametricNullness R rowKey,
          @ParametricNullness C columnKey,
          @ParametricNullness V value) {
    return new ImmutableCell<>(rowKey, columnKey, value);
  }

  static final class ImmutableCell<
          R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      extends AbstractCell<R, C, V> implements Serializable {
    @ParametricNullness private final R rowKey;
    @ParametricNullness private final C columnKey;
    @ParametricNullness private final V value;

    ImmutableCell(
        @ParametricNullness R rowKey,
        @ParametricNullness C columnKey,
        @ParametricNullness V value) {
      this.rowKey = rowKey;
      this.columnKey = columnKey;
      this.value = value;
    }

    @Override
    @ParametricNullness
    public R getRowKey() {
      return rowKey;
    }

    @Override
    @ParametricNullness
    public C getColumnKey() {
      return columnKey;
    }

    @Override
    @ParametricNullness
    public V getValue() {
      return value;
    }

    @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 0;
  }

  abstract static class AbstractCell<
          R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      implements Cell<R, C, V> {
    // needed for serialization
    AbstractCell() {}

    @Override
    public boolean equals(@Nullable Object obj) {
      if (obj == this) {
        return true;
      }
      if (obj instanceof Cell) {
        Cell<?, ?, ?> other = (Cell<?, ?, ?>) obj;
        return Objects.equals(getRowKey(), other.getRowKey())
            && Objects.equals(getColumnKey(), other.getColumnKey())
            && Objects.equals(getValue(), other.getValue());
      }
      return false;
    }

    @Override
    public int hashCode() {
      return Objects.hash(getRowKey(), getColumnKey(), getValue());
    }

    @Override
    public String toString() {
      return "(" + getRowKey() + "," + getColumnKey() + ")=" + getValue();
    }
  }

  /**
   * Creates a transposed view of a given table that flips its row and column keys. In other words,
   * calling {@code get(columnKey, rowKey)} on the generated table always returns the same value as
   * calling {@code get(rowKey, columnKey)} on the original table. Updating the original table
   * changes the contents of the transposed table and vice versa.
   *
   * <p>The returned table supports update operations as long as the input table supports the
   * analogous operation with swapped rows and columns. For example, in a {@link HashBasedTable}
   * instance, {@code rowKeySet().iterator()} supports {@code remove()} but {@code
   * columnKeySet().iterator()} doesn't. With a transposed {@link HashBasedTable}, it's the other
   * way around.
   */
  public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      Table<C, R, V> transpose(Table<R, C, V> table) {
    return (table instanceof TransposeTable)
        ? ((TransposeTable<R, C, V>) table).original
        : new TransposeTable<C, R, V>(table);
  }

  private static final class TransposeTable<
          C extends @Nullable Object, R extends @Nullable Object, V extends @Nullable Object>
      extends AbstractTable<C, R, V> {
    final Table<R, C, V> original;

    TransposeTable(Table<R, C, V> original) {
      this.original = checkNotNull(original);
    }

    @Override
    public void clear() {
      original.clear();
    }

    @Override
    public Map<C, V> column(@ParametricNullness R columnKey) {
      return original.row(columnKey);
    }

    @Override
    public Set<R> columnKeySet() {
      return original.rowKeySet();
    }

    @Override
    public Map<R, Map<C, V>> columnMap() {
      return original.rowMap();
    }

    @Override
    public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) {
      return original.contains(columnKey, rowKey);
    }

    @Override
    public boolean containsColumn(@Nullable Object columnKey) {
      return original.containsRow(columnKey);
    }

    @Override
    public boolean containsRow(@Nullable Object rowKey) {
      return original.containsColumn(rowKey);
    }

    @Override
    public boolean containsValue(@Nullable Object value) {
      return original.containsValue(value);
    }

    @Override
    public @Nullable V get(@Nullable Object rowKey, @Nullable Object columnKey) {
      return original.get(columnKey, rowKey);
    }

    @Override
    public @Nullable V put(
        @ParametricNullness C rowKey,
        @ParametricNullness R columnKey,
        @ParametricNullness V value) {
      return original.put(columnKey, rowKey, value);
    }

    @Override
    public void putAll(Table<? extends C, ? extends R, ? extends V> table) {
      original.putAll(transpose(table));
    }

    @Override
    public @Nullable V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
      return original.remove(columnKey, rowKey);
    }

    @Override
    public Map<R, V> row(@ParametricNullness C rowKey) {
      return original.column(rowKey);
    }

    @Override
    public Set<C> rowKeySet() {
      return original.columnKeySet();
    }

    @Override
    public Map<C, Map<R, V>> rowMap() {
      return original.columnMap();
    }

    @Override
    public int size() {
      return original.size();
    }

    @Override
    public Collection<V> values() {
      return original.values();
    }

    @Override
    Iterator<Cell<C, R, V>> cellIterator() {
      return transform(original.cellSet().iterator(), Tables::transposeCell);
    }

    @Override
    @GwtIncompatible // Spliterator
    Spliterator<Cell<C, R, V>> cellSpliterator() {
      return CollectSpliterators.map(
          original.cellSet().spliterator(),
          Spliterator.DISTINCT | Spliterator.NONNULL,
          Tables::transposeCell);
    }
  }

  private static <
          R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      Cell<C, R, V> transposeCell(Cell<R, C, V> cell) {
    return immutableCell(cell.getColumnKey(), cell.getRowKey(), cell.getValue());
  }

  /**
   * Creates a table that uses the specified backing map and factory. It can generate a table based
   * on arbitrary {@link Map} classes.
   *
   * <p>The {@code factory}-generated and {@code backingMap} classes determine the table iteration
   * order. However, the table's {@code row()} method returns instances of a different class than
   * {@code factory.get()} does.
   *
   * <p>Call this method only when the simpler factory methods in classes like {@link
   * HashBasedTable} and {@link TreeBasedTable} won't suffice.
   *
   * <p>The views returned by the {@code Table} methods {@link Table#column}, {@link
   * Table#columnKeySet}, and {@link Table#columnMap} have iterators that don't support {@code
   * remove()}. Otherwise, all optional operations are supported. Null row keys, columns keys, and
   * values are not supported.
   *
   * <p>Lookups by row key are often faster than lookups by column key, because the data is stored
   * in a {@code Map<R, Map<C, V>>}. A method call like {@code column(columnKey).get(rowKey)} still
   * runs quickly, since the row key is provided. However, {@code column(columnKey).size()} takes
   * longer, since an iteration across all row keys occurs.
   *
   * <p>Note that this implementation is not synchronized. If multiple threads access this table
   * concurrently and one of the threads modifies the table, it must be synchronized externally.
   *
   * <p>The table is serializable if {@code backingMap}, {@code factory}, the maps generated by
   * {@code factory}, and the table contents are all serializable.
   *
   * <p>Note: the table assumes complete ownership over of {@code backingMap} and the maps returned
   * by {@code factory}. Those objects should not be manually updated and they should not use soft,
   * weak, or phantom references.
   *
   * @param backingMap place to store the mapping from each row key to its corresponding column key
   *     / value map
   * @param factory supplier of new, empty maps that will each hold all column key / value mappings
   *     for a given row key
   * @throws IllegalArgumentException if {@code backingMap} is not empty
   * @since 10.0
   */
  public static <R, C, V> Table<R, C, V> newCustomTable(
      Map<R, Map<C, V>> backingMap, Supplier<? extends Map<C, V>> factory) {
    checkArgument(backingMap.isEmpty());
    checkNotNull(factory);
    // TODO(jlevy): Wrap factory to validate that the supplied maps are empty?
    return new StandardTable<>(backingMap, factory);
  }

  /**
   * Returns a view of a table where each value is transformed by a function. All other properties
   * of the table, such as iteration order, are left intact.
   *
   * <p>Changes in the underlying table are reflected in this view. Conversely, this view supports
   * removal operations, and these are reflected in the underlying table.
   *
   * <p>It's acceptable for the underlying table to contain null keys, and even null values provided
   * that the function is capable of accepting null input. The transformed table might contain null
   * values, if the function sometimes gives a null result.
   *
   * <p>The returned table is not thread-safe or serializable, even if the underlying table is.
   *
   * <p>The function is applied lazily, invoked when needed. This is necessary for the returned
   * table to be a view, but it means that the function will be applied many times for bulk
   * operations like {@link Table#containsValue} and {@code Table.toString()}. For this to perform
   * well, {@code function} should be fast. To avoid lazy evaluation when the returned table doesn't
   * need to be a view, copy the returned table into a new table of your choosing.
   *
   * @since 10.0
   */
  public static <
          R extends @Nullable Object,
          C extends @Nullable Object,
          V1 extends @Nullable Object,
          V2 extends @Nullable Object>
      Table<R, C, V2> transformValues(
          Table<R, C, V1> fromTable, Function<? super V1, V2> function) {
    return new TransformedTable<>(fromTable, function);
  }

  private static final class TransformedTable<
          R extends @Nullable Object,
          C extends @Nullable Object,
          V1 extends @Nullable Object,
          V2 extends @Nullable Object>
      extends AbstractTable<R, C, V2> {
    final Table<R, C, V1> fromTable;
    final Function<? super V1, V2> function;

    TransformedTable(Table<R, C, V1> fromTable, Function<? super V1, V2> function) {
      this.fromTable = checkNotNull(fromTable);
      this.function = checkNotNull(function);
    }

    @Override
    public boolean contains(@Nullable Object rowKey, @Nullable Object columnKey) {
      return fromTable.contains(rowKey, columnKey);
    }

    @Override
    public @Nullable V2 get(@Nullable Object rowKey, @Nullable Object columnKey) {
      // The function is passed a null input only when the table contains a null
      // value.
      // The cast is safe because of the contains() check.
      return contains(rowKey, columnKey)
          ? function.apply(uncheckedCastNullableTToT(fromTable.get(rowKey, columnKey)))
          : null;
    }

    @Override
    public int size() {
      return fromTable.size();
    }

    @Override
    public void clear() {
      fromTable.clear();
    }

    @Override
    public @Nullable V2 put(
        @ParametricNullness R rowKey,
        @ParametricNullness C columnKey,
        @ParametricNullness V2 value) {
      throw new UnsupportedOperationException();
    }

    @Override
    public void putAll(Table<? extends R, ? extends C, ? extends V2> table) {
      throw new UnsupportedOperationException();
    }

    @Override
    public @Nullable V2 remove(@Nullable Object rowKey, @Nullable Object columnKey) {
      return contains(rowKey, columnKey)
          // The cast is safe because of the contains() check.
          ? function.apply(uncheckedCastNullableTToT(fromTable.remove(rowKey, columnKey)))
          : null;
    }

    @Override
    public Map<C, V2> row(@ParametricNullness R rowKey) {
      return Maps.transformValues(fromTable.row(rowKey), function);
    }

    @Override
    public Map<R, V2> column(@ParametricNullness C columnKey) {
      return Maps.transformValues(fromTable.column(columnKey), function);
    }

    Cell<R, C, V2> applyToValue(Cell<R, C, V1> cell) {
      return immutableCell(cell.getRowKey(), cell.getColumnKey(), function.apply(cell.getValue()));
    }

    @Override
    Iterator<Cell<R, C, V2>> cellIterator() {
      return transform(fromTable.cellSet().iterator(), this::applyToValue);
    }

    @Override
    @GwtIncompatible // Spliterator
    Spliterator<Cell<R, C, V2>> cellSpliterator() {
      return CollectSpliterators.map(
          fromTable.cellSet().spliterator(),
          Spliterator.NONNULL | Spliterator.DISTINCT,
          this::applyToValue);
    }

    @Override
    public Set<R> rowKeySet() {
      return fromTable.rowKeySet();
    }

    @Override
    public Set<C> columnKeySet() {
      return fromTable.columnKeySet();
    }

    @Override
    Collection<V2> createValues() {
      return transform(fromTable.values(), function);
    }

    @Override
    public Map<R, Map<C, V2>> rowMap() {
      return Maps.transformValues(fromTable.rowMap(), row -> Maps.transformValues(row, function));
    }

    @Override
    public Map<C, Map<R, V2>> columnMap() {
      return Maps.transformValues(
          fromTable.columnMap(), column -> Maps.transformValues(column, function));
    }
  }

  /**
   * Returns an unmodifiable view of the specified table. This method allows modules to provide
   * users with "read-only" access to internal tables. Query operations on the returned table "read
   * through" to the specified table, and attempts to modify the returned table, whether direct or
   * via its collection views, result in an {@code UnsupportedOperationException}.
   *
   * <p>The returned table will be serializable if the specified table is serializable.
   *
   * <p>Consider using an {@link ImmutableTable}, which is guaranteed never to change.
   *
   * @since 11.0
   */
  public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      Table<R, C, V> unmodifiableTable(Table<? extends R, ? extends C, ? extends V> table) {
    return new UnmodifiableTable<>(table);
  }

  private static class UnmodifiableTable<
          R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      extends ForwardingTable<R, C, V> implements Serializable {
    final Table<? extends R, ? extends C, ? extends V> delegate;

    UnmodifiableTable(Table<? extends R, ? extends C, ? extends V> delegate) {
      this.delegate = checkNotNull(delegate);
    }

    @SuppressWarnings("unchecked") // safe, covariant cast
    @Override
    protected Table<R, C, V> delegate() {
      return (Table<R, C, V>) delegate;
    }

    @Override
    public Set<Cell<R, C, V>> cellSet() {
      return unmodifiableSet(super.cellSet());
    }

    @Override
    public void clear() {
      throw new UnsupportedOperationException();
    }

    @Override
    public Map<R, V> column(@ParametricNullness C columnKey) {
      return unmodifiableMap(super.column(columnKey));
    }

    @Override
    public Set<C> columnKeySet() {
      return unmodifiableSet(super.columnKeySet());
    }

    @Override
    public Map<C, Map<R, V>> columnMap() {
      return unmodifiableMap(Maps.transformValues(super.columnMap(), Collections::unmodifiableMap));
    }

    @Override
    public @Nullable V put(
        @ParametricNullness R rowKey,
        @ParametricNullness C columnKey,
        @ParametricNullness V value) {
      throw new UnsupportedOperationException();
    }

    @Override
    public void putAll(Table<? extends R, ? extends C, ? extends V> table) {
      throw new UnsupportedOperationException();
    }

    @Override
    public @Nullable V remove(@Nullable Object rowKey, @Nullable Object columnKey) {
      throw new UnsupportedOperationException();
    }

    @Override
    public Map<C, V> row(@ParametricNullness R rowKey) {
      return unmodifiableMap(super.row(rowKey));
    }

    @Override
    public Set<R> rowKeySet() {
      return unmodifiableSet(super.rowKeySet());
    }

    @Override
    public Map<R, Map<C, V>> rowMap() {
      return unmodifiableMap(Maps.transformValues(super.rowMap(), Collections::unmodifiableMap));
    }

    @Override
    public Collection<V> values() {
      return unmodifiableCollection(super.values());
    }

    @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 0;
  }

  /**
   * Returns an unmodifiable view of the specified row-sorted table. This method allows modules to
   * provide users with "read-only" access to internal tables. Query operations on the returned
   * table "read through" to the specified table, and attempts to modify the returned table, whether
   * direct or via its collection views, result in an {@code UnsupportedOperationException}.
   *
   * <p>The returned table will be serializable if the specified table is serializable.
   *
   * @param table the row-sorted table for which an unmodifiable view is to be returned
   * @return an unmodifiable view of the specified table
   * @since 11.0
   */
  public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      RowSortedTable<R, C, V> unmodifiableRowSortedTable(
          RowSortedTable<R, ? extends C, ? extends V> table) {
    /*
     * It's not ? extends R, because it's technically not covariant in R. Specifically,
     * table.rowMap().comparator() could return a comparator that only works for the ? extends R.
     * Collections.unmodifiableSortedMap makes the same distinction.
     */
    return new UnmodifiableRowSortedMap<>(table);
  }

  private static final class UnmodifiableRowSortedMap<
          R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      extends UnmodifiableTable<R, C, V> implements RowSortedTable<R, C, V> {

    UnmodifiableRowSortedMap(RowSortedTable<R, ? extends C, ? extends V> delegate) {
      super(delegate);
    }

    @Override
    protected RowSortedTable<R, C, V> delegate() {
      return (RowSortedTable<R, C, V>) super.delegate();
    }

    @Override
    public SortedMap<R, Map<C, V>> rowMap() {
      return unmodifiableSortedMap(
          Maps.transformValues(delegate().rowMap(), Collections::unmodifiableMap));
    }

    @Override
    public SortedSet<R> rowKeySet() {
      return unmodifiableSortedSet(delegate().rowKeySet());
    }

    @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 0;
  }

  /**
   * Returns a synchronized (thread-safe) table backed by the specified table. In order to guarantee
   * serial access, it is critical that <b>all</b> access to the backing table is accomplished
   * through the returned table.
   *
   * <p>It is imperative that the user manually synchronize on the returned table when accessing any
   * of its collection views:
   *
   * {@snippet :
   * Table<R, C, V> table = Tables.synchronizedTable(HashBasedTable.create());
   * ...
   * Map<C, V> row = table.row(rowKey); // Needn't be in synchronized block
   * ...
   * synchronized (table) { // Synchronizing on table, not row!
   *   Iterator<Entry<C, V>> i = row.entrySet().iterator(); // Must be in synchronized block
   *   while (i.hasNext()) {
   *     foo(i.next());
   *   }
   * }
   * }
   *
   * <p>Failure to follow this advice may result in non-deterministic behavior.
   *
   * <p>The returned table will be serializable if the specified table is serializable.
   *
   * @param table the table to be wrapped in a synchronized view
   * @return a synchronized view of the specified table
   * @since 22.0
   */
  @J2ktIncompatible // Synchronized
  public static <R extends @Nullable Object, C extends @Nullable Object, V extends @Nullable Object>
      Table<R, C, V> synchronizedTable(Table<R, C, V> table) {
    return Synchronized.table(table, null);
  }

  @SuppressWarnings("ReferenceEquality") // == fast path
  static boolean equalsImpl(Table<?, ?, ?> table, @Nullable Object obj) {
    if (obj == table) {
      return true;
    } else if (obj instanceof Table) {
      Table<?, ?, ?> that = (Table<?, ?, ?>) obj;
      return table.cellSet().equals(that.cellSet());
    } else {
      return false;
    }
  }
}