sparse

Documentation

Overview

Package sparse implements a simple type for sparse integer matrices. It is mainly used for parser tables (GOTO-table and ACTION-table). Every entry in the table is either a single int32 or a pair (int32,int32).

This implementation uses the COO algorithm (a.k.a. triplet-encoding).

https://medium.com/@jmaxg3/101-ways-to-store-a-sparse-matrix-c7f2bf15a229
https://www.coin-or.org/Ipopt/documentation/node38.html

BSD License

Copyright (c) 2017-20, Norbert Pillmayer

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of Norbert Pillmayer or the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• Constants
• type IntMatrix
  • func NewIntMatrix(m, n int, nullValue int32) *IntMatrix
  • func (m *IntMatrix) Add(i, j int, value int32) *IntMatrix
  • func (m *IntMatrix) M() int
  • func (m *IntMatrix) N() int
  • func (m *IntMatrix) NullValue() int32
  • func (m *IntMatrix) Set(i, j int, value int32) *IntMatrix
  • func (m *IntMatrix) Value(i, j int) int32
  • func (m *IntMatrix) ValueCount() int
  • func (m *IntMatrix) Values(i, j int) (int32, int32)

Constants

const DefaultNullValue = -2147483648

DefaultNullValue is the default empty-value for matrices (min int32).

Types

type IntMatrix

type IntMatrix struct {
	// contains filtered or unexported fields
}

IntMatrix is a type for a spare matrix of integer values. Construct with

M := NewIntMatrix(10, 10, -1)  // last parameter is M's null-value

Now

M.Set(2, 3, 4711)              // set a value
v := M.Value(2, 3)             // returns 4711
M.Add(2, 3, 123)               // add a second value
cnt := M.ValueCount()          // still returns 1 (one position set)
v = M.Value(10, 10)            // returns -1, i.e. the null-value

Values cannot be deleted, but may be overwritten with the null-value. Space for null-values is not re-claimed.

func NewIntMatrix

func NewIntMatrix(m, n int, nullValue int32) *IntMatrix

NewIntMatrix creates a new matrix for int, size m x n. The 3rd argument is a null-value, indicating empty entries (use DefaultNullValue if you haven't any specific requirements).

func (*IntMatrix) Add

func (m *IntMatrix) Add(i, j int, value int32) *IntMatrix

Add a value in the matrix at position (i,j).

func (*IntMatrix) M

func (m *IntMatrix) M() int

M returns the row count.

func (*IntMatrix) N

func (m *IntMatrix) N() int

N returns the column count.

func (*IntMatrix) NullValue

func (m *IntMatrix) NullValue() int32

NullValue returns this matrix' null value

func (*IntMatrix) Set

func (m *IntMatrix) Set(i, j int, value int32) *IntMatrix

Set a value in the matrix at position (i,j).

func (*IntMatrix) Value

func (m *IntMatrix) Value(i, j int) int32

Value returns the primary value at position (i,j), or NullValue

func (*IntMatrix) ValueCount

func (m *IntMatrix) ValueCount() int

ValueCount returns the number of values in the matrix.

func (*IntMatrix) Values

func (m *IntMatrix) Values(i, j int) (int32, int32)

Values returns the pair of values at position (i,j), or (NullValue, NullValue)