java - 排序父子关系

Question

我在为我的类 Page 找出一个简单的 compareTo 方法时遇到了一些问题:

• 页面通过 getParent() 引用父页面 - 可为空
• Page有一个变量order，它只决定在同一层级中的顺序

我喜欢按以下方式排序:

1. 家长A
2. A1 的子父
3. A2 的子 parent
4. 家长B
5. 父C
6. SubParentOfC1
7. C2 的子父类

我的 compareTo 需要如何查看才能解决这个问题？我尝试了以下方法，目前只能正确排序相同级别。

我的方法:

@Override
public int compareTo(@NonNull Object o) {
    int compare = 0;
    if (o instanceof Page) {
        Page other = (Page) o;
        if (other.parent != null) {
            compare = this.compareTo(other.parent);
        } else if (parent != null) {
            compare = this.parent.compareTo(other);
        }
        if (compare == 0) {
            compare = Integers.compareTo(this.order, other.order);
        }
    }
    return compare;
}

编辑:我的页面类:

class Page{
    int order;
    Page parent;
}

Answer 1

无需进行复杂的计算，您可以简单地依赖order 链。我使用了一个 String 来存储每个“节点”的链:

class Page implements Comparable<Page> {
    String name;
    int order;
    Page parent;
    String key;

    Page() {
        name = "root";
        order  = 0;
        parent = null;
        key    = "";
    }

    Page(String name, int order, Page parent) {
        this.name   = name;
        this.order  = order;
        this.parent = parent;
        key = parent.key + (char)order;
    }

    @Override
    public int compareTo(Page o) {
        return key.compareTo(o.key);
    }

    @Override
    public String toString() {
        return name;
    }
}

public static void main(String[] args) {
    Page root = new Page();

    Page b    = new Page("b"  , 2, root);
    Page b1   = new Page("b.1", 1, b);
    Page b3   = new Page("b.3", 3, b);
    Page b2   = new Page("b.2", 2, b);

    Page a    = new Page("a"  , 1, root);
    Page a2   = new Page("a.2", 2, a);
    Page a1   = new Page("a.1", 1, a);

    List<Page> pages = Arrays.asList(root, a, a1, a2, b, b1, b2, b3);
    System.out.println(pages);

    Collections.shuffle(pages);
    System.out.println(pages);

    Collections.sort(pages);
    System.out.println(pages);
}

这里的技巧是使用 String 作为可排序的 short 数组。该数组是 order 的组合，构成从根到节点的路径。 root 有一个键/id 为 [] 和 a 来自 root 的一个 child order 1 作为 [1] 的键/id。

这里是 key/id 矩阵:

┌──────┬────────┬───────┬────────────┬─────┐
│ Page │ Parent │ Order │ Parent Key │ Key │
├──────┼────────┼───────┼────────────┼─────┤
│ root │ -      │ -     │ -          │     │
│ a    │ root   │ 1     │            │ 1   │
│ a.1  │ a      │ 1     │ 1          │ 1 1 │
│ a.2  │ a      │ 2     │ 1          │ 1 2 │
│ b    │ root   │ 2     │            │ 2   │
│ b.1  │ b      │ 1     │ 2          │ 2 1 │
│ b.2  │ b      │ 2     │ 2          │ 2 2 │
│ b.3  │ b      │ 3     │ 2          │ 2 3 │
└──────┴────────┴───────┴────────────┴─────┘

这是另一棵树的例子(括号中的关键字)

root      (     )
├ z       (1    )
│ ├ a     (1 1  )
│ │ └ y   (1 1 1)
│ └ b     (1 2  )
│   └ x   (1 2 1)
└ c       (2    )
  ├ w     (2 1  )
  └ d     (2 2  )