5

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) {
ata
  • 8,853
  • 8
  • 42
  • 68

2 Answers2

7

"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.

Bing Zhao
  • 568
  • 6
  • 19
1

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.
 */
Alex Shesterov
  • 26,085
  • 12
  • 82
  • 103
  • This can't be true. That implementation of `TreeMap` dates back to Java 1.2 (1998). See source here: https://github.com/fanhongtao/JDK/blob/jdk_1.2.1/src/java/util/TreeMap.java The first ever release of C# (version 1.0) was in 2002! – Malt Jan 27 '19 at 14:19
  • But CLR started earlier than that, approximately 1998. – Alex Shesterov Jan 27 '19 at 16:42
  • Work on the CRL begun in June 98. Java 1.2 was released in December. Do you suggest that the team behind Java 1.2 copied a tree implementation from some unknown project at a different company that just got started 4 months before the release? Oh, and one of the very first things implemented in the CLR, just months after the several year long project was started was a tree? Take a look at Bing Zhao’s answer. It makes a LOT morse sense. – Malt Jan 27 '19 at 16:58
  • The code was not borrowed from C#. CLR in that context is short for Cormen, Leiserson and Rivest, authors of "Introduction to algorithms", as stated in the code comments: `Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.` – EmirCalabuch Dec 30 '19 at 06:03