Ищу элегантный дизайн представления данных для дерева каталогов - PullRequest
Новая
       6

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

3 голосов
/ 07 марта 2012

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

При заданном корневом пути я 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

Мне бы пришлось заново реализовать проверки для существующих каталогов, функции, которые дают мне позицию каталога/ file и т. д. Все это начинает ощущаться как переопределение существующих общих алгоритмов Tree.

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

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

1 Ответ

2 голосов
/ 07 марта 2012

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

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

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

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

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

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

...