masonry

1"use client";
2 
3import { Slot as SlotPrimitive } from "radix-ui";
4import * as React from "react";
5import { useComposedRefs } from "@/lib/compose-refs";
6import { useIsomorphicLayoutEffect } from "@/registry/bases/radix/hooks/use-isomorphic-layout-effect";
7 
8const NODE_COLOR = {
9  RED: 0,
10  BLACK: 1,
11  SENTINEL: 2,
12} as const;
13 
14const NODE_OPERATION = {
15  REMOVE: 0,
16  PRESERVE: 1,
17} as const;
18 
19type NodeColor = (typeof NODE_COLOR)[keyof typeof NODE_COLOR];
20type NodeOperation = (typeof NODE_OPERATION)[keyof typeof NODE_OPERATION];
21 
22interface ListNode {
23  index: number;
24  high: number;
25  next: ListNode | null;
26}
27 
28interface TreeNode {
29  max: number;
30  low: number;
31  high: number;
32  color: NodeColor;
33  parent: TreeNode;
34  right: TreeNode;
35  left: TreeNode;
36  list: ListNode;
37}
38 
39interface Tree {
40  root: TreeNode;
41  size: number;
42}
43 
44function addInterval(treeNode: TreeNode, high: number, index: number): boolean {
45  let node: ListNode | null = treeNode.list;
46  let prevNode: ListNode | undefined;
47 
48  while (node) {
49    if (node.index === index) return false;
50    if (high > node.high) break;
51    prevNode = node;
52    node = node.next;
53  }
54 
55  if (!prevNode) treeNode.list = { index, high, next: node };
56  if (prevNode) prevNode.next = { index, high, next: prevNode.next };
57 
58  return true;
59}
60 
61function removeInterval(
62  treeNode: TreeNode,
63  index: number,
64): NodeOperation | undefined {
65  let node: ListNode | null = treeNode.list;
66  if (node.index === index) {
67    if (node.next === null) return NODE_OPERATION.REMOVE;
68    treeNode.list = node.next;
69    return NODE_OPERATION.PRESERVE;
70  }
71 
72  let prevNode: ListNode | undefined = node;
73  node = node.next;
74 
75  while (node !== null) {
76    if (node.index === index) {
77      prevNode.next = node.next;
78      return NODE_OPERATION.PRESERVE;
79    }
80    prevNode = node;
81    node = node.next;
82  }
83}
84 
85const SENTINEL_NODE: TreeNode = {
86  low: 0,
87  max: 0,
88  high: 0,
89  color: NODE_COLOR.SENTINEL,
90  parent: undefined as unknown as TreeNode,
91  right: undefined as unknown as TreeNode,
92  left: undefined as unknown as TreeNode,
93  list: undefined as unknown as ListNode,
94};
95 
96SENTINEL_NODE.parent = SENTINEL_NODE;
97SENTINEL_NODE.left = SENTINEL_NODE;
98SENTINEL_NODE.right = SENTINEL_NODE;
99 
100function updateMax(node: TreeNode) {
101  const max = node.high;
102  if (node.left === SENTINEL_NODE && node.right === SENTINEL_NODE)
103    node.max = max;
104  else if (node.left === SENTINEL_NODE)
105    node.max = Math.max(node.right.max, max);
106  else if (node.right === SENTINEL_NODE)
107// … truncated