proto/Source/ntree.cpp

Go to the documentation of this file.

#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>

// Self header.
#include "ntree.h"
// Sum decompositions.
#include "utils.h"

#ifdef _DEPENDENCY_MODE

namespace ace {

typedef std::vector<subtree_t> subtrees_container_t;
typedef std::vector<subtrees_container_t> subtrees_to_merge_t;

subtrees_to_merge_t::size_type _product(subtrees_to_merge_t::size_type product_so_far, const subtrees_container_t& subtrees) {
    return product_so_far * subtrees.size();
}
    
void _join_subtrees(const subtrees_to_merge_t& subtrees_by_root_node, subtrees_container_t& results) {
    if ( subtrees_by_root_node.empty() ) {
        return;
    }
    
    // The number of results is product of multiplication of counts of various nodes subtrees.
    size_t results_count = std::accumulate(subtrees_by_root_node.begin(), subtrees_by_root_node.end(), 1, _product);
    results.reserve(results_count);

    // Iterate through vectors of subtrees and create desired subtrees.
    for ( size_t i = 0; i < subtrees_by_root_node.size(); ++i ) { // Loop through different nodes.
        for ( size_t j = 0; j < subtrees_by_root_node[i].size(); ++j ) { // Loop through subtrees of given node.
            // Loop as many times as needed. The more subtrees of given node,
            // the less loops performed (every subtree will be combined with the same number
            // of subtrees of different nodes.
            size_t loop = results_count/subtrees_by_root_node[i].size();
            for ( size_t k = 0; k < loop; ++k ) {
                if ( i == 0 ) {
                    // First outer loop, init resulting subtree with copy of j-th subtree of first node.
                    results.push_back(subtrees_by_root_node[i][j]);
                } else {
                    // Not first outer loop (subtree of later than first node), insert into existing subtree.
                    results[j*loop + k].insert(results[j*loop + k].end(), subtrees_by_root_node[i][j].begin(), subtrees_by_root_node[i][j].end());
                }
            }
        }
    }
}


/*  Interface item implementation - for info see description in header file.
 */
void extract_subtrees(ntree_t& nodes, tree_size_t subtree_size, mapped_subtrees_t& results) {

    if ( nodes.size() <= subtree_size ) {
        // Number of nodes is lesser than required subtree size.
        // Note: `nodes` container have one item more than is the nodes count.
        return;
    }
    
    // Utility object which precounts decomposition of all `sums` from 1 up to N
    // with use of M addends.
    // We used this decompositions to iterate through all posibilities how to construct
    // subtree of size N as composition of M smaller subtrees.
    // We are interested only in subtrees of maximum size `subtree_size`, so we only
    // want to get `subtree_size`-1 subtree nodes from childs of certain node.
    static SumDecompositions sum_decompositions(subtree_size-1, subtree_size*2);
    
    // Process queue - every node has to be processed once. The queue is initialized
    // with leaf nodes and order of processing of the rest of nodes is determined by
    // tree structure.
    std::queue<tree_size_t> process_queue;

    std::vector<mapped_subtrees_t> subtrees(nodes.size());
    std::vector<tree_size_t> childs_processed(nodes.size());
    
    // Step 0: Init the process queue with leaf nodes.
    // The 0-th node (abstract root) can be safely ignored.
    for ( tree_size_t i = 1; i < nodes.size(); ++i ) {
        if ( nodes[i].is_leaf() ) {
            // Add node to the process queue.
            process_queue.push(nodes[i].index());
        }
    }

    // Step 1: Cycle processing the queue.
    while ( !process_queue.empty() ) {
        // Current node.
        NTreeNode& current = nodes[process_queue.front()];
        // Parent node.
        NTreeNode& parent = nodes[current.parent()];
        
        // Every node is at least root of subtree of size one (containing only
        // the node itself), so...
        subtree_t new_one; // Create.
        new_one.push_back(current.index()); // Fill with current.
        // Subtrees are indexed by root nodes indices and the size of subtree is the map key.
        subtrees[current.index()].insert(mapped_subtrees_t::value_type(new_one.size(), new_one)); // Store.
        
        // Leaf or not leaf?:)
        if ( !current.is_leaf() ) {
            // Current node has some childs, process them (find all subtrees).

            // Few temporary containers...
            // There will be at most `subtree_size` subtrees_to_merge.
            subtrees_to_merge_t subtrees_to_merge;
            subtrees_to_merge.reserve(subtree_size);
            // Prepare container for results.
            subtrees_container_t merge_results;
            // 
            subtrees_container_t node_subtrees;
            
            for ( tree_size_t n = 2; n <= subtree_size; ++n ) {
                // Sum to get from childs.
                tree_size_t sum = n - 1;

                // Get decompositions of `sum` into `count_childs` addends
                const sum_decompositions_t *sd = sum_decompositions.get_decompositions_table(sum, current.count_childs());
                
                // Process them.
                for ( size_t i = 0; i < sd->size(); ++i ) { // Loop through every decomposition.
                    size_t j = 0;
                    for ( childs_t::const_iterator i_child = current.get_childs().begin(); i_child != current.get_childs().end(); ++i_child, ++j) { // Loop through every child node.
                        if ( (*sd)[i][j] == 0 ) {
                            // There is no such thing like subtree with zero nodes, so go to next.
                            continue;
                        }
                        // Get all of subtrees of required size.
                        std::pair<mapped_subtrees_t::const_iterator, mapped_subtrees_t::const_iterator> range = subtrees[*i_child].equal_range((*sd)[i][j]);
                        // Copy them into `node_subtrees`.
                        std::transform(range.first, range.second, std::back_inserter(node_subtrees), select2nd<mapped_subtrees_t::value_type>());
                        //
                        subtrees_to_merge.push_back(node_subtrees);
                        // Clear for use in next loop.
                        node_subtrees.clear();
                    }
                    // Join subtrees.
                    _join_subtrees(subtrees_to_merge, merge_results);
                    // Clear for use in next loop.
                    subtrees_to_merge.clear();
                    // Store the results as subtrees of current node,
                    // don't forget to insert current node as well!
                    // Also check, if there are any subtrees of size N!
                    // If so, store them in results.
                    for ( size_t n = 0; n < merge_results.size(); ++n ) {
                        // Insert current node as well!
                        merge_results[n].push_back(current.index());
                        subtrees[current.index()].insert(mapped_subtrees_t::value_type(merge_results[n].size(), merge_results[n]));
                        // Any subtree of desired size?
                        if ( merge_results[n].size() == subtree_size ) {
                            // Sort the subtree before copying it to results container!
                            std::sort(merge_results[n].begin(), merge_results[n].end());
                            results.insert(mapped_subtrees_t::value_type(current.index(), merge_results[n]));
                        }
                    }
                    // Clear results for use in next loop.
                    merge_results.clear();
                }
            }
        }

        // Node has been processed, so:
        // 1. Pop him from the queue.
        process_queue.pop();
        // 2. Increment processed childs counter of parent node.
        ++(childs_processed[parent.index()]);

        if ( !parent.is_abstract() && (parent.count_childs() == childs_processed[parent.index()]) ) {
            // Parent node is not the abstract root node and all its childs have been already processed.
            process_queue.push(parent.index());
        }
        
    }

}

} // namespace ace

#endif // _DEPENDENCY_MODE

---