Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

/*From CLR*/ in Java TreeMap implementation

Tags:

java

clr

I was looking Java's (JDK 1.6_45) TreeMap code to understand a problem I was having and on few methods I saw a comment saying /** From CLR */.

I was under the impression that CLR is Microsoft terminology for its common runtime. Is CLR terminology used for Java as well? If not, then is there a common agreement to use each others implementation (after converting of-course) or is it just some auto generated comment?

Example

/** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {
like image 908
ata Avatar asked Jul 20 '16 13:07

ata


2 Answers

"CLR" is an abbreviation of three persons, namely Cormen, Leiserson and Rivest, authors of the first edition of Introduction to Algorithms.

EmirCalabuch answered in another thread that

There is nothing peculiar in the TreeMap implementation of RBT. It closely follows the pseudocode given in CLRS's (Cormen, Leiserson, Rivest and Stein) book, which is what 99% of the implementations around do.

"CLRS" refers to the same book as "CLR" does. Since this kind of method closely follows Introduction to Algorithms, being commented with /** From CLR */ is reasonable.

like image 142
Bing Zhao Avatar answered Sep 25 '22 07:09

Bing Zhao


It looks like Java's TreeMap "borrowed" part of its implementation from JabberNet's Tree, which is written in C# — here the full C# source code.

Most probably one of the authors of the Java's TreeMap included the comment to reflect this fact (so "CLR" in the comment indeed means "Common Language Runtime").

Here a snippet from Java's TreeMap:

/** From CLR */
private void fixAfterDeletion(Entry<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry<K,V> sib = rightOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            if (colorOf(leftOf(sib))  == BLACK &&
                colorOf(rightOf(sib)) == BLACK) {
            ...

And here the corresponding snippet from the JabberNet C# code:

private void fixAfterDeletion(Node x)
{
    while ((x != root) && (colorOf(x) == NodeColor.BLACK))
    {
        if (x == leftOf(parentOf(x)))
        {
            Node sib = rightOf(parentOf(x));

            if (colorOf(sib) == NodeColor.RED)
            {
                setColor(sib, NodeColor.BLACK);
                setColor(parentOf(x), NodeColor.RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            if ((colorOf(leftOf(sib))  == NodeColor.BLACK) &&
                (colorOf(rightOf(sib)) == NodeColor.BLACK))
            ... 

As you can see, the code is almost identical — except for indentation, node class name and syntax differences.

This is also true for other methods marked as /** From CLR */.

However, the Java code does not seem to be fully auto-generated from the C# code, cf. this comment in the Java code:

/**
 * Balancing operations.
 *
 * Implementations of rebalancings during insertion and deletion are
 * slightly different than the CLR version.  Rather than using dummy
 * nilnodes, we use a set of accessors that deal properly with null.  They
 * are used to avoid messiness surrounding nullness checks in the main
 * algorithms.
 */
like image 36
Alex Shesterov Avatar answered Sep 23 '22 07:09

Alex Shesterov