README

Чистая и гибкая PHP библиотека для построения и манипулирования древовидными структурами. Разработана с использованием принципов SOLID и чистого кода для PHP 8+.

Возможности

🌳 Универсальные N-арные деревья - создавайте деревья с любым количеством потомков
🔍 Мощная система поиска - находите узлы по различным критериям
🔄 Гибкие итераторы - обход в глубину (DFS) и в ширину (BFS)
⚡ Динамические атрибуты - добавляйте любые свойства к узлам на лету
🛡️ Типобезопасность - строгая типизация PHP 8
✅ Полностью протестировано - высокое покрытие тестами
📦 Standalone - работает независимо от фреймворков

Требования

PHP >= 8.0

Установка

composer require datastructure/tree

Быстрый старт

<?php

use DataStructure\Tree\Node;
use DataStructure\Tree\Tree;

// Создание узлов
$root = new Node('root', ['name' => 'Корневая категория']);
$electronics = new Node('electronics', ['name' => 'Электроника']);
$computers = new Node('computers', ['name' => 'Компьютеры']);

// Построение дерева
$root->addChild($electronics);
$electronics->addChild($computers);

// Создание дерева
$tree = new Tree($root);

// Количество узлов
echo $tree->count(); // 3

Основное использование

Работа с узлами

Создание узлов с динамическими атрибутами

$node = new Node('product-1', [
    'name' => 'Ноутбук',
    'price' => 1500,
    'stock' => 10
]);

// Получение атрибутов
echo $node->getAttribute('name'); // "Ноутбук"
echo $node->getAttribute('discount', 0); // 0 (значение по умолчанию)

// Установка атрибутов
$node->setAttribute('discount', 10);
$node->setAttribute('featured', true);

// Проверка наличия атрибута
if ($node->hasAttribute('price')) {
    // ...
}

// Удаление атрибута
$node->removeAttribute('stock');

Работа с иерархией

$parent = new Node('parent');
$child1 = new Node('child1');
$child2 = new Node('child2');

// Добавление потомков
$parent->addChild($child1);
$parent->addChild($child2);

// Проверки
$parent->hasChildren(); // true
$parent->isRoot();      // true
$child1->isLeaf();      // true

// Получение связей
$child1->getParent();      // $parent
$parent->getChildren();    // [$child1, $child2]

// Получение предков и потомков
$child1->getAncestors();   // Все узлы от родителя до корня
$parent->getDescendants(); // Все дочерние узлы рекурсивно

// Глубина узла
$child1->getDepth(); // 1 (корень = 0)

Работа с деревьями

Создание дерева

$root = new Node('root', ['name' => 'Каталог']);
$tree = new Tree($root);

// Или из массива
$tree = Tree::fromArray([
    'id' => 'root',
    'attributes' => ['name' => 'Каталог'],
    'children' => [
        [
            'id' => 'child1',
            'attributes' => ['name' => 'Категория 1'],
            'children' => []
        ]
    ]
]);

Обход дерева

// Обход в глубину (DFS)
foreach ($tree->traverseDepthFirst() as $node) {
    echo $node->getAttribute('name') . "\n";
}

// Обход в ширину (BFS)
foreach ($tree->traverseBreadthFirst() as $node) {
    echo $node->getAttribute('name') . "\n";
}

// Выполнение функции для каждого узла
$tree->walk(function($node) {
    $node->setAttribute('visited', true);
});

Поиск узлов

Простой поиск

// Найти первый узел
$node = $tree->find(function($node) {
    return $node->getAttribute('price') > 1000;
});

// Найти все узлы
$nodes = $tree->findAll(function($node) {
    return $node->getAttribute('category') === 'electronics';
});

// Поиск по ID
$node = $tree->findById('product-123');

// Поиск по атрибуту
$nodes = $tree->findByAttribute('status', 'active');

Расширенный поиск с критериями

use DataStructure\Tree\Search\SearchCriteria;

$criteria = (new SearchCriteria())
    ->whereAttribute('status', 'active')
    ->whereDepthGreaterThan(0)
    ->whereIsLeaf();

// Найти первый подходящий узел
$node = $tree->find($criteria->toCallable());

// Найти все подходящие узлы
$nodes = $tree->findAll($criteria->toCallable());

Доступные методы SearchCriteria

$criteria = new SearchCriteria();

// Поиск по ID
$criteria->whereId('node-123');

// Поиск по атрибуту
$criteria->whereAttribute('type', 'category');

// Проверка наличия атрибута
$criteria->whereHasAttribute('price');

// Поиск корневых узлов
$criteria->whereIsRoot();

// Поиск листовых узлов
$criteria->whereIsLeaf();

// Поиск по глубине
$criteria->whereDepth(2);
$criteria->whereDepthGreaterThan(1);
$criteria->whereDepthLessThan(3);

// Кастомное условие
$criteria->where(function($node) {
    return str_starts_with($node->getId(), 'product-');
});

// Комбинирование условий
$criteria
    ->whereAttribute('status', 'active')
    ->whereDepthGreaterThan(0)
    ->where(fn($n) => $n->getAttribute('price') < 100);

Замена данных узла

$node = $tree->findById('product-1');

// Заменить/обновить атрибуты узла
$tree->replace($node, [
    'name' => 'Новое имя',
    'price' => 1200,
    'updated_at' => time()
]);

// Старые атрибуты сохраняются, новые добавляются/обновляются

Дополнительные методы дерева

// Подсчет всех узлов
$tree->count(); // 15

// Максимальная глубина дерева
$tree->getMaxDepth(); // 3

// Получение всех листовых узлов
$leaves = $tree->getLeaves();

// Получение узлов на определенной глубине
$level2Nodes = $tree->getNodesAtDepth(2);

// Проверка существования узла
$exists = $tree->exists(fn($n) => $n->getId() === 'target-id');

// Преобразование в массив
$array = $tree->toArray();

Примеры использования

Пример 1: Каталог товаров

use DataStructure\Tree\Node;
use DataStructure\Tree\Tree;

// Создание структуры каталога
$catalog = new Node('catalog', ['name' => 'Каталог']);
$electronics = new Node('electronics', ['name' => 'Электроника', 'active' => true]);
$computers = new Node('computers', ['name' => 'Компьютеры', 'active' => true]);
$laptops = new Node('laptops', ['name' => 'Ноутбуки', 'active' => true]);

$catalog->addChild($electronics);
$electronics->addChild($computers);
$computers->addChild($laptops);

$tree = new Tree($catalog);

// Поиск активных категорий
$activeCategories = $tree->findAll(fn($n) => $n->getAttribute('active') === true);

// Получение всех подкатегорий электроники
$electronics = $tree->findById('electronics');
$subcategories = $electronics->getDescendants();

Пример 2: Организационная структура

$ceo = new Node('ceo', ['name' => 'CEO', 'salary' => 200000]);
$cto = new Node('cto', ['name' => 'CTO', 'salary' => 150000]);
$developer1 = new Node('dev1', ['name' => 'Senior Developer', 'salary' => 100000]);
$developer2 = new Node('dev2', ['name' => 'Junior Developer', 'salary' => 60000]);

$ceo->addChild($cto);
$cto->addChild($developer1);
$cto->addChild($developer2);

$tree = new Tree($ceo);

// Найти всех с зарплатой больше 80000
$highEarners = $tree->findAll(fn($n) => $n->getAttribute('salary') > 80000);

// Получить всех подчиненных CTO
$ctoNode = $tree->findById('cto');
$subordinates = $ctoNode->getDescendants();

Пример 3: Система меню

$menu = new Node('main-menu', ['label' => 'Главное меню']);
$home = new Node('home', ['label' => 'Главная', 'url' => '/', 'visible' => true]);
$products = new Node('products', ['label' => 'Товары', 'url' => '/products', 'visible' => true]);
$sale = new Node('sale', ['label' => 'Распродажа', 'url' => '/sale', 'visible' => true]);

$menu->addChild($home);
$menu->addChild($products);
$products->addChild($sale);

$tree = new Tree($menu);

// Получить только видимые пункты меню
$visibleItems = $tree->findAll(fn($n) => $n->getAttribute('visible') === true);

// Обновить URL
$saleNode = $tree->findById('sale');
$tree->replace($saleNode, ['url' => '/special-sale', 'highlight' => true]);

Тестирование

# Установка зависимостей
composer install

# Запуск тестов
./vendor/bin/phpunit

# Запуск с покрытием
./vendor/bin/phpunit --coverage-html coverage

Архитектура

Библиотека следует принципам SOLID и чистого кода:

Single Responsibility: Каждый класс имеет одну ответственность
Open/Closed: Легко расширяется через интерфейсы
Liskov Substitution: Все реализации соответствуют контрактам
Interface Segregation: Интерфейсы разделены по функциональности
Dependency Inversion: Зависимости от абстракций, а не от реализаций

Структура проекта

src/
├── NodeInterface.php          # Интерфейс узла
├── Node.php                   # Реализация узла
├── TreeInterface.php          # Интерфейс дерева
├── Tree.php                   # Реализация дерева
├── Iterator/
│   ├── DepthFirstIterator.php  # Обход в глубину
│   └── BreadthFirstIterator.php # Обход в ширину
├── Search/
│   ├── SearchCriteria.php      # Построитель критериев поиска
│   └── NodeSearcher.php        # Поисковик узлов
└── Exception/
    ├── TreeException.php       # Базовое исключение
    └── NodeNotFoundException.php # Исключение "узел не найден"

Производительность

Эффективные алгоритмы обхода с использованием итераторов
Ленивая инициализация поисковика
Минимальное потребление памяти
Защита от циклических ссылок

Лицензия

MIT License

Автор

Edige

Вклад

Приветствуются pull requests! Для больших изменений сначала откройте issue для обсуждения предлагаемых изменений.

datastructure/tree

包简介

关键字：

README 文档