org.apache.sysds.runtime.data

## Class SparseBlock

- java.lang.Object
- - org.apache.sysds.runtime.data.SparseBlock

All Implemented Interfaces:
  Serializable

Direct Known Subclasses:
  SparseBlockCOO, SparseBlockCSR, SparseBlockMCSR

    public abstract class SparseBlock
    extends Object
    implements Serializable

This SparseBlock is an abstraction for different sparse matrix formats. Since the design is a tradeoff between performance and generality, we restrict this abstraction to row-major sparse representations for now. All sparse matrix block operations are supposed to be implemented against this abstraction in order to enable variability/extensibility. Example sparse format that can be implemented efficiently include CSR, MCSR, and - with performance drawbacks - COO.

See Also:
  Serialized Form

### Nested Class Summary

Nested Classes
`static class` `SparseBlock.Type`

### Constructor Summary

Constructors
Constructor and Description
`SparseBlock()`

### Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
`abstract boolean` `add(int r, int c, double v)` Add a value to a matrix cell (r,c).
`abstract void` `allocate(int r)` Allocate the underlying data structure holding non-zero values of row r if necessary.
`abstract void` `allocate(int r, int nnz)` Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.
`abstract void` `allocate(int r, int ennz, int maxnnz)` Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.
`abstract void` `append(int r, int c, double v)` Append a value to the end of the physical representation.
`abstract boolean` `checkValidity(int rlen, int clen, long nnz, boolean strict)` Validate the correctness of the internal data structures of the different sparse block implementations.
`abstract void` `compact(int r)` Re-allocate physical row if physical size exceeds logical size plus resize factor.
`abstract void` `deleteIndexRange(int r, int cl, int cu)` Deletes all non-zero values of the given column range [cl,cu) in row r.
`abstract SparseRow` `get(int r)` Get values of row r in the format of a sparse row.
`abstract double` `get(int r, int c)` Get value of matrix cell (r,c).
`Iterator<IJV>` `getIterator()` Get a non-zero iterator over the entire sparse block.
`Iterator<IJV>` `getIterator(int ru)` Get a non-zero iterator over the partial sparse block [0,ru).
`Iterator<IJV>` `getIterator(int rl, int ru)` Get a non-zero iterator over the subblock [rl, ru).
`abstract int[]` `indexes(int r)` Get the sorted array of column indexes of all non-zero entries in row r.
`boolean` `isAligned(int r, SparseBlock that)` Indicates if all non-zero values of row r are aligned with the same row of the given second sparse block instance, which can be exploited for more efficient operations.
`boolean` `isAligned(SparseBlock that)` Indicates if all non-zero values are aligned with the given second sparse block instance, which can be exploited for more efficient operations.
`abstract boolean` `isAllocated(int r)` Indicates if the underlying data structure for a given row is already allocated.
`abstract boolean` `isContiguous()` Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.
`abstract boolean` `isEmpty(int r)` Get information if row r is empty, i.e., does not contain non-zero values.
`abstract boolean` `isThreadSafe()` Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.
`abstract int` `numRows()` Get the number of rows in the sparse block.
`abstract int` `pos(int r)` Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).
`abstract int` `posFIndexGT(int r, int c)` Get position of first column index greater than column c in row r.
`abstract int` `posFIndexGTE(int r, int c)` Get position of first column index greater than or equal column c in row r.
`abstract int` `posFIndexLTE(int r, int c)` Get position of first column index lower than or equal column c in row r.
`abstract void` `reset()` Clears the sparse block by deleting non-zero values.
`abstract void` `reset(int ennz, int maxnnz)` Clears the sparse block by deleting non-zero values.
`abstract void` `reset(int r, int ennz, int maxnnz)` Clears row r of the sparse block by deleting non-zero values.
`abstract boolean` `set(int r, int c, double v)` Set the value of a matrix cell (r,c).
`abstract void` `set(int r, SparseRow row, boolean deep)` Set the values of row r to the given sparse row.
`abstract void` `setIndexRange(int r, int cl, int cu, double[] v, int[] vix, int vpos, int vlen)` Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r.
`abstract void` `setIndexRange(int r, int cl, int cu, double[] v, int vix, int vlen)` Sets a dense array of non-zeros values into the column range [cl,cu) in row r.
`abstract long` `size()` Get the number of non-zero values in the sparse block.
`abstract int` `size(int r)` Get the number of non-zero values in row r.
`abstract long` `size(int rl, int ru)` Get the number of non-zeros values in the row range of [rl, ru).
`abstract long` `size(int rl, int ru, int cl, int cu)` Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);
`abstract void` `sort()` Sort all non-zero value/index pairs of the sparse block by row and column index.
`abstract void` `sort(int r)` Sort all non-zero value/index pairs of row r column index.
`abstract String` `toString()`
`abstract double[]` `values(int r)` Get the array of all non-zero entries in row r, sorted by their column indexes.

### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, wait, wait, wait`

### Constructor Detail

#### SparseBlock

    public SparseBlock()

### Method Detail

#### allocate

    public abstract void allocate(int r)

Allocate the underlying data structure holding non-zero values of row r if necessary.

Parameters:
  `r` - row index

#### allocate

    public abstract void allocate(int r,
                                  int nnz)

Allocate the underlying data structure holding non-zero values of row r if necessary, w/ given size.

Parameters:
  `r` - row index
  `nnz` - number of non-zeros

#### allocate

    public abstract void allocate(int r,
                                  int ennz,
                                  int maxnnz)

Allocate the underlying data structure holding non-zero values of row r w/ the specified estimated nnz and max nnz.

Parameters:
  `r` - row index
  `ennz` - estimated non-zeros
  `maxnnz` - max non-zeros

#### compact

    public abstract void compact(int r)

Re-allocate physical row if physical size exceeds logical size plus resize factor.

Parameters:
  `r` - row index

#### numRows

    public abstract int numRows()

Get the number of rows in the sparse block.

Returns:
  number of rows

#### isThreadSafe

    public abstract boolean isThreadSafe()

Indicates if the underlying implementation allows thread-safe row updates if concurrent threads update disjoint rows.

Returns:
  true if thread-safe row updates

#### isContiguous

    public abstract boolean isContiguous()

Indicates if the underlying data structures returned by values and indexes are contiguous arrays, which can be exploited for more efficient operations.

Returns:
  true if underlying data structures are contiguous arrays

#### isAligned

    public boolean isAligned(SparseBlock that)

Indicates if all non-zero values are aligned with the given second sparse block instance, which can be exploited for more efficient operations. Two non-zeros are aligned if they have the same column index and reside in the same array position.

Parameters:
  `that` - sparse block
Returns:
  true if all non-zero values are aligned with the given second sparse block

#### isAligned

    public boolean isAligned(int r,
                             SparseBlock that)

Indicates if all non-zero values of row r are aligned with the same row of the given second sparse block instance, which can be exploited for more efficient operations. Two non-zeros are aligned if they have the same column index and reside in the same array position.

Parameters:
  `r` - row index starting at 0
  `that` - sparse block
Returns:
  true if all non-zero values of row r are aligned with the same row of the given second sparse block instance

#### isAllocated

    public abstract boolean isAllocated(int r)

Indicates if the underlying data structure for a given row is already allocated.

Parameters:
  `r` - row index
Returns:
  true if already allocated

#### reset

    public abstract void reset()

Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.

#### reset

    public abstract void reset(int ennz,
                               int maxnnz)

Clears the sparse block by deleting non-zero values. After this call all size() calls are guaranteed to return 0.

Parameters:
  `ennz` - estimated non-zeros
  `maxnnz` - max non-zeros

#### reset

    public abstract void reset(int r,
                               int ennz,
                               int maxnnz)

Clears row r of the sparse block by deleting non-zero values. After this call size(r) is guaranteed to return 0.

Parameters:
  `r` - row index
  `ennz` - estimated non-zeros
  `maxnnz` - max non-zeros

#### size

    public abstract long size()

Get the number of non-zero values in the sparse block.

Returns:
  number of non-zero values in sparse block

#### size

    public abstract int size(int r)

Get the number of non-zero values in row r.

Parameters:
  `r` - row index starting at 0
Returns:
  number of non-zero values in row r

#### size

    public abstract long size(int rl,
                              int ru)

Get the number of non-zeros values in the row range of [rl, ru).

Parameters:
  `rl` - row lower index
  `ru` - row upper index
Returns:
  number of non-zero values in the row range

#### size

    public abstract long size(int rl,
                              int ru,
                              int cl,
                              int cu)

Get the number of non-zeros values in the row and column range of [rl/cl, ru/cu);

Parameters:
  `rl` - row lower index
  `ru` - row upper index
  `cl` - column lower index
  `cu` - column upper index
Returns:
  number of non-zero values in the row and column range

#### isEmpty

    public abstract boolean isEmpty(int r)

Get information if row r is empty, i.e., does not contain non-zero values. Equivalent to size(r)==0. Users should do this check if it is unknown if the underlying row data structure is allocated.

Parameters:
  `r` - row index starting at 0
Returns:
  true if row does not contain non-zero values

#### checkValidity

    public abstract boolean checkValidity(int rlen,
                                          int clen,
                                          long nnz,
                                          boolean strict)

Validate the correctness of the internal data structures of the different sparse block implementations.

Parameters:
  `rlen` - number of rows
  `clen` - number of columns
  `nnz` - number of non zeros
  `strict` - enforce optional properties
Returns:
  true if the sparse block is valid wrt the corresponding format such as COO, CSR, MCSR.

#### indexes

    public abstract int[] indexes(int r)

Get the sorted array of column indexes of all non-zero entries in row r. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).

Parameters:
  `r` - row index starting at 0
Returns:
  sorted array of column indexes

#### values

    public abstract double[] values(int r)

Get the array of all non-zero entries in row r, sorted by their column indexes. Note that - for flexibility of the implementing format - the returned array may be larger, where the range for row r is given by [pos(r),pos(r)+size(r)).

Parameters:
  `r` - row index starting at 0
Returns:
  array of all non-zero entries in row r sorted by column indexes

#### pos

    public abstract int pos(int r)

Get the starting position of row r in the indexes/values arrays returned by indexes(r) and values(r).

Parameters:
  `r` - row index starting at 0
Returns:
  starting position of row r

#### set

    public abstract boolean set(int r,
                                int c,
                                double v)

Set the value of a matrix cell (r,c). This might update an existing non-zero value, insert a new non-zero value, or delete a non-zero value.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
  `v` - zero or non-zero value
Returns:
  true, if number of non-zeros changed

#### set

    public abstract void set(int r,
                             SparseRow row,
                             boolean deep)

Set the values of row r to the given sparse row. This might update existing non-zero values, insert a new row, or delete a row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.

Parameters:
  `r` - row index starting at 0
  `row` - sparse row
  `deep` - indicator to create deep copy of sparse row

#### add

    public abstract boolean add(int r,
                                int c,
                                double v)

Add a value to a matrix cell (r,c). This might update an existing non-zero value, or insert a new non-zero value.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
  `v` - zero or non-zero value
Returns:
  true, if number of non-zeros changed

#### append

    public abstract void append(int r,
                                int c,
                                double v)

Append a value to the end of the physical representation. This should only be used for operations with sequential write pattern or if followed by a sort() operation. Note that this operation does not perform any matrix cell updates.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
  `v` - zero or non-zero value

#### setIndexRange

    public abstract void setIndexRange(int r,
                                       int cl,
                                       int cu,
                                       double[] v,
                                       int vix,
                                       int vlen)

Sets a dense array of non-zeros values into the column range [cl,cu) in row r. The passed value array may be larger and the relevant range is given by [vix,vix+len).

Parameters:
  `r` - row index starting at 0
  `cl` - lower column index starting at 0
  `cu` - upper column index starting at 0
  `v` - value array
  `vix` - start index in value array
  `vlen` - number of relevant values

#### setIndexRange

    public abstract void setIndexRange(int r,
                                       int cl,
                                       int cu,
                                       double[] v,
                                       int[] vix,
                                       int vpos,
                                       int vlen)

Sets a sparse array of non-zeros values and indexes into the column range [cl,cu) in row r. The passed value array may be larger.

Parameters:
  `r` - row index starting at 0
  `cl` - lower column index starting at 0
  `cu` - upper column index starting at 0
  `v` - value array
  `vix` - column index array
  `vpos` - start index in value and index arrays
  `vlen` - number of relevant values

#### deleteIndexRange

    public abstract void deleteIndexRange(int r,
                                          int cl,
                                          int cu)

Deletes all non-zero values of the given column range [cl,cu) in row r.

Parameters:
  `r` - row index starting at 0
  `cl` - lower column index starting at 0
  `cu` - upper column index starting at 0

#### sort

    public abstract void sort()

Sort all non-zero value/index pairs of the sparse block by row and column index.

#### sort

    public abstract void sort(int r)

Sort all non-zero value/index pairs of row r column index.

Parameters:
  `r` - row index starting at 0

#### get

    public abstract double get(int r,
                               int c)

Get value of matrix cell (r,c). In case of non existing values this call returns 0.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
Returns:
  value of cell at position (r,c)

#### get

    public abstract SparseRow get(int r)

Get values of row r in the format of a sparse row. NOTE: This method exists for incremental runtime integration and might be deleted in the future.

Parameters:
  `r` - row index starting at 0
Returns:
  values of row r as a sparse row

#### posFIndexLTE

    public abstract int posFIndexLTE(int r,
                                     int c)

Get position of first column index lower than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
Returns:
  position of the first column index lower than or equal to column c in row r

#### posFIndexGTE

    public abstract int posFIndexGTE(int r,
                                     int c)

Get position of first column index greater than or equal column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
Returns:
  position of the first column index greater than or equal to column c in row r

#### posFIndexGT

    public abstract int posFIndexGT(int r,
                                    int c)

Get position of first column index greater than column c in row r. The position is relative to the indexes/values arrays returned by indexes(r) and values(r). If no such value exists, this call returns -1.

Parameters:
  `r` - row index starting at 0
  `c` - column index starting at 0
Returns:
  position of the first column index greater than column c in row r

#### getIterator

    public Iterator<IJV> getIterator()

Get a non-zero iterator over the entire sparse block. Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.

Returns:
  IJV iterator

#### getIterator

    public Iterator<IJV> getIterator(int ru)

Get a non-zero iterator over the partial sparse block [0,ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.

Parameters:
  `ru` - exclusive upper row index starting at 0
Returns:
  IJV iterator

#### getIterator

    public Iterator<IJV> getIterator(int rl,
                                     int ru)

Get a non-zero iterator over the subblock [rl, ru). Note that the returned IJV object is reused across next calls and should be directly consumed or deep copied.

Parameters:
  `rl` - inclusive lower row index starting at 0
  `ru` - exclusive upper row index starting at 0
Returns:
  IJV iterator

#### toString

    public abstract String toString()

Overrides:
  `toString` in class `Object`