10 #ifndef TPETRA_DETAILS_MERGE_HPP
11 #define TPETRA_DETAILS_MERGE_HPP
13 #include "TpetraCore_config.h"
14 #include "Teuchos_TestForException.hpp"
40 template<
class OrdinalType,
class IndexType>
43 const IndexType numCurInds,
44 const OrdinalType inputInds[],
45 const IndexType numInputInds)
47 IndexType mergeCount = 0;
49 if (numCurInds <= numInputInds) {
52 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
53 const OrdinalType inVal = inputInds[inPos];
54 for (IndexType curPos = 0; curPos < numCurInds; ++curPos) {
55 if (curInds[curPos] == inVal) {
64 for (IndexType curPos = 0; curPos < numCurInds; ++curPos) {
65 const OrdinalType curVal = curInds[curPos];
66 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
67 if (inputInds[inPos] == curVal) {
74 #ifdef HAVE_TPETRA_DEBUG
75 TEUCHOS_TEST_FOR_EXCEPTION
76 (mergeCount > numInputInds, std::logic_error,
"mergeCount = " <<
77 mergeCount <<
" > numInputInds = " << numInputInds <<
".");
78 #endif // HAVE_TPETRA_DEBUG
99 template<
class OrdinalType,
class IndexType>
102 const IndexType numCurInds,
103 const OrdinalType inputInds[],
104 const IndexType numInputInds)
109 IndexType curPos = 0;
111 IndexType mergeCount = 0;
112 while (inPos < numInputInds && curPos < numCurInds) {
113 const OrdinalType inVal = inputInds[inPos];
114 const OrdinalType curVal = curInds[curPos];
116 if (curVal == inVal) {
119 }
else if (curVal < inVal) {
126 #ifdef HAVE_TPETRA_DEBUG
127 TEUCHOS_TEST_FOR_EXCEPTION
128 (inPos > numInputInds, std::logic_error,
"inPos = " << inPos <<
129 " > numInputInds = " << numInputInds <<
".");
130 TEUCHOS_TEST_FOR_EXCEPTION
131 (curPos > numCurInds, std::logic_error,
"curPos = " << curPos <<
132 " > numCurInds = " << numCurInds <<
".");
133 TEUCHOS_TEST_FOR_EXCEPTION
134 (mergeCount > numInputInds, std::logic_error,
"mergeCount = " <<
135 mergeCount <<
" > numInputInds = " << numInputInds <<
".");
136 #endif // HAVE_TPETRA_DEBUG
171 template<
class OrdinalType,
class IndexType>
172 std::pair<bool, IndexType>
174 const IndexType midPos,
175 const IndexType endPos,
176 const OrdinalType inputInds[],
177 const IndexType numInputInds)
195 if (endPos >= numInputInds) {
197 for (IndexType k = 0; k < numInputInds; ++k) {
198 curInds[k] = inputInds[k];
200 std::sort (curInds, curInds + numInputInds);
201 return std::make_pair (
true, numInputInds);
204 return std::make_pair (
false, numInputInds);
211 const IndexType mergeCount =
212 countMergeSortedIndices<OrdinalType, IndexType> (curInds, midPos,
215 const IndexType extraSpaceNeeded = numInputInds - mergeCount;
216 const IndexType newRowLen = midPos + extraSpaceNeeded;
217 if (newRowLen > endPos) {
218 return std::make_pair (
false, newRowLen);
221 IndexType curPos = 0;
223 IndexType newPos = midPos;
224 while (inPos < numInputInds && curPos < midPos) {
225 const OrdinalType inVal = inputInds[inPos];
226 const OrdinalType curVal = curInds[curPos];
228 if (curVal == inVal) {
230 }
else if (curVal < inVal) {
235 curInds[newPos] = inVal;
243 for (; inPos < numInputInds && newPos < newRowLen; ++inPos, ++newPos) {
244 curInds[newPos] = inputInds[inPos];
247 #ifdef HAVE_TPETRA_DEBUG
248 TEUCHOS_TEST_FOR_EXCEPTION
249 (newPos != newRowLen, std::logic_error,
"mergeSortedIndices: newPos = "
250 << newPos <<
" != newRowLen = " << newRowLen <<
" = " << midPos <<
251 " + " << extraSpaceNeeded <<
". Please report this bug to the Tpetra "
253 #endif // HAVE_TPETRA_DEBUG
255 if (newPos != midPos) {
264 return std::make_pair (
true, newPos);
291 template<
class OrdinalType,
class IndexType>
292 std::pair<bool, IndexType>
294 const IndexType midPos,
295 const IndexType endPos,
296 const OrdinalType inputInds[],
297 const IndexType numInputInds)
315 if (endPos >= numInputInds) {
317 for (IndexType k = 0; k < numInputInds; ++k) {
318 curInds[k] = inputInds[k];
320 return std::make_pair (
true, numInputInds);
323 return std::make_pair (
false, numInputInds);
330 const IndexType mergeCount =
331 countMergeUnsortedIndices<OrdinalType, IndexType> (curInds, midPos,
334 const IndexType extraSpaceNeeded = numInputInds - mergeCount;
335 const IndexType newRowLen = midPos + extraSpaceNeeded;
336 if (newRowLen > endPos) {
337 return std::make_pair (
false, newRowLen);
342 IndexType newPos = midPos;
343 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
344 const OrdinalType inVal = inputInds[inPos];
346 for (IndexType curPos = 0; curPos < midPos; ++curPos) {
347 if (curInds[curPos] == inVal) {
352 curInds[newPos] = inVal;
356 return std::make_pair (
true, newPos);
385 template<
class OrdinalType,
class ValueType,
class IndexType>
386 std::pair<bool, IndexType>
389 const IndexType midPos,
390 const IndexType endPos,
391 const OrdinalType inputInds[],
392 const ValueType inputVals[],
393 const IndexType numInputInds)
411 if (endPos >= numInputInds) {
413 for (IndexType k = 0; k < numInputInds; ++k) {
414 curInds[k] = inputInds[k];
415 curVals[k] = inputVals[k];
417 return std::make_pair (
true, numInputInds);
420 return std::make_pair (
false, numInputInds);
427 const IndexType mergeCount =
428 countMergeUnsortedIndices<OrdinalType, IndexType> (curInds, midPos,
431 const IndexType extraSpaceNeeded = numInputInds - mergeCount;
432 const IndexType newRowLen = midPos + extraSpaceNeeded;
433 if (newRowLen > endPos) {
434 return std::make_pair (
false, newRowLen);
439 IndexType newPos = midPos;
440 for (IndexType inPos = 0; inPos < numInputInds; ++inPos) {
441 const OrdinalType inInd = inputInds[inPos];
443 for (IndexType curPos = 0; curPos < midPos; ++curPos) {
444 if (curInds[curPos] == inInd) {
446 curVals[curPos] += inputVals[inPos];
450 curInds[newPos] = inInd;
451 curVals[newPos] = inputVals[inPos];
455 return std::make_pair (
true, newPos);
463 #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...
void sort(View &view, const size_t &size)
Convenience wrapper for std::sort for host-accessible views.
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...