Как написать функцию поиска, чтобы получить путь к нужному файлу?

удалить направление

Прежде чем мы начнем, сначала удалите множество косвенность, вызванных более чем 20 переменными. Мы можем использовать только два (2) класса и один root -

class File {
  constructor(type, name) {
    this.name = name
    this.type = type
  }
}

class Folder {
  constructor(type, name, children) {
    this.name = name
    this.type = type
    this.children = children
  }
}

const root =
  new Folder("folder", "root folder", [
    new File("file", "file a1"),
    new File("file", "file a2"),
    new Folder("folder", "folder a3", [
      new Folder("folder", "folder b1", [
        new File("file", "file c1"),
        new File("file", "file c2")
      ]),
      new File("file", "file b2"),
      new File("file", "file b3"),
      new Folder("folder", "folder b4", [
        new File("file", "file c3"),
        new File("file", "file c4"),
        new File("file", "file c5")
      ])
    ]),
    new File("file", "file a4")
  ])

удалить избыточность

TYPES.FILE и TYPES.FOLDER не нужны, если у вас есть отдельные классы File и Folder. Каждый экземпляр уже будет иметь связанный тип —

class File {
  constructor(name) { // ✅ type not necessary
    this.name = name
  }
}

class Folder {
  constructor (name, children) { // ✅ type not necessary
    this.name = name
    this.children = children
  }
}

const root =
  new Folder("root folder", [
    new File("file a1"),
    new File("file a2"),
    new Folder("folder a3", [
      new Folder("folder b1", [
        new File("file c1"),
        new File("file c2")
      ]),
      new File("file b2"),
      new File("file b3"),
      new Folder("folder b4", [
        new File("file c3"),
        new File("file c4"),
        new File("file c5")
      ])
    ]),
    new File("file a4")
  ])

несколько возвращаемых значений

Поскольку файловые системы поддерживают папки или файлы с одинаковыми именами (в разных иерархиях), важно, чтобы наш алгоритм search мог сканировать все возможных совпадений запроса. Для полного примера давайте включим file c3 в folder b1иfolder b4. При поиске этого файла мы ожидаем, что будут возвращены оба пути —

const root =
  new Folder("root folder", [
    new File("file a1"),
    new File("file a2"),
    new Folder("folder a3", [
      new Folder("folder b1", [
        new File("file c1"),
        new File("file c2"),
        new File("file c3")  // ✅ could have the same name
      ]),
      new File("file b2"),
      new File("file b3"),
      new Folder("folder b4", [
        new File("file c3"), // ✅ could have the same name
        new File("file c4"),
        new File("file c5")
      ])
    ]),
    new File("file a4")
  ])

алгоритм

Теперь, когда мы исправили другие проблемы с кодом, давайте напишем search(t, query). Мы можем сделать это, используя индуктивное мышление —

1. Если t является файлом и его name соответствует query, выдать одноэлементный результат [t]
2. (индуктивный) t не является файлом. Если t является папкой и ее name соответствует query, введите одноэлементный результат [t]. И для всех child из t.children, для всех path рекурсивной подзадачи search(child, query) добавьте t к path и уступите.
3. (индуктивная) t не является ни файлом, ни папкой. Выдать ошибку типа, чтобы уведомить вызывающую сторону.

function* search(t, query) {
  switch(t?.constructor) {
    case File:
      if (t.name == query)
        yield [t]
      break
    case Folder:
      if (t.name == query)
        yield [t]
      for (const child of t.children)
        for (const path of search(child, query))
          yield [t, ...path]
      break
    default:
      throw Error(`cannot search unsupported type ${t}`)
  }
}

Вот несколько примеров поиска -

for (const path of search(root, "root folder"))
  console.info([".", ...path.map(f => f.name)].join("/"))

./root folder

for (const path of search(root, "file a1"))
  console.info([".", ...path.map(f => f.name)].join("/"))

./root folder/file a1

Несколько путей возвращаются, когда файл или папка найдены несколько раз -

for (const path of search(root, "file c3"))
  console.info([".", ...path.map(f => f.name)].join("/"))

./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

Когда файл или папка не могут быть найдены, вывод не выдается -

for (const path of search(root, "file Q"))
  console.info([".", ...path.map(f => f.name)].join("/"))

⚠️ no output

вызывающий решает эффект

Получая последовательность объектов Folder и File, наш алгоритм search остается универсальным и пригодным для повторного использования. По умолчанию строки не собираются, и в консоль ничего не записывается. Если вызывающая сторона хочет создать путь, разделенный /, это продемонстрировано выше. Варианты другого эффекта оставляются на усмотрение вызывающего абонента.

только один результат

Использование генератора идеально подходит для search, потому что вызывающая сторона может использовать все совпадения или любое их количество. В этом примере мы используем общий first, чтобы вернуть только совпадение первый. Обратите внимание, что генератор отменяется сразу после того, как найдено совпадение, и процессор не выполняет никакой дополнительной работы.

function first(iter) {
  for (const v of iter)
    return v
}

const match = first(search(root, "file c3"))

if (match)
  console.info("found:", match.map(f => f.name).join("/"))
else
  console.error("no match found")

found: root folderfolder a3/folder b1/file c3

Убедитесь, что вы выполняете правильную проверку нуля, если используете first таким образом, поскольку возможно, что search ничего не даст, если совпадение не найдено -

const match = first(search(root, "ZZZ"))

if (match)
  console.info("found:", match.map(f => f.name).join("/"))
else
  console.error("no match found")

no match found

поиск высшего порядка

В исходном алгоритме совпадения определяются с помощью ==. Алгоритм мог бы быть более полезным, если бы мы позволили вызывающей стороне указать, что представляет собой совпадение:

function* search(t, query) {
  switch(t?.constructor) {
    case File:
      if (Boolean(query(t.name))) // ✅ query is a func
        yield [t]
      break
    case Folder:
      if (Boolean(query(t.name))) // ✅ query is a func
        yield [t]
      for (const child of t.children)
        for (const path of search(child, query))
          yield [t, ...path]
      break
    default:
      throw Error(`cannot search unsupported type ${t}`)
  }
}

Найдем все файлы, которые начинаются с file c -

for (const path of search(root, filename => filename.startsWith("file c")))
  console.info([".", ...path.map(f => f.name)].join("/"))

./root folder/folder a3/folder b1/file c1
./root folder/folder a3/folder b1/file c2
./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3
./root folder/folder a3/folder b4/file c4
./root folder/folder a3/folder b4/file c5

специализация

С помощью функции высшего порядка search вы можете легко реализовать такие вещи, как searchByString. Это известно как специализация -

function searchByString(t, query) {
  return search(t, filename => filename == query)
}

for (const path of searchByString(root, "file c3"))
  console.info([".", ...path.map(f => f.name)].join("/"))

./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

демонстрация кода

Приведенный выше код был сжат, поэтому вы можете увидеть его все в одном месте. Бежать фрагмент и проверьте вывод -

class File { constructor(name) { this.name = name } }

class Folder { constructor(name, children) { this.name = name;  this.children = children } }

function* search(t, query) {
  switch(t?.constructor) {
    case File: if (Boolean(query(t.name))) yield [t];  break
    case Folder: if (Boolean(query(t.name))) yield [t]; for (const child of t.children) for (const path of search(child, query)) yield [t, ...path]; break
    default: throw Error(`cannot search unsupported type ${t}`)
  }
}

function searchByString(t, query) {
  return search(t, filename => filename == query)
}

const relative = (path) => [".", ...path.map(f => f.name)].join("/")

const root = new Folder("root folder", [new File("file a1"), new File("file a2"), new Folder("folder a3", [new Folder("folder b1", [new File("file c1"), new File("file c2"), new File("file c3")]), new File("file b2"), new File("file b3"), new Folder("folder b4", [new File("file c3"), new File("file c4"), new File("file c5")])]), new File("file a4")])

console.info("== exact match = = ")
for (const path of search(root, filename => filename == "root folder"))
  console.info(relative(path))

console.info("== starts with 'file c' = = ")
for (const path of search(root, filename => filename.startsWith("file c")))
  console.info(relative(path))

console.info("== searchByString = = ")
for (const path of searchByString(root, "file c3"))
  console.info(relative(path))

.as-console-wrapper { min-height: 100%; top: 0; }

== exact match ==
./root folder
== starts with 'file c' ==
./root folder/folder a3/folder b1/file c1
./root folder/folder a3/folder b1/file c2
./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3
./root folder/folder a3/folder b4/file c4
./root folder/folder a3/folder b4/file c5
== searchByString ==
./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

питон

search точно так же написано на Python -

class file:
  def __init__(self, name):
    self.name = name

class folder:
  def __init__(self, name, children):
    self.name = name
    self.children = children

def search(t, query):
  if isinstance(t, file):
    if t.name == query:
      yield [t]
  elif isinstance(t, folder):
    if t.name == query:
      yield [t]
    for child in t.children:
      for path in search(child, query):
        yield [t, *path]
  else:
    raise TypeError("unsupported", t)

Если вы используете Python 3.10, вам доступны некоторые новые функции. Настройте search, чтобы воспользоваться преимуществами нового структурного синтаксиса match..case -

from dataclasses import dataclass
from typing import Generator, Union

Ftree = Union["file", "folder"]

@dataclass
class file:
  name: str

@dataclass
class folder:
  name: str
  children: list[Ftree]

def search(t: Ftree, query: str) -> Generator[list[Ftree], None, None]:
  match t:
    case file(name):
      if name == query: yield [t]
    case folder(name, children):
      if name == query: yield [t]
      for child in t.children:
        for path in search(child, query):
          yield [t, *path]
    case _:
      raise TypeError("unsupported", t)

Дано дерево -

root = \
  folder("root folder", [
    file("file a1"),
    file("file a2"),
    folder("folder a3", [
      folder("folder b1", [
        file("file c1"),
        file("file c2"),
        file("file c3")
      ]),
      file("file b2"),
      file("file b3"),
      folder("folder b4", [
        file("file c3"),
        file("file c4"),
        file("file c5")
      ])
    ]),
    file("file a4")
  ])

Обе реализации ведут себя одинаково -

for path in search(root, "root folder"):
  print("/".join([".", *map(lambda f: f.name, path)]))

./root folder

for path in search(root, "file c3"):
  print("/".join([".", *map(lambda f: f.name, path)]))

./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3