Sparse 3D matrix in python just for insertion/deletion of elemets, deletion of rows, and fast access to non empty z dimension

Question

I'm looking for a matrix-like datatype that would get triplets (x, y, z) as keys, and can implement: - initial value - fast insertion/deletion - deletion of rows - given x, y get all z indices so that x, y, z is non default value.

This is used for an NFA parser, where x and z are states and y is a terminal.

Answer 1

A python 3.4 implementation:

class Sparse3DMatrix():
  def __init__(self, default_value=False, max_x=100, max_y=100):
    self._dim = 3
    self._max_x = max_x
    self._max_y = max_y
    self._init_non_empty_z()
    self._default_value = default_value
    self._elements = {}
  def __getitem__(self, triplet):
    assert(len(triplet) == self._dim)
    return self._elements.get(triplet, self._default_value)
  def __setitem__(self, triplet, value):
    assert(len(triplet) == self._dim)
    if value == self._default_value:
      if triplet in self._elements:
        self._delete_element(triplet)
    else:
      if triplet not in self._elements:
        self._add_element(triplet, value)
      else:
        self._elements[triplet] = value
  def _init_non_empty_z(self):
    self.non_empty_z = {}
    for i in range(self._max_x):
      for j in range(self._max_y):
        self.non_empty_z[i, j] = []
  def _delete_element(self, triplet):
    """ Deletes an element. Element is assumed to exist. """
    del self._elements[triplet]
    self.non_empty_z[triplet[0], triplet[1]].remove(triplet[2])
  def _add_element(self, triplet, value):
    """ Adds an element. triplet is assumed to be default value before call. """
    self._elements[triplet] = value
    self.non_empty_z[triplet[0], triplet[1]].append(triplet[2])
  def delete_by_axis(self, index, axis):
    """ Slow deletion of entire row / column / depth """
    old_triplets = self._elements.copy().items()
    self._elements = {}
    self._init_non_empty_z()
    for triplet, value in old_triplets:
      if triplet[axis] < index:
        self._add_element(triplet, value)
      elif triplet[axis] > index:
        new_triplet = list(triplet)
        new_triplet[axis] -= 1
        self._add_element(tuple(new_triplet), value)
  def all_non_default_value(self):
    return list(self._elements.keys())