file_tree.h

Go to the documentation of this file.

#ifndef FILE_TREE_H
#define FILE_TREE_H
#pragma once
/***************************************************************************
 *   Copyright (C) 2007-2013 Mike Kinghan, imk@burroingroingjoing.com      *
 *   All rights reserved.                                                  *
 *                                                                         *
 *   Contributed originally by Mike Kinghan, imk@burroingroingjoing.com    *
 *                                                                         *
 *   Redistribution and use in source and binary forms, with or without    *
 *   modification, are permitted provided that the following conditions    *
 *   are met:                                                              *
 *                                                                         *
 *   Redistributions of source code must retain the above copyright        *
 *   notice, this list of conditions and the following disclaimer.         *
 *                                                                         *
 *   Redistributions in binary form must reproduce the above copyright     *
 *   notice, this list of conditions and the following disclaimer in the   *
 *   documentation and/or other materials provided with the distribution.  *
 *                                                                         *
 *   Neither the name of Mike Kinghan nor the names of its contributors    *
 *   may be used to endorse or promote products derived from this software *
 *   without specific prior written permission.                            *
 *                                                                         *
 *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS   *
 *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT     *
 *   LIMITED TO, THE IMPLIED WARRANTIES OF  MERCHANTABILITY AND FITNESS    *
 *   FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE        *
 *   COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,   *
 *   INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,  *
 *   BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS *
 *   OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED    *
 *   AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,*
 *   OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF *
 *   THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH  *
 *   DAMAGE.                                                               *
 *                                                                         *
 **************************************************************************/
#include "prohibit.h"
#include "path.h"
#include "filesys.h"
#include <memory>
#include <map>

struct file_tree : private no_copy
{
        struct traverser;

        struct node {
                using node_ptr = std::shared_ptr<node>;
                using child_list = std::map<std::string,node_ptr>;
                using entry = child_list::value_type;
                using child_list_ptr = std::shared_ptr<child_list>;

                friend struct file_tree;

                bool is_file() const {
                        return _children.get() == nullptr;
                }

                bool is_dir() const {
                        return !is_file();
                }

                void traverse(traverser & action) const;

                node * root();

                template<typename Filter>
                unsigned insert(path_t & abs_path, Filter & filter) {
                        return intermediate_insert(abs_path,filter);
                }

        private:

                explicit node(node * parent = nullptr)
                        : _parent(parent) {}

                explicit node(child_list_ptr children)
                : _parent(nullptr),_children(children) {}

                node * guardian(std::string const & key) const {
                        return _parent && _parent->find(key) ? _parent : nullptr;
                }

                node * parent() const {
                        return _parent;
                }

                node * find(std::string const & key) {
                        node * hit = nullptr;
                        if (_children) {
                                auto where = _children->find(key);
                                if (where != _children->end()) {
                                        hit = where->second.get();
                                }
                        }
                        return hit;
                }

                node * ancestral_candidate_for_real_path(path_t const & cur_path,
                        path_t const & real_path);

                template<typename Filter>
                unsigned intermediate_insert(path_t & abs_path, Filter & filter);

                template<typename Filter>
                unsigned terminal_insert(path_t & abs_path, Filter & filter);

                void insert(std::string const & key, node_ptr & child);

#ifdef FILETREE_DEBUG
                static void display(std::string const & name,
                                    node const * n, unsigned indent = 0);
#endif
                node *_parent;
                std::shared_ptr<child_list> _children;
        };

public:

        using child_list = node::child_list;
        using node_ptr = node::node_ptr;
        using entry = node::entry;

        struct traverser : private no_copy {

                traverser() = default;

                virtual ~traverser() = default;

                void operator()(entry const & entry);

                virtual void enter_dir(std::string const & dirname) {};
                virtual void at_file(std::string const & filename) {};
                virtual void leave_dir(std::string const & dirname) {};

        protected:

                node const * _cur_dir = nullptr;
                path_t _cur_path;
        };

        struct no_filter {
                bool operator ()(std::string const &) const {
                        return true;
                }
        };

        file_tree()
                : _root(node::child_list_ptr(new child_list)) {}

        unsigned files() const {
                return _files;
        }

        void traverse(traverser & action) {
                _root.traverse(action);
        }

        template<typename Filter = file_tree::no_filter>
        void add(std::string const & path, Filter & filter) {
                path_t abs_path(fs::real_path(path));
                _root.insert(abs_path,filter);
#ifdef FILETREE_DEBUG
                node::display("ROOT",&_root,0);
#endif
        }

        template<class InIter, class Filter = file_tree::no_filter>
        void add(InIter start, InIter end, Filter & filter) {
                for (   ; start != end; add(*start++,filter)) {}
        }

private:

        node _root;
        unsigned _files = 0;

};

#endif // EOF