masonry

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