class TileExtractionException(Exception):
    """Thrown when a tile is requested but cannot be fetched"""
    pass class Image(object):
    """
    Abstract representation of an (possibly huge) image.
    To actually explore the image and its representation, it is recommended to iterate over tiles extracted
    using a TileTopology.

    Notes
    -----
    To avoid memory leaks the representation of the image should not be stored into memory as a class attribute.
    Alternatively, the loading should be deferred to the call of np_image.
    """
    __metaclass__ = ABCMeta

    @abstractproperty
    def height(self):
        """Return the height of the image
        Returns
        -------
        height: int
            Height of the image
        """
        pass

    @abstractproperty
    def width(self):
        """Return the width of the image
        Returns
        -------
        width: int
            Width of the image
        """
        pass

    @abstractproperty
    def channels(self):
        """Return the number of channels in the image
        Returns
        -------
        width: int
            Width of the image
        """
        pass

    @abstractproperty
    def np_image(self):
        """Return a numpy representation of the image

        Returns
        -------
        np_image: ndarray
            A numpy representation of the image

        Raises
        ------
        ImageExtractionException: when the image cannot be extracted (and so is its representation)

        Notes
        -----
        When working with very big images, this method may be "disabled" (i.e. raise NotImplementedError) to prevent
        user of the class to fully load them into memory. Tiles should be used instead to explore large images.
        """
        pass

    def window(self, offset, max_width, max_height, polygon_mask=None):
        """Build an image object representing a window of the image

        Parameters
        ----------
        offset: (int, int)
            The (x, y) coordinates of the pixel at the origin point of the window in the parent image
        max_width: int
            The maximum width of the window
        max_height: int
            The maximum height of the window
        polygon_mask: Polygon (optional, default: None)
            The polygon representing the alpha mask to apply to the image window. The polygon must be referenced
            to the full image top-left pixel.

        Returns
        -------
        window: ImageWindow
            The resulting image window
        """
        # width are bound to the current window size, not the parent one
        width = min(max_width, self.width - offset[0])
        height = min(max_height, self.height - offset[1])
        translated_polygon = translate(polygon_mask, -offset[0], -offset[1]) if polygon_mask is not None else None
        return ImageWindow(self, offset, width, height, polygon_mask=translated_polygon)

    def window_from_polygon(self, polygon, mask=False):
        """Build and return a window being the minimum bounding box around the passed polygon.
        At least a part of the polygon should fit the image

        Parameters
        ----------
        polygon: shapely.geometry.Polygon
            The polygon of which the minimum bounding window should be returned
        mask: boolean (optional, default: False)
            True for applying a mask to the image

        Returns
        -------
        window: ImageWindow
            The resulting image window

        Raises
        ------
        IndexError: if the polygon box offset is not inside the image
        """
        offset, width, height = Image.polygon_box(polygon)
        if not self._check_tile_offset(offset):
            raise IndexError("Offset {} is out of the image.".format(offset))
        return self.window(offset, width, height, polygon_mask=polygon if mask else None)

    def tile(self, tile_builder, offset, max_width, max_height, polygon_mask=None):
        """Extract a tile from the image

        Parameters
        ----------
        tile_builder: TileBuilder
            A tile builder for constructing the Tile object
        offset: (int, int)
            The (x, y) coordinates of the pixel at the origin point of the tile in the parent image
        max_width: int
            The maximum width of the tile
        max_height: int
            The maximum height of the tile
        polygon_mask: Polygon (optional, default: None)
            The polygon representing the alpha mask to apply to the image window. The polygon must be referenced
            to the full image top-left pixel.

        Returns
        -------
        tile: Tile
            The extracted tile

        Raises
        ------
        IndexError: if the offset is not inside the image
        TileExtractionException: if the tile cannot be extracted
        """
        if not self._check_tile_offset(offset):
            raise IndexError("Offset {} is out of the image.".format(offset))
        width = min(max_width, self.width - offset[0])
        height = min(max_height, self.height - offset[1])
        translated_polygon = translate(polygon_mask, -offset[0], -offset[1]) if polygon_mask is not None else None
        return tile_builder.build(self, offset, width, height, polygon_mask=translated_polygon)

    def tile_from_polygon(self, tile_builder, polygon, mask=False):
        """Build a tile being the minimum bounding box around the passed polygon

        Parameters
        ----------
        tile_builder: TileBuilder
            The builder for effectively building the tile
        polygon: shapely.geometry.Polygon
            The polygon of which the bounding tile should be returned
        mask: boolean (optional, default: False)
            True for applying the polygon as an alpha mask to the tile

        Returns
        -------
        tile: Tile
            The bounding tile

        Raises
        ------
        IndexError: if the offset is not inside the image
        TileExtractionException: if the tile cannot be extracted
        """
        offset, width, height = Image.polygon_box(polygon)
        return self.tile(tile_builder, offset, width, height, polygon_mask=polygon if mask else None)

    def tile_iterator(self, builder, max_width=1024, max_height=1024, overlap=0):
        """Build and return a tile iterator that iterates over the image

        Parameters
        ----------
        builder: TileBuilder
            The builder to user for actually constructing the tiles while iterating over the image
        max_width: int (optional, default: 1024)
            The maximum width of the tiles to build
        max_height: int (optional, default: 1024)
            The maximum height of the tiles to build
        overlap: int (optional, default: 0)
            The overlapping between tiles

        Returns
        -------
        iterator: TileTopologyIterator
            An iterator that iterates over a tile topology of the image
        """
        topology = TileTopology(self, max_width=max_width, max_height=max_height, overlap=overlap)
        return TileTopologyIterator(builder, topology)

    def tile_topology(self, tile_builder, max_width=1024, max_height=1024, overlap=0):
        """Builds a tile topology for this the image

        Parameters
        ----------
        tile_builder: TileBuilder
            The tile builder
        max_width: int (optional, default: 1024)
            The maximum width of the tiles to build
        max_height: int (optional, default: 1024)
            The maximum height of the tiles to build
        overlap: int (optional, default: 0)
            The overlapping between tiles

        Returns
        -------
        topology: TileTopology
            The image tile topology
        """
        return TileTopology(self, tile_builder,  max_width=max_width, max_height=max_height, overlap=overlap)

    def _check_tile_offset(self, offset):
        """Check whether the given tile offset belongs to the image

        Parameters
        ----------
        offset: (int, int)
            The (x, y) coordinates of the pixel at the origin point of the tile in the parent image

        Returns
        -------
        valid: bool
            True if the offset is valid, False otherwise
        """
        return 0 <= offset[0] < self.width and 0 <= offset[1] < self.height

    @staticmethod
    def polygon_box(polygon):
        """From a shapely polygon, return the information about the polygon bounding box.
        These information are offset (x, y), width and height.

        Parameters
        ----------
        polygon: shapely.geometry.Polygon
            The polygon of which the bounding box should be computed

        Returns
        -------
        offset: tuple (int, int)
            The offset of the polygon bounding box
        width: int
            The bounding box width
        height
            The bounding box heigth
        """
        minx, miny, maxx, maxy = polygon.bounds
        fminx, fminy = int(math.floor(minx)), int(math.floor(miny))
        cmaxx, cmaxy = int(math.ceil(maxx)), int(math.ceil(maxy))
        offset = (fminx, fminy)
        width = cmaxx - fminx
        height = cmaxy - fminy
        return offset, width, height

    @property
    def base_image(self):
        """Added for convenience. The base image of an image is the image itself by default.
        """
        return self class TileBuilder(object):
    """An interface to be implemented by any class which builds specific tiles
    """
    __metaclass__ = ABCMeta

    @abstractmethod
    def build(self, image, offset, width, height, polygon_mask=None):
        """Build and return a tile object

        Parameters
        ----------
        image: Image
            The image from which the tile is extracted
        offset: (int, int)
            The (x, y) coordinates of the pixel at the origin point of the slide in the parent image
        width: int
            The exact width of the tile
            /!\ The resulting tile must not overflow the image
        height: int
            The exact height of the tile
            /!\ The resulting tile must not overflow the image
        polygon_mask: Polygon (optional, default: None)
            The polygon representing the alpha mask to apply to the tile window

        Returns
        -------
        tile: Tile
            The built tile object

        Errors
        ------
        TypeError: when the reference image is not set
        TileExtractionException: when the tile cannot be extracted

        Notes
        -----
        The coordinates origin is the leftmost pixel at the top of the slide
        """
        pass

    def build_from_polygon(self, image, polygon, mask=False):
        """Build a tile boxing the given polygon in the image

        Parameters
        ----------
        image: Image
            The image from which the tile should be extracted
        polygon: Polygon
            The polygon of which the bounding tile should be returned
        mask: boolean (optional, default: False)
            True for applying the polygon as an alpha mask on the tile window

        Returns
        -------
        tile: Tile
            The bounding tile

        Errors
        ------
        TypeError: when the reference image is not set
        TileExtractionImage: when the tile cannot be extracted
        """
        return image.tile_from_polygon(self, polygon, mask=mask) class DefaultTileBuilder(TileBuilder):
    """A tile builder which builds Tile objects"""
    def build(self, image, offset, width, height, polygon_mask=None):
        return Tile(image, offset, width, height, polygon_mask=polygon_mask) class SkipBordersTileTopology(TileTopology):
    """A topology that ensures that all tiles have the specified dimensions. This is done by skipping tiles at right
    and bottom borders."""
    def __init__(self, topology):
        """
        Parameters
        ----------
        topology: TileTopology
            A regular topology
        """
        super(SkipBordersTileTopology, self).__init__(
            image=topology._image,
            tile_builder=topology._tile_builder,
            max_width=topology._max_width,
            max_height=topology._max_height,
            overlap=topology._overlap
        )
        self._parent = topology
        skip_h, skip_v = _borders_have_expected_size(topology, self._max_width, self._max_height)
        self._skip_h = skip_h
        self._skip_v = skip_v

    def _convert_id(self, parent_identifier):
        """Convert a parent tile identifier to the corresponding identifier for this topology.
        Returns
        -------
        identifier: int|None
            A valid identifier for this topology, None if the parent identifier corresponds to an invalid tile
        """
        if parent_identifier is None:
            return None
        row, col = self._parent._tile_coord(parent_identifier)
        # check that tile is actually valid
        if self._skip_h and col == self._parent.tile_horizontal_count - 1:
            return None
        if self._skip_v and row == row == self._parent.tile_vertical_count - 1:
            return None
        return parent_identifier - (row if self._skip_h else 0)

    @property
    def tile_horizontal_count(self):
        return super().tile_horizontal_count - (1 if self._skip_h else 0)

    @property
    def tile_vertical_count(self):
        return super().tile_vertical_count - (1 if self._skip_v else 0)

    def tile_neighbours(self, identifier):
        row, col = self._tile_coord(identifier)
        parent_identifier = identifier + (row if self._skip_h else 0)
        return tuple([self._convert_id(_id) for _id in self._parent.tile_neighbours(parent_identifier)]) class FixedSizeTileTopology(TileTopology):
    """A topology that ensures that all tiles have the specified dimensions. This is done by extending tiles at left
    and bottom borders to overlap their neighbouring by more than the specified overlap."""
    def __init__(self, topology):
        """
        Parameters
        ----------
        topology: TileTopology
            A regular topology
        """
        super(FixedSizeTileTopology, self).__init__(
            image=topology._image,
            tile_builder=topology._tile_builder,
            max_width=topology._max_width,
            max_height=topology._max_height,
            overlap=topology._overlap
        )

    def tile_offset(self, identifier):
        row, col = self._tile_coord(identifier)
        off_x, off_y = super().tile_offset(identifier)
        if row == self.tile_vertical_count - 1:
            off_y -= self._max_height - (self._image.height - off_y)
        if col == self.tile_horizontal_count - 1:
            off_x -= self._max_width - (self._image.width - off_x)
        # take max for when image is too small
        return max(off_x, 0), max(off_y, 0) class WorkflowInformation(object):
    """Workflow information classes (immutable)"""

    DATA_FIELD_POLYGONS = "polygons"
    DATA_FIELD_LABELS = "labels"
    TUPLE_FIELD_POLYGONS = "polygon"
    TUPLE_FIELD_LABELS = "label"

    def __init__(self, polygons, labels, timing, **kwargs):
        """Constructor
        Parameters
        ----------
        polygons: ndarray (subtype: Polygon, size: n)
            The detected objects
        labels: ndarray (subtype: int, size: n)
            Their associated labels
        timing: WorkflowTiming 
            The workflow execution timing information
        **kwargs: 
            Any other information gathered during execution. Each key must be the (pluralized) name of the data. Each 
            value is a tuple of which the first element is a ndarray of size n containing the items for this 
            information and the second element is the the singularized name (key singularized).
        
        Raises
        ------
        ValueError: if data size is invalid or if the passed names clash with class fields
        """
        self._data = {key: np.asarray(value[0]) for key, value in kwargs.items()}
        self._data[self.DATA_FIELD_POLYGONS] = shape_array(polygons)
        self._data[self.DATA_FIELD_LABELS] = np.array(labels)
        self._timing = timing

        # check arrays sizes
        curr_size = None
        for data_name, data_array in self._data.items():
            if curr_size is not None and curr_size != len(data_array):
                raise ValueError(
                    "All information vectors should have the same size. Field '"
                    "{}' has size {} while other(s) have {}.".format(data_name, len(data_array), curr_size)
                )
            curr_size = len(data_array)

        # add data fields as properties
        data_fields = set(kwargs.keys()).intersection(dir(self.__class__))
        if len(data_fields) > 0:
            raise ValueError("Some data fields clash with some class fields '{}'.".format(data_fields))

        self._tuple_type_fields = [self.TUPLE_FIELD_POLYGONS, self.TUPLE_FIELD_LABELS] + [v[1] for v in kwargs.values()]
        self._tuple_type = self._get_namedtuple(self._tuple_type_fields)
        self._fields = [self.DATA_FIELD_POLYGONS, self.DATA_FIELD_LABELS] + list(kwargs.keys())
        for field in kwargs.keys():
            self.__dict__[field] = self._data[field]

    @property
    def polygons(self):
        return self._data[self.DATA_FIELD_POLYGONS]

    @property
    def labels(self):
        return self._data[self.DATA_FIELD_LABELS]

    @property
    def timing(self):
        return self._timing

    @property
    def fields(self):
        return self._fields

    def __getitem__(self, item):
        return self._tuple_type(**{
            tuple_field: self._data[data_field][item]
            for data_field, tuple_field
            in zip(self._fields, self._tuple_type_fields)
        })

    def __len__(self):
        return len(self._data[self.DATA_FIELD_POLYGONS])

    def __iter__(self):
        for i in range(len(self)):
            yield self[i]

    def merge(self, other):
        """Merge the current information object with other into a new object"""
        self._is_compatible(other)
        other_fields = dict()
        for field, tuple_field in zip(self.fields, self._tuple_type_fields):
            if field == self.DATA_FIELD_POLYGONS or field == self.DATA_FIELD_LABELS :
                continue
            other_fields[field] = (
                np.concatenate((self._data[field], other._data[field])),
                tuple_field
            )
        return WorkflowInformation(
            polygons=np.concatenate((self.polygons, other.polygons)),
            labels=np.concatenate((self.labels, other.labels)),
            timing=merge_timings(self.timing, other.timing),
            **other_fields
        )

    def _is_compatible(self, other):
        """Check whether the other object is compatible for merging with the current one"""
        if not isinstance(other, WorkflowInformation):
            raise TypeError("'other' should be a WorkflowInformation object (actual type is '{}').".format(type(other)))
        other_fields = set(other.fields)
        if len(other_fields.intersection(self.fields)) != len(self.fields):
            raise ValueError("Fields in other information object are different.")
        other_tuple_fields = set(other._tuple_type_fields)
        if len(other_tuple_fields.intersection(self._tuple_type_fields)) != len(self._tuple_type_fields):
            raise ValueError("Tuple namefFields in other information object are different.")

    @classmethod
    def _get_namedtuple(cls, fields):
        return namedtuple('object_info', fields)

    def __getstate__(self):  # to make it serializable
        d = copy(self.__dict__)
        d["_tuple_type"] = None
        return d

    def __setstate__(self, state):
        self.__dict__.update(state)
        self._tuple_type = self._get_namedtuple(self._tuple_type_fields) class BinaryLocator(SemanticLocator):
    """Locator that assigns the 0-label to background and 255 to foreground
    Mostly there for backward compatibility.
    """
    def __init__(self):
        super(BinaryLocator, self).__init__(background=0) class SemanticLocator(object):
    """Interface to be implemented by Locator objects"""
    def __init__(self, background=-1):
        """
        Parameters
        ----------
        background: int (default: -1)
            The value corresponding to the background pixel label. Polygons won't be extracted for this class.
            If the value is not a class label, all the classes contained in the mask will be extracted.
        """
        self._background = background

    def locate(self, mask, offset=None):
        """Extract polygons representing the foreground elements of the segmented image.
        
        Parameters
        ----------
        mask: ndarray (shape: (width, height))
            A NumPy representation of a segmented image. Each pixel is associated with its (integer) class label. 
            
        offset: (int, int) (optional, default: (0,0))
            An offset indicating the coordinates of the top-leftmost pixel of the segmented image in the
            original image.
            
        Returns
        -------
        polygons : iterable (subtype: (shapely.geometry.Polygon, int))
            An iterable containing the polygons extracted from the segmented image as well as the pixel value
            which resulted in generating this polygon. The reference point (0,0) for the polygons coordinates is 
            the upper-left corner of the initial image.
        """
        return mask_to_objects_2d(mask, background=self._background, offset=offset) class Loggable(object):
    """A base class to be implemented by any component that can produce logs through a logger.
    By default the logger object is set with a SilentLogger.
    """
    __metaclass__ = ABCMeta

    def __init__(self, logger=SilentLogger()):
        self._logger = logger

    @property
    def logger(self):
        """Get the logger of the loggable object
        Returns
        -------
        logger: Logger
            The logger object
        """
        return self._logger

    @logger.setter
    def logger(self, logger):
        """Set the logger of the loggable object
        Parameters
        ----------
        logger: Logger
            The logger object to set
        """
        self._logger = logger class SilentLogger(Logger):
    """A logger that ignore messages
    """
    def __init__(self, prefix=True):
        Logger.__init__(self, Logger.SILENT, prefix=prefix)

    def _print(self, formatted_msg):
        pass class SemanticMerger(object):
    """A class for merging labelled polygons. Close polygons having the same label are merged.
    """
    def __init__(self, tolerance, policy=SemanticMergingPolicy.POLICY_NO_MERGE):
        """Constructor for Merger objects

        Parameters:
        -----------
        tolerance: int
            Maximal distance between two polygons so that they are considered from the same object
        policy: str
            A merging policy to apply for overlapping polygons with different classes
        """
        self._tolerance = tolerance
        self._policy = policy

    def merge(self, tiles, polygons, tile_topology, labels=None):
        """Merge the polygons passed in a per-tile fashion according to the tile topology

        Parameters
        ----------
        tiles: iterable of tile identifiers (size: n, subtype: int)
            The identifiers of the tiles containing the polygons to merge
        polygons: iterable (size: n, subtype: iterable of shapely.geometry.Polygon)
            The polygons to merge provided as an iterable of iterables. The iterable i in polygons contains all 
            the polygons detected in the tile tiles[i].
        tile_topology: TileTopology
            The tile topology that was used to generate the tiles passed in polygons_tiles
        labels: iterable (size: n, subtype: iterable of int, default: None)
            The labels associated with the polygons. If None, all polygons are considered to have the same label.
            
        Returns
        -------
        polygons: iterable (size: m, subtype: shapely.geometry.Polygon)
            An iterable of polygons objects containing the merged polygons
        out_labels: iterable (size: m, subtype: int)
            The labels of the merged polygons. If labels was None, this return value is omitted.
        """
        tiles_dict, polygons_dict, labels_dict = self._build_dicts(tiles, polygons, tile_topology, labels=labels)
        # no polygons
        if len(polygons_dict) <= 0:
            return np.array([]) if labels is None else (np.array([]), np.array([]))
        
        # stores the polygons indexes as nodes
        geom_uf = UnionFind(polygons_dict.keys())
        
        # add edges between polygons that should be merged
        for tile_id, tile_polygons in tiles_dict.items():
            # check whether polygons in neighbour tiles must be merged 
            for side, neighbour in enumerate(tile_topology.tile_neighbours(tile_id)):
                if neighbour is None:
                    continue
                curr_candidates = tile_polygons.polygons_by_side(side)
                neigh_candidates = tiles_dict[neighbour].polygons_by_side(TilePolygons.opposite_side(side))
                self._register_merge(curr_candidates, neigh_candidates, polygons_dict, labels_dict, geom_uf)
        
        merged_polygons, merged_labels = self._do_merge(geom_uf, polygons_dict, labels_dict)
        if labels is None:
            return shape_array(merged_polygons)
        else:
            return shape_array(merged_polygons), np.array(merged_labels)

    def _register_merge(self, polygons1, polygons2, polygons_dict, labels_dict, geom_uf):
        """Compare 2-by-2 the polygons in the two arrays. If they are very close (using `self._tolerance` as distance
        threshold) and can be merged regarding their labels and the merging policy, they are registered as polygons to 
        be merged in the geometry graph (the registration being an edge between the nodes corresponding to the polygons 
        in geom_graph).

        Parameters
        ----------
        polygons1: iterable
            Iterable of integers containing polygons indexes
        polygons2: iterable
            Iterable of integers containing polygons indexes
        polygons_dict: dict
            Dictionary mapping polygon identifiers with actual shapely polygons objects
        labels_dict: dict
            Dictionnary mapping polygon ids with their labels
        geom_graph: UnionFind
            Disjoint set structure for registering meregs
        """
        for poly_id1 in polygons1:
            for poly_id2 in polygons2:
                if geom_uf.same(poly_id1, poly_id2):
                    continue
                poly1, poly2 = polygons_dict[poly_id1], polygons_dict[poly_id2]
                label1, label2 = labels_dict[poly_id1], labels_dict[poly_id2]
                if poly1.distance(poly2) < self._tolerance and label1 == label2:
                    geom_uf.union(poly_id1, poly_id2)

    def _do_merge(self, geom_uf, polygons_dict, labels_dict):
        """Effectively merges the polygons that were registered to be merged in the geom_graph Graph and return the
        resulting polygons in a list.

        Parameters
        ----------
        geom_uf: UnionFind
            A disjoint set structure with registered merges
        polygons_dict: dict
            Dictionary mapping polygon identifiers with actual shapely polygons objects
        labels_dict: dict
            Dictionnary mapping polygon ids with their labels

        Returns
        -------
        polygons: iterable
            An iterable of polygons objects containing the merged polygons
        """
        dilation_dist = self._tolerance
        join = JOIN_STYLE.mitre
        merged_polygons = []
        merged_labels = []
        for component in geom_uf.connected_components():
            if len(component) == 1:
                polygon = polygons_dict[component[0]]
                label = labels_dict[component[0]]
            else:
                polygons = [polygons_dict[poly_id].buffer(dilation_dist, join_style=join) for poly_id in component]
                polygon = unary_union(polygons).buffer(-dilation_dist, join_style=join)
                # determine label (take label representing the largest area)
                areas = np.array([polygons_dict[poly_id].area for poly_id in component])
                labels = np.array([labels_dict[poly_id] for poly_id in component])
                label = aggr_max_area_label(areas, labels)
            merged_polygons.append(polygon)
            merged_labels.append(label)
        return merged_polygons, merged_labels

    def _build_dicts(self, tiles, polygons, topology, labels=None):
        """Given a array of tuples (polygons, tile), return dictionaries for executing the merging:

        Parameters
        ----------        
        tiles: iterable of tile identifiers (size: n, subtype: int)
            The identifiers of the tiles containing the polygons to merge
        polygons: iterable (size: n, subtype: iterable of shapely.geometry.Polygon)
            The polygons to merge provided as an iterable of iterables. The iterable i in polygons contains all 
            the polygons detected in the tile tiles[i].
        labels: iterable (size: n, subtype: iterable of int, default: None)
            The labels associated with the polygons. If None, all polygons are considered to have the same label.
        topology: TileTopology
            The tile topology

        Returns
        -------
        polygons_dict: dictionary
            Maps a unique integer identifier with a polygon. All the polygons passed to the functions are given an
            identifier and are stored in this dictionary
        tiles_dict:
            Maps a tile identifier with the an array containing the ids of the polygons located in this tile.
        """
        tiles_dict = dict()
        polygons_dict = dict()
        labels_dict = dict()

        polygon_cnt = 1
        for i, (tile_id, polygons) in enumerate(zip(tiles, polygons)):

            curr_tile_poly_dict = dict()
            for j, polygon in enumerate(polygons):
                curr_tile_poly_dict[polygon_cnt] = polygon
                labels_dict[polygon_cnt] = 1 if labels is None else labels[i][j]
                polygon_cnt += 1

            tiles_dict[tile_id] = TilePolygons(tile_id, topology, curr_tile_poly_dict, filter_dist=self._tolerance + topology.overlap)
            polygons_dict.update(curr_tile_poly_dict)

        return tiles_dict, polygons_dict, labels_dict class WorkflowTiming(dict):
    """A class that computes and stores execution times for various phases of the workflow.
    
    The timing object compute times on a per-phase basis. The phases are chosen by the caller and must
    be strings. To indicate sub-phases, the caller can use dot-notation. For instance, in "segment.cut", "cut" is 
    a sub-phase of "segment". 
    """

    def __init__(self, root=None):
        """
        Parameters
        ----------
        root: str (default: None)
            A root phase to prepend to any phase passed to the timing object. Set to None for not preprending anything.
        
        Raises
        ------
        ValueError: if the root phase is an invalid phase
        """
        super(WorkflowTiming, self).__init__()
        if root is not None:
            self._validate_phase(root)
        self._starts = dict()
        self._root = root

    def _full_phase(self, phase):
        """Return the full phase (user phase with prepended root phase)"""
        if self._root is not None:
            return ".".join([self._root, phase])
        else:
            return phase

    @classmethod
    def _validate_phase(cls, phase):
        """Validate the phase identifier 
        Parameters
        ----------
        phase: str
            The phase identifier to validate.
        
        Raises
        ------
        ValueError: if the phase is invalid (starts or ends with a dot or contains consecutive dots)
        """
        if phase is None or len(phase) == 0 or phase.startswith(".") or phase.endswith(".") or ".." in phase:
            raise ValueError("Invalid phase identifier ''.".format(phase))

    def start(self, phase):
        """Register the start time of the given phase
        Parameters
        ----------
        phase: str
            The phase for which to record the start time
        
        Raises
        ------
        ValueError: if the phase is invalid
        """
        WorkflowTiming._validate_phase(phase)
        full_phase = self._full_phase(phase)
        self._starts[full_phase] = timeit.default_timer()

    def end(self, phase):
        """Register the end time of the given phase
        Parameters
        ----------
        phase: str
            The phase for which to record the end time
        
        Raises
        ------
        ValueError: if the start time for this phase wasn't recorded
        """
        self._validate_phase(phase)
        full_phase = self._full_phase(phase)
        if full_phase not in self._starts:
            raise KeyError("No start was recorded for the phase '{}' (root:{})".format(full_phase, self._root))
        start = self._starts.pop(full_phase)
        duration = timeit.default_timer() - start
        if full_phase not in self:
            self[full_phase] = np.array([duration])
        else:
            self[full_phase] = np.concatenate((self[full_phase], [duration]))

    def cm(self, phase):
        """Returns a context manager for computing time for a given phase"""
        return TimingContextManager(self, phase)

    def total(self, phase):
        """Total duration of the given phase
        Parameters
        ----------
        phase: str  
            The phase to compute the duration
        
        Returns
        -------
        duration: float 
            Duration of the phase
        """
        self._validate_phase(phase)
        full_phase = self._full_phase(phase)
        if full_phase not in self:
            raise KeyError("Unknown phase '{}'.".format(full_phase))
        return np.sum(self[full_phase])

    def merge(self, other):
        """Merge two workflow timing objects. The recorded times for same phases are registered together.
        
        Parameters
        ----------
        other: WorkflowTiming
            The workflow timing to merge in the current one
        """
        if not isinstance(other, WorkflowTiming):
            raise TypeError("The `other` parameter should be a workflow timing object, object of type `{}` found.".format(type(other)))
        if other is self:
            return
        for phase, times in other.items():
            curr_times = self.get(phase, None)
            if curr_times is None:
                self[phase] = times
            else:
                self[phase] = np.concatenate((self.get(phase), times))

    def get_phases_hierarchy(self):
        """Return the hierarchy of phases"""
        keys = sorted(self.keys())
        splitted_keys = [k.split(".") for k in keys]
        return self._simplify_hierarchy(self._get_phases_hierarchy(splitted_keys), root=None)

    @classmethod
    def _get_phases_hierarchy(cls, phases):
        # create top level hierarchy
        hierarchy = {phase[0]: None for phase in phases if len(phase) >= 1}
        # extract non-final hierarchies and group according to top level phase
        splitted = [(phase[0], phase[1:]) for phase in phases if len(phase) > 1]
        non_final = dict()
        for top_phase, subphases in splitted:
            non_final[top_phase] = non_final.get(top_phase, []) + [subphases]
        # build final hierarchy
        for top_phase, subphases in non_final.items():
            hierarchy[top_phase] = cls._get_phases_hierarchy(subphases)
        return hierarchy

    def _simplify_hierarchy(self, hierarchy, root=None):
        if hierarchy is None:
            return None
        simplified = dict()
        for key, value in hierarchy.items():
            full_phase = ".".join([root, key]) if root is not None else key
            if full_phase not in self and value is not None and len(value) == 1:
                subkey = list(value.keys())[0]
                simplified[".".join([key, subkey])] = self._simplify_hierarchy(value[subkey], root=full_phase)
            else:
                simplified[key] = self._simplify_hierarchy(value, root=full_phase)
        return simplified

    def get_phase_statistics(self, phase):
        """Return time statistics in seconds for the given phase
        Parameters
        ----------
        phase: str
            The phase identifier
        
        Returns
        -------
        statistics: dict    
            A dictionary mapping statistic name (among 'max', 'min', 'mean', 'std', 'sum' and 'count') with their 
            respective values
        """
        if phase not in self:
            raise KeyError("Unknown phase '{}'.".format(phase))
        times = self[phase]
        return {
            "count": times.shape[0],
            "mean": np.mean(times),
            "std": np.std(times),
            "min": np.min(times),
            "max": np.max(times),
            "sum": np.sum(times)
        } def batch_split(n_batches, items):
    """Partition the items into a given number of batches of similar sizes (if the number of batches is greater than
    the number of items N in the topology, N batches are returned).

    Parameters
    ----------
    n_batches: int
        The number of batches
    items: iterable
        The elements to split into batches

    Returns
    -------
    batches: iterable (subtype: iterable (subtype: Tile), size: min(n_batches, N))
        The batches of tiles
    """
    item_count = len(items)
    if n_batches >= item_count:
        return [[item] for item in items]
    batches = [[] for _ in range(0, n_batches)]
    current_batch = 0
    bigger_batch_count = item_count % n_batches
    smaller_batch_size = (item_count // n_batches)
    bigger_batch_size = (item_count // n_batches) + 1
    for item in items:
        batches[current_batch].append(item)
        if (current_batch < bigger_batch_count and len(batches[current_batch]) >= bigger_batch_size) \
                or (current_batch >= bigger_batch_count and len(batches[current_batch]) >= smaller_batch_size):
            # check whether the current batch is full and should be changed
            current_batch += 1
    return batches def shape_array(sequence):
    array = np.empty(len(sequence), dtype=object)
    array[:] = sequence
    return array
import os
import numpy as np
from abc import abstractmethod
from joblib import delayed, Parallel
from .errors import TileExtractionException
from .image import Image, TileBuilder, DefaultTileBuilder, SkipBordersTileTopology, FixedSizeTileTopology
from .information import WorkflowInformation
from .locator import BinaryLocator, SemanticLocator
from .logging import Loggable, SilentLogger
from .merger import SemanticMerger
from .timing import WorkflowTiming
from .util import batch_split, shape_array
        Iterable containing the polygons found by the locate step
    """
    with timing.cm(SLDCWorkflow.TIMING_DETECT_SEGMENT):
        segmented = segmenter.segment_batch(images)
    with timing.cm(SLDCWorkflow.TIMING_DETECT_LOCATE):
        located = [locator.locate(segmented[i], offset=tiles[i].offset) for i in range(segmented.shape[0])]
    return located


def _batch_segment_locate(tile_ids, tile_topology, segmenter, locator, logger=SilentLogger(), timing_root=None,
                          batch_size=1):
    """Helper function for parallel execution. Error occurring in this method is notified by returning None in place of
    the found polygons list.

    Parameters
    ----------
    tile_ids: iterable (subtype: int, size: N)
        The identifiers of the tiles to be processed
    tile_topology: TileTopology
        The tile topology from which were extracted the identifiers to process
    segmenter: Segmenter
        The segmenter object
    locator: Locator
        The locator object
    batch_size: int
        Batch size for segmentation

    Returns
    -------
    timing: WorkflowTiming
        The timing of execution for processing of the tile.
    tiles_polygons: iterable (subtype: (int, shapely.geometry.Polygon), size: N)
        A list containing the tile identifiers and the polygons found inside them
    """
    timing = WorkflowTiming(root=timing_root)
    tiles_polygons = list()

    for start in range(0, len(tile_ids), batch_size):
        end = min(len(tile_ids), start + batch_size)
        batch_tile_ids = tile_ids[start:end]

        # extract tiles
        images = list()
        kept_tiles = list()
        for tile_id in batch_tile_ids:
            tile = tile_topology.tile(tile_id)
            try:
                with timing.cm(SLDCWorkflow.TIMING_DETECT_LOAD):
                    images.append(tile.np_image)
                kept_tiles.append(tile)
            except TileExtractionException as e:
                logger.w("Workflow: a tile (id:{}) couldn't be fetched computations '{}'".format(tile_id, str(e)))
                tiles_polygons.append((tile_id, []))

        located = _segment_locate(kept_tiles, np.array(images), segmenter, locator, timing)
        tiles_polygons.extend(zip(map(lambda t: t.identifier, kept_tiles), located))

    return timing, tiles_polygons


def _dc_with_timing(dispatcher_classifier, image, polygons, timing_root=None):
    """

    dispatcher_classifier:
    image:
    polygons:

    Returns
    -------
    pred: iterable (subtype: int, size: N)
        The classes predicted for the passed polygons
    proba: iterable (subtype: float, size: N)
        The probability estimates for the predicted classes
    dispatch: iterable (subtype: hashable, size: N)
        The label of the dispatching rules which dispatched the polygons
    timing: WorkflowTiming
        The timing object containing the execution times of the dispatching and classification steps
    """
    return dispatcher_classifier.dispatch_classify_batch(image, polygons, timing_root=timing_root)


def _parallel_segment_locate(pool, segmenter, locator, logger, tile_topology, timing):
    """Execute the segment locate phase
    Parameters
    ----------
    pool: Parallel
        A pool of processes
    segmenter: SemanticSegmenter
        A segmenter
    locator: Locator
        A locator
    logger: Logger
        A logger
    tile_topology: TileTopology
        A tile topology
    timing: WorkflowTiming
        A workflow timing object for computing time

    Returns
    -------
    tiles: iterable (size: n, subtype: int) 
        Iterable containing the tiles ids
    tile_polygons: iterable (size: n, subtype: iterable of Polygon objects))
        The iterable at index i contains the polygons and pixel values found in the tile having index tiles[i]
    """
    # partition the tiles into batches for submitting them to processes
    batches = tile_topology.partition_identifiers(pool.n_jobs)

    # execute
    results = pool(delayed(_batch_segment_locate)(
        tile_ids,
        tile_topology,
        segmenter,
        locator,
        logger,
        ".".join([SLDCWorkflow.TIMING_ROOT, SLDCWorkflow.TIMING_DETECT])
    ) for tile_ids in batches)

    sub_timings, tiles_polygons = list(zip(*results))
    tiles = np.array([tid for result in tiles_polygons for tid, _ in result])

    tile_polygons = shape_array([polygons for result in tiles_polygons for _, polygons in result])