Tree.h

/*
 
MIT License
 
Copyright (c) 2017 FMI Open Development / Markus Peura, first.last@fmi.fi
 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
 
*/
/*
Part of Rack development has been done in the BALTRAD projects part-financed
by the European Union (European Regional Development Fund and European
Neighbourhood Partnership Instrument, Baltic Sea Region Programme 2007-2013)
*/
 
#ifndef DRAIN_TREE_NAME
#warning "Use TreeOrdered.h or TreeUnordered.h to include this file."
#endif
 
 
#include <iterator>
#include <string>
#include <map>
 
 
#include <drain/Log.h>
#include <drain/TypeName.h>
#include <drain/TypeUtils.h>
#include <drain/Variable.h>  // NEW 2025 to support several types of initializer_list, not only pair<char*,char*>
 
 
#include "Path.h"
 
#include "TreeUtils.h"
 
namespace drain {
 
 
 
 
 
template <class T, bool EXCLUSIVE=false, class P=drain::Path<std::string,'/'> > // , class C=std::less<std::string>
class DRAIN_TREE_NAME { // : public AmbiValue<T,typename P::elem_t> { //: public TreeBase {
public:
 
    typedef drain::DRAIN_TREE_NAME<T,EXCLUSIVE,P> tree_t; //,C
    typedef T node_data_t;
    typedef P path_t;
    typedef typename path_t::elem_t key_t; // deprecating?
    typedef typename path_t::elem_t path_elem_t;
 
    typedef std::pair<key_t,tree_t> pair_t;
 
    typedef DRAIN_TREE_CONTAINER(key_t,tree_t) container_t;
 
    typedef typename container_t::iterator iterator;
    typedef typename container_t::const_iterator  const_iterator;
 
    inline
    DRAIN_TREE_NAME(){}; // :  separator(separator) {}; //parent(*this),
 
    inline
    DRAIN_TREE_NAME(const node_data_t &data) : data(data){}; //, separator(t.separator) {}; //parent(*this),
 
    inline
    DRAIN_TREE_NAME(const DRAIN_TREE_NAME &t) : data(t.data){}; //, separator(t.separator) {}; //parent(*this),
 
    virtual inline
    ~DRAIN_TREE_NAME(){};
 
 
    node_data_t data;
 
 
    // AMBIVALUED
    virtual inline
    bool hasMultipleData() const {
        // Return false, if own, local data (explain ??)
        return data.empty();
    };
 
    virtual inline
    const node_data_t & getData() const {return data;};
 
    virtual inline
    node_data_t & getData(){return data;};
 
    virtual inline
    const node_data_t & getData(const key_t & key) const {
        return retrieveChild(key).data;
    };
 
    virtual inline
    node_data_t & getData(const key_t & key){
        return retrieveChild(key).data;
    };
 
 
 
    inline
    typename container_t::const_iterator begin() const { return children.begin(); };
 
    inline
    typename container_t::const_iterator end() const { return children.end(); };
 
    inline
    typename container_t::iterator begin(){ return children.begin(); };
 
    inline
    typename container_t::iterator end(){ return children.end(); };
 
 
 
    static inline
    bool isExclusive(){
        return EXCLUSIVE;
    }
 
    static inline
    bool isMultiple(){
        #ifdef DRAIN_TREE_MULTI
        return true;
        #else
        return false;
        #endif
    }
 
    static inline
    bool isOrdered(){
        #ifdef DRAIN_TREE_ORDERED
        return true;
        #else
        return false;
        #endif
    }
 
 
 
    // TODO: what to do with the separator?
    inline
    tree_t &operator=(const tree_t &t){
        if (&t != this){
            data = t.data;
            //if (EXCLUSIVE){ ...or consider deep copy?
            clearChildren();
            //}
        }
        return *this;
    };
 
    // Needed? See next.
    /* THIS CAUSES PROBLEMS. with int x = tree; vs. tree = x;
    inline
    tree_t & operator=(const node_data_t &v){
        data = v;
        if (EXCLUSIVE){
            clearChildren();
        }
        return *this;
    };
    */
 
    /* 2025/01 => non-ref
    template <class S>
    inline
    tree_t & operator=(const std::initializer_list<S> &l){
        data = l;
        if (EXCLUSIVE){
            clearChildren();
        }
        return *this;
    }
    */
 
 
    // 2025/01 non-const
    /*
    template <class S>
    inline
    tree_t & operator=(std::initializer_list<S> l){
        data = l;
        if (EXCLUSIVE){
            clearChildren();
        }
        return *this;
    }
    */
 
 
 
    template <class T2>
    inline
    tree_t & operator=(const T2 &v){
        data = v;
        if (EXCLUSIVE){
            clearChildren();
        }
        return *this;
    }
 
 
    // This may cause problems, as non-template, and forces implementation of .data = std::string(str).
    inline
    tree_t & operator=(const char *str){
        return this->operator=(std::string(str));
    }
 
 
 
    template <typename K, typename V>
    inline  // 2025/01 experimental.
    tree_t & operator=(std::initializer_list<std::pair<K,V> > l){
        for (const auto & entry: l){
            *this << entry;
        }
        return *this;
    }
 
 
    inline  // 2025/01 experimental.
    tree_t & operator=(std::initializer_list<std::pair<const char *,const Variable> > l){
        if (EXCLUSIVE){
            clearData();
        }
        for (const auto & entry: l){
            this[entry.first] = entry.second;
        }
        return *this;
    }
 
    /*
    inline  // 2025/01 experimental.
    tree_t & operator=(std::initializer_list<std::pair<const char *,const char *> > l){
        for (const auto & entry: l){
            *this << entry;
        }
        return *this;
    }
    */
 
 
    template <typename V>
    inline
    tree_t & operator=(const std::initializer_list<V> & l){
        if (EXCLUSIVE){
            clearChildren();
        }
        this->data = l;
        return *this;
    }
 
    // See operator<<() below.
    typedef std::pair<key_t,node_data_t> node_pair_t;
 
    // 2025/01 experimental
    /*
    inline
    tree_t & operator=(std::initializer_list<node_pair_t> l){
        for (const auto & entry: l){
            *this << entry;
        }
        return *this;
    }
    */
 
    inline
    tree_t & operator<<(const node_pair_t & entry){
        if (EXCLUSIVE){
            clearData();
        }
        tree_t & child = retrieveChild(entry.first);
        child.data = entry.second;
        return child;
    }
 
 
    inline
    operator const node_data_t &() const {
        return data;
    };
 
    inline
    operator node_data_t &(){
        return data;
    };
 
 
    /*
    inline
    tree_t & operator[](const key_t & key){
        return retrieveChild(key);
    }
 
    inline
    const tree_t & operator[](const key_t & key) const {
        return retrieveChild(key);
    }
    */
 
 
    template <class K>
    inline
    tree_t & operator[](const K & key){
        return retrieveChild(getKey(key)); // 2026/02
        //return retrieveChild(key); // OLD
    }
 
    template <class K>
    inline
    const tree_t & operator[](const K & key) const {
        return retrieveChild(getKey(key)); // 2026/02
        // return retrieveChild(key); // OLD
    }
 
 
 
    inline
    tree_t & operator()(const path_t & path){
        /*
        if (superDebug){
            std::cout << __FILE__ << "tree_t & operator()(const path_t & path)" << '\n';
        }
        */
        return get(path.begin(), path.end());
    }
 
 
    template <class S>
    inline
    tree_t & operator()(const S & arg){
        return operator()(path_t(arg));
    }
 
 
    inline
    tree_t & operator()(const char *arg){
        return operator()(path_t(arg));
        // return operator()(std::string(arg));
    }
 
 
    inline
    const tree_t & operator()(const path_t & path) const {
        return get(path.begin(), path.end());
    }
 
    template <class S>
    inline
    const tree_t & operator()(const S & arg) const {
        return operator()(path_t(arg));
    }
 
    inline
    const tree_t & operator()(const char *arg) const {
        return operator()(path_t(arg));
        //return operator()(std::string(arg));
    }
 
 
    inline
    void clear(){
        clearData();
        clearChildren();
    };
 
    inline
    void clearData(){
        // Future option: data.clear() (applies to many stl classes, like strings and containers)
        data = getEmpty().data;
    };
 
 
    inline
    void clearChildren(){ // RAISE/virtualize
        children.clear();
    };
 
    /*
    void eraseChild(const key_t & key){
        children.erase(key);
    }
    */
 
 
    // ??-> If an ending slash is included, then groups but no datasets will be erased. (?)
    void erase(const path_t & path){ // RAISE/virtualize
 
        // drain::Logger mout(__FILE__, __FUNCTION__);
 
        // Idea: first assign the leaf, and step one back.
        typename path_t::const_iterator pit = path.end();
        if (pit == path.begin())
            return;
        else {
            // Move 'it' back one step, to point to the leaf (the last element in chain).
            --pit;
 
            // Safe (identity) if it == path.begin():
            tree_t & parent = this->get(path.begin(), pit);
 
            #ifdef DRAIN_TREE_ORDERED  // map
 
            // TODO: generalize "find" for find first, etc
            parent.children.erase(*pit);
 
            #else
 
            //drain::Logger(__FILE__, __LINE__, __FUNCTION__).error("unimplemented code");
            for (iterator it = children.begin(); it != children.end(); ++it){
                if (it->first == *pit){
                    // drain::Logger(__FILE__, __LINE__, __FUNCTION__).attention("deleting child: ", *pit);
                    parent.children.erase(it);
                    return;
                }
            }
 
 
            #endif
 
            //parent.eraseChild(*it);
 
        }
 
    }
 
    virtual inline
    const tree_t & getEmpty() const {
        return emptyNode;
    }
 
    // Ambiguous?
    virtual inline
    bool empty() const {
        return (data.empty() && !hasChildren());
    };
 
    inline
    bool hasChildren() const {
        return !children.empty();
    }
 
 
    virtual inline
    int hasChildren(const key_t &key) const {
 
        #ifdef DRAIN_TREE_ORDERED  // map
 
        if (!isMultiple()){
            return (children.find(key) == children.end()) ? 0 : 1;
        }
        // no-break for OrderedMultipleTree
 
        #endif
 
        // OrderedMultipleTree (passed through from the above #ifdef-#endif)
        // OrderedMultipleTree
        // UnorderedMultipleTree
 
        size_t count = 0;
        for (const auto & entry: children){
            if (entry.first == key){
                ++count;
            }
        }
        return count;
 
    };
 
 
    virtual inline
    bool hasChild(const key_t &key) const {
 
        #ifdef DRAIN_TREE_ORDERED
        // map -> native (NlogN) search
 
        return (children.find(key) != children.end());
 
        #else
        // list -> brute-force search
 
        for (const auto & entry: children){
            if (entry.first == key){
                return true;
            }
        }
        return false;
 
        #endif
    };
 
 
    template <typename K>
    inline
    bool hasChild(const K &key) const {
        return hasChild(getKey(key)); // 2025
        // return hasChild(static_cast<key_t>(key)); // OLDISH
    }
 
 
    inline
    bool hasPath(const path_t & path) const {
        return hasPath(path.begin(), path.end());
    }
 
    // protect:
    /*
    key_t getNewChildKey() const {
        // Consider error (unimplemented)
        return key_t();
    }
    */
 
 
    inline
    void initChild(tree_t & child) const {
    }
 
    static
    void generateKey(const tree_t & tree, typename P::elem_t & key);
 
 
    tree_t & addChild(){ // NEW 2026
        typename P::elem_t key;
        generateKey(*this, key);
        //return addChild(key_t());
        return addChild(key);
    }
 
    //  retrieve
 
 
    tree_t & addChild(const key_t & key){ // 2026/01 : explicit arg
 
        if (key.empty()){ // Should be exceptional... Warning?
            std::cerr << typeid(tree_t).name() << std::endl;
            throw std::runtime_error(drain::StringBuilder<':'>(__FILE__,__FUNCTION__, " empty key (ADD static child counter based naming)"));
            return *this;
        }
 
        if (EXCLUSIVE){
            // EXCLUSIVE = either data or children... so drop data now.
            this->clearData();
        }
 
        #ifdef DRAIN_TREE_ORDERED
        // Always unique ( ==non-multiple)
        iterator it = children.find(key);
        if (it != children.end()){
            return it->second;
        }
        else {
            tree_t & child = children.insert(children.begin(), pair_t(key, tree_t()))->second;
            initChild(child);
            return child;
        }
 
        #else
 
        // If not MULTIPLE, return the child if it exists
        if (!isMultiple()){
            for (auto & entry: children){
                // Brute-force search
                if (entry.first == key){
                    return entry.second;
                }
            }
        }
 
        // Add a child.
        children.push_back(pair_t(key, tree_t()));
        tree_t & child = children.back().second;
        initChild(child);
        return child;
 
        #endif
    };
 
 
    template <typename E>
    inline
    tree_t & addChild(const E & key){
        // Cast ensures forwarding to main function
        //return addChild(static_cast<key_t>(getKey(key)));
        return addChild(getKey(key));
    };
 
 
 
    inline
    tree_t & prependChild(){
        return prependChild(key_t());
    }
 
 
    // Push in the front. This is only available for ordered trees.
 
    template <typename E>
    inline
    tree_t & prependChild(const E & key){
        return prependChild(getKey(key));
    }
 
 
    //virtual
    tree_t & prependChild(const key_t & key){ // 2026/01 explicit arg
 
        #ifdef DRAIN_TREE_ORDERED
 
        return addChild(key);
 
        #else
 
        if (key.empty()){ // Should be exceptional... Warning?
            throw std::runtime_error(drain::StringBuilder<':'>(__FILE__,__FUNCTION__, " empty key (ADD static child counter based naming"));
            return *this;
        }
 
        if (EXCLUSIVE){
            this->clearData();
        }
 
        // Try searching first. So, does not reposition (delete and prepend) if exists.
        if (!isMultiple()){
            for (auto & entry: children){
                if (entry.first == key){
                    return entry.second;
                }
            }
        }
 
        // Add:
        children.push_front(pair_t(key, tree_t()));
        tree_t & child = children.front().second; //children.insert(children.begin(), pair_t(key, tree_t()))->second;
        initChild(child);
        return child;
        //return children.back().second;
        #endif
 
    };
 
 
    // retrieveChild(key, create ALWAYS / IF_NOT_FOUND
 
    virtual
    tree_t & retrieveChild(const key_t & key){
 
        if (key.empty())
            return *this;
 
        // ! if (EXCLUSIVE) this->clearData();
 
        #ifdef DRAIN_TREE_ORDERED
        // Old policy restored; keys must implement empty(), an empty key is indentified to the current node.
 
        // return children[key];
        iterator it = children.find(key);
        if (it != children.end()){
            return it->second;
        }
        else {
            tree_t & child = children.insert(children.begin(), pair_t(key, tree_t()))->second;
            initChild(child);
            return child;
            //
            // return children.insert(children.begin(), pair_t(key, tree_t()))->second;
        }
 
        #else
 
        for (auto & entry: children){
            if (entry.first == key){
                return entry.second;
            }
        }
        // if (EXCLUSIVE)   this->clearData();
        children.push_back(pair_t(key, tree_t()));
        tree_t & child = children.back().second; //children.insert(children.begin(), pair_t(key, tree_t()))->second;
        initChild(child);
        return child;
        // return children.back().second;
 
        #endif
    };
 
 
    virtual
    const tree_t & retrieveChild(const key_t & key) const {
 
        if (key.empty())
            return *this;
 
        #ifdef DRAIN_TREE_ORDERED
        const const_iterator it = children.find(key);
        if (it != children.end()){
            return it->second;
        }
        #else  // traverse
        for (const auto & entry: children){
            if (entry.first == key){
                return entry.second;
            }
        }
        #endif
 
        return getEmpty();
    };
 
 
    // Functions perhaps less relevant ....................................
 
 
    inline
    container_t & getChildren() { return children; };
 
    inline
    const container_t & getChildren() const { return children; };
 
 
 
    // New
    inline
    const node_data_t *operator->() const {
        return &data;
    };
 
    inline
    node_data_t *operator->(){
        return &data;
    };
 
 
    inline
    void swap(tree_t &t){
        children.swap(t.children);
        if (!data.empty()){
            Logger(__FILE__, __FUNCTION__).unimplemented("node data unempty but not swapped");
        }
    }
 
    /*
     *  As an option, child nodes can be addressed using keys which are not of key_y type, but can be converted to such.
     */
    static inline
    const key_t & getKey(const key_t & key){
        return key;
    }
 
    // NOTE: char * should not be directed to getKey! (But more to inst std::string(key)
    // Return to temp?
    static inline
    key_t getKey(const char * key){
        return key_t(key);
    }
 
    /*
     * As an option, child nodes can be addressed using keys which are not of key_y type, but can be converted to such.
     * Not that this version returns a constant reference.
     */
    template <typename K>
    static
    const key_t & getKey(const K & key); // left undefined!
 
 
protected:
 
    container_t children;
 
    static
    const tree_t emptyNode;
 
 
 
 
    bool hasPath(typename path_t::const_iterator it, typename path_t::const_iterator eit) const {
 
        if (it == eit) // empty path
            return true;
 
        const typename path_t::elem_t elem = *it;
 
        if (elem.empty())
            return hasPath(++it, eit);
        else if (!hasChild(elem))
            return false;
 
        return this->operator [](elem).hasPath(++it, eit);
 
    }
 
 
    inline
    tree_t & get(typename path_t::const_iterator it, typename path_t::const_iterator eit) {
 
        // Path empty => self-reference
        if (it == eit)
            return *this;
 
        // Path element is empty => proceed to next element
        if (it->empty())
            return get(++it, eit);
 
        tree_t & child = operator[](*it);
        return child.get(++it, eit);
 
    }
 
 
 
 
    inline
    const tree_t & get(typename path_t::const_iterator it, typename path_t::const_iterator eit) const {
 
        // Path empty => self-reference
        if (eit == it) // order, 2023/04
            return *this;
 
        // Path element is empty => skip it (proceed to next element)
        if (it->empty())
            return get(++it, eit);
 
        // NEW ~faulty? data1/data1/data1/...
 
        if (hasChild(*it)){
            //return retrieveChild(*it); <- ADD <- .get(++it, eit); ?
            return retrieveChild(*it).get(++it, eit);
        }
        else {
            return getEmpty();
        }
 
        // OLD (limited to map container, reconsider NEW, above!)
        /*
        typename tree_t::const_iterator child_it = this->children.find(*it);
        if (child_it == this->children.end())
            return getEmpty();
        else
            return child_it->second.get(++it, eit);
        */
 
        /*
        if (!hasChild(*it))
            return getEmpty();
        const tree_t & child = operator[](*it); // use find? Or better, direct child[key]
        //const tree_t & child = this->children[*it]; // use find? Or better, direct child[key] 2023/04
 
        return child.get(++it, eit);
        */
    }
 
 
 
};
 
template <class T, bool EXCLUSIVE, class P>
const DRAIN_TREE_NAME<T,EXCLUSIVE, P> DRAIN_TREE_NAME<T,EXCLUSIVE,P>::emptyNode;
 
template <class T, bool EXCLUSIVE, class P>
void DRAIN_TREE_NAME<T,EXCLUSIVE, P>::generateKey(const DRAIN_TREE_NAME<T,EXCLUSIVE, P> & tree, typename P::elem_t & key){
    std::stringstream k; // ("elem");
    k << "elem"; // number with 4 digits overwrites this?
    k.width(4);  // consider static member prefix
    k.fill('0');
    k << tree.getChildren().size();
    // Also derived classes require this assignment
    //key.assign(k.str());
    key = k.str();
}
 
 
 
 
// @certified
template <class T, bool EXCLUSIVE, class P>
struct TypeName<DRAIN_TREE_NAME<T,EXCLUSIVE, P> > {
 
    typedef DRAIN_TREE_NAME<T,EXCLUSIVE, P> tree_t;
 
    static
    const std::string & str(){
 
        static const std::string name = drain::StringBuilder<>(
                tree_t::isOrdered()?"Ordered":"Unordered",
                        tree_t::isMultiple()?"Multi":"","Tree",
                                tree_t::isExclusive()?"(Exclusive)":"",
                                        '<', TypeName<typename tree_t::node_data_t>::str(), '>'); // recursion...
                                                //'<', drain::Type::call<drain::simpleName>(typeid(typename tree_t::node_data_t)), '>');
        return name;
    }
 
};
 
} // drain::