Java Reference
In-Depth Information
Better Implementation of C
ur
I
nt
During interval analysis, nodes are incorporated into increasingly larger in-
tervalsastheloopatMarker
66
considers nodes in reverse order of their
depth-first numbering.
Initially, C
ur
I
nt
(
X
)
=
X
, and throughout the algo-
rithm, C
(
X
) returns the header of the most recently processed interval
containing
X
. While C
ur
I
nt
(
X
) changes continually as the outer intervals con-
taining
X
are discovered,
X
is mapped to its
immediately
containing interval
exactly once at Marker
70
. Therefore, throughout the algorithm, the following
holds for every node
X
:
ur
I
nt
⊥
(
X
has not yet been associated with an interval)
head
(
X
)
=
W
with
dfn
(
W
)
<
dfn
(
X
)
Exponentiation
of
head
can then be defined as the number of times the
head
map is applied:
0
(
X
)
head
=
X
head
i
(
X
)
=
head
(
head
i
−1
(
X
))
head
∗
(
X
)
=
Z
such that
Z
⊥
and
head
(
Z
)
=⊥
As the algorithmdiscovers intervals that surround
X
, evaluation of C
ur
I
nt
(
X
)
takes on the sequence
seq
(
X
)
=
X
,
head
(
X
)
,
head
(
head
(
X
))
,...,
root
(
X
) always returns
head
∗
(
X
), which is evaluated based on the intervals
discovered thus far.
C
ur
I
nt
=
X
.Even-
tually,
head
(
X
) is mapped at Marker
70
to an outer interval that contains
X
.
Subsequently, that interval's header is mapped to some outer interval. This
continues until the outermost interval of the graph (
root
) is found. At any
point in the algorithm's execution, the method C
Initially,
head
(
X
)
= ⊥
yielding C
ur
I
nt
(
X
)
ur
I
nt
(
X
) returns the current
value of
head
∗
(
X
).
For example, consider node 4 from Figure 14.32.
Initially,
seq
(4)
=
4
=
C
( 4 ). The next change occurs when node 4 is mapped to header 2, at
which point
ur
I
nt
seq
(4)
=
4
,
2
=
C
ur
I
nt
( 4 ). When the outer loop is processed,
seq
(
X
)
=
4
,
2
,
1
=
C
ur
I
nt
( 4 ). Finally the outermost interval headed by
root
is
processed so that
seq
(
X
)
=
4
,
2
,
1
,
0
=
C
ur
I
nt
(4).
(
X
) in Figure 14.35 visits every node
in
seq
(
X
) to reach its ultimate element, even though this sequence grows only
at its end. The more e
The naive implementation of C
ur
I
nt
cient implementation shown in Figure 14.38 uses
path
compression
to decrease the number of nodes that must be visited on average
