Buckets:
| import bisect | |
| import builtins | |
| import itertools | |
| import math | |
| import re | |
| from typing import Iterable, Optional, Union | |
| from ndindex import ndindex | |
| from .type_aliases import JSON, Chunks, EllipsisType | |
| def is_ellipsis(arg) -> bool: | |
| return isinstance(arg, EllipsisType) or (arg == Ellipsis) | |
| def merge_slices(*args: Union["NDSlice", "NDBlock"]) -> Union["NDSlice", "NDBlock"]: | |
| """Merge multiple NDSlices or NDBlocks | |
| Creates a single NDSlice or (NDBlock if all arguemnts are NDBlocks) if they are | |
| contiguous and compatible. | |
| """ | |
| if (len(args)) == 1: | |
| return args[0] | |
| # Check that all arguments have the same dimension | |
| if len(set(map(len, args))) != 1: | |
| raise ValueError("All NDSlices must have the same number of dimensions") | |
| # Loop over dimensions and check if they can be merged | |
| already_merged, result = False, [] | |
| for dim in zip(*args): | |
| # Ellipsis at the same position can be merged | |
| if all(map(is_ellipsis, dim)): | |
| result.append(Ellipsis) | |
| continue | |
| # Integers must match exactly or be consecutive and have no gaps | |
| if all(isinstance(d, int) for d in dim): | |
| if len(vals := set(dim)) == 1: | |
| # All integers are the same, keep this dimension as is | |
| result.append(vals.pop()) | |
| continue | |
| elif vals == set(range(min(vals), max(vals) + 1)): | |
| # Integers are consecutive, merge into a slice | |
| if already_merged: | |
| raise ValueError("Can not merge more than one dimension") | |
| result.append(builtins.slice(min(vals), max(vals) + 1)) | |
| already_merged = True | |
| continue | |
| else: | |
| raise ValueError( | |
| "Integer dimensions must match exactly " | |
| "or be consecutive and have no gaps" | |
| ) | |
| # Some dimensions could be integers and some are slices | |
| if any(isinstance(d, int) for d in dim): | |
| dim = tuple( | |
| builtins.slice(d, d + 1) if isinstance(d, int) else d for d in dim | |
| ) | |
| # Now we have only slices and can check for contiguity and compatibility | |
| if all(isinstance(d, builtins.slice) for d in dim): | |
| starts = set(d.start or 0 for d in dim) | |
| stops = set(d.stop for d in dim) | |
| if len(set(d.step or 1 for d in dim)) != 1: | |
| raise ValueError("Slice dimensions must have the same step") | |
| elif len(starts) == 1 and len(stops) == 1: | |
| # All slices are the same, keep this dimension as is | |
| result.append(dim[0]) | |
| continue | |
| elif ( | |
| (len(starts) == len(stops)) | |
| and (len(first := starts - stops) == 1) | |
| and (len(last := stops - starts) == 1) | |
| ): | |
| # Slices are consecutive, merge into a single slice | |
| if already_merged: | |
| raise ValueError("Can not merge more than one dimension") | |
| result.append(builtins.slice(first.pop(), last.pop(), dim[0].step)) | |
| already_merged = True | |
| continue | |
| elif starts == stops: | |
| # This is an empty dimension, keep it as is | |
| val = starts.pop() | |
| result.append(builtins.slice(val, val, dim[0].step)) | |
| continue | |
| # If we got here, the slices are not compatible and can not be merged | |
| raise ValueError("The slices are not compatible and can not be merged") | |
| _cls = NDBlock if all(isinstance(arg, NDBlock) for arg in args) else NDSlice | |
| return _cls(*result) | |
| def _num_steps(slc: builtins.slice) -> int: | |
| """Number of elements an expanded 1-D slice selects. | |
| Tolerates reversed slices that reach the start of the axis, whose expanded | |
| `stop` is negative (e.g. `slice(9, -11, -1)`) or `None`. For those the | |
| exclusive lower bound is `-1` in Python `range` terms, regardless of the | |
| particular negative value produced by `expand_for_shape`. | |
| """ | |
| start = slc.start or 0 | |
| step = slc.step or 1 | |
| stop = slc.stop | |
| if step < 0 and (stop is None or stop < 0): | |
| stop = -1 | |
| return len(range(start, stop, step)) | |
| def split_1d(start, stop, step, max_len: int, pref_splits: Optional[list[int]] = None): | |
| """Split a 1D slice into sub-slices that do not exceed max_len steps. | |
| Splits are chosen close to the ideal equal partition. If preferred | |
| split points are provided, the closest one to the ideal point is used | |
| as long as it does not violate the min/max constraints. | |
| """ | |
| # A reversed slice reaching the start of the axis is expanded (by ndindex) to | |
| # a negative canonical stop (e.g. slice(9, -11, -1)). Such a slice has no | |
| # non-negative integer stop, so partition it as if the exclusive bound were | |
| # -1 and emit stop=None for the final sub-slice that reaches index 0. | |
| reaches_start = step < 0 and stop is not None and stop < 0 | |
| eff_stop = -1 if reaches_start else stop | |
| # Total number of steps and max steps per split | |
| total_steps = math.ceil(abs(eff_stop - start) / abs(step)) | |
| # Convert preferred points to index space | |
| pref_indx = sorted( | |
| (x - start) // step | |
| for x in (pref_splits or []) | |
| if x in range(start, eff_stop, step) | |
| ) | |
| result, crnt_indx, _pi = [], 0, 0 | |
| while crnt_indx + max_len < total_steps: | |
| # Compute ideal next index for equal partitioning of the remaining steps | |
| steps_remained = total_steps - crnt_indx | |
| num_splits = max(1, math.ceil(steps_remained / max_len)) | |
| ideal_split_size = math.ceil(steps_remained / num_splits) | |
| next_indx = crnt_indx + ideal_split_size | |
| # Check if there are preferred points between the current index and the max allowed | |
| if pref_indx: | |
| pref_best = None | |
| while _pi < len(pref_indx) and pref_indx[_pi] <= crnt_indx + max_len: | |
| if pref_indx[_pi] > crnt_indx: | |
| pref_best = pref_best or pref_indx[_pi] | |
| if abs(pref_indx[_pi] - next_indx) < abs(pref_best - next_indx): | |
| pref_best = pref_indx[_pi] | |
| _pi += 1 | |
| next_indx = pref_best or next_indx | |
| result.append((start + crnt_indx * step, start + next_indx * step)) | |
| crnt_indx = next_indx | |
| result.append((start + crnt_indx * step, None if reaches_start else stop)) | |
| return result | |
| def split_slice( | |
| arr_slice: "NDSlice", max_size: int, pref_splits: Optional[list[list[int]]] = None | |
| ) -> dict[tuple[int, ...], "NDSlice"]: | |
| """Split an N-dimensional slice into smaller slices that do not exceed max_size | |
| Splits are chosen by iteratively subslicing along the most chunked or longest | |
| dimension until the resulting slices are all under the max_size limit. | |
| Parameters | |
| ---------- | |
| arr_slice : NDSlice | |
| The N-dimensional slice to split. The slice must be expanded to account for | |
| the specific shape (i.e. not contain any ":" or "..."). Integer dimensions | |
| are allowed. | |
| max_size : int | |
| The maximum allowed size (number of elements) for each resulting slice. | |
| pref_splits : list of list of int, optional | |
| Preferred split points for each dimension. | |
| Returns | |
| ------- | |
| dict[tuple[int, ...], NDSlice] | |
| A dictionary mapping from index tuples to the corresponding NDSlice objects. | |
| """ | |
| # Remove singleton dimensions and replace with slices for simplicity. Revert later | |
| is_int_dim = [isinstance(s, int) for s in arr_slice] | |
| arr_slice = arr_slice.unsqueeze() | |
| ndim = len(arr_slice) | |
| # Make sure preferred split points align with the step grid and within the bounds | |
| if pref_splits is not None: | |
| pref_splits = [ | |
| [ | |
| x | |
| for x in bnd | |
| if x in range(slc.start, slc.stop, slc.step or 1) and x != slc.start | |
| ] | |
| for bnd, slc in zip(pref_splits, arr_slice) | |
| ] | |
| # Start with the most chunked or longest dimension and subslice it | |
| sorting_order = ( | |
| [len(ps) for ps in pref_splits] | |
| if pref_splits is not None | |
| else [_num_steps(s) for s in arr_slice] | |
| ) | |
| result = [[s] for s in arr_slice] | |
| for d in sorted(range(ndim), key=lambda i: sorting_order[i], reverse=True): | |
| # Find the size of largest block along all other dimensions, excluding d | |
| max_other = math.prod( | |
| [max(_num_steps(s) for s in result[_d]) for _d in range(ndim) if _d != d] | |
| ) | |
| slc = result[d].pop() | |
| # Use maximum length along this dimension that keeps the slice under the limit | |
| splits = split_1d( | |
| slc.start, | |
| slc.stop, | |
| slc.step or 1, | |
| max_len=max(1, int(max_size / max_other)), | |
| pref_splits=pref_splits[d] if pref_splits is not None else None, | |
| ) | |
| result[d].extend([builtins.slice(a, b, slc.step) for a, b in splits]) | |
| # Check if we need further subslicing along other dimensions | |
| max_crnt = max(_num_steps(s) for s in result[d]) | |
| if max_crnt * max_other <= max_size: | |
| break | |
| # Replace (squeeze) any singleton slices if they were integers originally | |
| result = [[res[0].start] if flag else res for res, flag in zip(result, is_int_dim)] | |
| # Form the dict of Cartesian products | |
| keys = itertools.product( | |
| *(range(len(x)) for x in result if not isinstance(x[0], int)) | |
| ) | |
| vals = itertools.product(*result) | |
| return {k: NDSlice(v) for k, v in zip(keys, vals)} | |
| def _slc_with_int(slc: builtins.slice, idx: int) -> int: | |
| "Compose a (1D) slice with an integer index" | |
| if slc.start is None or slc.stop is None: | |
| raise ValueError("Composition with relative indexing is not supported.") | |
| start, stop, step = slc.start, slc.stop, slc.step or 1 | |
| # Estimate maximum length of the resulting shape after slice | |
| if step > 0: | |
| length = max(0, (stop - start + step - 1) // step) | |
| else: | |
| length = max(0, (start - stop - step - 1) // (-step)) | |
| # Normalize negative index | |
| if idx < 0: | |
| idx += length | |
| if idx < 0 or idx >= length: | |
| raise ValueError("Composition with out-of-bounds index") | |
| return start + step * idx | |
| def _slc_with_slc(slc1: builtins.slice, slc2: builtins.slice) -> builtins.slice: | |
| "Compose a (1D) slice with another slice" | |
| # Normalize first slice | |
| if slc1.start is None or slc1.stop is None: | |
| raise ValueError("Composition with relative indexing is not supported.") | |
| start1, stop1, step1 = slc1.start, slc1.stop, slc1.step or 1 | |
| # Estimate maximum length of the resulting shape after first slice | |
| if step1 > 0: | |
| length = max(0, (stop1 - start1 + step1 - 1) // step1) | |
| else: | |
| length = max(0, (start1 - stop1 - step1 - 1) // (-step1)) | |
| # Normalize second slice relative to the length of the first slice | |
| start2, stop2, step2 = slc2.indices(length) | |
| # Compose the two normalized slices | |
| new_start = start1 + step1 * start2 | |
| new_step = step1 * step2 | |
| new_stop = start1 + step1 * stop2 | |
| return builtins.slice(new_start, new_stop, new_step) | |
| def _is_scalar_slice( | |
| slc: Union[int, builtins.slice], length: Optional[int] = None | |
| ) -> bool: | |
| "Best effort to check if a slice selects a single element (scalar) along one dimension" | |
| if length is not None and isinstance(slc, builtins.slice): | |
| start, stop, step = slc.indices(length) | |
| return len(range(start, stop, step)) == 1 | |
| return isinstance(slc, int) or ( | |
| isinstance(slc, slice) | |
| and slc.start is not None | |
| and slc.stop is not None | |
| and slc.stop == slc.start + 1 | |
| ) | |
| def compose_slices(slc1: "NDSlice", slc2: "NDSlice") -> "NDSlice": | |
| """Compose two NDSlices | |
| Creates a single NDSlice that is the composition of the input slices, i.e. equivalent | |
| to applying them sequentially. For example, if arr is an array, then | |
| arr[slc1][slc2] is equivalent to arr[compose_slices(slc1, slc2)]. | |
| Note that Ellipsis in any of the slices may break the composition rule for | |
| arrays of certain shapes, so it is recommended to expand the slices for the specific | |
| shape before composing them. | |
| """ | |
| if (not slc1) or (not slc2): | |
| # If either slice is empty, the result is the other slice (which may also be empty) | |
| return slc1 or slc2 | |
| if not slc1.is_expanded(): | |
| # The left slice contains Ellipsis or the resulting shape is ambiguous | |
| raise ValueError( | |
| "Composition of slices with undetermined shape is not supported." | |
| ) | |
| res_rgt, i1l = [], len(slc1) | |
| res_lft, i2r = [], 0 | |
| if any(is_ellipsis(s) for s in slc2) and not is_ellipsis(slc2[-1]): | |
| # The right slice contains Ellipsis in other than the last position | |
| dim1 = sum(1 for s in slc1 if not isinstance(s, int)) | |
| if dim1 < len(slc2) - 1: | |
| raise ValueError( | |
| "Composition with Ellipsis in the right slice is only supported if it is " | |
| "the last element, or the left slice has enough dimensions to cover all " | |
| "non-Ellipsis elements of the right slice." | |
| ) | |
| # Start assembling the result from the right | |
| for s2 in reversed(slc2): | |
| if is_ellipsis(s2): | |
| break | |
| # Chose the next right-most (non-integer) item from the left slice | |
| i1l -= 1 | |
| s1 = slc1[i1l] | |
| while isinstance(s1, int) and i1l > 0: | |
| # Repeat: add the item, move the left counter until we find a non-integer item | |
| res_rgt.append(s1) | |
| i1l -= 1 | |
| s1 = slc1[i1l] | |
| # Now compose s1 and s2 and add to the result from the right | |
| if isinstance(s2, int): | |
| res_rgt.append(_slc_with_int(s1, s2)) | |
| elif isinstance(s2, builtins.slice): | |
| res_rgt.append(_slc_with_slc(s1, s2)) | |
| # All the right slice until Ellipsis is processed; and the remaining items from the left | |
| for s1 in slc1[:i1l]: | |
| # Left item is an integer, add it to the result and move on | |
| if isinstance(s1, int) or i2r >= len(slc2): | |
| res_lft.append(s1) | |
| continue | |
| # Left item is a slice, compose it with the next right item if there are any remaining | |
| s2 = slc2[i2r] | |
| if isinstance(s2, int): | |
| res_lft.append(_slc_with_int(s1, s2)) | |
| elif isinstance(s2, builtins.slice): | |
| res_lft.append(_slc_with_slc(s1, s2)) | |
| elif is_ellipsis(s2) or (len(slc2) == i2r + 1): | |
| res_lft.append(s1) | |
| continue | |
| i2r += 1 | |
| _cls = ( | |
| NDBlock if isinstance(slc1, NDBlock) and isinstance(slc2, NDBlock) else NDSlice | |
| ) | |
| return _cls(*res_lft, *reversed(res_rgt)) | |
| class NDSlice(tuple): | |
| """A representation of a slice for N-dimensional arrays. | |
| This class is a tuple of integers, slices, and Ellipsis objects. It is used to | |
| represent a slice of an N-dimensional array, similar to how numpy uses slices. | |
| It also provides methods to convert to and from JSON and numpy-style string | |
| representations of slices. To encode Ellipsis in JSON, it is represented as | |
| {"step": 0}, which is not a valid builtin.slice. | |
| """ | |
| def __new__( | |
| cls, *args: Union[int, builtins.slice, EllipsisType, Iterable, None] | |
| ) -> "NDSlice": | |
| if len(args) == 1 and (isinstance(args[0], (tuple, list)) or args[0] is None): | |
| return cls(*(args[0] or ())) | |
| if any(not isinstance(s, (int, builtins.slice, EllipsisType)) for s in args): | |
| raise TypeError( | |
| f"NDSlice expected int, slice or Ellipsis; got {args} instead. Use " | |
| "NDSlice.from_numpy_str() or NDSlice.from_json() to parse strings or JSON." | |
| ) | |
| if len([None for x in args if x == Ellipsis]) > 1: | |
| raise ValueError( | |
| f"NDSlice can only contain one Ellipsis; got {args} instead." | |
| ) | |
| return super().__new__(cls, tuple(args)) | |
| def __bool__(self) -> bool: | |
| "NDSlice is considered empty if all slices are '...' or ':', returning entire array" | |
| full_slices = ( | |
| builtins.slice(None), | |
| builtins.slice(0, None), | |
| builtins.slice(0, None, 1), | |
| builtins.slice(None, None, 1), | |
| Ellipsis, | |
| ) | |
| return bool(super()) and not all( | |
| is_ellipsis(s) or s in full_slices for s in self | |
| ) | |
| def __getitem__(self, key): | |
| "An element of this NDSlice or the composition with another NDSlice" | |
| if is_ellipsis(key): | |
| return self | |
| if isinstance(key, NDSlice): | |
| # Composition of slices: arr[slc1][slc2] is equivalent to arr[slc1[slc2]] | |
| return compose_slices(self, key) | |
| # Just return the element if it's not a slice composition | |
| return super().__getitem__(key) | |
| def from_json(cls, ser: list[JSON]) -> "NDSlice": | |
| "Deserialize a json representation of an NDSlice" | |
| result = [] | |
| for s in ser: | |
| if isinstance(s, dict): | |
| result.append( | |
| builtins.slice(s.get("start"), s.get("stop"), s.get("step")) | |
| ) | |
| elif isinstance(s, int): | |
| result.append(s) | |
| else: | |
| raise ValueError("Can not initialize NDSlice from %s", s) | |
| return cls(*result) | |
| def to_json(self, ndim: Optional[int] = None) -> list[JSON]: | |
| "Convert NDSlice into a JSON-serializable representation" | |
| if not ndim and (Ellipsis in self) and self[-1] != Ellipsis: | |
| raise ValueError( | |
| "Converting to JSON an NDSlice with Ellipsis in other than the last element " | |
| "requires the number of dimensions `ndim` to be specified." | |
| ) | |
| elif ndim is not None and ndim < len([x for x in self if x != Ellipsis]): | |
| raise ValueError( | |
| "Specified number of dimensions `ndim` is less than the number of elements." | |
| ) | |
| ndim = ndim or len(self) | |
| def convert_dimension(slc: Union[int, builtins.slice]) -> JSON: | |
| if isinstance(slc, builtins.slice): | |
| return ( | |
| ({} if slc.start is None else {"start": slc.start}) | |
| | ({} if slc.stop is None else {"stop": slc.stop}) | |
| | ({} if slc.step is None else {"step": slc.step}) | |
| ) | |
| elif isinstance(slc, int): | |
| return slc | |
| fwd, bwd = [], [] | |
| for s in self: | |
| if s == Ellipsis: | |
| break | |
| fwd.append(convert_dimension(s)) | |
| for s in reversed(self[len(fwd) + 1 :]): # noqa: E203 | |
| bwd.append(convert_dimension(s)) | |
| return fwd + [{} for _ in range(ndim - len(fwd) - len(bwd))] + [*reversed(bwd)] | |
| def is_expanded(self) -> bool: | |
| """Check the _necessary_ conditions to determine the resulting shape from the slice alone | |
| If True, the resulting shape can be determined without knowing the shape of the array | |
| this slice is applied to, i.e. it does not contain any ':', '...', or relative indexing. | |
| NOTE: This is a necessary but not sufficient condition; e.g. `slice(0, 5)` applied to an | |
| array of shape (3,) will still result in a shape of (3,), not (5,). | |
| """ | |
| def _is_absolute(s: builtins.slice) -> bool: | |
| return (s.start or 0) >= 0 and (s.stop is not None and s.stop >= 0) | |
| return all( | |
| (not is_ellipsis(s)) | |
| and (_is_absolute(s) if isinstance(s, builtins.slice) else True) | |
| for s in self | |
| ) | |
| def from_numpy_str(cls, arg: str) -> "NDSlice": | |
| """Parse and convert a numpy-style string representation of a slice | |
| For example, '(1:3, 4, 1:5:2, ...)' is converted to (slice(1, 3), 4, slice(1, 5, 2), ...). | |
| """ | |
| arg = arg.strip("(][)").replace(" ", "") | |
| if not arg: | |
| return cls() | |
| result = [] | |
| for part in arg.split(","): | |
| if part.strip() == "...": | |
| result.append(Ellipsis) | |
| elif part.strip() in {":", "::"}: | |
| result.append(builtins.slice(None)) | |
| elif m := re.match(r"^(-?\d+)::?$", part.strip()): | |
| # "start:" or "start::" | |
| start, stop = int(m.group(1)), None | |
| result.append(builtins.slice(start, stop)) | |
| elif m := re.match(r"^:(-?\d+):?$", part.strip()): | |
| # ":stop" or ":stop:" | |
| start, stop = None, int(m.group(1)) | |
| result.append(builtins.slice(start, stop)) | |
| elif m := re.match(r"^(-?\d+):(-?\d+):(-?\d+)$", part.strip()): | |
| # "start:stop:step" | |
| start, stop, step = map(int, m.groups()) | |
| result.append(builtins.slice(start, stop, step)) | |
| elif m := re.match(r"^(-?\d+):(-?\d+):*$", part.strip()): | |
| # "start:stop" or "start:stop:" | |
| start, stop = map(int, m.groups()) | |
| result.append(builtins.slice(start, stop)) | |
| elif m := re.match(r"^:(-?\d+):(-?\d+)$", part.strip()): | |
| # ":stop:step" | |
| stop, step = map(int, m.groups()) | |
| result.append(builtins.slice(None, stop, step)) | |
| elif m := re.match(r"^::(-?\d+)$", part.strip()): | |
| # "::step" | |
| step = int(m.group(1)) | |
| result.append(builtins.slice(None, None, step)) | |
| elif m := re.match(r"^(-?\d+)::(-?\d+)$", part.strip()): | |
| # "start::step" | |
| start, step = map(int, m.groups()) | |
| result.append(builtins.slice(start, None, step)) | |
| elif m := re.match(r"^(-?\d+)$", part.strip()): | |
| result.append(int(m.group())) | |
| else: | |
| raise ValueError(f'Invalid slice part: "{part}"') | |
| return cls(*result) | |
| def to_numpy_str(self) -> str: | |
| "Convert NDSlice to a numpy-style string representation" | |
| result = [] | |
| for s in self: | |
| if isinstance(s, builtins.slice): | |
| string_slice = ( | |
| f"{('' if s.start is None else s.start)}:" | |
| + ("" if s.stop is None else f"{s.stop}") | |
| + (f":{str(s.step)}" if s.step else "") | |
| ) | |
| result.append(string_slice) | |
| elif isinstance(s, int): | |
| result.append(str(s)) | |
| elif s is Ellipsis: | |
| result.append("...") | |
| else: | |
| raise ValueError("Unprocessable entry in NDSlice, %s", s) | |
| return ",".join(result) | |
| def is_valid_for_shape(self, shape: tuple[int, ...]) -> bool: | |
| "Check if this NDSlice is valid for an array of the given shape" | |
| return (not self) or ndindex(self).isvalid(shape) | |
| def expand_for_shape(self, shape: tuple[int, ...]) -> "NDSlice": | |
| "Expand this NDSlice (remove ':' or '...') for an array of the given shape" | |
| return self.__class__(*ndindex(self).expand(shape).raw) | |
| def shape_after_slice(self, shape: tuple[int, ...]) -> tuple[int, ...]: | |
| "Calculate the shape after applying NDSlice to an array of the given shape" | |
| return ndindex(self).newshape(shape) if self else shape | |
| def flat_indices(self, shape: tuple[int, ...]) -> tuple[int, ...]: | |
| """Return the flat (C-order) positions selected by this slice. | |
| Conceptually `numpy.arange(prod(shape)).reshape(shape)[self]` flattened | |
| to 1-D: it labels each cell of an array of `shape` with its C-order | |
| position and reports the positions this slice keeps. Integer entries drop | |
| a dimension; slices (including strided and negative) and Ellipsis are | |
| honored exactly as in NumPy indexing. | |
| This is the inverse-mapping companion to :meth:`shape_after_slice` (which | |
| gives the *shape* of a selection); here we get the flat *identities* of | |
| the selected cells. It is useful for mapping an N-dimensional selection | |
| back onto a flat, C-ordered collection -- e.g. finding which files of a | |
| stacked file-sequence a given slice touches, where each file occupies one | |
| cell of the stacking grid. | |
| Returns a `tuple` of Python ints (empty if the slice selects nothing). | |
| The selection order matches NumPy's, so the result also serves as the | |
| read order for the underlying elements. | |
| """ | |
| import numpy | |
| grid = numpy.arange(math.prod(shape)).reshape(shape) | |
| return tuple(grid[self.expand_for_shape(shape)].ravel().tolist()) | |
| def unsqueeze(self) -> "NDSlice": | |
| "Convert all integer dims to slices of length 1 to preserve the dimensionality" | |
| return self.__class__( | |
| *(builtins.slice(s, s + 1, 1) if isinstance(s, int) else s for s in self) | |
| ) | |
| def is_scalar(self, shape: tuple[int, ...]) -> bool: | |
| "Check if this NDSlice selects a single element (scalar) from an array of the given shape" | |
| return (len(self) == len(shape)) and all( | |
| _is_scalar_slice(s, length=l) for s, l in zip(self, shape) | |
| ) | |
| class NDBlock(NDSlice): | |
| """A slice used to specify a block index, i.e. a slice over the chunks of an array. | |
| A major requirement is for the sliced blocks/chunks to be contiguous, | |
| i.e. the `step` parameter along each dimension, if specified, must be 1. | |
| """ | |
| def __new__(cls, *args: Union[int, builtins.slice, EllipsisType]) -> "NDBlock": | |
| inst = super().__new__(cls, *args) | |
| for s in inst: | |
| if isinstance(s, builtins.slice) and s.step not in (None, 1): | |
| raise ValueError( | |
| f"NDBlock can only contain slices with step 1; got {s} instead." | |
| ) | |
| return inst | |
| def shape_from_chunks(self, chunks: Chunks) -> tuple[int, ...]: | |
| "Find the shape of the block of chunks for an array with the given chunks" | |
| expanded = self.expand_for_shape(tuple(map(len, chunks))) | |
| selected = tuple(ch[sl] for ch, sl in zip(chunks, expanded)) | |
| return tuple(sum(ch) if isinstance(ch, tuple) else ch for ch in selected) | |
| def slice_from_chunks(self, chunks: Chunks) -> NDSlice: | |
| "Find the slice over entire array with given chunks that selects this block" | |
| expanded = self.expand_for_shape(tuple(map(len, chunks))) | |
| slice_ = [] | |
| for sl, ch in zip(expanded, chunks): | |
| if isinstance(sl, int): | |
| start = sum(ch[:sl]) | |
| slice_.append(slice(start, start + ch[sl])) | |
| elif isinstance(sl, builtins.slice): | |
| start = sum(ch[: sl.start]) if sl.start is not None else None | |
| stop = sum(ch[: sl.stop]) if sl.stop is not None else None | |
| slice_.append(slice(start, stop)) | |
| return NDSlice(*slice_) | |
| def chunk_indices(self, chunks: Chunks) -> list[tuple[int, ...]]: | |
| """Return a list of all n-dimensional chunk indices in this block. | |
| Expands any slice dimensions into individual indices while keeping | |
| integer dimensions as-is. The result is a list of tuples where each | |
| tuple represents the chunk index for one block. | |
| Parameters | |
| ---------- | |
| chunks : Chunks | |
| The chunking scheme to determine the valid range of chunk indices. | |
| Returns | |
| ------- | |
| list[tuple[int, ...]] | |
| List of n-dimensional chunk index tuples. | |
| """ | |
| # Expand to get actual indices for each dimension | |
| expanded = self.expand_for_shape(tuple(len(ch) for ch in chunks)) | |
| # Convert each dimension to a list of indices | |
| dim_indices = [] | |
| for item in expanded: | |
| if isinstance(item, int): | |
| dim_indices.append([item]) | |
| elif isinstance(item, builtins.slice): | |
| # Extract start, stop from the slice (step is guaranteed to be 1 or None) | |
| start = item.start if item.start is not None else 0 | |
| stop = item.stop | |
| dim_indices.append(list(range(start, stop))) | |
| # Generate all combinations (Cartesian product) | |
| return sorted(itertools.product(*dim_indices)) | |
| def block_for_slice( | |
| chunks: Chunks, slice: Optional[Union[tuple, "NDSlice"]] = None | |
| ) -> tuple["NDBlock", "NDSlice"]: | |
| """Convert a slice on a chunked array into block indices and a slice within the block | |
| Given an array's chunking scheme and a slice to apply, this function determines: | |
| 1. Which blocks (chunks) are touched by the slice (returned as NDBlock) | |
| 2. What slice to apply within the concatenated blocks to get the final result | |
| This is useful for reading data using block-based access (e.g., read_block()) instead | |
| of full array slicing, which can be more efficient for large datasets by avoiding | |
| expensive path resolution operations. | |
| Parameters | |
| ---------- | |
| chunks : Chunks | |
| The chunking scheme as a tuple of tuples, where chunks[i] gives the sizes | |
| of chunks along dimension i. | |
| slice : tuple or NDSlice, optional | |
| The slice to apply to the full array. | |
| Returns | |
| ------- | |
| block : NDBlock | |
| The contiguous block indices touched by the slice. | |
| slice_within_blocks : NDSlice | |
| The slice to apply to the array formed by concatenating the selected blocks | |
| to produce the final result. | |
| """ | |
| # If empty slice, return all blocks and identity slice | |
| slice = NDSlice(slice or ()) | |
| if not slice: | |
| return ( | |
| NDBlock(*[builtins.slice(0, len(dim_chunks)) for dim_chunks in chunks]), | |
| NDSlice(), | |
| ) | |
| # Expand the slice for the specific shape (handles Ellipsis, etc.) | |
| shape = tuple(sum(dim_chunks) for dim_chunks in chunks) | |
| slice = slice.expand_for_shape(shape) | |
| # For each dimension, determine which chunks are touched and how to slice concatenated blocks | |
| block_slices, adjusted_slices = [], [] | |
| for dim_idx, (slc, dim_chunks) in enumerate(zip(slice, chunks)): | |
| # Compute chunk boundaries: [0, chunks[0], chunks[0]+chunks[1], ...] | |
| chunk_bounds = [0, *itertools.accumulate(dim_chunks)] | |
| if isinstance(slc, int): | |
| # Single index - find which chunk it falls in using binary search | |
| chunk_idx = bisect.bisect_right(chunk_bounds, slc) - 1 | |
| if chunk_idx < 0 or chunk_idx >= len(dim_chunks): | |
| raise IndexError( | |
| f"Index {slc} out of bounds for dimension {dim_idx} with shape {shape[dim_idx]}" | |
| ) | |
| block_slices.append(chunk_idx) | |
| adjusted_slices.append(slc - chunk_bounds[chunk_idx]) | |
| elif isinstance(slc, builtins.slice): | |
| # Normalize slice indices for this dimension | |
| start, stop, step = slc.indices(shape[dim_idx]) | |
| if step == 0: | |
| raise ValueError("slice step cannot be zero") | |
| # Find first and last chunks touched by this slice | |
| if step > 0: | |
| if start >= stop: | |
| block_slices.append(builtins.slice(0, 0)) | |
| adjusted_slices.append(builtins.slice(0, 0)) | |
| continue # Empty slice | |
| first_chunk = bisect.bisect_right(chunk_bounds, start) - 1 | |
| last_chunk = bisect.bisect_right(chunk_bounds, stop - 1) - 1 | |
| else: # step < 0 | |
| if start <= stop: | |
| block_slices.append(builtins.slice(0, 0)) | |
| adjusted_slices.append(builtins.slice(0, 0)) | |
| continue # Empty slice | |
| # Negative steps traverse from start down to stop (exclusive) | |
| # so elements go from start to stop+1 | |
| first_chunk = bisect.bisect_right(chunk_bounds, start) - 1 | |
| last_chunk = bisect.bisect_right(chunk_bounds, stop + 1) - 1 | |
| # Ensure first_chunk <= last_chunk for contiguous block range | |
| first_chunk, last_chunk = min(first_chunk, last_chunk), max( | |
| first_chunk, last_chunk | |
| ) | |
| # Block is the contiguous range of chunks | |
| if first_chunk == last_chunk: | |
| block_slices.append(first_chunk) | |
| else: | |
| block_slices.append(builtins.slice(first_chunk, last_chunk + 1)) | |
| # Compute adjusted slice within concatenated blocks | |
| first_chunk_start = chunk_bounds[first_chunk] | |
| adjusted_start = start - first_chunk_start | |
| adjusted_stop = stop - first_chunk_start | |
| # Special case: for negative steps, if stop would go before the start of | |
| # the first chunk, set it to None to indicate "go to the beginning" | |
| if step < 0 and stop < first_chunk_start: | |
| adjusted_stop = None | |
| # Normalize step=1 to step=None for consistency | |
| normalized_step = None if step == 1 else step | |
| adjusted_slices.append( | |
| builtins.slice(adjusted_start, adjusted_stop, normalized_step) | |
| ) | |
| return NDBlock(*block_slices), NDSlice(*adjusted_slices) | |
| def build_nested_grid(indices, callable=None, dim=0): | |
| """Build a nested list structure from flat N-dimensional indices. | |
| This function organizes a flat list of N-dimensional indices into a nested | |
| list structure suitable for np.block(). The nesting depth matches the | |
| dimensionality of the indices, with each level corresponding to one dimension. | |
| This is particularly useful when you have a collection of array chunks indexed | |
| by multi-dimensional coordinates and want to concatenate them efficiently using | |
| np.block(). | |
| Parameters | |
| ---------- | |
| indices : list[tuple[int, ...]] | |
| A list of N-dimensional index tuples. The indices should be sorted in | |
| lexicographic order (though groupby will work with any order that groups | |
| consecutive identical prefixes together). | |
| callable : callable, optional | |
| Optional function to apply to each index tuple at the leaf level. | |
| If None, the index tuple itself is returned. This is useful for | |
| retrieving actual data arrays corresponding to each index. | |
| For example: lambda idx: array_dict[idx] | |
| dim : int, optional | |
| Internal parameter used during recursion to track current dimension. | |
| Should not be set by users (defaults to 0). | |
| Returns | |
| ------- | |
| nested_list : list or object | |
| A nested list structure where the nesting depth equals len(indices[0]). | |
| At the leaf level, either the index tuples themselves or the result of | |
| callable(index) is stored. | |
| """ | |
| if dim == len(indices[0]): | |
| return callable(indices[0]) if callable else indices[0] | |
| groups = [ | |
| build_nested_grid(list(g), callable, dim + 1) | |
| for _, g in itertools.groupby(indices, key=lambda p: p[dim]) | |
| ] | |
| return groups | |
Xet Storage Details
- Size:
- 35.3 kB
- Xet hash:
- 6dff852ec09e0485389f753a085387d822b9db26fab192b111a33c997e35abd6
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.