root / synthbench / euroben-dm / mod2i / .svn / text-base / i_merge.f.svn-base @ 0:839f52ef7657
History | View | Annotate | Download (2.8 kB)
| 1 |
Subroutine i_merge( np, nodes, mx, keys, irnkl, itabl, itabr ) |
|---|---|
| 2 |
! -------------------------------------------------------------------- |
| 3 |
Implicit None |
| 4 |
|
| 5 |
Integer :: np, nodes, irnkl(np),itabl (nodes+1),itabr (nodes) |
| 6 |
Integer :: mx, keys(mx) |
| 7 |
|
| 8 |
Integer :: ik, itabk(nodes) |
| 9 |
Integer :: i, j, k, il, ir, ij, irnkj(nodes), jprocs |
| 10 |
Integer :: w(np) |
| 11 |
! -------------------------------------------------------------------- |
| 12 |
! Make sure that the indices have base 1. |
| 13 |
|
| 14 |
If ( itabl(1) /= 1) Then |
| 15 |
Do i = nodes+1, 1, -1 |
| 16 |
itabl(i) = itabl(i) - itabl(1) + 1 |
| 17 |
End Do |
| 18 |
End If |
| 19 |
|
| 20 |
Do i = 1, nodes |
| 21 |
itabr(i) = itabl(i+1) - 1 |
| 22 |
End Do |
| 23 |
|
| 24 |
Do j = 1,nodes |
| 25 |
itabk(j) = keys(itabl(j)) |
| 26 |
irnkj(j) = j |
| 27 |
End Do |
| 28 |
! -------------------------------------------------------------------- |
| 29 |
! Check for empty segments and remove them. |
| 30 |
|
| 31 |
jprocs = nodes |
| 32 |
i = 1 |
| 33 |
Do j = 1, nodes |
| 34 |
If ( itabl(irnkj(i)) > itabr(irnkj(i))) Then |
| 35 |
jprocs = jprocs - 1 |
| 36 |
Do k = i, jprocs |
| 37 |
irnkj(k) = irnkj(k+1) |
| 38 |
End Do |
| 39 |
Else |
| 40 |
i = i + 1 |
| 41 |
End If |
| 42 |
End Do |
| 43 |
|
| 44 |
! -------------------------------------------------------------------- |
| 45 |
! Sort the proc-way merging table: |
| 46 |
|
| 47 |
Do j = 2, jprocs |
| 48 |
|
| 49 |
! --- Consider each of the original elements in turn. |
| 50 |
|
| 51 |
ij = irnkj(j) |
| 52 |
ik = itabk(ij) |
| 53 |
|
| 54 |
! --- And look for a place to insert it; The slot "j" is now empty. |
| 55 |
|
| 56 |
Do i = j-1, 1, -1 |
| 57 |
If ( itabk(irnkj(i)) <= ik ) Go To 10 |
| 58 |
irnkj(i+1) = irnkj(i) |
| 59 |
End Do |
| 60 |
i = 0 |
| 61 |
10 Continue |
| 62 |
irnkj(i+1) = ij |
| 63 |
End Do |
| 64 |
! -------------------------------------------------------------------- |
| 65 |
! The merging table is now in sorted order. |
| 66 |
! proceed with the merge. |
| 67 |
|
| 68 |
Do i = 1, np |
| 69 |
|
| 70 |
! --- Remove the smallest element from the merging list. |
| 71 |
ij = irnkj(1) |
| 72 |
|
| 73 |
! --- Refresh the merge table. |
| 74 |
|
| 75 |
il = itabl(ij) + 1 |
| 76 |
ir = itabr(ij) |
| 77 |
ik = keys(il) |
| 78 |
itabk(ij) = ik |
| 79 |
itabl(ij) = il |
| 80 |
irnkl(il-1) = i |
| 81 |
|
| 82 |
! --- Pick out each element in turn; The first slot is now empty. |
| 83 |
|
| 84 |
If ( ir >= il ) Then ! --- Look for slot to insert new data. |
| 85 |
Do j = 1, jprocs-1 |
| 86 |
If ( itabk(irnkj(j+1)) >= ik ) Go To 20 |
| 87 |
irnkj(j) = irnkj(j+1) |
| 88 |
End Do |
| 89 |
j = jprocs |
| 90 |
20 Continue |
| 91 |
irnkj(j) = ij |
| 92 |
Else ! --- Retire a slot |
| 93 |
jprocs = jprocs-1 |
| 94 |
Do j = 1, jprocs |
| 95 |
irnkj(j) = irnkj(j+1) |
| 96 |
End Do |
| 97 |
End If |
| 98 |
End Do |
| 99 |
Do i = 1, np |
| 100 |
w(irnkl(i)) = keys(i) |
| 101 |
End Do |
| 102 |
keys(1:np) = w(1:np) |
| 103 |
! -------------------------------------------------------------------- |
| 104 |
End Subroutine i_merge |