# HG changeset patch
# User Jaroslav Hajek <highegg@gmail.com>
# Date 1270715397 -7200
# Node ID cb7ffe7288f0cf2a5493a26aa7f7e31efeb5c47d
# Parent  3b77db443cc0bae97000511d9804e4bb512f3dd8
improve & fix SparseRep reallocation and compression

diff --git a/liboctave/Sparse.cc b/liboctave/Sparse.cc
--- a/liboctave/Sparse.cc
+++ b/liboctave/Sparse.cc
@@ -113,91 +113,52 @@
 void
 Sparse<T>::SparseRep::maybe_compress (bool remove_zeros)
 {
-  octave_idx_type ndel = nzmx - c[ncols];
-  octave_idx_type nzero = 0;
-
   if (remove_zeros)
-    for (octave_idx_type i = 0; i < nzmx - ndel; i++)
-      if (d[i] == T ())
-        nzero++;
-
-  if (!ndel && !nzero)
-    return;
-
-  if (!nzero)
     {
-      octave_idx_type new_nzmx = nzmx - ndel;
-
-      T *new_data = new T [new_nzmx];
-      for (octave_idx_type i = 0; i < new_nzmx; i++)
-        new_data[i] = d[i];
-      delete [] d;
-      d = new_data;
-
-      octave_idx_type *new_ridx = new octave_idx_type [new_nzmx];
-      for (octave_idx_type i = 0; i < new_nzmx; i++)
-        new_ridx[i] = r[i];
-      delete [] r;
-      r = new_ridx;
+      octave_idx_type i = 0, k = 0;
+      for (octave_idx_type j = 1; j <= ncols; j++)
+        {
+          octave_idx_type u = c[j];
+          for (i = i; i < u; i++)
+            if (d[i] != T())
+              {
+                d[k] = d[i];
+                r[k++] = r[i];
+              }
+          c[j] = k;
+        }
     }
-  else
-    {
-      octave_idx_type new_nzmx = nzmx - ndel - nzero;
-
-      T *new_data = new T [new_nzmx];
-      octave_idx_type *new_ridx = new octave_idx_type [new_nzmx];
-
-      octave_idx_type ii = 0;
-      octave_idx_type ic = 0;
-      for (octave_idx_type j = 0; j < ncols; j++)
-        {
-          for (octave_idx_type k = ic; k < c[j+1]; k++)
-            if (d[k] != T ())
-              {
-                new_data [ii] = d[k];
-                new_ridx [ii++] = r[k];
-              }
-          ic = c[j+1];
-          c[j+1] = ii;
-        }
-
-      delete [] d;
-      d = new_data;
-
-      delete [] r;
-      r = new_ridx;
-    }
-
-  nzmx -= ndel + nzero;
+
+  change_length (c[ncols]);
 }
 
 template <class T>
 void
 Sparse<T>::SparseRep::change_length (octave_idx_type nz)
 {
-  if (nz != nzmx)
+  for (octave_idx_type j = ncols; j > 0 && c[j] > nz; j--)
+    c[j] = nz;
+
+  // We shall skip reallocation if we have less than 1/frac extra elements to
+  // discard.
+  static const int frac = 5;
+  if (nz > nzmx || nz < nzmx - nzmx/frac)
     {
-      octave_idx_type min_nzmx = (nz < nzmx ? nz : nzmx);
+      // Reallocate.
+      octave_idx_type min_nzmx = std::min (nz, nzmx);
 
       octave_idx_type * new_ridx = new octave_idx_type [nz];
-      for (octave_idx_type i = 0; i < min_nzmx; i++)
-        new_ridx[i] = r[i];
+      copy_or_memcpy (min_nzmx, r, new_ridx);
 
       delete [] r;
       r = new_ridx;
 
       T * new_data = new T [nz];
-      for (octave_idx_type i = 0; i < min_nzmx; i++)
-        new_data[i] = d[i];
+      copy_or_memcpy (min_nzmx, d, new_data);
 
       delete [] d;
       d = new_data;
 
-      if (nz < nzmx)
-        for (octave_idx_type i = 0; i <= ncols; i++)
-          if (c[i] > nz)
-            c[i] = nz;
-
       nzmx = nz;
     }
 }
diff --git a/liboctave/Sparse.h b/liboctave/Sparse.h
--- a/liboctave/Sparse.h
+++ b/liboctave/Sparse.h
@@ -409,7 +409,13 @@
 #endif
 
   Sparse<T> maybe_compress (bool remove_zeros = false) 
-  { rep->maybe_compress (remove_zeros); return (*this); }
+    { 
+      if (remove_zeros)
+        make_unique (); // Needs to unshare because elements are removed.
+
+      rep->maybe_compress (remove_zeros); 
+      return (*this); 
+    }
 
   Sparse<T> reshape (const dim_vector& new_dims) const;
 
@@ -424,7 +430,12 @@
 
   void resize (const dim_vector& dv);
 
-  void change_capacity (octave_idx_type nz) { rep->change_length (nz); }
+  void change_capacity (octave_idx_type nz) 
+    { 
+      if (nz < nnz ())
+        make_unique (); // Unshare now because elements will be truncated.
+      rep->change_length (nz); 
+    }
 
   Sparse<T>& insert (const Sparse<T>& a, octave_idx_type r, octave_idx_type c);
   Sparse<T>& insert (const Sparse<T>& a, const Array<octave_idx_type>& idx);