CCF-CSP202012-3带配额的文件系统

是全英文计算机组成原理前两周的作业，花了我快一周了

（好难xd

我自己写的代码：

#include <deque>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <utility>
using std::cin;
using std::cout;
typedef long long ll;

std::deque<std::string> &decodeFilePath(std::deque<std::string> &filePaths,
                                        const std::string &inputFilePaths) {
  std::stringstream ss(inputFilePaths);
  while (ss.good()) {
    std::string tempStr;
    std::getline(ss, tempStr, '/');
    filePaths.push_back(tempStr);
  }
  filePaths.pop_front();
  // this represent root
  if (filePaths.front() == "") {
    filePaths.clear();
  }
  return filePaths;
}

struct File {
  std::string fileName;
  ll size, sizeD = 0, sizeR = 0;
  ll LD = 0, LR = 0;
  File *parent = nullptr;
  std::unordered_map<std::string, File *> child;
  bool isFolder = true;

  // true: it is folder, false: not a folder
  File(std::string fileName, File *parent, bool isFolder, ll size = 0)
      : fileName(std::move(fileName)), parent(parent), isFolder(isFolder),
        size(size) {}
  ~File() {
    parent = nullptr;
    if (child.empty()) {
      return;
    }
    // if child is not empty
    for (auto &pair : child) {
      delete pair.second;
    }
    child.clear();
  }
};

inline bool isLDSatisfied(File *filePtr, ll size) {
  return (filePtr->LD == 0) || (filePtr->sizeD + size <= filePtr->LD);
}

bool isLRSatisfied(File *filePtr, ll size) {
  // if nullptr return true since is has no parents and it child root is already
  // satisfied.
  if (filePtr == nullptr) {
    return true;
  }
  // if itself dont satisfy
  if (filePtr->LR && (filePtr->sizeR + size > filePtr->LR)) {
    return false;
  }
  // find if it parent satisfy
  return isLRSatisfied(filePtr->parent, size);
}

bool create(File *filePtr, std::deque<std::string> &filePath, ll size) {
  // if its null
  if (filePtr == nullptr) {
    return false;
  }

  auto it = filePtr->child.find(filePath.front());
  // exit
  if (filePath.size() == 1) {
    // if found a file
    bool isSizeCheck = false;
    if (it != filePtr->child.end()) {
      // if its a folder
      if (it->second->isFolder) {
        // cannot replace folder
        return false;
      }
      // otherwise it is a normal file
      // see if it satisfies LD & LR before deleting it
      // the size is assumed that we have deleted it
      if (!(isLDSatisfied(filePtr, size - it->second->size) &&
            isLRSatisfied(filePtr, size - it->second->size))) {
        return false;
      }
      // we want to represent if its checked
      isSizeCheck = true;
      ll itSize = it->second->size;
      filePtr->sizeD -= itSize;
      // recursively substract the size
      File *tempPtr = filePtr;
      while (tempPtr != nullptr) {
        tempPtr->sizeR -= itSize;
        tempPtr = tempPtr->parent;
      }

      delete it->second;
      filePtr->child.erase(it);
    }

    // if not found a file, we will create a new one.
    // find if it satisfy LD and LR
    if (!(isSizeCheck ||
          (isLDSatisfied(filePtr, size) && isLRSatisfied(filePtr, size)))) {
      // not qualified
      return false;
    }

    filePtr->child.insert(
        {filePath.front(), new File(filePath.front(), filePtr, false, size)});
    // add size D and R in filePtr (folder)

    filePtr->sizeD += size;
    File *tempPtr = filePtr;
    while (tempPtr != nullptr) {
      tempPtr->sizeR += size;
      tempPtr = tempPtr->parent;
    }
    return true;
  }

  // non exit
  // dont find a file (folder or normal file)
  if (it == filePtr->child.end()) {
    // to create a new folder and go into it
    filePtr->child.insert(
        {filePath.front(), new File(filePath.front(), filePtr, true)});

    // get into next folder
    std::string tempStr = filePath.front();
    filePath.pop_front();
    // if insucessful
    if (create((filePtr->child)[tempStr], filePath, size) == false) {
      auto deleteIt = filePtr->child.find(tempStr);
      delete deleteIt->second;
      filePtr->child.erase(deleteIt);
      return false;
    }
    // if created sucessfully.
    return true;
  }

  // if a file is found
  // if its a normal file, path dont exist
  if (it->second->isFolder == false) {
    return false;
  }

  // if it is a folder, go to next level
  std::string temp = filePath.front();
  filePath.pop_front();
  return create(filePtr->child.find(temp)->second, filePath, size);
}

bool remove(File *filePtr, std::deque<std::string> &filePaths) {
  if (filePtr == nullptr) {
    return false;
  }

  auto it = filePtr->child.find(filePaths.front());
  // if not found a file
  if (it == filePtr->child.end()) {
    // do nothing
    return true;
  }

  // if found

  // the exit
  if (filePaths.size() == 1) {
    ll size;
    // if found file is a normal file
    if (it->second->isFolder == false) {
      size = it->second->size;
      filePtr->sizeD -= size;
    } else { // it is a folder
      size = it->second->sizeR;
    }

    // recursively substract size
    File *tempPtr = filePtr;
    while (tempPtr != nullptr) {
      tempPtr->sizeR -= size;
      tempPtr = tempPtr->parent;
    }

    // after deleting it
    delete it->second;
    filePtr->child.erase(it);
    // sucessfully deleted
    return true;
  }

  // if it is not a exit
  // if it is not a folder(normal file), the path dont exist
  if (it->second->isFolder == false) {
    // do nothing
    return true;
  }
  // otherwise it is a folder
  filePaths.pop_front();
  return remove(it->second, filePaths);
}

bool qualify(File *filePtr, std::deque<std::string> &filePaths, ll LD, ll LR) {
  // if filePtr is null
  if (filePtr == nullptr) {
    return false;
  }
  // if the path is root
  if (filePaths.empty()) {
    if (!((LD == 0 || filePtr->sizeD <= LD) &&
          (LR == 0 || filePtr->sizeR <= LR))) {
      return false;
    }
    filePtr->LD = LD;
    filePtr->LR = LR;
    return true;
  }
  // if not root

  auto it = filePtr->child.find(filePaths.front());
  // if not found, path is not exist
  if (it == filePtr->child.end()) {
    return false;
  }
  // if found:
  // if it is a normal file, path dont exist or cannot qualify a normal file
  if (it->second->isFolder == false) {
    return false;
  }
  // if its a folder
  // exit
  if (filePaths.size() == 1) {
    // if dont satisfy
    if (!((LD == 0 || it->second->sizeD <= LD) &&
          (LR == 0 || it->second->sizeR <= LR))) {
      return false;
    }
    // if satisfy
    // modify
    it->second->LD = LD;
    it->second->LR = LR;
    return true;
  }
  // if not in exit, go to the next level
  filePaths.pop_front();
  return qualify(it->second, filePaths, LD, LR);
}

int main(int argc, char const *argv[]) {
  std::ios::sync_with_stdio(false);

  File *root = new File("", nullptr, true);
  int n;
  (cin >> n).get();
  for (int i = 0; i < n; i++) {
    std::string instruction;
    std::getline(cin, instruction);
    const char insType = instruction.front();
    instruction.erase(instruction.begin(), instruction.begin() + 2);

    std::stringstream ss(instruction);
    std::string inputFilePaths;
    std::deque<std::string> filePaths;
    ss >> inputFilePaths;
    decodeFilePath(filePaths, inputFilePaths);

    if (insType == 'C') {
      // do create
      ll fileSize;
      ss >> fileSize;
      cout << (create(root, filePaths, fileSize) ? 'Y' : 'N') << std::endl;
      continue;
    }

    if (insType == 'R') {
      // do remove
      cout << (remove(root, filePaths) ? 'Y' : 'N') << std::endl;
      continue;
    }

    if (insType == 'Q') {
      // do qualify
      ll LD, LR;
      ss >> LD >> LR;
      cout << (qualify(root, filePaths, LD, LR) ? 'Y' : 'N') << std::endl;
      continue;
    }
  }

  delete root;
  return 0;
}