Ищем элегантный дизайн представления данных для дерева каталогов

Question

Я ищу совет по Элегантный дизайн для представления каталога файлов без символических ссылок в Python, где я могу запросить отношения в терминах «принадлежит» (например, G является подкаталог/A/B/C). Мое нынешнее мышление идет в этом направлении:

Путь к корню I os.path.walk() сверху вниз. Два класса представляют типы узлов, которые меня интересуют, и я отслеживаю родительские дочерние отношения.

class ADir(object): 
    def __init_(self, name, parent=None): 
     self.name = name 
     self.parent = parent 
     self.children = [] 
    def add_child(self, id): 
     self.children.append(id) 

class AFile(object): 
    def __init_(self, name, parent=None): 
     self.name = name 
     self.parent = parent 

я бы повторно осуществить проверку для существующих каталогов, функций, которые дают мне позицию каталог/файл и т.д. Это все начинает чувствовать себя очень похож на переопределённом существующие, общие алгоритмы дерева.

Траулинг-лоток StackExchange, Google и т. Д. Дает множество различных подходов. Ничто из того, что я нашел, похоже, не использует естественные границы, заданные структурой каталогов.

Любые мысли и указатели на обсуждения, записи в блогах и код оцениваются.

Answer 1

Проблема с древовидными структурами на современных языках состоит в том, что трудно создать одну структуру, соответствующую всем этим. Существует много способов создания тройки (с родительским указателем или без него, детьми могут быть пары (двоичные или красно-черные деревья) или списки (с индексированием ключей поиска и без них).

Хотя можно определить обход алгоритмы для всех из них, но каждый алгоритм нуждается в отдельной реализации.

Тогда у нас есть проблема поиска элементов в дереве. Работаем ли мы по индексу (довольно бесполезно в бинарных деревьях)? Какой-то идентификатор? идентификаторы имеют? Как мы создаем пути из этих идентификаторов? Как мы представляем относительные пути?

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

Кроме того, большинство языков OO не поддерживают достаточно способов создания классов из фрагментов существующих классов. Вы можете наследовать (но тогда вы получаете все), множественное наследование (еще больше проблем), mix in (некоторые функции множественного наследования без каких-либо недостатков). Но у меня действительно отсутствует функция, которая гласит: принять метод x() от типа Foo и метод y() от Bar для сборки Baz.

Без этого базовый класс дерева основанный на OO нуждается в большой настройке для вашего конкретного случая использования, в то время как для непосредственного внедрения той же функции потребуется такая же сумма (или даже меньше) строк кода.