Hexlet logo

Python: Trees

Theory: Manipulating the virtual file system

The library we use to build trees is designed only for immutable file structures. It means we cannot change it once we create it. But it is possible to make a new one based on the old one and modify some parts.

We deliberately chose to use an immutable structure for this course. This structure is easier to debug, and you're less likely to make mistakes. And it allows you to immerse yourself as much as possible in higher-order functions.

Basic operations with nodes

The python-immutable-fs-trees package allows you to create trees and extract data from previously created files and directories. It means you don't have to crawl through the internal structure of the tree itself:

from hexlet import fs
tree = fs.mkdir('/', [fs.mkfile('hexlet.log')], {'hidden': True})
fs.get_name(tree)
# '/'
fs.get_meta(tree).get('hidden')
# True
[file] = fs.get_children(tree)
fs.get_name(file)
# 'hexlet.log'
fs.get_meta(file).get('unknown')

# Don't do this
# Files have no children
fs.get_children(file)

Additionally, the package has two functions for checking types. Using them, you can selectively work with files and directories:

from hexlet import fs
tree = fs.mkdir('/', [fs.mkfile('hexlet.log')], {'hidden': True})
fs.is_directory(tree)
# True
fs.is_file(tree)
# False
[file] = fs.get_children(tree)
fs.is_file(file)
# True
fs.is_directory(file)
# False

The operations we have looked at are enough to perform any transformations on files and directories. Let us start with the simplest ones, which don't require recursive traversal.

Processing

Any processing in an immutable style boils down to new data formation based on old ones. Below, we'll implement some conversion options that say more about this idea. Changing the file name looks like this:

from hexlet import fs
import copy

file = fs.mkfile('one', {'size': 35})
# It is important to keep the metadata when renaming
new_meta = copy.deepcopy(fs.get_meta(file))
new_file = fs.mkfile('new name', new_meta)

A new file is created here with the metadata of the old. Before we created a new file, we cloned metadata by deep cloning. Why? We pass dictionaries by reference. If we do not clone, the new file will contain the metadata of the old one. If we want to change something, changing the new one means breaking the old one:

file = fs.mkfile('one', {'size': 35})
new_meta = fs.get_meta(file)
new_meta['size'] = 15
new_file = fs.mkfile('new name', new_meta)
fs.get_meta(new_file)
# {'size': 15}

# The metadata has changed
fs.get_meta(file)
# {'size': 15}

Sorting the contents of a directory looks like this:

tree = fs.mkdir('/', [
    fs.mkfile('one'),
    fs.mkfile('two'),
    fs.mkdir('three'),
])

children = fs.get_children(tree)
new_meta = copy.deepcopy(fs.get_meta(tree))
# The `reverse` function changes the array, so we clone
new_children = children[:]
# Sorting in reverse order and expanding the list
new_children.reverse()
tree2 = fs.mkdir(fs.get_name(tree), new_children, new_meta)
list(map(fs.get_name, fs.get_children(tree2)))
# ['three', 'two', 'one']

Updating the contents of a directory looks like this:

tree = fs.mkdir('/', [
    fs.mkfile('oNe'),
    fs.mkfile('Two'),
    fs.mkdir('THREE'),
])

# We see lowercase directory and file names within a specific directory here
def to_lower(node):
    name = fs.get_name(node)
    new_meta = copy.deepcopy(fs.get_meta(node))
    if fs.is_directory(node):
        return fs.mkdir(name.lower(), fs.get_children(node), new_meta)
    return fs.mkfile(name.lower(), new_meta)

children = fs.get_children(tree)
new_children = list(map(to_lower, children))
# Don't forget to copy the metadata
new_meta = copy.deepcopy(fs.get_meta(tree))
tree2 = fs.mkdir(fs.get_name(tree), new_children, new_meta)
list(map(fs.get_name, fs.get_children(tree2)))
# ['one', 'two', 'three']

Deleting files within a directory looks like this:

tree = fs.mkdir('/', [
    fs.mkfile('one'),
    fs.mkfile('two'),
    fs.mkdir('three'),
])

children = fs.get_children(tree)
new_children = list(filter(fs.is_directory, children))
new_meta = copy.deepcopy(fs.get_meta(tree))
fs.mkdir(fs.get_name(tree), new_children, new_meta)
# {'name': '/', 'children': [{'name': 'three', 'children': [], 'meta': {},
# 'type': 'directory'}], 'meta': {}, 'type': 'directory'}