π The open-source, offline-first Notion, Obsidian & Confluence alternative. Advanced Markdown, multi-tenant teams, OIDC/SSO, and local S3 backups. Deploy in one command.
Vue dockergolangkanbanknowledge-baseknowledge-managementmarkdownnote-takingnotesnotes-appnotionnuxtnuxtjsoffline-firstoidcpwaselfhostedssovuevuejswiki
export interface TreeItem<T = unknown, ID = string> {
id: ID;
parentId?: string | null;
label: string;
data: T;
route: string;
icon?: string;
children?: TreeItem<T>[];
onClick?: () => void;
}
export interface ReadonlyIndexedCollection<T> {
size: number;
get(id: string): T | undefined;
getChildrenIds(parentId: string | null | undefined): string[];
}
export class TreeBuilder<T extends { id: string; parent_id?: string | null; role?: number; order?: number }> {
private transformCache = new Map<string, TreeItem<T>>();
constructor(
private readonly collection: ReadonlyIndexedCollection<T>,
private readonly transform: (item: T) => Omit<TreeItem<T>, 'children'>,
private readonly sortNodes: (a: TreeItem<T>, b: TreeItem<T>) => number,
) {}
/**
* Transform a raw node into a TreeItem, using the cache if available.
*/
public getTransformedItem(id: string): TreeItem<T> | undefined {
if (this.transformCache.has(id)) {
return this.transformCache.get(id);
}
const rawNode = this.collection.get(id) as T;
if (!rawNode) return undefined;
const item: TreeItem<T> = {
...this.transform(rawNode),
children: [],
};
this.transformCache.set(id, item);
return item;
}
/**
* Build the entire descending tree recursively, starting from the roots
* @param options Optional filters for nodes and roots
* @returns An array of TreeItem representing the tree structure
*/
buildTree(options?: { nodeFilter?: (node: T) => boolean; rootFilter?: (node: T) => boolean }): TreeItem<T>[] {
const rootIds = this.collection.getChildrenIds(null);
const buildSubtree = (id: string): TreeItem<T> | undefined => {
const rawNode = this.collection.get(id) as T;
if (!rawNode) return undefined;
if (options?.nodeFilter && !options.nodeFilter(rawNode)) {
return undefined;
}
const item = this.getTransformedItem(id);
if (!item) return undefined;
const childrenIds = this.collection.getChildrenIds(id);
if (childrenIds.length > 0) {
const mappedChildren = childrenIds.map(childId => buildSubtree(childId)).filter((c): c is TreeItem<T> => !!c);
if (mappedChildren.length > 1) {
mappedChildren.sort(this.sortNodes);
}
item.children = mappedChildren.length > 0 ? mappedChildren : undefined;
} else {
item.children = undefined;
}
return item;
};
const rootItems = rootIds
.filter(id => {
const node = this.collection.get(id) as T;
if (!node) return false;
if (options?.rootFilter && !options.rootFilter(node)) return false;
return true;
})
.map(id => buildSubtree(id))
.filter((item): item is TreeItem<T> => !!item);
if (rootItems.length > 1) {
rootItems.sort(this.sortNodes);
}
return rootItems;
}
/**
* Get the next or previous sibling of a node, optionally filtered by a predicate
*/
getSibling(id: string, direction: number, filter?: (item?: T) => boolean): TreeItem<T> | undefined {
const currentItem = this.getTransformedItem(id);
if (!currentItem) return undefined;
let siblings = this.collection
.getChildrenIds(currentItem.parentId ?? null)
.map(id => this.getTransformedItem(id))
.filter((s): s is TreeItem<T> => !!s);
if (filter) siblings = siblings.filter(s => filter(s.data));
const index = siblings.findIndex(s => s.id === id);
if (index === -1) return undefined;
return siblings[index + direction] ?? undefined;
}
/**
* Clear the transformation cache, useful when the underlying collection changes
* to ensure that the tree is rebuilt with the latest data.
*/
public clearCache() {
this.transformCache.clear();
}
}
/** Filter tree recursively, keeping branches with matches */
export function filterTree<T extends TreeItem<unknown>>(items: T[], predicate: (item: T) => boolean): T[] {
const result: T[] = [];
for (const item of items) {
const filteredChildren = item.children ? filterTree(item.children as T[], predicate) : [];
if (predicate(item) || filteredChildren.length > 0) {
result.push({ ...item, children: filteredChildren.length ? filteredChildren : undefined } as T);
}
}
return result;
}
export function filterTreeByLabel<T extends TreeItem>(items: T[], query: string): T[] {
const lowerQuery = query.toLowerCase();
return filterTree(items, item => item.label.toLowerCase().includes(lowerQuery));
}
/**
* Flatten a tree structure into a flat array of TreeItems, preserving the order
* @param items The tree structure to flatten
* @returns A flat array of TreeItems
*/
export function flattenTree<T>(items: TreeItem<T>[]): TreeItem<T>[] {
const result: TreeItem<T>[] = [];
const stack = [...items].reverse();
while (stack.length > 0) {
const node = stack.pop()!;
result.push(node);
if (node.children) {
stack.push(...[...node.children].reverse());
}
}
return result;
}