From 91ee2616a14012cb043e48bdc2527fa1e6a18773 Mon Sep 17 00:00:00 2001
From: kronbichler <kronbichler@0785d39b-7218-0410-832d-ea1e28bc413d>
Date: Mon, 6 Apr 2009 15:44:14 +0000
Subject: [PATCH] Write a smarter add_entries function for
 CompressedSparsityPattern.

git-svn-id: https://svn.dealii.org/trunk@18556 0785d39b-7218-0410-832d-ea1e28bc413d
---
 .../include/lac/compressed_sparsity_pattern.h |  22 +--
 .../lac/source/compressed_sparsity_pattern.cc | 136 ++++++++++++++++++
 2 files changed, 141 insertions(+), 17 deletions(-)

diff --git a/deal.II/lac/include/lac/compressed_sparsity_pattern.h b/deal.II/lac/include/lac/compressed_sparsity_pattern.h
index 233931e50b..4603b5fc95 100644
--- a/deal.II/lac/include/lac/compressed_sparsity_pattern.h
+++ b/deal.II/lac/include/lac/compressed_sparsity_pattern.h
@@ -200,7 +200,7 @@ class CompressedSparsityPattern : public Subscriptor
     void add_entries (const unsigned int row, 
 		      ForwardIterator    begin,
 		      ForwardIterator    end,
-		      const bool         indices_are_sorted = false);
+		      const bool         indices_are_unique_and_sorted = false);
 
 				     /**
 				      * Check if a value at a certain
@@ -435,7 +435,8 @@ class CompressedSparsityPattern : public Subscriptor
                                           */
         template <typename ForwardIterator>
 	void add_entries (ForwardIterator begin,
-			  ForwardIterator end);
+			  ForwardIterator end,
+			  const bool indices_are_sorted);
 
                                          /**
                                           * Flush the cache my merging it with
@@ -480,19 +481,6 @@ CompressedSparsityPattern::Line::add (const unsigned int j)
 
 
 
-template <typename ForwardIterator>
-inline
-void
-CompressedSparsityPattern::Line::add_entries (ForwardIterator begin,
-					      ForwardIterator end)
-{
-  // right now, just forward to the individual function.
-  for (ForwardIterator it = begin; it != end; ++it)
-    add (*it);
-}
-
-
-
 inline
 unsigned int
 CompressedSparsityPattern::n_rows () const
@@ -530,11 +518,11 @@ void
 CompressedSparsityPattern::add_entries (const unsigned int row,
 					ForwardIterator begin,
 					ForwardIterator end,
-					const bool         /*indices_are_sorted*/)
+					const bool      indices_are_sorted)
 {
   Assert (row < rows, ExcIndexRange (row, 0, rows));
 
-  lines[row].add_entries (begin, end);
+  lines[row].add_entries (begin, end, indices_are_sorted);
 }
 
 
diff --git a/deal.II/lac/source/compressed_sparsity_pattern.cc b/deal.II/lac/source/compressed_sparsity_pattern.cc
index c7bd346606..48249c7050 100644
--- a/deal.II/lac/source/compressed_sparsity_pattern.cc
+++ b/deal.II/lac/source/compressed_sparsity_pattern.cc
@@ -96,6 +96,12 @@ CompressedSparsityPattern::Line::flush_cache () const
       }
     }
 
+				   // TODO: could use the add_entries
+                                   // function of the constraint line for
+                                   // doing this, but that one is
+                                   // non-const. Still need to figure out
+                                   // how to do that.
+
                                    // next job is to merge the two
                                    // arrays. special case the case that the
                                    // original array is empty.
@@ -189,6 +195,126 @@ CompressedSparsityPattern::Line::flush_cache () const
 
 
 
+template <typename ForwardIterator>
+void
+CompressedSparsityPattern::Line::add_entries (ForwardIterator begin,
+					      ForwardIterator end,
+					      const bool indices_are_sorted)
+{
+				   // use the same code as when flushing the
+				   // cache in case we have many (more than
+				   // three) entries in a sorted
+				   // list. Otherwise, go on to the single
+				   // add() function.
+  const int n_elements = end - begin;
+  if (n_elements <= 0)
+    return;
+
+  const unsigned int n_cols = static_cast<unsigned int>(n_elements);
+  const unsigned int stop_size = entries.size() + n_cols;
+
+  if (indices_are_sorted == true)
+    {
+
+                                   // next job is to merge the two
+                                   // arrays. special case the case that the
+                                   // original array is empty.
+      if (entries.size() == 0)
+	{
+	  entries.resize (n_cols);
+	  ForwardIterator my_it = begin;
+	  for (unsigned int i=0; i<n_cols; ++i)
+	    entries[i] = *my_it++;
+	}
+      else
+	{
+                                       // first count how many of the cache
+                                       // entries are already in the main
+                                       // array, so that we can efficiently
+                                       // allocate memory
+	  unsigned int n_new_entries = 0;
+	  {
+	    unsigned int entry_position = 0;
+	    ForwardIterator my_it = begin;
+	    while ((entry_position<entries.size()) &&
+		   (my_it != end))
+	      {
+		++n_new_entries;
+		if (entries[entry_position] < *my_it)
+		  ++entry_position;
+		else if (entries[entry_position] == *my_it)
+		  {
+		    ++entry_position;
+		    ++my_it;
+		  }
+		else
+		  ++my_it;
+	      }
+
+                                         // scoop up leftovers in arrays
+	    n_new_entries += (entries.size() - entry_position) +
+	                     (end - my_it);
+	  }
+
+                                       // then allocate new memory and merge
+                                       // arrays, if there are any entries at
+                                       // all that need to be merged
+	  Assert (n_new_entries >= entries.size(),
+		  ExcInternalError());
+	  if (n_new_entries > entries.size())
+	    {
+	      std::vector<unsigned int> new_entries;
+	      new_entries.reserve (n_new_entries);
+	      ForwardIterator my_it = begin;
+	      unsigned int entry_position = 0;
+	      while ((entry_position<entries.size()) &&
+		     (my_it != end))
+		if (entries[entry_position] < *my_it)
+		  {
+		    new_entries.push_back (entries[entry_position]);
+		    ++entry_position;
+		  }
+		else if (entries[entry_position] == *my_it)
+		  {
+		    new_entries.push_back (entries[entry_position]);
+		    ++entry_position;
+		    ++my_it;
+		  }
+		else
+		  {
+		    new_entries.push_back (*my_it);
+		    ++my_it;
+		  }
+
+					   // copy remaining elements from the
+					   // array that we haven't
+					   // finished. note that at most one
+					   // of the following loops will run
+					   // at all
+	      for (; entry_position < entries.size(); ++entry_position)
+		new_entries.push_back (entries[entry_position]);
+	      for (; my_it != end; ++my_it)
+		new_entries.push_back (*my_it);
+
+	      Assert (new_entries.size() == n_new_entries,
+		      ExcInternalError());
+
+					   // finally swap old and new array,
+					   // and set cache size to zero
+	      new_entries.swap (entries);
+	    }
+	}
+      return;
+    }
+
+				   // otherwise, insert the indices one
+				   // after each other
+  for (ForwardIterator it = begin; it != end; ++it)
+    add (*it);
+}
+
+
+
 CompressedSparsityPattern::CompressedSparsityPattern ()
                 :
 		rows(0),
@@ -418,4 +544,14 @@ CompressedSparsityPattern::n_nonzero_elements () const
   return n;
 }
 
+
+// explicit instantiations
+template void CompressedSparsityPattern::Line::add_entries(unsigned int *,
+							   unsigned int *,
+							   const bool);
+template void CompressedSparsityPattern::Line::
+add_entries(std::vector<unsigned int>::iterator,
+	    std::vector<unsigned int>::iterator,
+	    const bool);
+
 DEAL_II_NAMESPACE_CLOSE
-- 
2.39.5