Как сделать дерево чекбоксов, храня дерево в Map

Question

Как сделать дерево чекбоксов, храня дерево в Map

Рейтинг: 2Ответов: 1Опубликовано: 12.03.2023

Я захотел разобраться как создавать дерево чекбоксов с нуля. Написал вот такое и у меня возникла проблема.

Я придумал хранить дерево в виде Map<string, TreeNode>, где string - это id, а TreeNode - узел дерева, который имеет свойство parent - null или свойство id, ссылающийся на другой элемент в Map.
Также у TreeNode присутствует свойство child: string[], массив id, по этим id также можно получить элементы из Map по id.

Проблема: не могу засунуть детей(child) на правильный уровень вложенности. Получается, что у узлов первого уровня(level: 0)в child присутствует не узлы первого уровня(level: 1), а все узлы, которые ниже идут в детей.

Вот функция для генерации дерева:

private generateTree(data: TreeData, level: number, parentKey: string | null, treeParent: Map<string, TreeNode> | null): Map<string, TreeNode> {
    const tree = treeParent === null ? new Map<string, TreeNode>() : treeParent;

    for (const key in data) {
        const dataItem = data[key];
        const id = window.crypto.randomUUID();
        const parent = parentKey === null ? null : parentKey;
        const state: TreeNodeState = 'unchecked';
        let child: string[] = [];

        if (Array.isArray(dataItem) && dataItem.length > 0) {
            child = this.generateChildIdNodes(dataItem, level + 1, id, tree);
        } else if (dataItem !== null && typeof dataItem === 'object' && !Array.isArray(dataItem)) {
            const childTree = this.generateTree(dataItem, level + 1, id, new Map());
            child = [...childTree.keys()];

            for (const [key, value] of childTree) {

                if (value.level === level + 1) {
                    tree.set(key, value);
                }
            }
        }

        tree.set(id, {
            id,
            name: key,
            level,
            state,
            parent,
            child
        });
    }

    return tree;
}

Если из этого for убрать if и делать tree.set без проверок, то получается эта ситуация, что дети получаются все, включая других вложенных детей. Если оставить - получается так, что я получаю узлы 0 уровня правильно, в детях получаю правильно узлы первого уровня, но дальше детей нету

for (const [key, value] of childTree) {
    if (value.level === level + 1) {
        tree.set(key, value);
    }
}

angular-tree.types.ts Типизация

export interface TreeNode {
    id: string;
    name: string;
    state: TreeNodeState,
    level: number;
    parent: string | null;
    child: string[];
}

export interface TreeNestedNode {
    id: string;
    name: string;
    state: TreeNodeState,
    level: number;
    parent: TreeNestedNode | null;
    child: TreeNestedNode[];
}

export type TreeNodeState = 'checked' | 'unchecked' | 'indeterminate';
export type TreeNodeStateEditable = 'checked' | 'unchecked';

export type TreeData = {
    [key: string]: null | string[] | TreeData;
};

angular-tree.component.ts - Инициализация сервиса

import { Component, OnInit } from '@angular/core';
import { TreeData, TreeNode } from './angular-tree.types';
import { TreeGeneratorService } from './services/tree-generator.service';


@Component({
    selector: 'app-angular-tree',
    templateUrl: './angular-tree.component.html',
    styleUrls: ['./angular-tree.component.scss']
})
export class AngularTreeComponent implements OnInit {

    private treeData: TreeData = {
        Groceries: {
            'Almond Meal flour': null,
            'Organic eggs': null,
            'Protein Powder': null,
            Fruits: {
                Apple: null,
                Berries: ['Blueberry', 'Raspberry'],
                Orange: null,
            },
        },
        Reminders: ['Cook dinner', 'Read the Material Design spec', 'Upgrade Application to Angular'],
        Tasks: null
    }

    constructor(
        private treeGeneratorService: TreeGeneratorService
    ) { }

    ngOnInit(): void {
        const tree = this.treeGeneratorService.initTree(this.treeData);

        this.treeGeneratorService.nestedTree$.subscribe(nestedNodes => {
            console.log(nestedNodes);
        });

        (window as any).treeGeneratorService = this.treeGeneratorService;

    }

}

tree-generator.service.ts Логика

import { Injectable } from '@angular/core';
import { BehaviorSubject, Observable } from 'rxjs';
import { TreeData, TreeNestedNode, TreeNode, TreeNodeState, TreeNodeStateEditable } from '../angular-tree.types';

@Injectable({
    providedIn: 'root'
})
export class TreeGeneratorService {
    constructor() { }

    private _subjTree: BehaviorSubject<Map<string, TreeNode> | null> = new BehaviorSubject<Map<string, TreeNode> | null>(null);
    private _subjNestedTree: BehaviorSubject<TreeNestedNode[]> = new BehaviorSubject<TreeNestedNode[]>([]);
    public nestedTree$: Observable<TreeNestedNode[]> = this._subjNestedTree.asObservable();
    private tree: Map<string, TreeNode> | null = null;

    public initTree(data: TreeData): Map<string, TreeNode> {
        this.tree = this.generateTree(data, 0, null, null);

        this.updateTree();

        return this.tree;
    }

    private generateTree(data: TreeData, level: number, parentKey: string | null, treeParent: Map<string, TreeNode> | null): Map<string, TreeNode> {
        const tree = treeParent === null ? new Map<string, TreeNode>() : treeParent;

        for (const key in data) {
            const dataItem = data[key];
            const id = window.crypto.randomUUID();
            const parent = parentKey === null ? null : parentKey;
            const state: TreeNodeState = 'unchecked';
            let child: string[] = [];

            if (Array.isArray(dataItem) && dataItem.length > 0) {
                child = this.generateChildIdNodes(dataItem, level + 1, id, tree);
            } else if (dataItem !== null && typeof dataItem === 'object' && !Array.isArray(dataItem)) {
                const childTree = this.generateTree(dataItem, level + 1, id, new Map());
                child = [...childTree.keys()];

                for (const [key, value] of childTree) {

                    if (value.level === level + 1) {
                        tree.set(key, value);
                    }
                }
            }

            tree.set(id, {
                id,
                name: key,
                level,
                state,
                parent,
                child
            });
        }

        return tree;
    }

    private generateChildIdNodes(data: string[], level: number, parentKey: string, tree: Map<string, TreeNode>): string[] {
        const flatNodesId: string[] = [];

        for (const item of data) {

            const id = window.crypto.randomUUID();
            const state: TreeNodeState = 'unchecked';

            const flatNode = {
                id,
                name: item,
                level,
                state,
                parent: parentKey,
                child: []
            };

            tree.set(id, flatNode);
            flatNodesId.push(id);
        }

        return flatNodesId;
    }

    public getNodeById(idNode: string): TreeNode | null {
        if (this.tree === null) return null;
        const node = this.tree.get(idNode);

        return node === undefined ? null : node;
    }

    public getChildNodesFromTree(idNode: string): TreeNode[] {
        const tree = this.tree;
        if (tree === null) return [];
        const node = this.getNodeById(idNode);

        if (node === null || node.child.length === 0) return [];

        const childNodes = node.child.map(idChild => tree.get(idChild)).filter(item => item !== undefined) as TreeNode[];
        return childNodes;
    }

    public getParentNodeFromTree(idNode: string): TreeNode | null {
        const tree = this.tree;
        if (tree === null) return null;
        const node = this.getNodeById(idNode);

        if (node === null || node.parent === null) return null;

        const parentNode = this.getNodeById(node.parent);

        if (parentNode === null) return null;

        return parentNode;
    }

    public getNodesFromTreeByLevel(level: number): TreeNode[] {
        const tree = this.tree;
        if (tree === null) return [];
        const nodes = [];

        for (const [key, value] of tree) {
            const node = this.getNodeById(key);

            if (node === null) continue;
            if (node.level === level) {
                nodes.push(node);
            }
        }

        return nodes;
    }

    private updateTree(): void {
        const tree = this.tree;
        if (tree === null) return;

        this._subjNestedTree.next(this.getNestedTree());
        this._subjTree.next(tree);
    }

    public getNestedTree(): TreeNestedNode[] {
        const tree = this.tree;
        if (tree === null) return [];

        const nodesFromLevel0: TreeNode[] = this.getNodesFromTreeByLevel(0);
        const nestedNodes = nodesFromLevel0.map(flatNode => this.createNestedNode(flatNode, null));

        return nestedNodes;
    }

    /**
     * Создаёт вложенный узёл, идёт строго вниз, создавая вложенные узлы в child, не идёт наверх в parent, но создаёт в parent ссылку на родителельский вложенный(nested) узел
    */
    private createNestedNode(node: TreeNode, parentNestedNode: TreeNestedNode | null): TreeNestedNode {
        const nestedNode: TreeNestedNode = {
            id: node.id,
            name: node.name,
            state: node.state,
            level: node.level,
            child: [],
            parent: parentNestedNode
        };

        const childFlatNodes = this.getChildNodesFromTree(node.id);
        const childNestedNodes = childFlatNodes.map(flatNode => this.createNestedNode(flatNode, nestedNode));
        nestedNode.child = [...childNestedNodes];

        return nestedNode;
    }

    public setState(idNode: string, state: TreeNodeStateEditable): void {
        const tree = this.tree;
        if (tree === null) return;
        const node = this.getNodeById(idNode);

        if (node === null) return;

        if (state === 'checked') {
            node.state = 'checked';
            tree.set(node.id, node);
            this.setStateChildNodes(node, state);
            this.setStateParentNodes(node);
        } else if (state === 'unchecked') {
            node.state = 'unchecked';
            tree.set(node.id, node);
            this.setStateChildNodes(node, state);
            this.setStateParentNodes(node);
        }

        this.updateTree();
    }

    private setStateChildNodes(node: TreeNode, state: TreeNodeStateEditable): void {
        const tree = this.tree;
        if (tree === null) return;
        if (node.child.length === 0) return;

        const childNodes = this.getChildNodesFromTree(node.id);

        for (const childNode of childNodes) {
            childNode.state = state;
            tree.set(childNode.id, childNode);
            this.setStateChildNodes(childNode, state);
        }
    }

    private setStateParentNodes(node: TreeNode): void {
        const tree = this.tree;
        if (tree === null) return;
        const parentNode = this.getParentNodeFromTree(node.id);

        if (parentNode === null) return;

        const childNodes = this.getChildNodesFromTree(parentNode.id);
        let parentNodeState: TreeNodeState | null = null;
        const checkedChildNodesCount = childNodes.reduce((acc, curr) => curr.state === 'checked' ? acc + 1 : acc, 0);
        const uncheckedChildNodesCount = childNodes.reduce((acc, curr) => curr.state === 'unchecked' ? acc + 1 : acc, 0);
        const indeterminateChildNodesCount = childNodes.reduce((acc, curr) => curr.state === 'indeterminate' ? acc + 1 : acc, 0);

        if (indeterminateChildNodesCount > 0) {
            parentNodeState = 'indeterminate';
        } else if (checkedChildNodesCount > 0 && uncheckedChildNodesCount > 0) {
            parentNodeState = 'indeterminate';
        } else if (checkedChildNodesCount === childNodes.length) {
            parentNodeState = 'checked';
        } else if (uncheckedChildNodesCount === childNodes.length) {
            parentNodeState = 'unchecked';
        }

        if (parentNodeState === null) return;

        parentNode.state = parentNodeState;
        tree.set(parentNode.id, parentNode);
        this.setStateParentNodes(parentNode);
    }

}

javascript typescript алгоритм angular рекурсия

Источник: Stack Overflow на русском

Answer 1

▲ 3Принят

Раз уж начал отвечать, пришлось ставить node, npm, angular CLI, vscode и прочую шелуху, чтобы разобраться, что у вас в коде творится =)

Напутали вы сильно довольно. Во первых, вы все узлы держите в одной мапе. С одной стороны, кажется, что здесь

const childTree = this.generateTree(dataItem, level + 1, id, new Map());

вы создаете новую мапу, но сразу же ниже

tree.set(key, value);

вы из дочерней мапы скидываете узлы в родительскую, потому узлы с третьего уровня попадают в узлы первго уровня. Если уже рассуждать логически, то вам вместо

if (value.level === level + 1)

надо писать

if (value.parent === id)

что чуть чуть улучшит ситуацию, но не на сильно много =)

С вашего позволения, я немного порефачил ваш код.

Во первых, вообще не вижу какого то смысла в дочерних-родительских хештаблицах. Потому я сделал одну таблицу на все узлы.

Во вторых, вообще никакого смысла методу generateTree возвращать хеш таблицу, потому он будет возвращать массив айдишников узлов, что он создаст - это поможет заполнить child (увидите в коде).

Ну и пару тройку еще изменений, косметических.

Теперь метод генерации дерева выглядит так (пардоньте за качество кода, я в ваших тайпскиптах не силен, как и во фронтендах)

private generateTree(data: TreeData, level: number, parent: string | null, tree: Map<string, TreeNode>): string[] {
    const ret: string[] = [];

    for (const key in data) {
        const dataItem = data[key];
        const id = window.crypto.randomUUID();
        let child: string[] = [];

        if (Array.isArray(dataItem)) {
            child = this.generateChildIdNodes(dataItem, level + 1, id, tree);
        } else if (dataItem !== null && typeof dataItem === 'object') {
            child = this.generateTree(dataItem, level + 1, id, tree);
        }

        ret.push(id);

        tree.set(id, {
            id,
            name: key,
            level,
            state: 'unchecked',
            parent,
            child
        });
    }

    return ret;
}

Инициализация дерева тоже чуть поменяется, вот так

public initTree(data: TreeData): Map<string, TreeNode> {
    this.tree = new Map();
    this.generateTree(data, 0, null, this.tree);
    this.updateTree();
    return this.tree;
}

Ну и все, результат в консоли

Вариант с "чистой" функцией. Лично я в нем смысла не вижу особо да и медленней он, но должен сработать

public initTree(data: TreeData): Map<string, TreeNode> {
    this.tree = this.generateTree(data, 0, null);   
    this.updateTree();
    return this.tree;
}

private generateTree(data: TreeData, level: number, parent: string | null) : Map<string, TreeNode> {
    const tree: Map<string, TreeNode> = new Map();

    for (const key in data) {
        const dataItem = data[key];
        const id = window.crypto.randomUUID();
        let child: string[] = [];           

        if (Array.isArray(dataItem)) {              
            child = this.generateChildIdNodes(dataItem, level + 1, id, tree);               
        } else if (dataItem !== null && typeof dataItem === 'object') {
            let childTree = this.generateTree(dataItem, level + 1, id);
            for (const [key, value] of childTree) {
                tree.set(key, value);
                if (value.parent === id) child.push(key);
            }
        }           

        tree.set(id, {
            id,
            name: key,
            level,
            state: 'unchecked',
            parent,
            child
        });
    }
    
    return tree;
}

p.s.

На будущее, хотелось бы попросить вас добавлять только релевантный код в вопрос. Например, в данном случае, не было необходимости добавлять сюда ангуляр, простого тайпскрипта с коротенькой инструкцией как его скопилить и запустить хватило бы за глаза, тем более, что никакого UI тут нет - чисто вывод в консольку. Подробнее можно почитать тут Как создать минимальный, самодостаточный и воспроизводимый пример

Как сделать дерево чекбоксов, храня дерево в Map

Ответы