42 #ifndef TPETRA_DETAILS_MERGE_HPP
43 #define TPETRA_DETAILS_MERGE_HPP
45 #include "TpetraCore_config.h"
46 #include "Teuchos_TestForException.hpp"
72 template<
class OrdinalType,
class IndexType>
75 const IndexType numCurInds,
76 const OrdinalType inputInds[],
77 const IndexType numInputInds)
79 IndexType mergeCount = 0;
81 if (numCurInds <= numInputInds) {
84 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
85 const OrdinalType inVal = inputInds[inPos];
86 for (IndexType curPos = 0; curPos < numCurInds; ++curPos) {
87 if (curInds[curPos] == inVal) {
96 for (IndexType curPos = 0; curPos < numCurInds; ++curPos) {
97 const OrdinalType curVal = curInds[curPos];
98 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
99 if (inputInds[inPos] == curVal) {
106 #ifdef HAVE_TPETRA_DEBUG
107 TEUCHOS_TEST_FOR_EXCEPTION
108 (mergeCount > numInputInds, std::logic_error,
"mergeCount = " <<
109 mergeCount <<
" > numInputInds = " << numInputInds <<
".");
110 #endif // HAVE_TPETRA_DEBUG
131 template<
class OrdinalType,
class IndexType>
134 const IndexType numCurInds,
135 const OrdinalType inputInds[],
136 const IndexType numInputInds)
141 IndexType curPos = 0;
143 IndexType mergeCount = 0;
144 while (inPos < numInputInds && curPos < numCurInds) {
145 const OrdinalType inVal = inputInds[inPos];
146 const OrdinalType curVal = curInds[curPos];
148 if (curVal == inVal) {
151 }
else if (curVal < inVal) {
158 #ifdef HAVE_TPETRA_DEBUG
159 TEUCHOS_TEST_FOR_EXCEPTION
160 (inPos > numInputInds, std::logic_error,
"inPos = " << inPos <<
161 " > numInputInds = " << numInputInds <<
".");
162 TEUCHOS_TEST_FOR_EXCEPTION
163 (curPos > numCurInds, std::logic_error,
"curPos = " << curPos <<
164 " > numCurInds = " << numCurInds <<
".");
165 TEUCHOS_TEST_FOR_EXCEPTION
166 (mergeCount > numInputInds, std::logic_error,
"mergeCount = " <<
167 mergeCount <<
" > numInputInds = " << numInputInds <<
".");
168 #endif // HAVE_TPETRA_DEBUG
203 template<
class OrdinalType,
class IndexType>
204 std::pair<bool, IndexType>
206 const IndexType midPos,
207 const IndexType endPos,
208 const OrdinalType inputInds[],
209 const IndexType numInputInds)
227 if (endPos >= numInputInds) {
229 for (IndexType k = 0; k < numInputInds; ++k) {
230 curInds[k] = inputInds[k];
232 std::sort (curInds, curInds + numInputInds);
233 return std::make_pair (
true, numInputInds);
236 return std::make_pair (
false, numInputInds);
243 const IndexType mergeCount =
244 countMergeSortedIndices<OrdinalType, IndexType> (curInds, midPos,
247 const IndexType extraSpaceNeeded = numInputInds - mergeCount;
248 const IndexType newRowLen = midPos + extraSpaceNeeded;
249 if (newRowLen > endPos) {
250 return std::make_pair (
false, newRowLen);
253 IndexType curPos = 0;
255 IndexType newPos = midPos;
256 while (inPos < numInputInds && curPos < midPos) {
257 const OrdinalType inVal = inputInds[inPos];
258 const OrdinalType curVal = curInds[curPos];
260 if (curVal == inVal) {
262 }
else if (curVal < inVal) {
267 curInds[newPos] = inVal;
275 for (; inPos < numInputInds && newPos < newRowLen; ++inPos, ++newPos) {
276 curInds[newPos] = inputInds[inPos];
279 #ifdef HAVE_TPETRA_DEBUG
280 TEUCHOS_TEST_FOR_EXCEPTION
281 (newPos != newRowLen, std::logic_error,
"mergeSortedIndices: newPos = "
282 << newPos <<
" != newRowLen = " << newRowLen <<
" = " << midPos <<
283 " + " << extraSpaceNeeded <<
". Please report this bug to the Tpetra "
285 #endif // HAVE_TPETRA_DEBUG
287 if (newPos != midPos) {
294 std::sort (curInds, curInds + newPos);
296 return std::make_pair (
true, newPos);
323 template<
class OrdinalType,
class IndexType>
324 std::pair<bool, IndexType>
326 const IndexType midPos,
327 const IndexType endPos,
328 const OrdinalType inputInds[],
329 const IndexType numInputInds)
347 if (endPos >= numInputInds) {
349 for (IndexType k = 0; k < numInputInds; ++k) {
350 curInds[k] = inputInds[k];
352 return std::make_pair (
true, numInputInds);
355 return std::make_pair (
false, numInputInds);
362 const IndexType mergeCount =
363 countMergeUnsortedIndices<OrdinalType, IndexType> (curInds, midPos,
366 const IndexType extraSpaceNeeded = numInputInds - mergeCount;
367 const IndexType newRowLen = midPos + extraSpaceNeeded;
368 if (newRowLen > endPos) {
369 return std::make_pair (
false, newRowLen);
374 IndexType newPos = midPos;
375 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
376 const OrdinalType inVal = inputInds[inPos];
378 for (IndexType curPos = 0; curPos < midPos; ++curPos) {
379 if (curInds[curPos] == inVal) {
384 curInds[newPos] = inVal;
388 return std::make_pair (
true, newPos);
417 template<
class OrdinalType,
class ValueType,
class IndexType>
418 std::pair<bool, IndexType>
421 const IndexType midPos,
422 const IndexType endPos,
423 const OrdinalType inputInds[],
424 const ValueType inputVals[],
425 const IndexType numInputInds)
443 if (endPos >= numInputInds) {
445 for (IndexType k = 0; k < numInputInds; ++k) {
446 curInds[k] = inputInds[k];
447 curVals[k] = inputVals[k];
449 return std::make_pair (
true, numInputInds);
452 return std::make_pair (
false, numInputInds);
459 const IndexType mergeCount =
460 countMergeUnsortedIndices<OrdinalType, IndexType> (curInds, midPos,
463 const IndexType extraSpaceNeeded = numInputInds - mergeCount;
464 const IndexType newRowLen = midPos + extraSpaceNeeded;
465 if (newRowLen > endPos) {
466 return std::make_pair (
false, newRowLen);
471 IndexType newPos = midPos;
472 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
473 const OrdinalType inInd = inputInds[inPos];
475 for (IndexType curPos = 0; curPos < midPos; ++curPos) {
476 if (curInds[curPos] == inInd) {
478 curVals[curPos] += inputVals[inPos];
482 curInds[newPos] = inInd;
483 curVals[newPos] = inputVals[inPos];
487 return std::make_pair (
true, newPos);
495 #endif // TPETRA_DETAILS_MERGE_HPP
std::pair< bool, IndexType > mergeUnsortedIndicesAndValues(OrdinalType curInds[], ValueType curVals[], const IndexType midPos, const IndexType endPos, const OrdinalType inputInds[], const ValueType inputVals[], const IndexType numInputInds)
Attempt to merge the input indices and values into the current row's column indices and corresponding...
std::pair< bool, IndexType > mergeSortedIndices(OrdinalType curInds[], const IndexType midPos, const IndexType endPos, const OrdinalType inputInds[], const IndexType numInputInds)
Attempt to merge the input indices into the current row's column indices, assuming that both the curr...
IndexType countMergeUnsortedIndices(const OrdinalType curInds[], const IndexType numCurInds, const OrdinalType inputInds[], const IndexType numInputInds)
Count the number of column indices that can be merged into the current row, assuming that both the cu...
IndexType countMergeSortedIndices(const OrdinalType curInds[], const IndexType numCurInds, const OrdinalType inputInds[], const IndexType numInputInds)
Count the number of column indices that can be merged into the current row, assuming that both the cu...
std::pair< bool, IndexType > mergeUnsortedIndices(OrdinalType curInds[], const IndexType midPos, const IndexType endPos, const OrdinalType inputInds[], const IndexType numInputInds)
Attempt to merge the input indices into the current row's column indices, assuming that both the curr...