Can You Explain How Tarjan's Pseudocode Works to Someone Familiar with C or Java?
$begingroup$
The Short Story
A famous computer scientist Tarjan wrote a book years ago. It contains absolutely bizarre pseudo-code. Would someone please explain it?
The Long Story #
Tarjan is known for many acomplishments, including the fact that he was co-inventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.
All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:
Dijkstra's Guarded Command Language
SETL
ALGOL
I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.
An example of a function written in Tarjan's language is shown below:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2) fi;
if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;
rank (h1) := rank(right(h1)) + 1;
return h1,
end mesh;
I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, Matlab and many others.
programming-languages
New contributor
$endgroup$
add a comment |
$begingroup$
The Short Story
A famous computer scientist Tarjan wrote a book years ago. It contains absolutely bizarre pseudo-code. Would someone please explain it?
The Long Story #
Tarjan is known for many acomplishments, including the fact that he was co-inventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.
All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:
Dijkstra's Guarded Command Language
SETL
ALGOL
I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.
An example of a function written in Tarjan's language is shown below:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2) fi;
if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;
rank (h1) := rank(right(h1)) + 1;
return h1,
end mesh;
I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, Matlab and many others.
programming-languages
New contributor
$endgroup$
add a comment |
$begingroup$
The Short Story
A famous computer scientist Tarjan wrote a book years ago. It contains absolutely bizarre pseudo-code. Would someone please explain it?
The Long Story #
Tarjan is known for many acomplishments, including the fact that he was co-inventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.
All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:
Dijkstra's Guarded Command Language
SETL
ALGOL
I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.
An example of a function written in Tarjan's language is shown below:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2) fi;
if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;
rank (h1) := rank(right(h1)) + 1;
return h1,
end mesh;
I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, Matlab and many others.
programming-languages
New contributor
$endgroup$
The Short Story
A famous computer scientist Tarjan wrote a book years ago. It contains absolutely bizarre pseudo-code. Would someone please explain it?
The Long Story #
Tarjan is known for many acomplishments, including the fact that he was co-inventor of splay trees. He published a book, "Data Structures and Network Algorithms," during the 1980s.
All of the pseudo-code in Tarjan's book is written in a language of his own devising. The pseudo-code conventions are very regimented. It's almost a true language, and one could imagine writing a compiler for it. Tarjan writes that his language is based upon the following three:
Dijkstra's Guarded Command Language
SETL
ALGOL
I am hoping that someone familiar with one or two of the above languages, or the work of Tarjan, will be able to answer my question.
An example of a function written in Tarjan's language is shown below:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2) fi;
if rank (left (h1)) < rank (right (h1)) → left(h1) ⟷ right(h1) fi;
rank (h1) := rank(right(h1)) + 1;
return h1,
end mesh;
I have seen lots of pseudo-code, but I have never seen anything like Tarjan's. How does Tarjan's pseudocode work? How can examples of Tarjan's pseudocode be re-written as something which looks more like C or Java? It need not even be C or Java. The if-else construct in Tarjan's language is not only different from C-family languages, but also different from Python, Matlab and many others.
programming-languages
programming-languages
New contributor
New contributor
New contributor
asked 2 hours ago
Sam MuldoonSam Muldoon
313
313
New contributor
New contributor
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Table of Contents #
I will divide my explanation of Tarjan's pseudocode into the following sections:
(1) Tarjan's If-else Blocks (the ->
& |
operators)
(2) Assignment and Equality Tests (:=
and =
)
(3) There is else if
, but no else
construct
(4) Tarjan's Conditional Assignment Operator := if
(4.5) Tarjan Arrays (or Lists)
(5) Additional Examples of Tarjan's if
and := if
(6) Summary of Operators
(7) Tarjan's Double-pointed Arrow Operator (⟷
)
**(8) Tarjan's do-loops are like C/Java while-loops **
**(9) Tarjan's Conditional-assignment operator with all false conditions **
1) Tarjan's If-else Blocks #
(the operators →
and |
)
The if-else
construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator ->
(or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.
For example, in Tarjan's language we might have:
# Example One
if a = 4 → x := 9 fi
If we partially translate the line of Tarjan code above into C or Java, we get the following:
if (a = 4)
x := 9
fi
Instead of a right curly braces (as in C and Java) Tarjan ends an if
-block with a backwards spelling of the key-word: fi
If we continue translating our above example, we get:
if (a = 4) {
x := 9
}
(2) Assignment and Equality Tests (:=
and =
)#
Tarjan uses =
for equality tests, not assignments.
Tarjan's =
is like Java ==
Tarjan uses :=
for assignment.
Tarjan's :=
is like Java =
Thus, if we continue translating our example, we have:
if (a == 4) {
x = 9
}
A vertical bar (or "pipe" or |
) in Tarjan's language is equivalent to the else if
keyword in C or Java.
For example, in Tarjan's language we might have:
# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi
The Tarjan-code above translates to:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
(3) else if
only and no else
construct
Earlier, I covered the basics of if
-statements without describing the nuances. However, we will not discuss a small detail. The last clause in a Tarjan-ian if-else
block must always contain an arrow (→
) operator. As such, there is no else
in Tarjan's language, only else if
. The closest thing to an else
-block in Tarjan's language is to make the rightmost test-condition true
.
if a = 4 → x := 9 | a > 4 → y := 11 | true → z := 99 fi
In C/Java, we would have:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
else { // else if (true)
z = 99
}
Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:
if condition
→ stuff to do
| condition
→ stuff to do
[...]
| condition
→ stuff to do
fi
The character |
is like if else
The character →
separates the test-condition from the stuff-to-do.
(4) Tarjan's Conditional Assignment Operator := if
#
Tarjan's if
can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if
. Somewhat confusingly, Tarjan still uses the notation/syntax if
for the second type of if
-construct. Which if
is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if
is always pre-fixed by an assignment operator.
For example, we might have the following Tarjan code:
# Example Three
x := if a = 4 → 9 fi
Begin Digression###
After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:
x := if (a = 4) → 9 fi
a = 4
is not an assignment operation. a = 4
is like a == 4
-- it returns true or false.
End Digression###
It can help to think of := if
as syntax for a single operator, distinct from :=
and if
In fact, we will refer to the := if
operator as the "conditional assignment" operator.
For if
we list (condition → action)
. For := if
we list (condition → value)
where value
is teh right-hand-side value we might assign to the left-hand-side lhs
# Tarjan Example Four
lhs := if (a = 4) → rhs fi
in C or Java might look like:
# Example Four
if (a == 4) {
lhs = rhs
}
Consider the following example of "conditional assignment" in Tarjanian code:
# Tarjan Instantiation of Example Five
x := a = 4 → 9 | a > 4 → 11 | true → 99 fi
In C/Java, we would have:
// C/Java Instantiation of Example Five
if (a == 4) {
x = 9
}
else if (a > 4) {
x = 11
}
else if (true) { // else
x = 99
}
(5) Summary of Operators:
So far, we have:
:=
...... Assignment operator (C/Java=
)=
...... Equality test (C/Java==
)→
...... Delimiter between test-condition of an if-block and the body of an if-block|
..... C/Java else-ifif ... fi
..... if-else block:= if... fi
..... Conditional assignment based on an if-else block
(5.5) Tarjan Lists/Arrays:
Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else
statements.
list1 := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3 := ["a", "b", "c", "d"];
list4 := [ ]; # an empty array
Tarjan array elementa are accessed with parentheses ()
, not square-brackets
Indexing begins at 1
. Thus,
list3 := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true
Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]
nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]
The equality operator is defined for arrays. The following code prints true
x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)
Tarjan's way to test if an array is empty is to compare it to an empty array
arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment
One can create a view (not copy) of a sub-array, by providing multiple indices to operator ()
combined with ..
list3 := ["a", "b", "c", "d"]
beg := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"
end := list3(3..)
# end == ["c", "d"]
# end(1) == "c"
mid := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"
# `list3(4)` is valid, but `mid(4)` is not
(6) Additional Examples of Tarjan's if
and := if
#
The following is another examples of an Tarjan conditional assignment (:= if
):
# Tarjan Example Six
a := (false --> a | true --> b | false --> c1 + c2 | (2 + 3 < 99) --> d)
(true --> b)
is the leftmost (cond --> action)
clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b
Below is our most complicated example of Tarjan code thus far:
# Tarjan Example -- merge two sorted lists
list function merge (list s, t);
return if s = --> t
| t = [ ] --> s
| s != [ ] and t != and s(l) <= t(1) -->
[s(1)]& merge(s[2..], t)
| s != [ ]and t != [ ] and s(1) > r(l) -->
[t(1)] & merge (s,t(2..))
fi
end merge;
The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.
list merge (list s, list t) {
if (s is empty) {
return t;
}
else if (t is empty){
return s;
}
else if (s[1] <= t[1]) {
return CONCATENATE([s[1]], merge(s[2...], t));
else { // else if (s[1] > t[1])
return CONCATENATE ([t[1]], merge(s,t[2..]);
}
}
Below is yet another example of Tarjan-code and a translation in something similar to C or Java:
heap function meld (heap h1, h2);
return if h1 = null --> h2
| h2 = null --> h1
| h1 not null and h2 not null --> mesh (h1, h2)
fi
end meld;
Below is the C/Java translation:
HeapNode meld (HeapNode h1, HeapNode h2) {
if (h1 == null) {
return h2;
}
else if (h2 == null) {
return h1;
} else {
mesh(h1, h2)
}
} // end function
(7) Tarjan's Double-pointed Arrow Operator (<-->
)#
Below is an example of Tarjan code:
x <--> y
What Does a Double Arrow (⟷
) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<-->
is a swap operation. The following prints true
x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true
After performing x <--> y
, x
points to the object which y
used to point to and y
points to the object which x
used to point to.
Below is a Tarjan statement using the <-->
operator:
x := [1, 2, 3]
y := [4, 5, 6]
x <--> y
Below is a translation from the Tarjan code above to alternative pseudocode:
Pointer X = address of array [1, 2, 3];
Pointer Y = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;
Alternatively, we could have:
void operator_double_arrow(Array** lhs, Array** rhs) {
// swap lhs and rhs
int** old_lhs = 0;
old_lhs = lhs;
*lhs = *rhs;
*rhs = *old_lhs;
return;
}
int main() {
Array* lhs = new Array<int>(1, 2, 3);
Array* rhs = new Array<int>(4, 5, 6);
operator_double_arrow(&lhs, &rhs);
delete lhs;
delete rhs;
return 0;
}
Below is an example of one of Tarjan's functions using the ⟷
operator:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2)
fi;
if rank (left (h1)) < rank (right (h1))
→ left(h1) ⟷ right(h1)
fi;
rank (h1) := rank(right(h1)) + 1;
return h1;
end mesh;
Below is a translation of Tarjan's mesh
function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷
operator works.
node pointer function mesh(node pointers h1, h2) {
if (h1.key) > h2.key) {
// swap h1 and h2
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
// Now, h2.key <= h1.key
if (h1.right == null) {
h1.right = h2;
} else // h1.key != null {
h1.right = mesh(h1.right, h2);
}
if (h1.left.rank < h1.right.rank ) {
// swap h1.left and h1.right
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
h1.rank = h1.right.rank + 1;
return h1;
}
(8) Tarjan's do-loops are like C/Java while-loops #
Tarjan's language if
and for
constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do
. All do
-loops end with the keyword od
, which is the backwards spelling of do
. Below is an example:
sum := 0
do sum < 50 → sum := sum + 1
In C-style pseudocode, we have:
sum = 0;
while(sum < 50) {
sum = sum + 1;
}
The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true)
with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
// This `continue` statement is questionable
}
break;
}
Below, we have a more complicated Tarjan do
-loop:
sum := 0
do sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5
C/Java-style pseudocode for the complicated Tarjan do
-loop is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
}
else if (sum < 99) {
sum = sum + 5;
continue;
}
break;
}
(9) Tarjan's Conditional-assignment operator with all false conditions
Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.
Notably, when the conditional assignment operator := if
is used, and no condition is true, I am not what value is assigned to the variable.
x := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi
I am not sure, but it is possible that no assignment is made to x
:
x = 0;
if (false) {
x = 1;
}
else if (false) {
x = 2;
}
else if (99 < 2) {
x = 3;
}
// At this point (x == 0)
You could require that the left-hand-side variable seen in an := if
statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.
Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null
value, and store null
in the left-hand argument of the assignment.
New contributor
$endgroup$
add a comment |
$begingroup$
Never seen this before but I think I can infer what's meant from context.. Presumably the ⟷
must be a swap operation, and if G1 -> S1 | G2 - >S2 | ... fi
is an if/then/else-type construct that also returns a value, like the ternary ?:
operator in C and Java.
With that in hand we could write the above function in a Java-like language like so:
HeapNode mesh(HeapNode h1, HeapNode h2)
{
if(h1.key > h2.key)
{
// swap h1 and h2
HeapNode t = h1;
h1 = h2;
h2 = t;
}
// One of the two cases has to hold in this case so we won't get to the
// exception, but it'd be an exception if none of the cases were satisified
// since this needs to return *something*.
h1.right = (h1.right == null) ? h2
: (h1.right != null) ? mesh(h1.right, h2)
: throw new Exception();
if(h1.left.rank < h1.right.rank)
{
// swap h1.left and h1.right
HeapNode t = h1.left;
h1.left = h1.right;
h1.right = t;
}
h1.rank = h1.right.rank + 1;
return h1;
}
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103816%2fcan-you-explain-how-tarjans-pseudocode-works-to-someone-familiar-with-c-or-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Table of Contents #
I will divide my explanation of Tarjan's pseudocode into the following sections:
(1) Tarjan's If-else Blocks (the ->
& |
operators)
(2) Assignment and Equality Tests (:=
and =
)
(3) There is else if
, but no else
construct
(4) Tarjan's Conditional Assignment Operator := if
(4.5) Tarjan Arrays (or Lists)
(5) Additional Examples of Tarjan's if
and := if
(6) Summary of Operators
(7) Tarjan's Double-pointed Arrow Operator (⟷
)
**(8) Tarjan's do-loops are like C/Java while-loops **
**(9) Tarjan's Conditional-assignment operator with all false conditions **
1) Tarjan's If-else Blocks #
(the operators →
and |
)
The if-else
construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator ->
(or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.
For example, in Tarjan's language we might have:
# Example One
if a = 4 → x := 9 fi
If we partially translate the line of Tarjan code above into C or Java, we get the following:
if (a = 4)
x := 9
fi
Instead of a right curly braces (as in C and Java) Tarjan ends an if
-block with a backwards spelling of the key-word: fi
If we continue translating our above example, we get:
if (a = 4) {
x := 9
}
(2) Assignment and Equality Tests (:=
and =
)#
Tarjan uses =
for equality tests, not assignments.
Tarjan's =
is like Java ==
Tarjan uses :=
for assignment.
Tarjan's :=
is like Java =
Thus, if we continue translating our example, we have:
if (a == 4) {
x = 9
}
A vertical bar (or "pipe" or |
) in Tarjan's language is equivalent to the else if
keyword in C or Java.
For example, in Tarjan's language we might have:
# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi
The Tarjan-code above translates to:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
(3) else if
only and no else
construct
Earlier, I covered the basics of if
-statements without describing the nuances. However, we will not discuss a small detail. The last clause in a Tarjan-ian if-else
block must always contain an arrow (→
) operator. As such, there is no else
in Tarjan's language, only else if
. The closest thing to an else
-block in Tarjan's language is to make the rightmost test-condition true
.
if a = 4 → x := 9 | a > 4 → y := 11 | true → z := 99 fi
In C/Java, we would have:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
else { // else if (true)
z = 99
}
Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:
if condition
→ stuff to do
| condition
→ stuff to do
[...]
| condition
→ stuff to do
fi
The character |
is like if else
The character →
separates the test-condition from the stuff-to-do.
(4) Tarjan's Conditional Assignment Operator := if
#
Tarjan's if
can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if
. Somewhat confusingly, Tarjan still uses the notation/syntax if
for the second type of if
-construct. Which if
is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if
is always pre-fixed by an assignment operator.
For example, we might have the following Tarjan code:
# Example Three
x := if a = 4 → 9 fi
Begin Digression###
After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:
x := if (a = 4) → 9 fi
a = 4
is not an assignment operation. a = 4
is like a == 4
-- it returns true or false.
End Digression###
It can help to think of := if
as syntax for a single operator, distinct from :=
and if
In fact, we will refer to the := if
operator as the "conditional assignment" operator.
For if
we list (condition → action)
. For := if
we list (condition → value)
where value
is teh right-hand-side value we might assign to the left-hand-side lhs
# Tarjan Example Four
lhs := if (a = 4) → rhs fi
in C or Java might look like:
# Example Four
if (a == 4) {
lhs = rhs
}
Consider the following example of "conditional assignment" in Tarjanian code:
# Tarjan Instantiation of Example Five
x := a = 4 → 9 | a > 4 → 11 | true → 99 fi
In C/Java, we would have:
// C/Java Instantiation of Example Five
if (a == 4) {
x = 9
}
else if (a > 4) {
x = 11
}
else if (true) { // else
x = 99
}
(5) Summary of Operators:
So far, we have:
:=
...... Assignment operator (C/Java=
)=
...... Equality test (C/Java==
)→
...... Delimiter between test-condition of an if-block and the body of an if-block|
..... C/Java else-ifif ... fi
..... if-else block:= if... fi
..... Conditional assignment based on an if-else block
(5.5) Tarjan Lists/Arrays:
Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else
statements.
list1 := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3 := ["a", "b", "c", "d"];
list4 := [ ]; # an empty array
Tarjan array elementa are accessed with parentheses ()
, not square-brackets
Indexing begins at 1
. Thus,
list3 := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true
Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]
nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]
The equality operator is defined for arrays. The following code prints true
x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)
Tarjan's way to test if an array is empty is to compare it to an empty array
arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment
One can create a view (not copy) of a sub-array, by providing multiple indices to operator ()
combined with ..
list3 := ["a", "b", "c", "d"]
beg := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"
end := list3(3..)
# end == ["c", "d"]
# end(1) == "c"
mid := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"
# `list3(4)` is valid, but `mid(4)` is not
(6) Additional Examples of Tarjan's if
and := if
#
The following is another examples of an Tarjan conditional assignment (:= if
):
# Tarjan Example Six
a := (false --> a | true --> b | false --> c1 + c2 | (2 + 3 < 99) --> d)
(true --> b)
is the leftmost (cond --> action)
clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b
Below is our most complicated example of Tarjan code thus far:
# Tarjan Example -- merge two sorted lists
list function merge (list s, t);
return if s = --> t
| t = [ ] --> s
| s != [ ] and t != and s(l) <= t(1) -->
[s(1)]& merge(s[2..], t)
| s != [ ]and t != [ ] and s(1) > r(l) -->
[t(1)] & merge (s,t(2..))
fi
end merge;
The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.
list merge (list s, list t) {
if (s is empty) {
return t;
}
else if (t is empty){
return s;
}
else if (s[1] <= t[1]) {
return CONCATENATE([s[1]], merge(s[2...], t));
else { // else if (s[1] > t[1])
return CONCATENATE ([t[1]], merge(s,t[2..]);
}
}
Below is yet another example of Tarjan-code and a translation in something similar to C or Java:
heap function meld (heap h1, h2);
return if h1 = null --> h2
| h2 = null --> h1
| h1 not null and h2 not null --> mesh (h1, h2)
fi
end meld;
Below is the C/Java translation:
HeapNode meld (HeapNode h1, HeapNode h2) {
if (h1 == null) {
return h2;
}
else if (h2 == null) {
return h1;
} else {
mesh(h1, h2)
}
} // end function
(7) Tarjan's Double-pointed Arrow Operator (<-->
)#
Below is an example of Tarjan code:
x <--> y
What Does a Double Arrow (⟷
) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<-->
is a swap operation. The following prints true
x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true
After performing x <--> y
, x
points to the object which y
used to point to and y
points to the object which x
used to point to.
Below is a Tarjan statement using the <-->
operator:
x := [1, 2, 3]
y := [4, 5, 6]
x <--> y
Below is a translation from the Tarjan code above to alternative pseudocode:
Pointer X = address of array [1, 2, 3];
Pointer Y = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;
Alternatively, we could have:
void operator_double_arrow(Array** lhs, Array** rhs) {
// swap lhs and rhs
int** old_lhs = 0;
old_lhs = lhs;
*lhs = *rhs;
*rhs = *old_lhs;
return;
}
int main() {
Array* lhs = new Array<int>(1, 2, 3);
Array* rhs = new Array<int>(4, 5, 6);
operator_double_arrow(&lhs, &rhs);
delete lhs;
delete rhs;
return 0;
}
Below is an example of one of Tarjan's functions using the ⟷
operator:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2)
fi;
if rank (left (h1)) < rank (right (h1))
→ left(h1) ⟷ right(h1)
fi;
rank (h1) := rank(right(h1)) + 1;
return h1;
end mesh;
Below is a translation of Tarjan's mesh
function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷
operator works.
node pointer function mesh(node pointers h1, h2) {
if (h1.key) > h2.key) {
// swap h1 and h2
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
// Now, h2.key <= h1.key
if (h1.right == null) {
h1.right = h2;
} else // h1.key != null {
h1.right = mesh(h1.right, h2);
}
if (h1.left.rank < h1.right.rank ) {
// swap h1.left and h1.right
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
h1.rank = h1.right.rank + 1;
return h1;
}
(8) Tarjan's do-loops are like C/Java while-loops #
Tarjan's language if
and for
constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do
. All do
-loops end with the keyword od
, which is the backwards spelling of do
. Below is an example:
sum := 0
do sum < 50 → sum := sum + 1
In C-style pseudocode, we have:
sum = 0;
while(sum < 50) {
sum = sum + 1;
}
The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true)
with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
// This `continue` statement is questionable
}
break;
}
Below, we have a more complicated Tarjan do
-loop:
sum := 0
do sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5
C/Java-style pseudocode for the complicated Tarjan do
-loop is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
}
else if (sum < 99) {
sum = sum + 5;
continue;
}
break;
}
(9) Tarjan's Conditional-assignment operator with all false conditions
Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.
Notably, when the conditional assignment operator := if
is used, and no condition is true, I am not what value is assigned to the variable.
x := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi
I am not sure, but it is possible that no assignment is made to x
:
x = 0;
if (false) {
x = 1;
}
else if (false) {
x = 2;
}
else if (99 < 2) {
x = 3;
}
// At this point (x == 0)
You could require that the left-hand-side variable seen in an := if
statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.
Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null
value, and store null
in the left-hand argument of the assignment.
New contributor
$endgroup$
add a comment |
$begingroup$
Table of Contents #
I will divide my explanation of Tarjan's pseudocode into the following sections:
(1) Tarjan's If-else Blocks (the ->
& |
operators)
(2) Assignment and Equality Tests (:=
and =
)
(3) There is else if
, but no else
construct
(4) Tarjan's Conditional Assignment Operator := if
(4.5) Tarjan Arrays (or Lists)
(5) Additional Examples of Tarjan's if
and := if
(6) Summary of Operators
(7) Tarjan's Double-pointed Arrow Operator (⟷
)
**(8) Tarjan's do-loops are like C/Java while-loops **
**(9) Tarjan's Conditional-assignment operator with all false conditions **
1) Tarjan's If-else Blocks #
(the operators →
and |
)
The if-else
construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator ->
(or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.
For example, in Tarjan's language we might have:
# Example One
if a = 4 → x := 9 fi
If we partially translate the line of Tarjan code above into C or Java, we get the following:
if (a = 4)
x := 9
fi
Instead of a right curly braces (as in C and Java) Tarjan ends an if
-block with a backwards spelling of the key-word: fi
If we continue translating our above example, we get:
if (a = 4) {
x := 9
}
(2) Assignment and Equality Tests (:=
and =
)#
Tarjan uses =
for equality tests, not assignments.
Tarjan's =
is like Java ==
Tarjan uses :=
for assignment.
Tarjan's :=
is like Java =
Thus, if we continue translating our example, we have:
if (a == 4) {
x = 9
}
A vertical bar (or "pipe" or |
) in Tarjan's language is equivalent to the else if
keyword in C or Java.
For example, in Tarjan's language we might have:
# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi
The Tarjan-code above translates to:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
(3) else if
only and no else
construct
Earlier, I covered the basics of if
-statements without describing the nuances. However, we will not discuss a small detail. The last clause in a Tarjan-ian if-else
block must always contain an arrow (→
) operator. As such, there is no else
in Tarjan's language, only else if
. The closest thing to an else
-block in Tarjan's language is to make the rightmost test-condition true
.
if a = 4 → x := 9 | a > 4 → y := 11 | true → z := 99 fi
In C/Java, we would have:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
else { // else if (true)
z = 99
}
Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:
if condition
→ stuff to do
| condition
→ stuff to do
[...]
| condition
→ stuff to do
fi
The character |
is like if else
The character →
separates the test-condition from the stuff-to-do.
(4) Tarjan's Conditional Assignment Operator := if
#
Tarjan's if
can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if
. Somewhat confusingly, Tarjan still uses the notation/syntax if
for the second type of if
-construct. Which if
is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if
is always pre-fixed by an assignment operator.
For example, we might have the following Tarjan code:
# Example Three
x := if a = 4 → 9 fi
Begin Digression###
After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:
x := if (a = 4) → 9 fi
a = 4
is not an assignment operation. a = 4
is like a == 4
-- it returns true or false.
End Digression###
It can help to think of := if
as syntax for a single operator, distinct from :=
and if
In fact, we will refer to the := if
operator as the "conditional assignment" operator.
For if
we list (condition → action)
. For := if
we list (condition → value)
where value
is teh right-hand-side value we might assign to the left-hand-side lhs
# Tarjan Example Four
lhs := if (a = 4) → rhs fi
in C or Java might look like:
# Example Four
if (a == 4) {
lhs = rhs
}
Consider the following example of "conditional assignment" in Tarjanian code:
# Tarjan Instantiation of Example Five
x := a = 4 → 9 | a > 4 → 11 | true → 99 fi
In C/Java, we would have:
// C/Java Instantiation of Example Five
if (a == 4) {
x = 9
}
else if (a > 4) {
x = 11
}
else if (true) { // else
x = 99
}
(5) Summary of Operators:
So far, we have:
:=
...... Assignment operator (C/Java=
)=
...... Equality test (C/Java==
)→
...... Delimiter between test-condition of an if-block and the body of an if-block|
..... C/Java else-ifif ... fi
..... if-else block:= if... fi
..... Conditional assignment based on an if-else block
(5.5) Tarjan Lists/Arrays:
Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else
statements.
list1 := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3 := ["a", "b", "c", "d"];
list4 := [ ]; # an empty array
Tarjan array elementa are accessed with parentheses ()
, not square-brackets
Indexing begins at 1
. Thus,
list3 := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true
Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]
nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]
The equality operator is defined for arrays. The following code prints true
x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)
Tarjan's way to test if an array is empty is to compare it to an empty array
arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment
One can create a view (not copy) of a sub-array, by providing multiple indices to operator ()
combined with ..
list3 := ["a", "b", "c", "d"]
beg := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"
end := list3(3..)
# end == ["c", "d"]
# end(1) == "c"
mid := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"
# `list3(4)` is valid, but `mid(4)` is not
(6) Additional Examples of Tarjan's if
and := if
#
The following is another examples of an Tarjan conditional assignment (:= if
):
# Tarjan Example Six
a := (false --> a | true --> b | false --> c1 + c2 | (2 + 3 < 99) --> d)
(true --> b)
is the leftmost (cond --> action)
clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b
Below is our most complicated example of Tarjan code thus far:
# Tarjan Example -- merge two sorted lists
list function merge (list s, t);
return if s = --> t
| t = [ ] --> s
| s != [ ] and t != and s(l) <= t(1) -->
[s(1)]& merge(s[2..], t)
| s != [ ]and t != [ ] and s(1) > r(l) -->
[t(1)] & merge (s,t(2..))
fi
end merge;
The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.
list merge (list s, list t) {
if (s is empty) {
return t;
}
else if (t is empty){
return s;
}
else if (s[1] <= t[1]) {
return CONCATENATE([s[1]], merge(s[2...], t));
else { // else if (s[1] > t[1])
return CONCATENATE ([t[1]], merge(s,t[2..]);
}
}
Below is yet another example of Tarjan-code and a translation in something similar to C or Java:
heap function meld (heap h1, h2);
return if h1 = null --> h2
| h2 = null --> h1
| h1 not null and h2 not null --> mesh (h1, h2)
fi
end meld;
Below is the C/Java translation:
HeapNode meld (HeapNode h1, HeapNode h2) {
if (h1 == null) {
return h2;
}
else if (h2 == null) {
return h1;
} else {
mesh(h1, h2)
}
} // end function
(7) Tarjan's Double-pointed Arrow Operator (<-->
)#
Below is an example of Tarjan code:
x <--> y
What Does a Double Arrow (⟷
) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<-->
is a swap operation. The following prints true
x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true
After performing x <--> y
, x
points to the object which y
used to point to and y
points to the object which x
used to point to.
Below is a Tarjan statement using the <-->
operator:
x := [1, 2, 3]
y := [4, 5, 6]
x <--> y
Below is a translation from the Tarjan code above to alternative pseudocode:
Pointer X = address of array [1, 2, 3];
Pointer Y = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;
Alternatively, we could have:
void operator_double_arrow(Array** lhs, Array** rhs) {
// swap lhs and rhs
int** old_lhs = 0;
old_lhs = lhs;
*lhs = *rhs;
*rhs = *old_lhs;
return;
}
int main() {
Array* lhs = new Array<int>(1, 2, 3);
Array* rhs = new Array<int>(4, 5, 6);
operator_double_arrow(&lhs, &rhs);
delete lhs;
delete rhs;
return 0;
}
Below is an example of one of Tarjan's functions using the ⟷
operator:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2)
fi;
if rank (left (h1)) < rank (right (h1))
→ left(h1) ⟷ right(h1)
fi;
rank (h1) := rank(right(h1)) + 1;
return h1;
end mesh;
Below is a translation of Tarjan's mesh
function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷
operator works.
node pointer function mesh(node pointers h1, h2) {
if (h1.key) > h2.key) {
// swap h1 and h2
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
// Now, h2.key <= h1.key
if (h1.right == null) {
h1.right = h2;
} else // h1.key != null {
h1.right = mesh(h1.right, h2);
}
if (h1.left.rank < h1.right.rank ) {
// swap h1.left and h1.right
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
h1.rank = h1.right.rank + 1;
return h1;
}
(8) Tarjan's do-loops are like C/Java while-loops #
Tarjan's language if
and for
constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do
. All do
-loops end with the keyword od
, which is the backwards spelling of do
. Below is an example:
sum := 0
do sum < 50 → sum := sum + 1
In C-style pseudocode, we have:
sum = 0;
while(sum < 50) {
sum = sum + 1;
}
The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true)
with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
// This `continue` statement is questionable
}
break;
}
Below, we have a more complicated Tarjan do
-loop:
sum := 0
do sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5
C/Java-style pseudocode for the complicated Tarjan do
-loop is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
}
else if (sum < 99) {
sum = sum + 5;
continue;
}
break;
}
(9) Tarjan's Conditional-assignment operator with all false conditions
Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.
Notably, when the conditional assignment operator := if
is used, and no condition is true, I am not what value is assigned to the variable.
x := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi
I am not sure, but it is possible that no assignment is made to x
:
x = 0;
if (false) {
x = 1;
}
else if (false) {
x = 2;
}
else if (99 < 2) {
x = 3;
}
// At this point (x == 0)
You could require that the left-hand-side variable seen in an := if
statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.
Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null
value, and store null
in the left-hand argument of the assignment.
New contributor
$endgroup$
add a comment |
$begingroup$
Table of Contents #
I will divide my explanation of Tarjan's pseudocode into the following sections:
(1) Tarjan's If-else Blocks (the ->
& |
operators)
(2) Assignment and Equality Tests (:=
and =
)
(3) There is else if
, but no else
construct
(4) Tarjan's Conditional Assignment Operator := if
(4.5) Tarjan Arrays (or Lists)
(5) Additional Examples of Tarjan's if
and := if
(6) Summary of Operators
(7) Tarjan's Double-pointed Arrow Operator (⟷
)
**(8) Tarjan's do-loops are like C/Java while-loops **
**(9) Tarjan's Conditional-assignment operator with all false conditions **
1) Tarjan's If-else Blocks #
(the operators →
and |
)
The if-else
construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator ->
(or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.
For example, in Tarjan's language we might have:
# Example One
if a = 4 → x := 9 fi
If we partially translate the line of Tarjan code above into C or Java, we get the following:
if (a = 4)
x := 9
fi
Instead of a right curly braces (as in C and Java) Tarjan ends an if
-block with a backwards spelling of the key-word: fi
If we continue translating our above example, we get:
if (a = 4) {
x := 9
}
(2) Assignment and Equality Tests (:=
and =
)#
Tarjan uses =
for equality tests, not assignments.
Tarjan's =
is like Java ==
Tarjan uses :=
for assignment.
Tarjan's :=
is like Java =
Thus, if we continue translating our example, we have:
if (a == 4) {
x = 9
}
A vertical bar (or "pipe" or |
) in Tarjan's language is equivalent to the else if
keyword in C or Java.
For example, in Tarjan's language we might have:
# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi
The Tarjan-code above translates to:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
(3) else if
only and no else
construct
Earlier, I covered the basics of if
-statements without describing the nuances. However, we will not discuss a small detail. The last clause in a Tarjan-ian if-else
block must always contain an arrow (→
) operator. As such, there is no else
in Tarjan's language, only else if
. The closest thing to an else
-block in Tarjan's language is to make the rightmost test-condition true
.
if a = 4 → x := 9 | a > 4 → y := 11 | true → z := 99 fi
In C/Java, we would have:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
else { // else if (true)
z = 99
}
Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:
if condition
→ stuff to do
| condition
→ stuff to do
[...]
| condition
→ stuff to do
fi
The character |
is like if else
The character →
separates the test-condition from the stuff-to-do.
(4) Tarjan's Conditional Assignment Operator := if
#
Tarjan's if
can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if
. Somewhat confusingly, Tarjan still uses the notation/syntax if
for the second type of if
-construct. Which if
is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if
is always pre-fixed by an assignment operator.
For example, we might have the following Tarjan code:
# Example Three
x := if a = 4 → 9 fi
Begin Digression###
After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:
x := if (a = 4) → 9 fi
a = 4
is not an assignment operation. a = 4
is like a == 4
-- it returns true or false.
End Digression###
It can help to think of := if
as syntax for a single operator, distinct from :=
and if
In fact, we will refer to the := if
operator as the "conditional assignment" operator.
For if
we list (condition → action)
. For := if
we list (condition → value)
where value
is teh right-hand-side value we might assign to the left-hand-side lhs
# Tarjan Example Four
lhs := if (a = 4) → rhs fi
in C or Java might look like:
# Example Four
if (a == 4) {
lhs = rhs
}
Consider the following example of "conditional assignment" in Tarjanian code:
# Tarjan Instantiation of Example Five
x := a = 4 → 9 | a > 4 → 11 | true → 99 fi
In C/Java, we would have:
// C/Java Instantiation of Example Five
if (a == 4) {
x = 9
}
else if (a > 4) {
x = 11
}
else if (true) { // else
x = 99
}
(5) Summary of Operators:
So far, we have:
:=
...... Assignment operator (C/Java=
)=
...... Equality test (C/Java==
)→
...... Delimiter between test-condition of an if-block and the body of an if-block|
..... C/Java else-ifif ... fi
..... if-else block:= if... fi
..... Conditional assignment based on an if-else block
(5.5) Tarjan Lists/Arrays:
Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else
statements.
list1 := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3 := ["a", "b", "c", "d"];
list4 := [ ]; # an empty array
Tarjan array elementa are accessed with parentheses ()
, not square-brackets
Indexing begins at 1
. Thus,
list3 := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true
Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]
nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]
The equality operator is defined for arrays. The following code prints true
x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)
Tarjan's way to test if an array is empty is to compare it to an empty array
arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment
One can create a view (not copy) of a sub-array, by providing multiple indices to operator ()
combined with ..
list3 := ["a", "b", "c", "d"]
beg := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"
end := list3(3..)
# end == ["c", "d"]
# end(1) == "c"
mid := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"
# `list3(4)` is valid, but `mid(4)` is not
(6) Additional Examples of Tarjan's if
and := if
#
The following is another examples of an Tarjan conditional assignment (:= if
):
# Tarjan Example Six
a := (false --> a | true --> b | false --> c1 + c2 | (2 + 3 < 99) --> d)
(true --> b)
is the leftmost (cond --> action)
clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b
Below is our most complicated example of Tarjan code thus far:
# Tarjan Example -- merge two sorted lists
list function merge (list s, t);
return if s = --> t
| t = [ ] --> s
| s != [ ] and t != and s(l) <= t(1) -->
[s(1)]& merge(s[2..], t)
| s != [ ]and t != [ ] and s(1) > r(l) -->
[t(1)] & merge (s,t(2..))
fi
end merge;
The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.
list merge (list s, list t) {
if (s is empty) {
return t;
}
else if (t is empty){
return s;
}
else if (s[1] <= t[1]) {
return CONCATENATE([s[1]], merge(s[2...], t));
else { // else if (s[1] > t[1])
return CONCATENATE ([t[1]], merge(s,t[2..]);
}
}
Below is yet another example of Tarjan-code and a translation in something similar to C or Java:
heap function meld (heap h1, h2);
return if h1 = null --> h2
| h2 = null --> h1
| h1 not null and h2 not null --> mesh (h1, h2)
fi
end meld;
Below is the C/Java translation:
HeapNode meld (HeapNode h1, HeapNode h2) {
if (h1 == null) {
return h2;
}
else if (h2 == null) {
return h1;
} else {
mesh(h1, h2)
}
} // end function
(7) Tarjan's Double-pointed Arrow Operator (<-->
)#
Below is an example of Tarjan code:
x <--> y
What Does a Double Arrow (⟷
) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<-->
is a swap operation. The following prints true
x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true
After performing x <--> y
, x
points to the object which y
used to point to and y
points to the object which x
used to point to.
Below is a Tarjan statement using the <-->
operator:
x := [1, 2, 3]
y := [4, 5, 6]
x <--> y
Below is a translation from the Tarjan code above to alternative pseudocode:
Pointer X = address of array [1, 2, 3];
Pointer Y = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;
Alternatively, we could have:
void operator_double_arrow(Array** lhs, Array** rhs) {
// swap lhs and rhs
int** old_lhs = 0;
old_lhs = lhs;
*lhs = *rhs;
*rhs = *old_lhs;
return;
}
int main() {
Array* lhs = new Array<int>(1, 2, 3);
Array* rhs = new Array<int>(4, 5, 6);
operator_double_arrow(&lhs, &rhs);
delete lhs;
delete rhs;
return 0;
}
Below is an example of one of Tarjan's functions using the ⟷
operator:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2)
fi;
if rank (left (h1)) < rank (right (h1))
→ left(h1) ⟷ right(h1)
fi;
rank (h1) := rank(right(h1)) + 1;
return h1;
end mesh;
Below is a translation of Tarjan's mesh
function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷
operator works.
node pointer function mesh(node pointers h1, h2) {
if (h1.key) > h2.key) {
// swap h1 and h2
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
// Now, h2.key <= h1.key
if (h1.right == null) {
h1.right = h2;
} else // h1.key != null {
h1.right = mesh(h1.right, h2);
}
if (h1.left.rank < h1.right.rank ) {
// swap h1.left and h1.right
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
h1.rank = h1.right.rank + 1;
return h1;
}
(8) Tarjan's do-loops are like C/Java while-loops #
Tarjan's language if
and for
constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do
. All do
-loops end with the keyword od
, which is the backwards spelling of do
. Below is an example:
sum := 0
do sum < 50 → sum := sum + 1
In C-style pseudocode, we have:
sum = 0;
while(sum < 50) {
sum = sum + 1;
}
The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true)
with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
// This `continue` statement is questionable
}
break;
}
Below, we have a more complicated Tarjan do
-loop:
sum := 0
do sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5
C/Java-style pseudocode for the complicated Tarjan do
-loop is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
}
else if (sum < 99) {
sum = sum + 5;
continue;
}
break;
}
(9) Tarjan's Conditional-assignment operator with all false conditions
Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.
Notably, when the conditional assignment operator := if
is used, and no condition is true, I am not what value is assigned to the variable.
x := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi
I am not sure, but it is possible that no assignment is made to x
:
x = 0;
if (false) {
x = 1;
}
else if (false) {
x = 2;
}
else if (99 < 2) {
x = 3;
}
// At this point (x == 0)
You could require that the left-hand-side variable seen in an := if
statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.
Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null
value, and store null
in the left-hand argument of the assignment.
New contributor
$endgroup$
Table of Contents #
I will divide my explanation of Tarjan's pseudocode into the following sections:
(1) Tarjan's If-else Blocks (the ->
& |
operators)
(2) Assignment and Equality Tests (:=
and =
)
(3) There is else if
, but no else
construct
(4) Tarjan's Conditional Assignment Operator := if
(4.5) Tarjan Arrays (or Lists)
(5) Additional Examples of Tarjan's if
and := if
(6) Summary of Operators
(7) Tarjan's Double-pointed Arrow Operator (⟷
)
**(8) Tarjan's do-loops are like C/Java while-loops **
**(9) Tarjan's Conditional-assignment operator with all false conditions **
1) Tarjan's If-else Blocks #
(the operators →
and |
)
The if-else
construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator ->
(or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.
For example, in Tarjan's language we might have:
# Example One
if a = 4 → x := 9 fi
If we partially translate the line of Tarjan code above into C or Java, we get the following:
if (a = 4)
x := 9
fi
Instead of a right curly braces (as in C and Java) Tarjan ends an if
-block with a backwards spelling of the key-word: fi
If we continue translating our above example, we get:
if (a = 4) {
x := 9
}
(2) Assignment and Equality Tests (:=
and =
)#
Tarjan uses =
for equality tests, not assignments.
Tarjan's =
is like Java ==
Tarjan uses :=
for assignment.
Tarjan's :=
is like Java =
Thus, if we continue translating our example, we have:
if (a == 4) {
x = 9
}
A vertical bar (or "pipe" or |
) in Tarjan's language is equivalent to the else if
keyword in C or Java.
For example, in Tarjan's language we might have:
# Example Two
if a = 4 → x := 9 | a > 4 → y := 11 fi
The Tarjan-code above translates to:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
(3) else if
only and no else
construct
Earlier, I covered the basics of if
-statements without describing the nuances. However, we will not discuss a small detail. The last clause in a Tarjan-ian if-else
block must always contain an arrow (→
) operator. As such, there is no else
in Tarjan's language, only else if
. The closest thing to an else
-block in Tarjan's language is to make the rightmost test-condition true
.
if a = 4 → x := 9 | a > 4 → y := 11 | true → z := 99 fi
In C/Java, we would have:
if (a == 4) {
x = 9
}
else if (a > 4) {
y = 11
}
else { // else if (true)
z = 99
}
Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:
if condition
→ stuff to do
| condition
→ stuff to do
[...]
| condition
→ stuff to do
fi
The character |
is like if else
The character →
separates the test-condition from the stuff-to-do.
(4) Tarjan's Conditional Assignment Operator := if
#
Tarjan's if
can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if
. Somewhat confusingly, Tarjan still uses the notation/syntax if
for the second type of if
-construct. Which if
is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if
is always pre-fixed by an assignment operator.
For example, we might have the following Tarjan code:
# Example Three
x := if a = 4 → 9 fi
Begin Digression###
After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:
x := if (a = 4) → 9 fi
a = 4
is not an assignment operation. a = 4
is like a == 4
-- it returns true or false.
End Digression###
It can help to think of := if
as syntax for a single operator, distinct from :=
and if
In fact, we will refer to the := if
operator as the "conditional assignment" operator.
For if
we list (condition → action)
. For := if
we list (condition → value)
where value
is teh right-hand-side value we might assign to the left-hand-side lhs
# Tarjan Example Four
lhs := if (a = 4) → rhs fi
in C or Java might look like:
# Example Four
if (a == 4) {
lhs = rhs
}
Consider the following example of "conditional assignment" in Tarjanian code:
# Tarjan Instantiation of Example Five
x := a = 4 → 9 | a > 4 → 11 | true → 99 fi
In C/Java, we would have:
// C/Java Instantiation of Example Five
if (a == 4) {
x = 9
}
else if (a > 4) {
x = 11
}
else if (true) { // else
x = 99
}
(5) Summary of Operators:
So far, we have:
:=
...... Assignment operator (C/Java=
)=
...... Equality test (C/Java==
)→
...... Delimiter between test-condition of an if-block and the body of an if-block|
..... C/Java else-ifif ... fi
..... if-else block:= if... fi
..... Conditional assignment based on an if-else block
(5.5) Tarjan Lists/Arrays:
Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else
statements.
list1 := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3 := ["a", "b", "c", "d"];
list4 := [ ]; # an empty array
Tarjan array elementa are accessed with parentheses ()
, not square-brackets
Indexing begins at 1
. Thus,
list3 := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true
Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]
nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]
The equality operator is defined for arrays. The following code prints true
x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)
Tarjan's way to test if an array is empty is to compare it to an empty array
arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment
One can create a view (not copy) of a sub-array, by providing multiple indices to operator ()
combined with ..
list3 := ["a", "b", "c", "d"]
beg := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"
end := list3(3..)
# end == ["c", "d"]
# end(1) == "c"
mid := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"
# `list3(4)` is valid, but `mid(4)` is not
(6) Additional Examples of Tarjan's if
and := if
#
The following is another examples of an Tarjan conditional assignment (:= if
):
# Tarjan Example Six
a := (false --> a | true --> b | false --> c1 + c2 | (2 + 3 < 99) --> d)
(true --> b)
is the leftmost (cond --> action)
clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b
Below is our most complicated example of Tarjan code thus far:
# Tarjan Example -- merge two sorted lists
list function merge (list s, t);
return if s = --> t
| t = [ ] --> s
| s != [ ] and t != and s(l) <= t(1) -->
[s(1)]& merge(s[2..], t)
| s != [ ]and t != [ ] and s(1) > r(l) -->
[t(1)] & merge (s,t(2..))
fi
end merge;
The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.
list merge (list s, list t) {
if (s is empty) {
return t;
}
else if (t is empty){
return s;
}
else if (s[1] <= t[1]) {
return CONCATENATE([s[1]], merge(s[2...], t));
else { // else if (s[1] > t[1])
return CONCATENATE ([t[1]], merge(s,t[2..]);
}
}
Below is yet another example of Tarjan-code and a translation in something similar to C or Java:
heap function meld (heap h1, h2);
return if h1 = null --> h2
| h2 = null --> h1
| h1 not null and h2 not null --> mesh (h1, h2)
fi
end meld;
Below is the C/Java translation:
HeapNode meld (HeapNode h1, HeapNode h2) {
if (h1 == null) {
return h2;
}
else if (h2 == null) {
return h1;
} else {
mesh(h1, h2)
}
} // end function
(7) Tarjan's Double-pointed Arrow Operator (<-->
)#
Below is an example of Tarjan code:
x <--> y
What Does a Double Arrow (⟷
) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<-->
is a swap operation. The following prints true
x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true
After performing x <--> y
, x
points to the object which y
used to point to and y
points to the object which x
used to point to.
Below is a Tarjan statement using the <-->
operator:
x := [1, 2, 3]
y := [4, 5, 6]
x <--> y
Below is a translation from the Tarjan code above to alternative pseudocode:
Pointer X = address of array [1, 2, 3];
Pointer Y = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;
Alternatively, we could have:
void operator_double_arrow(Array** lhs, Array** rhs) {
// swap lhs and rhs
int** old_lhs = 0;
old_lhs = lhs;
*lhs = *rhs;
*rhs = *old_lhs;
return;
}
int main() {
Array* lhs = new Array<int>(1, 2, 3);
Array* rhs = new Array<int>(4, 5, 6);
operator_double_arrow(&lhs, &rhs);
delete lhs;
delete rhs;
return 0;
}
Below is an example of one of Tarjan's functions using the ⟷
operator:
heap function mesh (heap nodes h1, h2);
if key(h1) > key(h2) → h1 ⟷ h2 fi;
right (h1) := if right(h1) = null → h2
|right(h1) ≠ null → mesh (right(h1), h2)
fi;
if rank (left (h1)) < rank (right (h1))
→ left(h1) ⟷ right(h1)
fi;
rank (h1) := rank(right(h1)) + 1;
return h1;
end mesh;
Below is a translation of Tarjan's mesh
function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷
operator works.
node pointer function mesh(node pointers h1, h2) {
if (h1.key) > h2.key) {
// swap h1 and h2
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
// Now, h2.key <= h1.key
if (h1.right == null) {
h1.right = h2;
} else // h1.key != null {
h1.right = mesh(h1.right, h2);
}
if (h1.left.rank < h1.right.rank ) {
// swap h1.left and h1.right
node pointer temp;
temp = h1;
h1 = h2;
h2 = temp;
}
h1.rank = h1.right.rank + 1;
return h1;
}
(8) Tarjan's do-loops are like C/Java while-loops #
Tarjan's language if
and for
constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do
. All do
-loops end with the keyword od
, which is the backwards spelling of do
. Below is an example:
sum := 0
do sum < 50 → sum := sum + 1
In C-style pseudocode, we have:
sum = 0;
while(sum < 50) {
sum = sum + 1;
}
The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true)
with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
// This `continue` statement is questionable
}
break;
}
Below, we have a more complicated Tarjan do
-loop:
sum := 0
do sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5
C/Java-style pseudocode for the complicated Tarjan do
-loop is as follows:
sum = 0;
while(true) {
if (sum < 50) {
sum = sum + 1;
continue;
}
else if (sum < 99) {
sum = sum + 5;
continue;
}
break;
}
(9) Tarjan's Conditional-assignment operator with all false conditions
Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.
Notably, when the conditional assignment operator := if
is used, and no condition is true, I am not what value is assigned to the variable.
x := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi
I am not sure, but it is possible that no assignment is made to x
:
x = 0;
if (false) {
x = 1;
}
else if (false) {
x = 2;
}
else if (99 < 2) {
x = 3;
}
// At this point (x == 0)
You could require that the left-hand-side variable seen in an := if
statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.
Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null
value, and store null
in the left-hand argument of the assignment.
New contributor
New contributor
answered 1 hour ago
Sam MuldoonSam Muldoon
313
313
New contributor
New contributor
add a comment |
add a comment |
$begingroup$
Never seen this before but I think I can infer what's meant from context.. Presumably the ⟷
must be a swap operation, and if G1 -> S1 | G2 - >S2 | ... fi
is an if/then/else-type construct that also returns a value, like the ternary ?:
operator in C and Java.
With that in hand we could write the above function in a Java-like language like so:
HeapNode mesh(HeapNode h1, HeapNode h2)
{
if(h1.key > h2.key)
{
// swap h1 and h2
HeapNode t = h1;
h1 = h2;
h2 = t;
}
// One of the two cases has to hold in this case so we won't get to the
// exception, but it'd be an exception if none of the cases were satisified
// since this needs to return *something*.
h1.right = (h1.right == null) ? h2
: (h1.right != null) ? mesh(h1.right, h2)
: throw new Exception();
if(h1.left.rank < h1.right.rank)
{
// swap h1.left and h1.right
HeapNode t = h1.left;
h1.left = h1.right;
h1.right = t;
}
h1.rank = h1.right.rank + 1;
return h1;
}
$endgroup$
add a comment |
$begingroup$
Never seen this before but I think I can infer what's meant from context.. Presumably the ⟷
must be a swap operation, and if G1 -> S1 | G2 - >S2 | ... fi
is an if/then/else-type construct that also returns a value, like the ternary ?:
operator in C and Java.
With that in hand we could write the above function in a Java-like language like so:
HeapNode mesh(HeapNode h1, HeapNode h2)
{
if(h1.key > h2.key)
{
// swap h1 and h2
HeapNode t = h1;
h1 = h2;
h2 = t;
}
// One of the two cases has to hold in this case so we won't get to the
// exception, but it'd be an exception if none of the cases were satisified
// since this needs to return *something*.
h1.right = (h1.right == null) ? h2
: (h1.right != null) ? mesh(h1.right, h2)
: throw new Exception();
if(h1.left.rank < h1.right.rank)
{
// swap h1.left and h1.right
HeapNode t = h1.left;
h1.left = h1.right;
h1.right = t;
}
h1.rank = h1.right.rank + 1;
return h1;
}
$endgroup$
add a comment |
$begingroup$
Never seen this before but I think I can infer what's meant from context.. Presumably the ⟷
must be a swap operation, and if G1 -> S1 | G2 - >S2 | ... fi
is an if/then/else-type construct that also returns a value, like the ternary ?:
operator in C and Java.
With that in hand we could write the above function in a Java-like language like so:
HeapNode mesh(HeapNode h1, HeapNode h2)
{
if(h1.key > h2.key)
{
// swap h1 and h2
HeapNode t = h1;
h1 = h2;
h2 = t;
}
// One of the two cases has to hold in this case so we won't get to the
// exception, but it'd be an exception if none of the cases were satisified
// since this needs to return *something*.
h1.right = (h1.right == null) ? h2
: (h1.right != null) ? mesh(h1.right, h2)
: throw new Exception();
if(h1.left.rank < h1.right.rank)
{
// swap h1.left and h1.right
HeapNode t = h1.left;
h1.left = h1.right;
h1.right = t;
}
h1.rank = h1.right.rank + 1;
return h1;
}
$endgroup$
Never seen this before but I think I can infer what's meant from context.. Presumably the ⟷
must be a swap operation, and if G1 -> S1 | G2 - >S2 | ... fi
is an if/then/else-type construct that also returns a value, like the ternary ?:
operator in C and Java.
With that in hand we could write the above function in a Java-like language like so:
HeapNode mesh(HeapNode h1, HeapNode h2)
{
if(h1.key > h2.key)
{
// swap h1 and h2
HeapNode t = h1;
h1 = h2;
h2 = t;
}
// One of the two cases has to hold in this case so we won't get to the
// exception, but it'd be an exception if none of the cases were satisified
// since this needs to return *something*.
h1.right = (h1.right == null) ? h2
: (h1.right != null) ? mesh(h1.right, h2)
: throw new Exception();
if(h1.left.rank < h1.right.rank)
{
// swap h1.left and h1.right
HeapNode t = h1.left;
h1.left = h1.right;
h1.right = t;
}
h1.rank = h1.right.rank + 1;
return h1;
}
answered 1 hour ago
Daniel McLauryDaniel McLaury
27216
27216
add a comment |
add a comment |
Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.
Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.
Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.
Sam Muldoon is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f103816%2fcan-you-explain-how-tarjans-pseudocode-works-to-someone-familiar-with-c-or-java%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown