#ifndef TREE_LIST_H
#define TREE_LIST_H

    #include <stdbool.h> // bool
    #include <string.h> // NULL

    // Tree List of nodes
    // Sychov A., 13/08/2019
    // Allows to organize your data into the tree-like list and
    // ... attach some data to each node.

    // @TREE_LIST_DEEP_ENABLE
    // Enable deep search in tree-list using "default" nodes.
    // If user marks the node as default, the search continues inside it 
    // even if no specfied node found during flat search. Each default node
    // can contain either normal and default nodes, that can be used in
    // recursive search. The depth of recursive search can be limited by
    // user using @TREE_LIST_RECURSIVE_LIMIT_ENABLE macro 
    #define TREE_LIST_DEEP_ENABLE                  1

    // @TREE_LIST_RECURSIVE_LIMIT_ENABLE
    // Only used if @TREE_LIST_DEEP_ENABLE is enabled
    // Limits the maximum recursive depth during deep search.
    // User defines it's own procedure to allow/disallow enter each
    // next recurisve level of search. See @fTreeListSearchDeepRecursiveLimiter_t
    #define TREE_LIST_RECURSIVE_LIMIT_ENABLE       1

    // @TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
    // Only used if @TREE_LIST_DEEP_ENABLE is enabled
    // Enable feature of searching for the parent of found node during
    // deep search. See @fTreeListSearchDeepResultNotify_t
    #define TREE_LIST_DEEP_PARENT_SEARCH_ENABLE    1

    union sTreeList_t;

    typedef union sTreeList_t
    {
        struct {
        void * key;
        union sTreeList_t * list;
        void * ctx;
        };
        struct {
        const void * c_key;
        const union sTreeList_t * c_list;
        const void * c_ctx;
        };
    }
    sTreeList_t;
    
    // @DECLARE_TREE_LIST_NODE
    // Declares simple node: it contains only child nodes.
    #define DECLARE_TREE_LIST_NODE( nodekey_, nodechilds_ )\
       { .key = nodekey_, .list = nodechilds_, .ctx = NULL }

    // @DECLARE_TREE_LIST_CNODE
    // Declares simple constant node: it contains only child nodes.
    #define DECLARE_TREE_LIST_CNODE( nodekey_, nodechilds_ )\
       { .c_key = nodekey_, .c_list = nodechilds_, .c_ctx = NULL }

    // @DECLARE_TREE_LIST_NODE_EX
    // Declares extended node: it contains either context and child nodes.
    #define DECLARE_TREE_LIST_NODE_EX( nodekey_, nodechilds_, nodectx_ )\
       { .key = nodekey_, .list = nodechilds_, .ctx = nodectx_ }

    // @DECLARE_TREE_LIST_CNODE_EX
    // Declares extended constant node: it contains either context and child nodes.
    #define DECLARE_TREE_LIST_CNODE_EX( nodekey_, nodechilds_, nodectx_ )\
       { .c_key = nodekey_, .c_list = nodechilds_, .c_ctx = nodectx_ }

    // @DECLARE_TREE_LIST_LEAF
    // Declares a tree leaf: leaf does not contain any nodes.
    #define DECLARE_TREE_LIST_LEAF( nodekey_, nodectx_ )\
       { .key = nodekey_, .list = NULL, .ctx = nodectx_ }

    // @DECLARE_TREE_LIST_CLEAF
    // Declares a tree constant leaf: leaf does not contain any nodes.
    #define DECLARE_TREE_LIST_CLEAF( nodekey_, nodectx_ )\
       { .c_key = nodekey_, .c_list = NULL, .c_ctx = nodectx_ }

    // @DECLARE_TREE_LIST_LAST
    // Declares the end of sibling list
    // Each list of tree-list nodes shall contain this element in the end.
    #define DECLARE_TREE_LIST_LAST()\
       { .c_key = NULL, .c_list = NULL, .c_ctx = NULL }

    // @fTreeListComparer_t
    // Tree-list compare function prototype.
    // The function shall be able to compare a couple of keys for equality.
    // This interface is used in @tree_list_search to compare two nodes,
    // ... where @key_a is a node's key, and @key_b is a @search_key argument.
    // Returns: true if equal, false otherwise
    typedef bool ( * fTreeListComparer_t )( const void * key_a, const void * key_b );

    #if TREE_LIST_DEEP_ENABLE
    // @fTreeListNextKey_t
    // Tree-list abstract function to get next key to search.
    // @ctx - abstract context pointer, is passed to used-defined function in used-dependent format; 
    // Returns: 
    // NON NULL: a search key to be used as @search_key parameter in @tree_list_search;
    // NULL: terminate the search (end of command is reached)
    typedef const void * ( * fTreeListNextKey )( void * ctx );
    #endif

    #if TREE_LIST_DEEP_ENABLE
    // @fTreeListForEach_t
    // Tree-list abstract function prototype.
    // Used in @tree_list_foreach function as an user function callback
    // @node - current node;
    // @ctx - user dependent context;
    // Returns: true - continue walking; false - terminate walking;
    typedef bool ( * fTreeListForEach_t )( const sTreeList_t * node, void * ctx );
    #endif

    #if TREE_LIST_DEEP_ENABLE
    // @fTreeListForEach_t
    // Tree-list abstraction function prototype.
    // Checks if the specified node can be considered as default node.
    // @node - node to check;
    // @ctx - optional user dependent context, can be NULL;
    // Returns:
    // - true: the specified @node is the default node;
    // - false: the specified @node is not the default node;
    typedef bool ( * fTreeListIsDefault_t )( const sTreeList_t * node, void * ctx );
    #endif

    #if TREE_LIST_DEEP_ENABLE
    // @tree_list_foreach
    // Tree-List iteration function
    // Walks the specified node seaching for derived nodes. Each node found is passed to the specified
    // by user function @fcall with the specified user dependent context @ctx
    // Function walks the current node while @fcall returns 'true', and returns current node immediately as
    // far as @fcall returns 'false'. The function returns NULL if @fcall never returns 'false'.
    // @ref_node - the tree node to walk in;
    // @fcall - user defined function callback;
    // @ctx - user defined function context;
    // Returns: tree-list node in case @fcall have returned 'false', or NULL otherwise.
    const sTreeList_t * tree_list_foreach( const sTreeList_t * ref_node, fTreeListForEach_t fcall, void * ctx );
    #endif

    // @tree_list_search
    // Search in the tree list @in for the node specified by @key using
    // ... the compare function @fcmp.
    // @in - the tree list to search in, shall not be NULL;
    // @search_key - the node key to search for, shall not be NULL;
    // @fcmp - nodes comparator, shall not be NULL; 
    // @def_node - the default node to be returned if no node found by @search_key, can be NULL;
    // Returns: the node pointer if found, @def_node otherwise.
    // Note: The list @in shall be terminated by DECLARE_TREE_LIST_LAST() element.
    const sTreeList_t * tree_list_search( const sTreeList_t * in,
                                          const void * search_key,
                                          fTreeListComparer_t fcmp,
                                          const sTreeList_t * def_node );

    #if TREE_LIST_DEEP_ENABLE
    #if TREE_LIST_RECURSIVE_LIMIT_ENABLE
    // @fTreeListSearchDeepRecursiveLimiter_t
    // Tree-list abstraction function prototype.
    // Limits the depth of recursive searching in @tree_list_search_deep.
    // Is called by each call @tree_list_search_deep to count calls;    
    // User must implement user-dependent way to count recursive calls
    // using @dir and @ctx parameters;
    // @dir - direction: true - enter recursive call, false - leave call;
    // @ctx - mandatory user dependent context.
    // Returns, if @dir is 'true':
    // - true: recursive call is possible;
    // - false: recursive call is impossible;
    // Returns, if @dir is 'false': does not matter;
    // Note: direct calls of @tree_list_search_deep never use this function,
    // only recursive calls can be limited by this function; so, this function can return 'false'
    // forever to limit all recursive calls (call depth > 1) and allow direct calls.
    typedef bool ( * fTreeListSearchDeepRecursiveLimiter_t )( bool dir, void * ctx );
    #endif
    #endif

    #if TREE_LIST_DEEP_ENABLE
    #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
    // @fTreeListSearchDeepResultNotify_t
    // Tree-list abstraction function prototype.
    // Defines user-dependent funtion callback protype used to notify the user
    // after successful search and pass the search results. User can agree and accept the result,
    // or disagree and continue searching for the next result.
    // Parameters:
    // @found - the search result (found node), not NULL;
    // @parent - the found node parent node, not NULL;
    // @user_ctx - user dependent context passed to @tree_list_search_deep in @user_ctx argument
    // Returns: the result acception: 'true' to agree and terminate searching and 'false' to disagree
    // and continue searching.
    // Note: the function is not being invoked if no result found.
    typedef bool ( * fTreeListSearchDeepResultNotify_t )( const sTreeList_t * found,
                                                          const sTreeList_t * parent,
                                                          void * user_ctx );
    #endif
    #endif

    #if TREE_LIST_DEEP_ENABLE
    // @sTreeListSearchDeep_FSet_t
    // Functional set for @tree_list_search
    typedef struct
    {
      fTreeListNextKey fnext;                         // next key getter, mandatory, can not be NULL
      fTreeListComparer_t fcmp;                       // node comparer, mandatory, can not be NULL
      fTreeListIsDefault_t fisdef;                    // default node detector, optional, can be NULL
      #if TREE_LIST_RECURSIVE_LIMIT_ENABLE
      fTreeListSearchDeepRecursiveLimiter_t freclim;  // recursive call limiter, optional, can be NULL
      #endif
      #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
      fTreeListSearchDeepResultNotify_t fagree;       // result notification/agreeing, optional, can be NULL
      #endif
    }
    sTreeListSearchDeep_FSet_t;
    #endif

    #if TREE_LIST_DEEP_ENABLE
    // @tree_list_search_deep_int
    // Extended search for a key chain in the tree-list.
    // @ref_node - base node, root, the node to start search from;
    // @fs - functional set, see @sTreeListSearchDeep_FSet_t:
    //  - fnext: user-defined abstract routine to retrieve next key in the chain;
    //  - fcmp: user-defined abstract predicate to compare nodes;
    //  - fisdef: user-defined predicate to determine if the node is the "default" node;
    //  - freclim: user-defined abstract routine to limit recursive calls, see @fTreeListSearchDeepRecursiveLimiter_t;
    // @user_ctx - user-dependent context, will be passed to routines in functional set @fs;
    // Returns:
    //  NON NULL: found node;
    //  NULL: node not found;
    const sTreeList_t * tree_list_search_deep( const sTreeList_t * ref_node, 
                                               const sTreeListSearchDeep_FSet_t * fs,
                                               void * user_ctx );
    #endif
#endif