Class SparseElementSearch

java.lang.Object

org.flag4j.linalg.ops.sparse.SparseElementSearch

public final class SparseElementSearch
extends Object

This class provides methods for efficiently finding if a sparse vector, matrix, or tensor contains a non-zero item at a specified index.

Method Summary

Modifier and Type	Method	Description
static int	binarySearchCoo(int[][] indices, int[] target)	Performs a binary search of the indices of a sparse COO tensor to find a target index.
static int	matrixBinarySearch(int[] rowIndices, int[] colIndices, int rowKey, int colKey)	Preforms a binary search along the row and column indices of the non-zero values of a sparse matrix for the location of an entry with the specified target indices.
static int[]	matrixFindRowStartEnd(int[] rowIndices, int rowKey)	Finds the indices of the first and last non-zero element in the specified row of a sparse matrix.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

matrixBinarySearch

public static int matrixBinarySearch(int[] rowIndices,
 int[] colIndices,
 int rowKey,
 int colKey)

Preforms a binary search along the row and column indices of the non-zero values of a sparse matrix for the location of an entry with the specified target indices.

Parameters:

rowIndices - Row indices of the matrix to search within.

colIndices - Column indices of the matrix to search within.

rowKey - Target row index.

colKey - Target col index.

Returns:

The location of the non-zero element (within the non-zero values array of src) with the specified row and column indices. If this value does not exist, then (-(insertion point) - 1) will be returned. The insertion point is defined as the point at which the value, with the row and column key, would be inserted into the array: the index of the first element greater than the key, or src.data.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

matrixFindRowStartEnd

public static int[] matrixFindRowStartEnd(int[] rowIndices,
 int rowKey)

Finds the indices of the first and last non-zero element in the specified row of a sparse matrix. If there is no non-zero element in the sparse matrix at the specified row, negative values will be returned.

Parameters:

rowIndices - Row indices of the matrix to search within.

rowKey - Index of the row to search for within the row indices of the src matrix.

Returns:

If it exists, the first and last index of the non-zero element in the sparse matrix which has the specified rowKey as its row index.

binarySearchCoo

public static int binarySearchCoo(int[][] indices,
 int[] target)

Performs a binary search of the indices of a sparse COO tensor to find a target index.

Parameters:

indices - The non-zero indices of the COO tensor. Assumed to be rectangular array.

target - The target index to find in indices. Must satisfy target.length == indices[0].length if indices.length > 0.

Returns:

index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element in the range greater than the key, or toIndex if all elements in the range are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Throws:

IllegalArgumentException - If target.length != indices[0].length.