#127 Code refactoring in BCRSMatrix::addindex

Metadata

Property	Value
Reported by	unknown (unknown)
Reported at	May 15, 2006 14:33
Type	Feature Request
Version	Git (pre2.4) [autotools]
Operating System	Unspecified / All
Closed by	Oliver Sander (oliver.sander@tu-dresden.de)
Closed at	May 23, 2006 10:04
Closed in version	Unknown
Resolution	Implemented
Comment	Implemented by a patch by Martin Weiser in revision 608

Description

Use of STL algorithms simplifies code in BCRSMatrix::addindex.

void addindex (size_type row, size_type col)
{
  if (build_mode!=random)
	DUNE_THROW(ISTLError,"requires random build mode");	  
  if (ready)
	DUNE_THROW(ISTLError,"matrix already built up");

      // This code
      // >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
      if (col >= m)
        DUNE_THROW(ISTLError,"column index exceeds matrix size");

      // get row range
      size_type* const first = r[row].getindexptr();
      size_type* const last = first + r[row].getsize();

      // find correct insertion position for new column index
      size_type* pos = std::lower_bound(first,last,col);

      // check if index is already in row
      if (pos!=last && *pos == col) return;

      // find end of already inserted column indices
      size_type* end = std::lower_bound(pos,last,m);
      if (end==last)
        DUNE_THROW(ISTLError,"row is too small");

      // insert new column index at correct position
      std::copy_backward(pos,end,end+1);
      *pos = col;
      // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
      // should be functionally equivalent to (except for an
      // additional safety check), easier to maintain and slightly
      // more efficient than the following original code:
      // 
  // // get row 
  // size_type* p = r[row].getindexptr();
  // size_type  s = r[row].getsize();
  // 
  // // binary search for col
  // size_type l=0, r=s-1;
  // while (l<r)
  //       {
  //         size_type q = (l+r)/2;
  //         if (col <= p[q]) r=q;
  //         else l = q+1;
  //       }
      // 
  // // check if index is already in row
  // if (p[l]==col) return; 
      // 
  // // no, find first free entry by binary search
  // l=0; r=s-1;
  // while (l<r)
  //       {
  //         size_type q = (l+r)/2;
  //         if (m <= p[q]) r=q;
  //         else l = q+1;
  //       }
  // if (p[l]!=m)
  //       DUNE_THROW(ISTLError,"row is too small");	  
  //       
  // // now p[l] is the leftmost free entry
  // p[l] = col;
      // 
  // // use insertion sort to move index to correct position
  // for (size_type i=l-1; i>=0; i--)
  //       if (p[i]>p[i+1])
  //         std::swap(p[i],p[i+1]);
  //       else
  //         break;
}