core/model/comp_graph.cpp

0001 /*
0002  * SPDX-FileCopyrightText: 2019-2023 Mattia Basaglia <dev@dragon.best>
0003  *
0004  * SPDX-License-Identifier: GPL-3.0-or-later
0005  */
0006
0007 #include "comp_graph.hpp"
0008
0009 #include <unordered_set>
0010 #include <unordered_map>
0011 #include <deque>
0012
0013 #include "model/document.hpp"
0014 #include "model/assets/assets.hpp"
0015 #include "model/shapes/precomp_layer.hpp"
0016
0017 void glaxnimate::model::CompGraph::add_composition(glaxnimate::model::Composition* comp)
0018 {
0019     std::vector<glaxnimate::model::PreCompLayer*>& comp_layers = layers[comp];
0020     std::deque<glaxnimate::model::DocumentNode*> nodes(comp->docnode_children().begin(), comp->docnode_children().end());
0021
0022     while ( !nodes.empty() )
0023     {
0024         auto front = nodes.front();
0025         nodes.pop_front();
0026         if ( auto layer = front->cast<glaxnimate::model::PreCompLayer>() )
0027             comp_layers.push_back(layer);
0028         else
0029             nodes.insert(nodes.end(), front->docnode_children().begin(), front->docnode_children().end());
0030     }
0031 }
0032
0033 void glaxnimate::model::CompGraph::remove_composition(glaxnimate::model::Composition* comp)
0034 {
0035     layers.erase(comp);
0036 }
0037
0038 bool glaxnimate::model::CompGraph::is_ancestor_of(glaxnimate::model::Composition* ancestor, glaxnimate::model::Composition* descendant) const
0039 {
0040     std::unordered_set<glaxnimate::model::Composition*> checked;
0041     std::unordered_set<glaxnimate::model::Composition*> not_checked;
0042     not_checked.insert(ancestor);
0043
0044     while ( !not_checked.empty() )
0045     {
0046         std::unordered_set<glaxnimate::model::Composition*> next;
0047
0048         for ( glaxnimate::model::Composition* comp : not_checked )
0049         {
0050             if ( comp == descendant )
0051                 return true;
0052
0053             auto it = layers.find(comp);
0054             if ( it == layers.end() )
0055                 continue;
0056
0057             for ( auto layer : layers.at(comp) )
0058             {
0059                 auto laycomp = layer->composition.get();
0060                 if ( laycomp && !checked.count(laycomp) )
0061                     next.insert(laycomp);
0062             }
0063
0064             checked.insert(comp);
0065         }
0066
0067         not_checked = std::move(next);
0068     }
0069
0070     return false;
0071 }
0072
0073 std::vector<glaxnimate::model::Composition *> glaxnimate::model::CompGraph::children(glaxnimate::model::Composition* comp) const
0074 {
0075     std::unordered_set<glaxnimate::model::Composition*> vals;
0076     for ( auto layer : layers.at(comp) )
0077     {
0078         if ( auto laycomp = layer->composition.get() )
0079             vals.insert(laycomp);
0080     }
0081
0082     return std::vector<glaxnimate::model::Composition *>(vals.begin(), vals.end());
0083 }
0084
0085 static bool recursive_is_ancestor_of(
0086     glaxnimate::model::Composition* ancestor,
0087     glaxnimate::model::Composition* descendant,
0088     std::unordered_map<glaxnimate::model::Composition*, bool>& cache,
0089     const std::unordered_map<glaxnimate::model::Composition*, std::vector<glaxnimate::model::PreCompLayer*>>& layers
0090 )
0091 {
0092     if ( ancestor == descendant )
0093         return cache[ancestor] = true;
0094
0095     auto it = cache.find(ancestor);
0096     if ( it != cache.end() )
0097         return it->second;
0098
0099     int is_ancestor = 0;
0100
0101     for ( auto layer : layers.at(ancestor) )
0102     {
0103         if ( auto laycomp = layer->composition.get() )
0104             is_ancestor += recursive_is_ancestor_of(laycomp, descendant, cache, layers);
0105     }
0106
0107     return cache[ancestor] = is_ancestor;
0108 }
0109
0110 std::vector<glaxnimate::model::Composition *> glaxnimate::model::CompGraph::possible_descendants(glaxnimate::model::Composition* ancestor, glaxnimate::model::Document* document) const
0111 {
0112     std::unordered_map<glaxnimate::model::Composition*, bool> cache;
0113     std::vector<glaxnimate::model::Composition*> valid;
0114
0115     for ( const auto& precomp : document->assets()->compositions->values )
0116     {
0117         if ( !recursive_is_ancestor_of(precomp.get(), ancestor, cache, layers) )
0118             valid.push_back(precomp.get());
0119     }
0120
0121     return valid;
0122 }
0123
0124 void glaxnimate::model::CompGraph::add_connection(glaxnimate::model::Composition* comp, glaxnimate::model::PreCompLayer* layer)
0125 {
0126     auto it = layers.find(comp);
0127     if ( it != layers.end() )
0128         it->second.push_back(layer);
0129 }
0130
0131 void glaxnimate::model::CompGraph::remove_connection(glaxnimate::model::Composition* comp, glaxnimate::model::PreCompLayer* layer)
0132 {
0133     auto it_map = layers.find(comp);
0134     if ( it_map != layers.end() )
0135     {
0136         auto it_v = std::find(it_map->second.begin(), it_map->second.end(), layer);
0137         if ( it_v != it_map->second.end() )
0138         {
0139             if ( it_v != it_map->second.end() - 1 )
0140                 std::swap(*it_v, it_map->second.back());
0141             it_map->second.pop_back();
0142         }
0143     }
0144 }
0145