# HG changeset patch
# User Jason Riedy <jason@acm.org>
# Date 1237237387 14400
# Node ID 542015fada9e87c149d9d3e7a8a6dcc5719f48fc
# Parent  22c8272af34bfcc66b1dc9be25b8cd6269812cd8
Eliminate the workspace in sparse transpose.

The output's cidx (column start offset array) can serve as the
workspace, so the routines operate in the space of their output.

diff -r 22c8272af34b -r 542015fada9e liboctave/CSparse.cc
--- a/liboctave/CSparse.cc	Tue Mar 17 08:49:08 2009 +0100
+++ b/liboctave/CSparse.cc	Mon Mar 16 17:03:07 2009 -0400
@@ -646,28 +646,28 @@
   octave_idx_type nz = nnz ();
   SparseComplexMatrix retval (nc, nr, nz);
 
-  OCTAVE_LOCAL_BUFFER (octave_idx_type, w, nr + 1);
-  for (octave_idx_type i = 0; i < nr; i++)
-    w[i] = 0;
   for (octave_idx_type i = 0; i < nz; i++)
-    w[ridx(i)]++;
+    retval.xcidx (ridx (i) + 1)++;
+  // retval.xcidx[1:nr] holds the row degrees for rows 0:(nr-1)
   nz = 0;
-  for (octave_idx_type i = 0; i < nr; i++)
+  for (octave_idx_type i = 1; i <= nr; i++)
     {
-      retval.xcidx(i) = nz;
-      nz += w[i];
-      w[i] = retval.xcidx(i);
+      const octave_idx_type tmp = retval.xcidx (i);
+      retval.xcidx (i) = nz;
+      nz += tmp;
     }
-  retval.xcidx(nr) = nz;
-  w[nr] = nz;
+  // retval.xcidx[1:nr] holds row entry *start* offsets for rows 0:(nr-1)
 
   for (octave_idx_type j = 0; j < nc; j++)
     for (octave_idx_type k = cidx(j); k < cidx(j+1); k++)
       {
-	octave_idx_type q = w [ridx(k)]++;
+	octave_idx_type q = retval.xcidx (ridx (k) + 1)++;
 	retval.xridx (q) = j;
 	retval.xdata (q) = conj (data (k));
       }
+  assert (nnz () == retval.xcidx (nr));
+  // retval.xcidx[1:nr] holds row entry *end* offsets for rows 0:(nr-1)
+  // and retval.xcidx[0:(nr-1)] holds their row entry *start* offsets
 
   return retval;
 }
diff -r 22c8272af34b -r 542015fada9e liboctave/ChangeLog
--- a/liboctave/ChangeLog	Tue Mar 17 08:49:08 2009 +0100
+++ b/liboctave/ChangeLog	Mon Mar 16 17:03:07 2009 -0400
@@ -1,3 +1,10 @@
+2009-03-16  Jason Riedy  <jason@acm.org>
+
+	* Sparse.cc (transpose): Eliminate the workspace by computing in
+	retval.xcidx.
+	* CSparse.cc (hermitian): Eliminate the workspace by computing in
+	retval.xcidx.
+
 2009-03-14  Jaroslav Hajek  <highegg@gmail.com>
 
 	* mx-op-decl.h (NDS_BOOL_OP_DECLS, SND_BOOL_OP_DECLS, NDND_BOOL_OP_DECLS): Support compound binary ops.
diff -r 22c8272af34b -r 542015fada9e liboctave/Sparse.cc
--- a/liboctave/Sparse.cc	Tue Mar 17 08:49:08 2009 +0100
+++ b/liboctave/Sparse.cc	Mon Mar 16 17:03:07 2009 -0400
@@ -1062,28 +1062,28 @@
   octave_idx_type nz = nnz ();
   Sparse<T> retval (nc, nr, nz);
 
-  OCTAVE_LOCAL_BUFFER (octave_idx_type, w, nr + 1);
-  for (octave_idx_type i = 0; i < nr; i++)
-    w[i] = 0;
   for (octave_idx_type i = 0; i < nz; i++)
-    w[ridx(i)]++;
+    retval.xcidx (ridx (i) + 1)++;
+  // retval.xcidx[1:nr] holds the row degrees for rows 0:(nr-1)
   nz = 0;
-  for (octave_idx_type i = 0; i < nr; i++)
+  for (octave_idx_type i = 1; i <= nr; i++)
     {
-      retval.xcidx(i) = nz;
-      nz += w[i];
-      w[i] = retval.xcidx(i);
+      const octave_idx_type tmp = retval.xcidx (i);
+      retval.xcidx (i) = nz;
+      nz += tmp;
     }
-  retval.xcidx(nr) = nz;
-  w[nr] = nz;
+  // retval.xcidx[1:nr] holds row entry *start* offsets for rows 0:(nr-1)
 
   for (octave_idx_type j = 0; j < nc; j++)
     for (octave_idx_type k = cidx(j); k < cidx(j+1); k++)
       {
-	octave_idx_type q = w [ridx(k)]++;
+	octave_idx_type q = retval.xcidx (ridx (k) + 1)++;
 	retval.xridx (q) = j;
 	retval.xdata (q) = data (k);
       }
+  assert (nnz () == retval.xcidx (nr));
+  // retval.xcidx[1:nr] holds row entry *end* offsets for rows 0:(nr-1)
+  // and retval.xcidx[0:(nr-1)] holds their row entry *start* offsets
 
   return retval;
 }