import itertools
import warnings
from collections import Counter
from typing import Iterable, Sequence, Union

import pandas as pd

from . import dtypes
from .concat import concat
from .dataarray import DataArray
from .dataset import Dataset
from .merge import merge
from .utils import iterate_nested


def _infer_concat_order_from_positions(datasets):
    return dict(_infer_tile_ids_from_nested_list(datasets, ()))


def _infer_tile_ids_from_nested_list(entry, current_pos):
    """
    Given a list of lists (of lists...) of objects, returns a iterator
    which returns a tuple containing the index of each object in the nested
    list structure as the key, and the object. This can then be called by the
    dict constructor to create a dictionary of the objects organised by their
    position in the original nested list.

    Recursively traverses the given structure, while keeping track of the
    current position. Should work for any type of object which isn't a list.

    Parameters
    ----------
    entry : list[list[obj, obj, ...], ...]
        List of lists of arbitrary depth, containing objects in the order
        they are to be concatenated.

    Returns
    -------
    combined_tile_ids : dict[tuple(int, ...), obj]
    """

    if isinstance(entry, list):
        for i, item in enumerate(entry):
            yield from _infer_tile_ids_from_nested_list(item, current_pos + (i,))
    else:
        yield current_pos, entry


def _ensure_same_types(series, dim):

    if series.dtype == object:
        types = set(series.map(type))
        if len(types) > 1:
            try:
                import cftime

                cftimes = any(issubclass(t, cftime.datetime) for t in types)
            except ImportError:
                cftimes = False

            types = ", ".join(t.__name__ for t in types)

            error_msg = (
                f"Cannot combine along dimension '{dim}' with mixed types."
                f" Found: {types}."
            )
            if cftimes:
                error_msg = (
                    f"{error_msg} If importing data directly from a file then "
                    f"setting `use_cftime=True` may fix this issue."
                )

            raise TypeError(error_msg)


def _infer_concat_order_from_coords(datasets):

    concat_dims = []
    tile_ids = [() for ds in datasets]

    # All datasets have same variables because they've been grouped as such
    ds0 = datasets[0]
    for dim in ds0.dims:

        # Check if dim is a coordinate dimension
        if dim in ds0:

            # Need to read coordinate values to do ordering
            indexes = [ds.xindexes.get(dim) for ds in datasets]
            if any(index is None for index in indexes):
                raise ValueError(
                    "Every dimension needs a coordinate for "
                    "inferring concatenation order"
                )

            # TODO (benbovy, flexible indexes): support flexible indexes?
            indexes = [index.to_pandas_index() for index in indexes]

            # If dimension coordinate values are same on every dataset then
            # should be leaving this dimension alone (it's just a "bystander")
            if not all(index.equals(indexes[0]) for index in indexes[1:]):

                # Infer order datasets should be arranged in along this dim
                concat_dims.append(dim)

                if all(index.is_monotonic_increasing for index in indexes):
                    ascending = True
                elif all(index.is_monotonic_decreasing for index in indexes):
                    ascending = False
                else:
                    raise ValueError(
                        "Coordinate variable {} is neither "
                        "monotonically increasing nor "
                        "monotonically decreasing on all datasets".format(dim)
                    )

                # Assume that any two datasets whose coord along dim starts
                # with the same value have the same coord values throughout.
                if any(index.size == 0 for index in indexes):
                    raise ValueError("Cannot handle size zero dimensions")
                first_items = pd.Index([index[0] for index in indexes])

                series = first_items.to_series()

                # ensure series does not contain mixed types, e.g. cftime calendars
                _ensure_same_types(series, dim)

                # Sort datasets along dim
                # We want rank but with identical elements given identical
                # position indices - they should be concatenated along another
                # dimension, not along this one
                rank = series.rank(
                    method="dense", ascending=ascending, numeric_only=False
                )
                order = rank.astype(int).values - 1

                # Append positions along extra dimension to structure which
                # encodes the multi-dimensional concatenation order
                tile_ids = [
                    tile_id + (position,) for tile_id, position in zip(tile_ids, order)
                ]

    if len(datasets) > 1 and not concat_dims:
        raise ValueError(
            "Could not find any dimension coordinates to use to "
            "order the datasets for concatenation"
        )

    combined_ids = dict(zip(tile_ids, datasets))

    return combined_ids, concat_dims


def _check_dimension_depth_tile_ids(combined_tile_ids):
    """
    Check all tuples are the same length, i.e. check that all lists are
    nested to the same depth.
    """
    tile_ids = combined_tile_ids.keys()
    nesting_depths = [len(tile_id) for tile_id in tile_ids]
    if not nesting_depths:
        nesting_depths = [0]
    if set(nesting_depths) != {nesting_depths[0]}:
        raise ValueError(
            "The supplied objects do not form a hypercube because"
            " sub-lists do not have consistent depths"
        )
    # return these just to be reused in _check_shape_tile_ids
    return tile_ids, nesting_depths


def _check_shape_tile_ids(combined_tile_ids):
    """Check all lists along one dimension are same length."""
    tile_ids, nesting_depths = _check_dimension_depth_tile_ids(combined_tile_ids)
    for dim in range(nesting_depths[0]):
        indices_along_dim = [tile_id[dim] for tile_id in tile_ids]
        occurrences = Counter(indices_along_dim)
        if len(set(occurrences.values())) != 1:
            raise ValueError(
                "The supplied objects do not form a hypercube "
                "because sub-lists do not have consistent "
                "lengths along dimension" + str(dim)
            )


def _combine_nd(
    combined_ids,
    concat_dims,
    data_vars="all",
    coords="different",
    compat="no_conflicts",
    fill_value=dtypes.NA,
    join="outer",
    combine_attrs="drop",
):
    """
    Combines an N-dimensional structure of datasets into one by applying a
    series of either concat and merge operations along each dimension.

    No checks are performed on the consistency of the datasets, concat_dims or
    tile_IDs, because it is assumed that this has already been done.

    Parameters
    ----------
    combined_ids : Dict[Tuple[int, ...]], xarray.Dataset]
        Structure containing all datasets to be concatenated with "tile_IDs" as
        keys, which specify position within the desired final combined result.
    concat_dims : sequence of str
        The dimensions along which the datasets should be concatenated. Must be
        in order, and the length must match the length of the tuples used as
        keys in combined_ids. If the string is a dimension name then concat
        along that dimension, if it is None then merge.

    Returns
    -------
    combined_ds : xarray.Dataset
    """

    example_tile_id = next(iter(combined_ids.keys()))

    n_dims = len(example_tile_id)
    if len(concat_dims) != n_dims:
        raise ValueError(
            "concat_dims has length {} but the datasets "
            "passed are nested in a {}-dimensional structure".format(
                len(concat_dims), n_dims
            )
        )

    # Each iteration of this loop reduces the length of the tile_ids tuples
    # by one. It always combines along the first dimension, removing the first
    # element of the tuple
    for concat_dim in concat_dims:
        combined_ids = _combine_all_along_first_dim(
            combined_ids,
            dim=concat_dim,
            data_vars=data_vars,
            coords=coords,
            compat=compat,
            fill_value=fill_value,
            join=join,
            combine_attrs=combine_attrs,
        )
    (combined_ds,) = combined_ids.values()
    return combined_ds


def _combine_all_along_first_dim(
    combined_ids,
    dim,
    data_vars,
    coords,
    compat,
    fill_value=dtypes.NA,
    join="outer",
    combine_attrs="drop",
):

    # Group into lines of datasets which must be combined along dim
    # need to sort by _new_tile_id first for groupby to work
    # TODO: is the sorted need?
    combined_ids = dict(sorted(combined_ids.items(), key=_new_tile_id))
    grouped = itertools.groupby(combined_ids.items(), key=_new_tile_id)

    # Combine all of these datasets along dim
    new_combined_ids = {}
    for new_id, group in grouped:
        combined_ids = dict(sorted(group))
        datasets = combined_ids.values()
        new_combined_ids[new_id] = _combine_1d(
            datasets, dim, compat, data_vars, coords, fill_value, join, combine_attrs
        )
    return new_combined_ids


def _combine_1d(
    datasets,
    concat_dim,
    compat="no_conflicts",
    data_vars="all",
    coords="different",
    fill_value=dtypes.NA,
    join="outer",
    combine_attrs="drop",
):
    """
    Applies either concat or merge to 1D list of datasets depending on value
    of concat_dim
    """

    if concat_dim is not None:
        try:
            combined = concat(
                datasets,
                dim=concat_dim,
                data_vars=data_vars,
                coords=coords,
                compat=compat,
                fill_value=fill_value,
                join=join,
                combine_attrs=combine_attrs,
            )
        except ValueError as err:
            if "encountered unexpected variable" in str(err):
                raise ValueError(
                    "These objects cannot be combined using only "
                    "xarray.combine_nested, instead either use "
                    "xarray.combine_by_coords, or do it manually "
                    "with xarray.concat, xarray.merge and "
                    "xarray.align"
                )
            else:
                raise
    else:
        combined = merge(
            datasets,
            compat=compat,
            fill_value=fill_value,
            join=join,
            combine_attrs=combine_attrs,
        )

    return combined


def _new_tile_id(single_id_ds_pair):
    tile_id, ds = single_id_ds_pair
    return tile_id[1:]


def _nested_combine(
    datasets,
    concat_dims,
    compat,
    data_vars,
    coords,
    ids,
    fill_value=dtypes.NA,
    join="outer",
    combine_attrs="drop",
):

    if len(datasets) == 0:
        return Dataset()

    # Arrange datasets for concatenation
    # Use information from the shape of the user input
    if not ids:
        # Determine tile_IDs by structure of input in N-D
        # (i.e. ordering in list-of-lists)
        combined_ids = _infer_concat_order_from_positions(datasets)
    else:
        # Already sorted so just use the ids already passed
        combined_ids = dict(zip(ids, datasets))

    # Check that the inferred shape is combinable
    _check_shape_tile_ids(combined_ids)

    # Apply series of concatenate or merge operations along each dimension
    combined = _combine_nd(
        combined_ids,
        concat_dims,
        compat=compat,
        data_vars=data_vars,
        coords=coords,
        fill_value=fill_value,
        join=join,
        combine_attrs=combine_attrs,
    )
    return combined


# Define type for arbitrarily-nested list of lists recursively
# Currently mypy cannot handle this but other linters can (https://stackoverflow.com/a/53845083/3154101)
DATASET_HYPERCUBE = Union[Dataset, Iterable["DATASET_HYPERCUBE"]]  # type: ignore


def combine_nested(
    datasets: DATASET_HYPERCUBE,
    concat_dim: Union[
        str, DataArray, None, Sequence[Union[str, "DataArray", pd.Index, None]]
    ],
    compat: str = "no_conflicts",
    data_vars: str = "all",
    coords: str = "different",
    fill_value: object = dtypes.NA,
    join: str = "outer",
    combine_attrs: str = "drop",
) -> Dataset:
    """
    Explicitly combine an N-dimensional grid of datasets into one by using a
    succession of concat and merge operations along each dimension of the grid.

    Does not sort the supplied datasets under any circumstances, so the
    datasets must be passed in the order you wish them to be concatenated. It
    does align coordinates, but different variables on datasets can cause it to
    fail under some scenarios. In complex cases, you may need to clean up your
    data and use concat/merge explicitly.

    To concatenate along multiple dimensions the datasets must be passed as a
    nested list-of-lists, with a depth equal to the length of ``concat_dims``.
    ``combine_nested`` will concatenate along the top-level list first.

    Useful for combining datasets from a set of nested directories, or for
    collecting the output of a simulation parallelized along multiple
    dimensions.