#include <iostream>
#include <vector>
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <string.h>
#include <algorithm>

typedef struct {
	std::string name;
	size_t size;
} MyFile;

typedef struct {
  std::string name;
  std::vector<void*> folders;
  void* parent;
  std::vector<MyFile*> files;
} Folder;

/**
 * Gets a subdir in the given dir, making a new one if one doesn't already exist
 */
Folder* getDir(Folder* src, const std::string& dir) {
	auto found = std::find_if(src->folders.begin(), src->folders.end(), [&](void* f) {
		Folder* f2 = (Folder*)f;
		return f2->name.compare(dir) == 0;
	});

	Folder* f;
	if (found == src->folders.end()) {
		Folder* newf = new Folder();
		newf->name = dir;
		newf->parent = (void*)src;
		src->folders.push_back((void*)newf);
		f = newf;
	} else {
		f = (Folder*)*found;
	}
	return f;
}

void rmdirRecursive(Folder* f) {

	for (auto file : f->files) {
		delete file;
	}

	f->files.clear();

	for (auto folder : f->folders) {
		Folder* fsub = (Folder*)folder;
		rmdirRecursive(fsub);
		delete fsub;
	}

	f->folders.clear();
}

size_t getSizeRecursive(Folder* f) {
	size_t total = 0;

	for (auto& f : f->files) {
		total += f->size;
	}

	for (auto folder : f->folders) {
		Folder* fsub = (Folder*)folder;
		total += getSizeRecursive(fsub);
	}

	return total;
}

/**
 * Traverses the folder tree and recursive adds all folders into output
 * if their size if larger than limit_size
 */
std::vector<Folder*> traverseSizes(Folder* f, size_t limit_size) {
	std::vector<Folder*> ret;

	size_t s = getSizeRecursive(f);
	if (s >= limit_size) {
		ret.push_back(f);
	}

	for (auto& f2 : f->folders) {
		auto vec2 = traverseSizes((Folder*)f2, limit_size);
		ret.insert(ret.end(), vec2.begin(), vec2.end());
	}

	return ret;
}

bool hasFile(Folder* f, const std::string& n) {
	for (auto& f : f->files) {
		if (f->name.compare(n) == 0) {
			return true;
		}
	}
	return false;
}

std::vector<std::string> split(std::string s, std::string delimiter) {
    size_t pos_start = 0, pos_end, delim_len = delimiter.length();
    std::string token;
    std::vector<std::string> res;

    while ((pos_end = s.find (delimiter, pos_start)) != std::string::npos) {
        token = s.substr (pos_start, pos_end - pos_start);
        pos_start = pos_end + delim_len;
        res.push_back (token);
    }

    res.push_back (s.substr (pos_start));
    return res;
}

int main(int argc, char** argv) {

	if (argc < 2) {
		std::cout << "invalid input" << std::endl;
		return 1;
	}

	const std::string fpath = argv[1];

	struct stat st;
	int ret = stat(fpath.c_str(), &st);
	if (ret != 0) {
		std::cout << "failed statting: " << fpath << ", " << strerror(errno) << std::endl;
		return 1;
	}

	FILE* fin = fopen(fpath.c_str(), "r");
	if (!fin) {
		std::cout << "Failed opening: " << argv[1] << std::endl;
		return 1;
	}

	char* buf = new char[st.st_size];
	memset(buf, 0, st.st_size);
	size_t r = fread(buf, 1, st.st_size, fin);
	fclose(fin);

	if (r != st.st_size) {
		std::cout << "read: " << r << "/" << st.st_size << " bytes" << std::endl;
		delete[] buf;
		return 1;
	}

	std::vector<std::string> lines;
	std::string l;

	for (size_t t = 0; t < st.st_size; ++t) {
		if (buf[t] == '\n') {
			lines.push_back(l);
			l = std::string();
			continue;
		}

		l += buf[t];
	}

	std::cout << "there are: " << lines.size() << " lines" << std::endl;
	delete[] buf;

	Folder root;
	root.name = "/";
	Folder* cwd = &root;

	bool listing = false;

	for (auto& line: lines) {

		if (line[0] == '$') {
			// command
			line.erase(0, 2);
			if (line.rfind("cd ", 0) == 0)  {
				auto v = split(line, " ");
				if (v.size() != 2) {
					std::cout << "Invalid cd: " << line << std::endl;
					return 1;
				}

				if (v[1].compare("..") == 0) {
					cwd = (Folder*)cwd->parent;
				} else {
					Folder* fnew = getDir(cwd, v[1]);
					cwd = fnew;
				}
			} else if (line.compare("ls") == 0) {
			} else {
				std::cout << "Invalid command: " << line << std::endl;
				return 1;
			}
		} else {
			// listing folders and files for cwd
			auto v = split(line, " ");
			if (v.size() != 2) {
				std::cout << "Invalid file or dir: " << line << std::endl;
				return 1;
			}

			if (line.rfind("dir ", 0) == 0)  {
				Folder* fnew = getDir(cwd, v[1]);
			} else {
				if (hasFile(cwd, v[1])) {
					std::cout << "already added: " << v[1] << std::endl;
					continue;
				}
				MyFile* f = new MyFile();
				f->name = v[1];
				f->size = std::stoi(v[0]);
				cwd->files.push_back(f);
			}
		}
	}

	size_t device_space = 70000000;
	size_t space_needed = 30000000;

	size_t used_size = getSizeRecursive(&root);
	size_t must_free = space_needed - (device_space - used_size);
	std::cout << "must free " << must_free << std::endl;

	// List folders larger than must_free
	std::vector<Folder*> selected = traverseSizes(&root, must_free);

	std::cout << "can free: " << selected.size() << " folders" << std::endl;
	size_t current_min = device_space;
	std::string name;

	for (auto iter : selected) {
		Folder* fptr = (Folder*)iter;
		size_t s = getSizeRecursive(fptr);
		if (s < current_min) {
			current_min = s;
			name = fptr->name;
			std::cout << "asd: " << fptr->name << std::endl;
		}
	}

	std::cout << "smallest folder to free: " << current_min << ", " << name << std::endl;

	rmdirRecursive(&root);
	return 0;
}