/来自 CLR/ Java 中的 TreeMap 实现

Question

我正在寻找 Java 的 (JDK 1.6_45) TreeMap 代码来理解我遇到的问题，在一些方法中我看到一条评论说 /**来自 CLR */。

我的印象是 CLR 是 Microsoft 对其公共运行时的术语。 CLR 术语也用于 Java 吗？如果没有，那么是否有一个共同的协议来使用彼此的实现（当然在转换之后）或者它只是一些自动生成的评论？

示例

/** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {

Answer 1

它看起来像 Java 的 TreeMap "borrowed" 部分实现来自 JabberNet's Tree, which is written in C# — here the full C# source code。

很可能 Java 的一位作者 TreeMap 包含了反映这一事实的评论（因此评论中的 "CLR" 确实意味着 "Common Language Runtime"） .

这里是一个片段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) {
            ...

这里是相应的片段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))
            ...

如您所见，代码几乎相同 — 除了缩进、节点 class 名称和语法差异。

标记为/** From CLR */的其他方法也是如此。

但是，Java 代码确实 而不是 似乎是完全从 C# 代码自动生成的，请参见。 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.
 */

Answer 2

"CLR"是Introduction to Algorithms第一版作者Cormen、Leiserson和Rivest三个人的缩写.

EmirCalabuch 在 another thread 中回答说

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" 与 "CLR" 指的是同一本书。由于这种方法紧跟Introduction to Algorithms，因此注释为/** From CLR */是合理的。

/来自 CLR/ Java 中的 TreeMap 实现

/From CLR/ in Java TreeMap implementation

java

clr

/*来自 CLR*/ Java 中的 TreeMap 实现

/*From CLR*/ in Java TreeMap implementation

java

clr

/来自 CLR/ Java 中的 TreeMap 实现

/From CLR/ in Java TreeMap implementation