"""
Generate random regions.

Randomly form regions given various types of constraints
on cardinality and composition.
"""

__author__ = "David Folch David.Folch@nau.edu, Serge Rey sergio.rey@ucr.edu"

import copy

import numpy as np

from .components import check_contiguity

__all__ = ["RandomRegions", "RandomRegion"]


class RandomRegions:
    """Generate a list of RandomRegion instances.

    Parameters
    ----------

    area_ids : list
        The IDs indexing the areas to be grouped into regions (must be in
        the same order as spatial weights matrix if this is provided).
    num_regions : int (default None)
        The number of regions to generate (if ``None`` then this is chosen
        randomly from 2 to :math:`n` where :math:`n` is the number of areas).
    cardinality : list (default None)
        A list containing the number of areas to assign to regions
        (if ``num_regions`` is also provided then ``len(cardinality)``
        must equal ``num_regions``; if ``None`` then a list of length
        ``num_regions`` will be generated randomly).
    contiguity : libpysal.weights.W (default None)
        A spatial weights object (if ``None`` then contiguity will be ignored).
    maxiter : int (default 100)
        The maximum number attempts (for each permutation) at finding
        a feasible solution (only affects contiguity constrained regions).
    compact : bool (default False)
        Attempt to build compact regions (only affects contiguity constrained regions).
    max_swaps : int (default 1000000)
        The maximum number of swaps to find a feasible solution
        (only affects contiguity constrained regions).
    permutations : int (default 99)
        The number of ``RandomRegion`` instances to generate.

    Attributes
    ----------

    solutions : list
        A list of length ``permutations`` containing all
        ``RandomRegion`` instances generated.
    solutions_feas : list
        A list of the ``RandomRegion`` instances that resulted in feasible solutions.

    Examples
    --------

    Setup the data.

    >>> import libpysal
    >>> import numpy
    >>> from spopt.region import RandomRegions, RandomRegion
    >>> nregs = 13
    >>> cards = list(range(2,14)) + [10]
    >>> w = libpysal.weights.lat2W(10,10,rook=True)
    >>> ids = w.id_order

    Unconstrained:

    >>> numpy.random.seed(10)
    >>> t0 = RandomRegions(ids, permutations=2)
    >>> t0.solutions[0].regions[0]
    [19, 14, 43, 37, 66, 3, 79, 41, 38, 68, 2, 1, 60]

    Cardinality and contiguity constrained (``num_regions`` implied):

    >>> numpy.random.seed(60)
    >>> t1 = RandomRegions(
    ...     ids, num_regions=nregs, cardinality=cards, contiguity=w, permutations=2
    ... )
    >>> t1.solutions[0].regions[0]
    [62, 61, 81, 71, 64, 90, 72, 51, 80, 63, 50, 73, 52]

    Cardinality constrained (``num_regions`` implied):

    >>> numpy.random.seed(100)
    >>> t2 = RandomRegions(
    ...     ids, num_regions=nregs, cardinality=cards, permutations=2
    ... )
    >>> t2.solutions[0].regions[0]
    [37, 62]

    Number of regions and contiguity constrained:

    >>> numpy.random.seed(100)
    >>> t3 = RandomRegions(ids, num_regions=nregs, contiguity=w, permutations=2)
    >>> t3.solutions[0].regions[1]
    [62, 52, 51, 63, 61, 73, 41, 53, 60, 83, 42, 31, 32]

    Cardinality and contiguity constrained:

    >>> numpy.random.seed(60)
    >>> t4 = RandomRegions(ids, cardinality=cards, contiguity=w, permutations=2)
    >>> t4.solutions[0].regions[0]
    [62, 61, 81, 71, 64, 90, 72, 51, 80, 63, 50, 73, 52]

    Number of regions constrained:

    >>> numpy.random.seed(100)
    >>> t5 = RandomRegions(ids, num_regions=nregs, permutations=2)
    >>> t5.solutions[0].regions[0]
    [37, 62, 26, 41, 35, 25, 36]

    Cardinality constrained:

    >>> numpy.random.seed(100)
    >>> t6 = RandomRegions(ids, cardinality=cards, permutations=2)
    >>> t6.solutions[0].regions[0]
    [37, 62]

    Contiguity constrained:

    >>> numpy.random.seed(100)
    >>> t7 = RandomRegions(ids, contiguity=w, permutations=2)
    >>> t7.solutions[0].regions[1]
    [62, 61, 71, 63]

    """

    def __init__(
        self,
        area_ids,
        num_regions=None,
        cardinality=None,
        contiguity=None,
        maxiter=100,
        compact=False,
        max_swaps=1000000,
        permutations=99,
    ):
        solutions = []
        for _i in range(permutations):
            solutions.append(
                RandomRegion(
                    area_ids,
                    num_regions,
                    cardinality,
                    contiguity,
                    maxiter,
                    compact,
                    max_swaps,
                )
            )
        self.solutions = solutions
        self.solutions_feas = []
        for i in solutions:
            if i.feasible:
                self.solutions_feas.append(i)


class RandomRegion:
    """Randomly combine a given set of areas into two
    or more regions based on various constraints.

    Parameters
    ----------

    area_ids : list
        The IDs indexing the areas to be grouped into regions (must be in
        the same order as spatial weights matrix if this is provided).
    num_regions : int (default None)
        The number of regions to generate (if ``None`` then this is chosen
        randomly from 2 to :math:`n` where :math:`n` is the number of areas).
    cardinality : list (default None)
        A list containing the number of areas to assign to regions
        (if ``num_regions`` is also provided then ``len(cardinality)``
        must equal ``num_regions``; if ``None`` then a list of length
        ``num_regions`` will be generated randomly).
    contiguity : libpysal.weights.W (default None)
        A spatial weights object (if ``None`` then contiguity will be ignored).
    maxiter : int (default 100)
        The maximum number attempts (for each permutation) at finding
        a feasible solution (only affects contiguity constrained regions).
    compact : bool (default False)
        Attempt to build compact regions (only affects contiguity constrained regions).
    max_swaps : int (default 1000000)
        The maximum number of swaps to find a feasible solution
        (only affects contiguity constrained regions).

    Attributes
    ----------

    feasible : bool
        If ``True`` then solution was found.
    regions : list
        A list of lists of regions where each list has the IDs of areas in that region.

    Examples
    --------

    Setup the data.

    >>> import libpysal
    >>> import numpy
    >>> from spopt.region import RandomRegions, RandomRegion
    >>> nregs = 13
    >>> cards = list(range(2,14)) + [10]
    >>> w = libpysal.weights.lat2W(10,10,rook=True)
    >>> ids = w.id_order

    Unconstrained:

    >>> numpy.random.seed(10)
    >>> t0 = RandomRegion(ids)
    >>> t0.regions[0]
    [19, 14, 43, 37, 66, 3, 79, 41, 38, 68, 2, 1, 60]

    Cardinality and contiguity constrained (``num_regions`` implied):

    >>> numpy.random.seed(60)
    >>> t1 = RandomRegion(ids, num_regions=nregs, cardinality=cards, contiguity=w)
    >>> t1.regions[0]
    [62, 61, 81, 71, 64, 90, 72, 51, 80, 63, 50, 73, 52]

    Cardinality constrained (``num_regions`` implied):

    >>> numpy.random.seed(100)
    >>> t2 = RandomRegion(ids, num_regions=nregs, cardinality=cards)
    >>> t2.regions[0]
    [37, 62]

    Number of regions and contiguity constrained:

    >>> numpy.random.seed(100)
    >>> t3 = RandomRegion(ids, num_regions=nregs, contiguity=w)
    >>> t3.regions[1]
    [62, 52, 51, 63, 61, 73, 41, 53, 60, 83, 42, 31, 32]

    Cardinality and contiguity constrained:

    >>> numpy.random.seed(60)
    >>> t4 = RandomRegion(ids, cardinality=cards, contiguity=w)
    >>> t4.regions[0]
    [62, 61, 81, 71, 64, 90, 72, 51, 80, 63, 50, 73, 52]

    Number of regions constrained:

    >>> numpy.random.seed(100)
    >>> t5 = RandomRegion(ids, num_regions=nregs)
    >>> t5.regions[0]
    [37, 62, 26, 41, 35, 25, 36]

    Cardinality constrained:

    >>> numpy.random.seed(100)
    >>> t6 = RandomRegion(ids, cardinality=cards)
    >>> t6.regions[0]
    [37, 62]

    Contiguity constrained:

    >>> numpy.random.seed(100)
    >>> t7 = RandomRegion(ids, contiguity=w)
    >>> t7.regions[0]
    [37, 36, 38, 39]

    """

    def __init__(
        self,
        area_ids,
        num_regions=None,
        cardinality=None,
        contiguity=None,
        maxiter=1000,
        compact=False,
        max_swaps=1000000,
    ):
        self.n = len(area_ids)
        ids = copy.copy(area_ids)
        self.ids = list(np.random.permutation(ids))
        self.area_ids = area_ids
        self.regions = []
        self.feasible = True

        # tests for input argument consistency
        if cardinality and self.n != sum(cardinality):
            self.feasible = False
            raise ValueError(
                f"Number of areas ({self.n}) does not match "
                f"`cardinality` ({sum(cardinality)})."
            )
        if contiguity and area_ids != contiguity.id_order:
            self.feasible = False
            raise ValueError(
                "Order of `area_ids` must match order in `contiguity`. Inspect "
                "the `area_ids` and `contiguity.id_order` input parameters."
            )
        if num_regions and cardinality and num_regions != len(cardinality):
            self.feasible = False
            raise ValueError(
                f"Number of regions ({num_regions}) does not match "
                f"`cardinality` ({len(cardinality)})."
            )

        # dispatches the appropriate algorithm
        if num_regions and cardinality and contiguity:
            # conditioning on cardinality and contiguity (number of regions implied)
            self.build_contig_regions(
                num_regions, cardinality, contiguity, maxiter, compact, max_swaps
            )
        elif num_regions and cardinality:
            # conditioning on cardinality (number of regions implied)
            region_breaks = self.cards2breaks(cardinality)
            self.build_noncontig_regions(num_regions, region_breaks)
        elif num_regions and contiguity:
            # conditioning on number of regions and contiguity
            cards = self.get_cards(num_regions)
            self.build_contig_regions(
                num_regions, cards, contiguity, maxiter, compact, max_swaps
            )
        elif cardinality and contiguity:
            # conditioning on cardinality and contiguity
            num_regions = len(cardinality)
            self.build_contig_regions(
                num_regions, cardinality, contiguity, maxiter, compact, max_swaps
            )
        elif num_regions:
            # conditioning on number of regions only
            region_breaks = self.get_region_breaks(num_regions)
            self.build_noncontig_regions(num_regions, region_breaks)
        elif cardinality:
            # conditioning on number of cardinality only
            num_regions = len(cardinality)
            region_breaks = self.cards2breaks(cardinality)
            self.build_noncontig_regions(num_regions, region_breaks)
        elif contiguity:
            # conditioning on number of contiguity only
            num_regions = self.get_num_regions()
            cards = self.get_cards(num_regions)
            self.build_contig_regions(
                num_regions, cards, contiguity, maxiter, compact, max_swaps
            )
        else:
            # unconditioned
            num_regions = self.get_num_regions()
            region_breaks = self.get_region_breaks(num_regions)
            self.build_noncontig_regions(num_regions, region_breaks)

    def get_num_regions(self):
        return np.random.randint(2, self.n)

    def get_region_breaks(self, num_regions):
        region_breaks = set()
        while len(region_breaks) < num_regions - 1:
            region_breaks.add(np.random.randint(1, self.n - 1))
        region_breaks = list(region_breaks)
        region_breaks.sort()
        return region_breaks

    def get_cards(self, num_regions):
        region_breaks = self.get_region_breaks(num_regions)
        cards = []
        start = 0
        for i in region_breaks:
            cards.append(i - start)
            start = i
        cards.append(self.n - start)
        return cards

    def cards2breaks(self, cards):
        region_breaks = []
        break_point = 0
        for i in cards:
            break_point += i
            region_breaks.append(break_point)
        region_breaks.pop()
        return region_breaks

    def build_noncontig_regions(self, num_regions, region_breaks):  # noqa ARG002
        start = 0
        for i in region_breaks:
            self.regions.append(self.ids[start:i])
            start = i
        self.regions.append(self.ids[start:])

    def grow_compact(self, w, test_card, region, candidates, potential):
        # try to build a compact region by exhausting all existing
        # potential areas before adding new potential areas
        add_areas = []
        while potential and len(region) < test_card:
            pot_index = np.random.randint(0, len(potential))
            add_area = potential[pot_index]
            region.append(add_area)
            candidates.remove(add_area)
            potential.remove(add_area)
            add_areas.append(add_area)
        for i in add_areas:
            potential.extend(
                [
                    j
                    for j in w.neighbors[i]
                    if j not in region and j not in potential and j in candidates
                ]
            )
        return region, candidates, potential

    def grow_free(self, w, test_card, region, candidates, potential):  # noqa ARG002
        # increment potential areas after each new area is
        # added to the region (faster than the grow_compact)
        pot_index = np.random.randint(0, len(potential))
        add_area = potential[pot_index]
        region.append(add_area)
        candidates.remove(add_area)
        potential.remove(add_area)
        potential.extend(
            [
                i
                for i in w.neighbors[add_area]
                if i not in region and i not in potential and i in candidates
            ]
        )
        return region, candidates, potential

    def build_contig_regions(
        self, num_regions, cardinality, w, maxiter, compact, max_swaps
    ):
        grow_region = self.grow_compact if compact else self.grow_free
        _iter = 0
        while _iter < maxiter:
            # regionalization setup
            regions = []
            size_pre = 0
            counter = -1
            area2region = {}
            self.feasible = False
            swap_count = 0
            cards = copy.copy(cardinality)
            cards.sort()  # try to build largest regions first (pop from end of list)
            candidates = copy.copy(self.ids)  # these are already shuffled

            # begin building regions
            while candidates and swap_count < max_swaps:
                # setup test to determine if swapping is needed
                if size_pre == len(regions):
                    counter += 1
                else:
                    counter = 0
                    size_pre = len(regions)
                # test if swapping is needed
                if counter == len(candidates):
                    # start swapping
                    # -- swapping simply changes the candidate list
                    swap_in = None  # area to become new candidate
                    while swap_in is None:  # PEP8 E711
                        swap_count += 1
                        swap_out = candidates.pop(0)  # area to remove from candidates
                        swap_neighs = copy.copy(w.neighbors[swap_out])
                        swap_neighs = list(np.random.permutation(swap_neighs))
                        # select area to add to candidates
                        # -- (i.e. remove from an existing region)
                        for i in swap_neighs:
                            if i not in candidates:
                                join = i  # area linking swap_in to swap_out
                                swap_index = area2region[join]
                                swap_region = regions[swap_index]
                                swap_region = list(np.random.permutation(swap_region))
                                for j in swap_region:
                                    # test to ensure region
                                    # connectivity after removing area
                                    swap_region_test = swap_region[:] + [swap_out]
                                    if check_contiguity(w, swap_region_test, j):
                                        swap_in = j
                                        break
                            if swap_in is not None:  # PEP8 E711
                                break
                        else:
                            candidates.append(swap_out)
                    # swapping cleanup
                    regions[swap_index].remove(swap_in)
                    regions[swap_index].append(swap_out)
                    area2region.pop(swap_in)
                    area2region[swap_out] = swap_index
                    candidates.append(swap_in)
                    counter = 0

                # setup to build a single region
                building = True
                seed = candidates.pop(0)
                region = [seed]
                potential = [i for i in w.neighbors[seed] if i in candidates]
                test_card = cards.pop()

                # begin building single region
                while building and len(region) < test_card:
                    if potential:
                        region, candidates, potential = grow_region(
                            w, test_card, region, candidates, potential
                        )
                    else:
                        # not enough potential neighbors to reach test_card size
                        building = False
                        cards.append(test_card)
                        if len(region) in cards:
                            # constructed region matches another candidate region size
                            cards.remove(len(region))
                        else:
                            # constructed region doesn't match a candidate region size
                            candidates.extend(region)
                            region = []

                # cleanup when successful region built
                if region:
                    regions.append(region)
                    region_index = len(regions) - 1
                    for i in region:
                        # area2region needed for swapping
                        area2region[i] = region_index
            # handling of regionalization result
            if len(regions) < num_regions:
                # regionalization failed
                self.ids = list(np.random.permutation(self.ids))
                regions = []
                _iter += 1
            else:
                # regionalization successful
                self.feasible = True
                _iter = maxiter
        self.regions = regions
