Global Positioning System Reference
In-Depth Information
Algorithm 4:
Compare_base
()
Input:
k
2
1
, k
2
2
.
k
2
1
= (
part
1
,win
1
)
, k
2
2
= (
part
2
,win
2
)
Output:
0 (
k
2
1
and
k
2
2
belong to the same group),
−
1 (group number of
k
2
1
<
group number of
k
2
2
), or +1 (group number
k
2
1
>
group number
of
k
2
2
)
1
:
if
(
win
1
=
−
1)
∧
(
win
2
=
−
1)
then
// basePart-basePart
2
:
if
(
part
1
=
part
2
)
then
3
: return 0
4
:
else
5
: return (
part
1
< part
2
)?
−
1 : +1
6
:
end if
7
:
else if
(
win
1
=
−
1)
∧
(
win
2
≠
−
1)
then
// basePart-winPart
8
: return -1
9
:
else if
(
win
1
≠
−
1)
∧
(
win
2
=
−
1)
then
// winPart-basePart
10
: return +1
11
:
else
// (
win
1
≠
−
1)
∧
(
win
2
≠
−
1), winPart-winPart
12
:
min
1
← min
(
part
1
,win
1
)
13
:
max
1
← max
(
part
1
,win
1
)
14
:
min
2
← min
(
part
2
,win
2
)
15
:
max
2
← max
(
part
2
,win
2
)
16
:
if
(
min
1
=
min
2
)
∧
(
max
1
=
max
2
)
then
// elements belong to the
// same window-pair
17
: return 0
18
:
else
// elements do not belong to the same window-pair
19
:
if
min
1
=
min
2
then
20
: return (
max
1
< max
2
)?
−
1 : +1
21
:
else
22
: return (
min
1
< min
2
)?
−
1 : +1
23
:
end if
24
:
end if
25
:
end if
then
keys. When both keys belong to base partitions, the algorithm orders them,
based on their pivot indices (lines 1 to 6). When one key belongs to a base
partition and the other one to a window-pair partition, the algorithm orders
them giving the base key a lower order than the window-pair key (lines 7
to 10). Finally, if both keys belong to window-pair partitions, the algorithm
orders them based on the pair (minimum pivot index, maximum pivot
index) using lexicographical order (lines 11 to 25). The
min
and
max
functions
are used to group together all the intermediate records of a window-pair
independently of the specifi c window they belong to Fig. 6b shows the order
of partitions generated by
Compare_base
for the scenario with two pivots
presented in Fig. 5. Figure 6c shows the order of partitions for the case of
a base round with three pivots.
Search WWH ::
Custom Search