HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

What does up arrow ($\uparrow$) mean in pseudocode?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
uparrowpseudocodearrowwhatmeandoes

Problem

I'm learning vantage point trees, and I met this while reading the paper Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces by Peter Yianilos (Proceedings of SODA 1993, SIAM, pages 311–321; PDF). The following pseudocode appears in Algorithm 1.

$$\begin{align*}
\hspace{2em}&\hspace{-2em}
\textbf{function}\text{ Make_vp_tree(}S\text{)}\\
&\textbf{if }S=\emptyset\textbf{ then return }\emptyset\\
&\text{new(node);}\\
&\text{node}\!\uparrow\!\!\text{.p} := \text{Select_vp(}S\text{);}\\
&\text{node}\!\uparrow\!\!\text{.mu} := \text{Median}_{s\in S}\, d(p,s);\\
&\dotsc
\end{align*}$$

node is a node of vp-tree, so I know what node.p means, but what do that up arrow means in this context?

Solution

The algorithms in the paper you link to are described in a notation quite similar to Pascal, a language that treats pointers in a very particular way. In Pascal, pointers are declared as references to values of specific types (a pointer to an integer can never refer to a boolean, for instance).

The upward arrow, in the example you reproduce, is a dereferencing operator. Clearly, node is a pointer to a value of a record type (not a record itself), of which p and mu are fields, so node.p has no meaning.

Check out this similar question for further clarification.

Context

StackExchange Computer Science Q#51277, answer score: 14

Revisions (0)

No revisions yet.