Java Reference
In-Depth Information
/
Initially, soln(X)=X
/
function
C
ur
I
nt
(
X
)
returns
node
call
compress
(
X
)
76
return
(
soln
(
X
))
end
77
procedure
compress
(
X
)
if
head
(
soln
(
X
))
⊥
78
then
if
soln
(
X
)
=
X
then
SameSoln
←
head
(
X
)
else
79
SameSoln
←
soln
(
X
)
80
call
compress
(
SameSoln
)
81
soln
(
X
)
←
soln
(
SameSoln
)
82
end
Figure 14.38: Better implementation of C
ur
I
nt
.
to evaluate C
ur
I
nt
(
X
). For each node
X
,
soln
(
X
) is the most recently computed
value of C
at Marker
76
is responsible for
updating
soln
(
X
)incase
seq
(
X
) has been extended since the last evaluation.
The
ur
I
nt
(
X
). The call to
compress
method not only updates
soln
(
X
), it also updates
soln
(
Z
)ateach
node
Z
that must be visited to compute
soln
(
X
). Because such nodes are visited
anyway for computing
soln
(
X
), the extra updates are (asymptotically) free and
they can save time later should
soln
(
Z
)berequired.
Based on the above definitions,
compress
soln
(
X
) should return the last element
of
seq
(
X
)whenC
ur
I
nt
(
X
) is called. The staleness of
soln
(
X
)istestedat
Marker
78
. f
head
(
soln
(
X
))
=
seq
(
X
) and the solution is
current. Otherwise, a solution is recursively demanded by observing:
= ⊥
,then
soln
(
X
)
soln
(
soln
(
X
))
X
soln
(
head
(
X
)) otherwise
if
soln
(
X
)
soln
(
X
)
=
In other words, if
soln
(
X
) was previously
Y
X
,thenC
(
Y
)
and the solution at
X
can be computed once the solution at
Y
is available. On
the other hand, if
soln
(
X
)
ur
I
nt
(
X
)
=
C
ur
I
nt
=
X
, then the solution at
X
shouldbethesameas
the solution at
head
(
X
). The proper choice is made at Markers
79
and
80
by
assigning the variable
SameSoln
. Compression is then requested for
SameSoln
at Marker
81
. This solution is used at Marker
82
to update
soln
(
X
). Because
C
ur
I
nt
is recursive, the update at Marker
82
is applied to all nodes for which
C
ur
I
nt
was called on behalf of
X
.
