|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
1 sec |
32 MB |
Description
Terminology
- A file tree is a tree structure that organizes files and directories (folders).
- At the top, there is a special directory called the root directory, written as /.
- Current working directory, means the directory you are currently at.
- A path describes how to reach a file or a directory, you can refer to 02-basic-computing page 13 for more information about absolute path and relative path.
Task description
- You have to implement a file tree.
- You start from an empty file tree that only has a single root directory /.
- You will then receive a sequence of commands, and you need to process the commands in order, update the file tree, and print the outputs of some commands.
Notices
- EXAMPLE in the following decription are the extra sample. You can test them manualy by setting DEBUG_MODE to True.
- The command after > is the input.
- The path before > is the current working directory.
- All the
PATH mentioned in the following can be an absolute path or a relative path.
- We have modified or simplified some commands for convenience, so some details might be different from the the os module or a real file system, try not to mix them up.
TODO function
- path_to_nodes(PATH)
- Given a path, you have to return the absoulte path in a list of nodes List[Node].
- If PATH does not exist, return None.
TODO commands
- cd PATH
- Functionality:
- Change the current working directory to PATH.
- Exception:
- If PATH does not exist or is not a directory, do nothing.
-
EXAMPLE
-
Current existing directories:
/
/A
/A/B
/A/C
Commands start here:
/ > cd .. # Already in /, do nothing
/ > cd ./A
/A > cd B
/A/B > cd ..
/A > cd /D # Directory D does not exist, do nothing
/A > cd /A/C
/A/C >
- ls
- touch PATH
- PATH can be decomposed into {PARENT_PATH, FILE_NAME}.
- Functionality:
- Create a file named FILE_NAME under PARENT_PATH directory.
- Exception:
- If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
- If a file or a directory named FILE_NAME already exists under PARENT_PATH directory, do nothing.
-
EXAMPLE
-
Current existing directories:
/
/A
/A/B
Commands start here:
/ > cd A
/A > touch hi # File /A/hi is created
/A > touch /A/B/sus # File /A/B/sus is created
/A > touch /C/no # /C does not exist, do nothing
- rm PATH
PATH can be decomposed into {PARENT_PATH, FILE_NAME}- Functionality:
- Remove a file named FILE_NAME under PARENT_PATH directory.
- Exception:
- If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
- If FILE_NAME does not exists under PARENT_PATH directory, do nothing.
-
EXAMPLE
-
Current existing directories and files:
/
/A
/A/B
/A/f (file)
/A/g (file)
Commands start here:
/ > cd A
/A > rm /A/f # File /A/f is removed
/A > rm ./g # File /A/g is removed
/A > rm B # /A/B is not a file, do nothing
Template
- class Node
- Each node represents a directory or a file in the file tree.
- mkdir PATH
- PATH can be decomposed into {PARENT_PATH, DIR_NAME}
- Functionality:
- Create a directory named DIR_NAME under PARENT_PATH directory.
- Exception:
- If any nodes in PARENT_PATH does not exist or is not a directory, do nothing.
- If a file or a directory named DIR_NAME already exists under PARENT_PATH directory, do nothing.
import sys
class Node:
def __init__(self, name, is_dir, parent=None):
self.name = name
self.is_dir = is_dir
self.parent = parent
self.children = {}
class FileTree:
def __init__(self):
self.root = Node("/", True, None)
self.cwd = self.root
# !!! You can add more functions if needed !!! #
def path_to_nodes(self, path):
# TODO
pass
def mkdir(self, path):
if path.endswith('/') and len(path) > 1:
path = path[:-1]
idx = path.rfind('/')
if idx == -1:
p_path, name = ".", path
elif idx == 0:
p_path, name = "/", path[1:]
else:
p_path, name = path[:idx], path[idx+1:]
nodes = self.path_to_nodes(p_path)
if nodes:
parent = nodes[-1]
if parent.is_dir and name not in parent.children:
parent.children[name] = Node(name, True, parent)
def cd(self, path):
# TODO
pass
def ls(self):
# TODO
pass
def touch(self, path):
# TODO
pass
def rm(self, path):
# TODO
pass
# Debug functions
def print_prompt(self):
nodes = self.path_to_nodes(".")
path_str = "/" + "/".join([n.name for n in nodes[1:]])
if path_str.endswith("/") and len(path_str) > 1: path_str = path_str[:-1]
print(f"{path_str} >", end=" ", flush=True)
def print_all(self, node=None, prefix=""):
if node is None: node, prefix = self.root, ""
current = prefix + ("/" + node.name if node != self.root else "")
print(current if node.is_dir else f"{current} (file)")
if node.is_dir:
for k in sorted(node.children): self.print_all(node.children[k], current)
def main():
ft = FileTree()
# !!! Enable debug mode here !!!
# !!! Remember to disable it when submitting !!!
DEBUG_MODE = True
while True:
if DEBUG_MODE: ft.print_prompt()
try:
line = sys.stdin.readline()
if not line:
if DEBUG_MODE: print()
break
except: break
line = line.strip()
if not line: continue
p = line.split()
cmd, args = p[0], p[1:]
if cmd == 'mkdir' and len(args)==1: ft.mkdir(args[0])
elif cmd == 'cd' and len(args)==1: ft.cd(args[0])
elif cmd == 'ls' and len(args)==0: ft.ls()
elif cmd == 'touch' and len(args)==1: ft.touch(args[0])
elif cmd == 'rm' and len(args)==1: ft.rm(args[0])
elif cmd == 'print_all': ft.print_all()
if DEBUG_MODE and cmd != 'ls':
print("--- Tree ---"); ft.print_all(); print("------------")
if __name__ == "__main__":
main()
Input
- Each line contains a single command.
- Command names and arguments are separated by a single space.
- Paths never contain spaces.
- File and directory names consist only of letters and digits.
- Input is read until
EOF.
Output
Only the following command produce output:
- ls
- Print the names of all direct children (files and directories) in lexicographical order.
- Print all names on one line, separated by a single space. (No additional space after last one)
- If the directory is empty, print an empty line.