LeetCode 588. Design In Memory File System
原题链接
困难
作者:
JasonSun
,
2020-02-19 13:18:17
,
所有人可见
,
阅读 1041
Algorithm (Design, Implementation)
- We model file or dir as node in a tree. The inspiration for which comes from Linux’s file system design (for more information see http://www.linfo.org/inode.html). At each node we store four values:
name
: the name of the file or dir
content
: the content of the file (if it is a file)
is_file
: a flag indicating if the current file object is a file or not
links
: a map
storing subdirectories and files in this directory, provided that the current file object is a folder.
- Then
mkdir
, ls
, addContentToFile
and readContentFromFile
could be implemented in a traditional depth first search manner.
- In order to facilitate the parsing of the file/dir path, we use a simple tokenizer to assist the depth first search. For more details, see the actual implementation.
- Memory safety is taken care of by using an
std::unique_ptr
Code (Cpp17)
class tokenizer {
private:
string data_;
int cursor_;
public:
tokenizer(const string& str) : data_(str), cursor_(0){};
private:
void ready() {
if (data_[cursor_] == ' ' and cursor_ + 1 < size(data_)) {
cursor_++;
ready();
}
}
char read() { return data_[cursor_++]; };
public:
bool has_next() { return cursor_ < size(data_); }
char peek() { return cursor_ < size(data_) ? data_[cursor_] : '\n'; };
void consume() { read(); };
template <typename T, typename std::enable_if_t<std::is_same_v<string, T>>* = nullptr>
T next() {
ready();
string result{};
while (has_next() and isalpha(peek()))
result.push_back(read());
return result;
}
template <typename T, typename std::enable_if_t<std::is_same_v<int, T>>* = nullptr>
T next() {
ready();
int acc = 0;
while (has_next() and isdigit(peek()))
acc = (acc * 10) + read() - '0';
return acc;
}
};
struct inode_t {
std::string name;
std::unordered_map<std::string, std::unique_ptr<inode_t>> links;
bool is_file;
std::string content;
};
class FileSystem {
private:
std::unique_ptr<inode_t> root;
public:
FileSystem() : root(new inode_t{}){ root.get()->links["/"] = std::make_unique<inode_t>(); }
vector<string> ls(string path) {
auto tokens = tokenizer(path);
std::function<std::vector<std::string>(inode_t*)> go = [&](inode_t* node) {
if (not tokens.has_next()) {
const auto files = [&](std::vector<std::string> self = {}) {
for (const auto & [name, _] : node->links)
self.emplace_back(name);
if (node->is_file)
self.emplace_back(node->name);
std::sort(std::begin(self), std::end(self));
return self;
}();
return files;
}
else if (tokens.peek() == '/' and node == root.get())
return tokens.consume(), go(node->links["/"].get());
else if (tokens.peek() == '/' and node != root.get())
return tokens.consume(), go(node);
else if (isalpha(tokens.peek()))
return go(node->links[tokens.next<string>()].get());
throw std::domain_error("unmatched ls");
};
return go(root.get());
}
void mkdir(string path) {
auto tokens = tokenizer(path);
std::function<void(inode_t*)> go = [&](inode_t* node) {
if (not tokens.has_next())
return;
else if (tokens.peek() == '/' and node == root.get())
tokens.consume(), go(node->links["/"].get());
else if (tokens.peek() == '/' and node != root.get())
tokens.consume(), go(node);
else if (isalpha(tokens.peek())) {
const auto dir_name = tokens.next<string>();
if (node->links.find(dir_name) == std::end(node->links))
node->links[dir_name] = std::unique_ptr<inode_t>{new inode_t{dir_name}};
go(node->links[dir_name].get());
}
};
go(root.get());
}
void addContentToFile(string filePath, string content) {
auto tokens = tokenizer(filePath);
std::function<void(inode_t*)> go = [&](inode_t* node) {
if (not tokens.has_next()) {
if (not node->is_file) {
node->is_file = true;
node->content = content;
}
else
for (const char ch : content)
node->content.push_back(ch);
}
else if (tokens.peek() == '/' and node == root.get())
tokens.consume(), go(node->links["/"].get());
else if (tokens.peek() == '/' and node != root.get())
tokens.consume(), go(node);
else if (isalpha(tokens.peek())) {
const auto dir_name = tokens.next<string>();
if (node->links.find(dir_name) == std::end(node->links))
node->links[dir_name] = std::unique_ptr<inode_t>{new inode_t{dir_name}};
go(node->links[dir_name].get());
}
};
go(root.get());
}
string readContentFromFile(string filePath) {
auto tokens = tokenizer(filePath);
std::function<std::string(inode_t*)> go = [&](inode_t* node) {
if (not tokens.has_next())
return node->is_file ? node->content : std::string{};
else if (tokens.peek() == '/' and node == root.get())
return tokens.consume(), go(node->links["/"].get());
else if (tokens.peek() == '/' and node != root.get())
return tokens.consume(), go(node);
else if (isalpha(tokens.peek()))
return go(node->links[tokens.next<string>()].get());
throw std::domain_error("unmatched case");
};
return go(root.get());
}
};