Skip to content

DPArray#

This file provides the DPArray class.

DPArray #

DPArray class.

Parameters:

Name Type Description Default
shape array - like

The dimensions of the array.

 required
array_name str

Name of the array, this is used by dp.Logger when the DP algorithm interacts with multiple arrays. The array name is displayed as the figure title when the array is visualized.

 'dp_array'
logger Logger

Logger object that tracks the actions performed on this array, including READ, WRITE, and HIGHLIGHT. This object is used to reproduce frame-by-frame animation of the DP algorithm.

 None
dtype str or data - type

Data type of the DPArray. We only support "f" / np.float32 and "d" / np.float64.

 float64

Attributes:

Name Type Description
_arr array

Contains the values of the DP array.
_occupied_arr array

A mask that indicates which index is filled.
Source code in dp/_dp_array.py 
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
class DPArray:
    """DPArray class.

    Args:
        shape (array-like): The dimensions of the array.
        array_name (str): Name of the array, this is used by ``dp.Logger`` when
            the DP algorithm interacts with multiple arrays. The array name is
            displayed as the figure title when the array is visualized.
        logger (dp.Logger): Logger object that tracks the actions performed on
            this array, including READ, WRITE, and HIGHLIGHT. This object is
            used to reproduce frame-by-frame animation of the DP algorithm.
        dtype (str or data-type): Data type of the DPArray. We only support
            ``"f"`` / ``np.float32`` and ``"d"`` / ``np.float64``.

    Attributes:
        _arr (np.array): Contains the values of the DP array.
        _occupied_arr (np.array): A mask that indicates which index is filled.
    """

    def __init__(
        self,
        shape,
        array_name="dp_array",
        *,
        logger=None,
        dtype=np.float64,
    ):
        """Initializes the DPArray."""
        self._dtype = self._parse_dtype(dtype)

        self._arr = np.full(shape, dtype=self._dtype, fill_value=np.nan)
        self._occupied_arr = np.zeros_like(self._arr, dtype=bool)

        self._logger = Logger() if logger is None else logger
        self._logger.add_array(array_name, shape)

        self._array_name = array_name

    @staticmethod
    def _parse_dtype(dtype):
        """Parses the dtype passed into the constructor.

        Returns:
            np.float32 and np.float64
        Raises:
            ValueError: Unsupported dtype.
        """
        # First convert str dtype's to np.dtype.
        if isinstance(dtype, str):
            dtype = np.dtype(dtype)

        # np.dtype is not np.float32 or np.float64, but it compares equal.
        if dtype == np.float32:
            return np.float32
        if dtype == np.float64:
            return np.float64
        if dtype == int:
            return int

        raise ValueError("Unsupported dtype. Must be np.float32 or"
                         "np.float64")

    def annotate(self, annotation, idx=None):
        """Annotates the array or a cell of the array. 
        This annotation will be associated with the last regular operation.

        Args:
            annotation (str): The annotation to be added.
            idx (int or tuple of ints): The index of the array. If None, the
                annotation will be associated with the entire array.
        """
        self._logger.append_annotation(self._array_name, annotation, idx)

    def get_timesteps(self):
        """Retrieve the timesteps of all DPArrays associated with this array's 
            logger.

        Returns:
            list of timesteps where each timestep is:
            timestep: {
                "array_name": {
                    "contents": array contents at this timestep,
                    Op.READ: [idx1, idx2, ...],
                    Op.WRITE: [idx1, idx2, ...],
                    Op.HIGHLIGHT: [idx1, idx2, ...],
                },
                "array_2": {
                    ...
                },
            }

        """
        return self._logger.to_timesteps()

    def print_timesteps(self):
        """Prints the timesteps in color. Currently works for 1D arrays only.

        Raises:
            ValueError: If the array shapes are not 1D.
        """
        self._logger.print_timesteps()

    def __getitem__(self, idx):
        """Retrieve an item using [] operator.

        Args:
            idx (int): The index of the array.

        Returns:  
            self.dtype or np.ndarray: corresponding item

        Warnings:
            Raises an warning when an undefined index is referenced.
        """
        if not np.all(self._occupied_arr[idx]):
            read_indices = np.full(self._arr.shape, False)
            read_indices[idx] = True
            undef_read_indices = np.flatnonzero(
                np.asarray(~self.occupied_arr & read_indices))
            warnings.warn(
                f"Referencing undefined elements in "
                f"'{self._array_name}'. Undefined elements: "
                f"{undef_read_indices}.",
                category=RuntimeWarning)
        log_idx = _nd_slice_to_indices(self._arr, idx)
        self._logger.append(self._array_name, Op.READ, log_idx)
        return self._arr[idx]

    def __setitem__(self, idx, value):
        """Set an item using the assignment operator.

        Args:
            idx (int): The index of the array.
            value (self.dtype or array-like): The assigned value.

        Raises:
            ValueError: If ``idx`` is a slice object.
        """
        log_idx = _nd_slice_to_indices(self._arr, idx)

        value = self.dtype(value)
        if isinstance(value, self.dtype):
            value = np.full(len(log_idx), value)

        self._arr[idx] = value.reshape(self._arr[idx].shape)
        self._occupied_arr[idx] = True
        self._logger.append(self._array_name, Op.WRITE, log_idx, value)

    def __eq__(self, other):
        """Equal to operator.

        Args:
            other (DPArray or array-like): Other container.

        Returns:
            np.ndarray: True/False mask.
        """
        if isinstance(other, DPArray):
            return self.arr == other.arr
        return self.arr == other

    def __ne__(self, other):
        """Not equal to operator.

        Args:
            other (DPArray or array-like): Other container.

        Returns:
            np.ndarray: True/False mask.
        """
        if isinstance(other, DPArray):
            return self.arr != other.arr
        return self.arr != other

    def _cmp(self, cmp, indices, elements=None):
        """Helper function for comparing a list of elements.

        Iterates through a list of element and outputs the "largest" element
        according to the cmp function. The indices corresponding to the final
        output will be highlighted in the DP array. To use this function,
        provide a list of elements and a list of indices for each element.
        For example,
        ```
        cmp = lambda x, y: x > y
        elements = [0, 1, 2, 3, 4, 4]
        indices = [None, 2, 4, 6, 8, 1]
        ```
        The output of this function will be `4` and indices `8` and `1` will be
        highlighted.

        Args:
            cmp (callable): A callable that returns boolean. cmp(x, y) == True
                if x is larger than y. For example, x > y for maximum and
                x < y for minimum.
            indices (array-like): An array of indices of the elements. This
                array has the same shape as elements.
            elements (array-like): An array of elements to be compared.
                These can be elements directly from the array (i.e. arr[0]), or
                modified elements (i.e. arr[0] + 1). If elements is None, the
                value of array at the indices queried is used.

        Returns:
            dtype: Final result of the comparisons

        Raises:
            ValueError: Indices and elements must have same length.
            ValueError: Indices and elements cannot be empty.
        """
        # Elements is an optional argument
        if elements is None:
            elements = [self[idx] for idx in indices]
        # TODO shape check for slices.
        if len(indices) != len(elements):
            raise ValueError("indices and elements must have same length")
        if len(elements) == 0 or len(indices) == 0:
            raise ValueError("indices and elements cannot be empty")

        best_indices = [indices[0]]
        best_element = elements[0]
        for i, e in zip(indices, elements):
            # Unravel when index is a slice.
            if isinstance(i, slice) and isinstance(e, np.ndarray):
                # Get argmax indices.
                slice_max_idx = e.flatten().argmax()
                slice_indices = _nd_slice_to_indices(self._arr, i)
                i = slice_indices[slice_max_idx]
                # Get max element.
                e = np.max(e)
            else:
                # Make index into a singleton.
                i = [i]

            # If new best index/element is found.
            if cmp(e, best_element):
                best_indices = i
                best_element = e

            # If index has equivalent element to the best element.
            elif e == best_element:
                best_indices.extend(i)

        # Highlight and write value.
        self.logger.append(self._array_name, Op.MAXMIN, best_indices)
        return best_element

    def max(self, indices, elements=None):
        """Outputs the maximum value and highlight its corresponding index.

        Args:
            elements (array-like): An array of elements to be compared.
                These can be elements directly from the array (i.e. arr[0]), or
                modified elements (i.e. arr[0] + 1).
            indices (array-like): An array of indices of the elements.
                indices[i] correspond to elements[i]. If elements[i] is not an
                element of the DP array, item[i] should be None. If elements 
                is None, the value of array at the indices queried is used.

        Returns:
            self.dtype: Maximum value of the elements.
        """
        return self._cmp(lambda x, y: x > y, indices, elements)

    def min(self, indices, elements=None):
        """Outputs the minimum value and highlight its corresponding index.

        Args:
            indices (array-like): An array of indices of the elements.
                indices[i] correspond to elements[i]. If elements[i] is not an
                element of the DP array, item[i] should be None.
            elements (array-like): An array of elements to be compared.
                These can be elements directly from the array (i.e. arr[0]), or
                modified elements (i.e. arr[0] + 1). If elements is None, the
                value of array at the indices queried is used.

        Returns:
            self.dtype: Minimum value of the elements.
        """
        return self._cmp(lambda x, y: x < y, indices, elements)

    def add_traceback_path(self, path):
        """Add a traceback path to this DPArray object.

        Paths added to a DPArray object will be displayed when calling display()
        on that DPArray object. The path will appear on the last frame of the
        visualization window (slider is in the rightmost position).

        Args:
            path (list of tuples): A list of indices to be displayed.
            Indices should be tuples with as many elements as the dimension
            of the array (the number of dimensions is given by len(shape)).
        """
        log_idx = _nd_slice_to_indices(self._arr, path)
        self._logger.append(self._array_name, Op.READ, log_idx)

    @property
    def arr(self):
        """Returns the np.ndarray that contains the DP array."""
        return np.array(self._arr, copy=True)

    @property
    def shape(self):
        """Returns the shape of the DP array."""
        return self._arr.shape

    @property
    def occupied_arr(self):
        """Returns the np.ndarray that contains the occupied mask."""
        return np.array(self._occupied_arr, copy=True)

    @property
    def logger(self):
        """Returns the np.ndarray that contains all the computations."""
        return self._logger

    @property
    def dtype(self):
        """Returns the data type of the array."""
        return self._dtype

    @property
    def array_name(self):
        """Returns the array name."""
        return self._array_name

arr property #

Returns the np.ndarray that contains the DP array.

array_name property #

Returns the array name.

dtype property #

Returns the data type of the array.

logger property #

Returns the np.ndarray that contains all the computations.

occupied_arr property #

Returns the np.ndarray that contains the occupied mask.

shape property #

Returns the shape of the DP array.

__eq__(other) #

Equal to operator.

Parameters:

Name Type Description Default
other DPArray or array - like

Other container.

 required

Returns:

Type Description
ndarray

True/False mask.
Source code in dp/_dp_array.py 
158
159
160
161
162
163
164
165
166
167
168
169
def __eq__(self, other):
    """Equal to operator.

    Args:
        other (DPArray or array-like): Other container.

    Returns:
        np.ndarray: True/False mask.
    """
    if isinstance(other, DPArray):
        return self.arr == other.arr
    return self.arr == other

__getitem__(idx) #

Retrieve an item using [] operator.

Parameters:

Name Type Description Default
idx int

The index of the array.

 required

Returns:

Type Description
dtype or ndarray

corresponding item
Source code in dp/_dp_array.py 
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
def __getitem__(self, idx):
    """Retrieve an item using [] operator.

    Args:
        idx (int): The index of the array.

    Returns:  
        self.dtype or np.ndarray: corresponding item

    Warnings:
        Raises an warning when an undefined index is referenced.
    """
    if not np.all(self._occupied_arr[idx]):
        read_indices = np.full(self._arr.shape, False)
        read_indices[idx] = True
        undef_read_indices = np.flatnonzero(
            np.asarray(~self.occupied_arr & read_indices))
        warnings.warn(
            f"Referencing undefined elements in "
            f"'{self._array_name}'. Undefined elements: "
            f"{undef_read_indices}.",
            category=RuntimeWarning)
    log_idx = _nd_slice_to_indices(self._arr, idx)
    self._logger.append(self._array_name, Op.READ, log_idx)
    return self._arr[idx]

__init__(shape, array_name='dp_array', *, logger=None, dtype=np.float64) #

Initializes the DPArray.

Source code in dp/_dp_array.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def __init__(
    self,
    shape,
    array_name="dp_array",
    *,
    logger=None,
    dtype=np.float64,
):
    """Initializes the DPArray."""
    self._dtype = self._parse_dtype(dtype)

    self._arr = np.full(shape, dtype=self._dtype, fill_value=np.nan)
    self._occupied_arr = np.zeros_like(self._arr, dtype=bool)

    self._logger = Logger() if logger is None else logger
    self._logger.add_array(array_name, shape)

    self._array_name = array_name

__ne__(other) #

Not equal to operator.

Parameters:

Name Type Description Default
other DPArray or array - like

Other container.

 required

Returns:

Type Description
ndarray

True/False mask.
Source code in dp/_dp_array.py 
171
172
173
174
175
176
177
178
179
180
181
182
def __ne__(self, other):
    """Not equal to operator.

    Args:
        other (DPArray or array-like): Other container.

    Returns:
        np.ndarray: True/False mask.
    """
    if isinstance(other, DPArray):
        return self.arr != other.arr
    return self.arr != other

__setitem__(idx, value) #

Set an item using the assignment operator.

Parameters:

Name Type Description Default
idx int

The index of the array.

 required
value dtype or array - like

The assigned value.

 required

Raises:

Type Description
ValueError

If idx is a slice object.
Source code in dp/_dp_array.py 
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
def __setitem__(self, idx, value):
    """Set an item using the assignment operator.

    Args:
        idx (int): The index of the array.
        value (self.dtype or array-like): The assigned value.

    Raises:
        ValueError: If ``idx`` is a slice object.
    """
    log_idx = _nd_slice_to_indices(self._arr, idx)

    value = self.dtype(value)
    if isinstance(value, self.dtype):
        value = np.full(len(log_idx), value)

    self._arr[idx] = value.reshape(self._arr[idx].shape)
    self._occupied_arr[idx] = True
    self._logger.append(self._array_name, Op.WRITE, log_idx, value)

add_traceback_path(path) #

Add a traceback path to this DPArray object.

Paths added to a DPArray object will be displayed when calling display() on that DPArray object. The path will appear on the last frame of the visualization window (slider is in the rightmost position).

Parameters:

Name Type Description Default
path list of tuples

A list of indices to be displayed.

 required
Source code in dp/_dp_array.py 
289
290
291
292
293
294
295
296
297
298
299
300
301
302
def add_traceback_path(self, path):
    """Add a traceback path to this DPArray object.

    Paths added to a DPArray object will be displayed when calling display()
    on that DPArray object. The path will appear on the last frame of the
    visualization window (slider is in the rightmost position).

    Args:
        path (list of tuples): A list of indices to be displayed.
        Indices should be tuples with as many elements as the dimension
        of the array (the number of dimensions is given by len(shape)).
    """
    log_idx = _nd_slice_to_indices(self._arr, path)
    self._logger.append(self._array_name, Op.READ, log_idx)

annotate(annotation, idx=None) #

Annotates the array or a cell of the array. This annotation will be associated with the last regular operation.

Parameters:

Name Type Description Default
annotation str

The annotation to be added.

 required
idx int or tuple of ints

The index of the array. If None, the annotation will be associated with the entire array.

 None
Source code in dp/_dp_array.py 
72
73
74
75
76
77
78
79
80
81
def annotate(self, annotation, idx=None):
    """Annotates the array or a cell of the array. 
    This annotation will be associated with the last regular operation.

    Args:
        annotation (str): The annotation to be added.
        idx (int or tuple of ints): The index of the array. If None, the
            annotation will be associated with the entire array.
    """
    self._logger.append_annotation(self._array_name, annotation, idx)

get_timesteps() #

Retrieve the timesteps of all DPArrays associated with this array's logger.

Returns:

Type Description
list of timesteps where each timestep is
timestep

{ "array_name": { "contents": array contents at this timestep, Op.READ: [idx1, idx2, ...], Op.WRITE: [idx1, idx2, ...], Op.HIGHLIGHT: [idx1, idx2, ...], }, "array_2": { ... },

}
Source code in dp/_dp_array.py 
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
def get_timesteps(self):
    """Retrieve the timesteps of all DPArrays associated with this array's 
        logger.

    Returns:
        list of timesteps where each timestep is:
        timestep: {
            "array_name": {
                "contents": array contents at this timestep,
                Op.READ: [idx1, idx2, ...],
                Op.WRITE: [idx1, idx2, ...],
                Op.HIGHLIGHT: [idx1, idx2, ...],
            },
            "array_2": {
                ...
            },
        }

    """
    return self._logger.to_timesteps()

max(indices, elements=None) #

Outputs the maximum value and highlight its corresponding index.

Parameters:

Name Type Description Default
elements array - like

An array of elements to be compared. These can be elements directly from the array (i.e. arr[0]), or modified elements (i.e. arr[0] + 1).

 None
indices array - like

An array of indices of the elements. indices[i] correspond to elements[i]. If elements[i] is not an element of the DP array, item[i] should be None. If elements is None, the value of array at the indices queried is used.

 required

Returns:

Type Description
dtype

Maximum value of the elements.
Source code in dp/_dp_array.py 
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
def max(self, indices, elements=None):
    """Outputs the maximum value and highlight its corresponding index.

    Args:
        elements (array-like): An array of elements to be compared.
            These can be elements directly from the array (i.e. arr[0]), or
            modified elements (i.e. arr[0] + 1).
        indices (array-like): An array of indices of the elements.
            indices[i] correspond to elements[i]. If elements[i] is not an
            element of the DP array, item[i] should be None. If elements 
            is None, the value of array at the indices queried is used.

    Returns:
        self.dtype: Maximum value of the elements.
    """
    return self._cmp(lambda x, y: x > y, indices, elements)

min(indices, elements=None) #

Outputs the minimum value and highlight its corresponding index.

Parameters:

Name Type Description Default
indices array - like

An array of indices of the elements. indices[i] correspond to elements[i]. If elements[i] is not an element of the DP array, item[i] should be None.

 required
elements array - like

An array of elements to be compared. These can be elements directly from the array (i.e. arr[0]), or modified elements (i.e. arr[0] + 1). If elements is None, the value of array at the indices queried is used.

 None

Returns:

Type Description
dtype

Minimum value of the elements.
Source code in dp/_dp_array.py 
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
def min(self, indices, elements=None):
    """Outputs the minimum value and highlight its corresponding index.

    Args:
        indices (array-like): An array of indices of the elements.
            indices[i] correspond to elements[i]. If elements[i] is not an
            element of the DP array, item[i] should be None.
        elements (array-like): An array of elements to be compared.
            These can be elements directly from the array (i.e. arr[0]), or
            modified elements (i.e. arr[0] + 1). If elements is None, the
            value of array at the indices queried is used.

    Returns:
        self.dtype: Minimum value of the elements.
    """
    return self._cmp(lambda x, y: x < y, indices, elements)

print_timesteps() #

Prints the timesteps in color. Currently works for 1D arrays only.

Raises:

Type Description
ValueError

If the array shapes are not 1D.
Source code in dp/_dp_array.py 
104
105
106
107
108
109
110
def print_timesteps(self):
    """Prints the timesteps in color. Currently works for 1D arrays only.

    Raises:
        ValueError: If the array shapes are not 1D.
    """
    self._logger.print_timesteps()