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
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `SparseBlock.Type`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `SparseBlock()`

  - ### Method Summary

    All Methods Instance Methods Abstract Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `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`

Copyright © 2021 The Apache Software Foundation. All rights reserved.