#include <iostream>
#include <vector>
#include <dirent.h>

class MyDir {
public:
    typedef struct dir_entry * dir_entry_t;
    struct dir_entry {
        std::string name, path;
        void *subdirs;
    };

    typedef std::vector<struct dir_entry> dirs_t;

    MyDir(std::string path);
    ~MyDir(void);

    MyDir::dirs_t find(std::string str);

private:
    dirs_t *dirs;
    void parse_dir(std::string prefix, std::string subpath, dirs_t *dir);
    void _find(std::string str, MyDir::dirs_t *results,
    MyDir::dirs_t *cdir);
};

MyDir::MyDir(std::string path) {
    this->dirs = new dirs_t;

    this->parse_dir(path, "", this->dirs);
}

static inline void destroy_dir_entry(MyDir::dirs_t *dir) {
    MyDir::dirs_t::iterator it;

    for (it = dir->begin(); it != dir->end(); it++) {
        if (it->subdirs != NULL)
            destroy_dir_entry((MyDir::dirs_t *)it->subdirs);
    }

    delete dir;
}

MyDir::~MyDir(void) {
    destroy_dir_entry(this->dirs);
}

static inline int my_dir_filter(struct dirent *entry) {
    std::string name = entry->d_name;

    if (name == "." || name == "..")
        return 0;

    if (entry->d_type == DT_DIR)
        return 1;

    return 0;
}

void MyDir::parse_dir(std::string prefix, std::string subpath, dirs_t *dir) {
    struct dirent **dirs;
    int rval = 0;
    std::string full_path = prefix;

    if (full_path[full_path.length() - 1] != '/')
        full_path += '/';

    full_path += subpath;

    rval = scandir(full_path.c_str(), &dirs, my_dir_filter, NULL);

    struct dir_entry dentry;
    dentry.name = subpath;
    dentry.path = full_path;
    dentry.subdirs = NULL;

    if (rval == -1 || !rval) {
        dir->push_back(dentry);

        return;
    }

    dirs_t *cdir = new dirs_t;
    dentry.subdirs = (dir_entry_t)cdir;
    dir->push_back(dentry);

    for (int i = 0; i != rval; i++) {
        std::string spath = dirs[i]->d_name;

        parse_dir(full_path, spath, cdir);
    }
}

void MyDir::_find
(std::string str, dirs_t *results, MyDir::dirs_t *cdir) {
    MyDir::dirs_t::iterator it;

    for (it = cdir->begin(); it != cdir->end(); it++) {
        if (it->name.find(str) != std::string::npos)
            results->push_back(*it);

        if (it->subdirs != NULL)
            _find(str, results, (MyDir::dirs_t *)it->subdirs);
    }
}

MyDir::dirs_t MyDir::find(std::string str) {
    dirs_t results;

    this->_find(str, &results, this->dirs);

    return results;
}

int main(int argc, char **argv) {
    if (argc != 3)
        return 1;

    std::cout << "Indexing " << argv[1] << " ..." << std::endl;
    MyDir dir(argv[1]);

    std::cout << "Searching for" << argv[2] << " ..." << std::endl;
    MyDir::dirs_t find_results = dir.find(argv[2]);

    std::cout << "Results (" << find_results.size() << "):" << std::endl;

    MyDir::dirs_t::iterator fit;
    for (fit = find_results.begin(); fit != find_results.end(); fit++) {
        std::cout << fit->path << std::endl;
    }

    return 0;
}