text: r"""
  Sparse Matrices over a general ring
  
  EXAMPLES::
  
      sage: R.<x> = PolynomialRing(QQ)
      sage: M = MatrixSpace(QQ['x'],2,3,sparse=True); M
      Full MatrixSpace of 2 by 3 sparse matrices over Univariate Polynomial Ring in x over Rational Field
      sage: a = M(range(6)); a
      [0 1 2]
      [3 4 5]
      sage: b = M([x^n for n in range(6)]); b
      [  1   x x^2]
      [x^3 x^4 x^5]
      sage: a * b.transpose()
      [            2*x^2 + x           2*x^5 + x^4]
      [      5*x^2 + 4*x + 3 5*x^5 + 4*x^4 + 3*x^3]
      sage: pari(a)*pari(b.transpose())
      [2*x^2 + x, 2*x^5 + x^4; 5*x^2 + 4*x + 3, 5*x^5 + 4*x^4 + 3*x^3]
      sage: c = copy(b); c
      [  1   x x^2]
      [x^3 x^4 x^5]
      sage: c[0,0] = 5; c
      [  5   x x^2]
      [x^3 x^4 x^5]
      sage: b[0,0]
      1
      sage: c.dict()
      {(0, 0): 5, (0, 1): x, (0, 2): x^2, (1, 0): x^3, (1, 1): x^4, (1, 2): x^5}
      sage: c.list()
      [5, x, x^2, x^3, x^4, x^5]
      sage: c.rows()
      [(5, x, x^2), (x^3, x^4, x^5)]
      sage: TestSuite(c).run()
      sage: d = c.change_ring(CC['x']); d
      [5.00000000000000                x              x^2]
      [             x^3              x^4              x^5]
      sage: latex(c)
      \left(\begin{array}{rrr}
      5 & x & x^{2} \\
      x^{3} & x^{4} & x^{5}
      \end{array}\right)
      sage: c.sparse_rows()
      [(5, x, x^2), (x^3, x^4, x^5)]
      sage: d = c.dense_matrix(); d
      [  5   x x^2]
      [x^3 x^4 x^5]
      sage: parent(d)
      Full MatrixSpace of 2 by 3 dense matrices over Univariate Polynomial Ring in x over Rational Field
      sage: c.sparse_matrix() is c
      True
      sage: c.is_sparse()
      True
  """
  
  cimport sage.matrix.matrix as matrix
  cimport sage.matrix.matrix_sparse as matrix_sparse
  cimport sage.structure.element
  from sage.structure.element cimport ModuleElement
  from .args cimport MatrixArgs_init
  
  import sage.misc.misc as misc
  
  cdef class Matrix_generic_sparse(matrix_sparse.Matrix_sparse):
      r"""
      Generic sparse matrix.
  
      The ``Matrix_generic_sparse`` class derives from
      :class:`~sage.matrix.matrix_sparse.Matrix_sparse`, and defines functionality
      for sparse matrices over any base ring. A generic sparse matrix is
      represented using a dictionary whose keys are pairs of integers `(i,j)` and
      values in the base ring. The values of the dictionary must never be zero.
  
      EXAMPLES::
  
          sage: R.<a,b> = PolynomialRing(ZZ,'a,b')
          sage: M = MatrixSpace(R,5,5,sparse=True)
          sage: M({(0,0):5*a+2*b, (3,4): -a})
          [5*a + 2*b         0         0         0         0]
          [        0         0         0         0         0]
          [        0         0         0         0         0]
          [        0         0         0         0        -a]
          [        0         0         0         0         0]
          sage: M(3)
          [3 0 0 0 0]
          [0 3 0 0 0]
          [0 0 3 0 0]
          [0 0 0 3 0]
          [0 0 0 0 3]
          sage: V = FreeModule(ZZ, 5,sparse=True)
          sage: m = M([V({0:3}), V({2:2, 4:-1}), V(0), V(0), V({1:2})])
          sage: m
          [ 3  0  0  0  0]
          [ 0  0  2  0 -1]
          [ 0  0  0  0  0]
          [ 0  0  0  0  0]
          [ 0  2  0  0  0]
  
      .. NOTE::
  
          The datastructure can potentially be optimized. Firstly, as noticed in
          :trac:`17663`, we lose time in using 2-tuples to store indices.
          Secondly, there is no fast way to access non-zero elements in a given
          row/column.
      """
      def __cinit__(self):
          self._entries = {}  # crucial so that pickling works
          self._zero = self._base_ring.zero()
  
      def __init__(self, parent, entries=None, copy=None, bint coerce=True):
          r"""
          Create a sparse matrix over the given base ring.
  
          INPUT:
  
          - ``parent`` -- a matrix space
  
          - ``entries`` -- see :func:`matrix`
  
          - ``copy`` -- ignored (for backwards compatibility)
  
          - ``coerce`` -- if False, assume without checking that the
            entries lie in the base ring
  
          TESTS::
  
              sage: R.<a> = PolynomialRing(ZZ,'a')
              sage: M = MatrixSpace(R,2,3,sparse=True)
              sage: m = M([4,1,0,0,0,2]); m
              [4 1 0]
              [0 0 2]
              sage: m2 = copy(m)
              sage: m2[0,0] = -1
              sage: m[0,0]
              4
              sage: loads(dumps(m)) == m
              True
  
              sage: R2.<a,b> = PolynomialRing(QQ)
              sage: M2 = MatrixSpace(R2,2,3,sparse=True)
              sage: M2(m)
              [4 1 0]
              [0 0 2]
              sage: M2.has_coerce_map_from(M)
              True
  
              sage: M3 = M2.change_ring(R2.fraction_field())
              sage: M3.has_coerce_map_from(M2)
              True
  
          Check that it is not possible to use wrong indices::
  
              sage: M = MatrixSpace(R,2,2,sparse=True)
              sage: M({(3,0): 1})
              Traceback (most recent call last):
              ...
              IndexError: invalid row index 3
              sage: M({(0,-3): 1})
              Traceback (most recent call last):
              ...
              IndexError: invalid column index -3
  
          But negative indices are valid and wrap around::
  
              sage: M({(-1,-1): 1})
              [0 0]
              [0 1]
          """
          ma = MatrixArgs_init(parent, entries)
          self._entries = ma.dict(coerce)
  
      def __nonzero__(self):
          r"""
          Test wether this matrix is non-zero.
  
          TESTS::
  
              sage: R.<a,b> = Zmod(5)['a','b']
              sage: m = matrix(R,3,4,sparse=True)
              sage: bool(m)      # indirect doctest
              False
              sage: m[0,3] = 1
              sage: bool(m)      # indirect doctest
              True
              sage: m[0,3] = 0   # indirect doctest
              sage: bool(m)
              False
              sage: m.is_zero()  # indirect doctest
              True
          """
          return bool(self._entries)
  
      cdef set_unsafe(self, Py_ssize_t i, Py_ssize_t j, value):
          if not value:
              try:
                  del self._entries[(i,j)]
              except KeyError:
                  pass
          else:
              self._entries[(i,j)] = value
  
      cdef get_unsafe(self, Py_ssize_t i, Py_ssize_t j):
          return self._entries.get((i,j), self._zero)
  
      cdef bint get_is_zero_unsafe(self, Py_ssize_t i, Py_ssize_t j):
          """
          Return 1 if the entry ``(i, j)`` is zero, otherwise 0.
  
          EXAMPLES::
  
              sage: R.<a,b> = Zmod(5)['a','b']
              sage: m = matrix(R,2,4, {(1,3): a, (0,0):b}, sparse=True)
              sage: m.zero_pattern_matrix()  # indirect doctest
              [0 1 1 1]
              [1 1 1 0]
          """
          return (i,j) not in self._entries
  
      def _pickle(self):
          version = 0
          return self._entries, version
  
      def _unpickle(self, data, int version):
          """
          EXAMPLES::
  
              sage: R.<x> = ZZ[]
              sage: a = matrix(R, [[1,10],[3,4]],sparse=True); a
              [ 1 10]
              [ 3  4]
              sage: loads(dumps(a)) == a
              True
          """
          if version == 0:
              self._entries = data
              self._zero = self._base_ring(0)
          else:
              raise RuntimeError("unknown matrix version (=%s)"%version)
  
      ########################################################################
      # LEVEL 2 functionality
      # x  * cdef _add_
      #    * cdef _mul_
      #    * cpdef _richcmp_
      #    * __neg__
      #    * __invert__
      # x  * __copy__
      #    * _multiply_classical
      # x  * _list -- copy of the list of underlying elements
      # x  * _dict -- copy of the sparse dictionary of underlying elements
      ########################################################################
  
      cpdef _add_(self, _other):
          """
          EXAMPLES::
  
              sage: R.<x> = QQ[]
              sage: a = matrix(R, [[1,10],[3,4]],sparse=True); a
              [ 1 10]
              [ 3  4]
              sage: a+a
              [ 2 20]
              [ 6  8]
  
          ::
  
              sage: a = matrix(R, [[1,10,-5/3],[2/8,3,4]], sparse=True); a
              [   1   10 -5/3]
              [ 1/4    3    4]
              sage: a+a
              [    2    20 -10/3]
              [  1/2     6     8]
          """
          # Compute the sum of two sparse matrices.
          # This is complicated because of how we represent sparse matrices.
          # Algorithm:
          #   1. Sort both entry coefficient lists.
          #   2. March through building a new list, adding when the two i,j are the same.
          cdef Py_ssize_t i, j, len_v, len_w
          cdef Matrix_generic_sparse other
          other = <Matrix_generic_sparse> _other
          cdef list v = sorted(self._entries.items())
          cdef list w = sorted(other._entries.items())
          s = {}
          i = 0  # pointer into self
          j = 0  # pointer into other
          len_v = len(v)
          len_w = len(w)
          while i < len_v and j < len_w:
              vi = v[i][0]
              wj = w[j][0]
              if vi < wj:
                  s[vi] = v[i][1]
                  i += 1
              elif vi > wj:
                  s[wj] = w[j][1]
                  j += 1
              else:  # equal
                  sm = v[i][1] + w[j][1]
                  if sm:
                      s[vi] = sm
                  i += 1
                  j += 1
          while i < len(v):
              s[v[i][0]] = v[i][1]
              i += 1
          while j < len(w):
              s[w[j][0]] = w[j][1]
              j += 1
  
          cdef Matrix_generic_sparse A
          A = Matrix_generic_sparse.__new__(Matrix_generic_sparse, self._parent, 0,0,0)
          matrix.Matrix.__init__(A, self._parent)
          A._entries = s
          A._zero = self._zero
          A._base_ring = self._base_ring
          return A
  
      def __copy__(self):
          A = self.__class__(self._parent, self._entries, copy = True, coerce=False)
          if self._subdivisions is not None:
              A.subdivide(*self.subdivisions())
          return A
  
  
      def _list(self):
          """
          Return all entries of self as a list of numbers of rows times
          number of columns entries.
          """
          cdef Py_ssize_t i,j
          cdef list v = self.fetch('list')
          if v is None:
              v = [self._zero]*(self._nrows * self._ncols)
              for (i,j), x in self._entries.iteritems():
                  v[i*self._ncols + j] = x
              self.cache('list', v)
          return v
  
      def _dict(self):
          """
          Return the underlying dictionary of self.
  
          This is used in comparisons.
  
          TESTS::
  
              sage: R.<a,b> = Zmod(6)[]
              sage: M = MatrixSpace(R, 3, 4)
              sage: m = M({(0,3): a+3*b*a, (1,1): -b})
              sage: m == m    # indirect doctest
              True
              sage: M(0) == m # indirect doctest
              False
          """
          return self._entries
  
      ########################################################################
      # LEVEL 3 functionality -- matrix windows, etc.
      ########################################################################
  
      def _nonzero_positions_by_row(self, copy=True):
          r"""
          TESTS::
  
              sage: R.<a> = PolynomialRing(Zmod(8), 'a')
              sage: M = MatrixSpace(R,4,3,sparse=True)
              sage: m = M({(3,0): 1, (3,1): 2*a^2 + 1, (2,0): -1, (0,1): -2})
              sage: m._nonzero_positions_by_row()
              [(0, 1), (2, 0), (3, 0), (3, 1)]
          """
          cdef list v = self.fetch('nonzero_positions')
          if v is None:
              v = sorted(self._entries)
              self.cache('nonzero_positions', v)
          if copy:
              return v[:]
          return v
  
      def _nonzero_positions_by_column(self, copy=True):
          r"""
          TESTS::
  
              sage: R.<a> = PolynomialRing(Zmod(8), 'a')
              sage: M = MatrixSpace(R,4,3,sparse=True)
              sage: m = M({(3,0): 1, (3,1): 2*a^2 + 1, (2,0): -1, (0,1): -2})
              sage: m._nonzero_positions_by_column()
              [(2, 0), (3, 0), (0, 1), (3, 1)]
          """
          cdef list v = self.fetch('nonzero_positions_by_column')
          if v is None:
              v = sorted(self._entries, key=lambda x: (x[1], x[0]))
              self.cache('nonzero_positions_by_column', v)
          if copy:
              return v[:]
          return v
  
  
  ####################################################################################
  # Various helper functions
  ####################################################################################
  
  def Matrix_sparse_from_rows(X):
      """
      INPUT:
  
      -  ``X`` - nonempty list of SparseVector rows
  
  
      OUTPUT: Sparse_matrix with those rows.
  
      EXAMPLES::
  
          sage: V = VectorSpace(QQ,20,sparse=True)
          sage: v = V(0)
          sage: v[9] = 4
          sage: from sage.matrix.matrix_generic_sparse import Matrix_sparse_from_rows
          sage: Matrix_sparse_from_rows([v])
          [0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0]
          sage: Matrix_sparse_from_rows([v, v, v, V(0)])
          [0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0]
          [0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0]
          [0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0]
          [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
      """
      cdef Py_ssize_t i, j
  
      if not isinstance(X, (list, tuple)):
          raise TypeError("X (=%s) must be a list or tuple" % X)
      if not X:
          raise ArithmeticError("X must be nonempty")
  
      from . import matrix_space
      entries = {}
      R = X[0].base_ring()
      ncols = X[0].degree()
      for i from 0 <= i < len(X):
          for j, x in X[i].iteritems():
              entries[(i,j)] = x
      M = matrix_space.MatrixSpace(R, len(X), ncols, sparse=True)
      return M(entries, coerce=False, copy=False)
  