src/document-subset.cpp

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * Inkscape::DocumentSubset - view of a document including only a subset
   4  *                            of nodes
   5  *
   6  * Copyright 2006  MenTaLguY  <mental@rydia.net>
   7  *   Abhishek Sharma
   8  *
   9  * Released under GNU GPL v2+, read the file 'COPYING' for more information.
  10  */
  11
  12 #include <map>
  13
  14 #include "document-subset.h"
  15
  16 #include "object/sp-object.h"
  17
  18
  19 namespace Inkscape {
  20
  21 struct DocumentSubset::Relations
  22 {
  23     typedef std::vector<SPObject *> Siblings;
  24
  25     struct Record {
  26         SPObject *parent;
  27         Siblings children;
  28
  29         sigc::connection release_connection;
  30         sigc::connection position_changed_connection;
  31
  32         Record() : parent(nullptr) {}
  33
  34         unsigned childIndex(SPObject *obj) {
  35             Siblings::iterator found;
  36             found = std::find(children.begin(), children.end(), obj);
  37             if ( found != children.end() ) {
  38                 return found - children.begin();
  39             } else {
  40                 return 0;
  41             }
  42         }
  43
  44         unsigned findInsertIndex(SPObject *obj) const {
  45             if (children.empty()) {
  46                 return 0;
  47             } else {
  48                 Siblings::const_iterator first=children.begin();
  49                 Siblings::const_iterator last=children.end() - 1;
  50
  51                 while ( first != last ) {
  52                     Siblings::const_iterator mid = first + ( last - first + 1 ) / 2;
  53                     int pos = sp_object_compare_position(*mid, obj);
  54                     if ( pos < 0 ) {
  55                         first = mid;
  56                     } else if ( pos > 0 ) {
  57                         if ( last == mid ) {
  58                             last = mid - 1; // already at the top limit
  59                         } else {
  60                             last = mid;
  61                         }
  62                     } else {
  63                         g_assert_not_reached();
  64                     }
  65                 }
  66
  67                 if ( first == last ) {
  68                     // compare to the single possibility left
  69                     int pos = sp_object_compare_position(*last, obj);
  70                     if ( pos < 0 ) {
  71                         ++last;
  72                     }
  73                 }
  74
  75                 return last - children.begin();
  76             }
  77         }
  78
  79         void addChild(SPObject *obj) {
  80             unsigned index=findInsertIndex(obj);
  81             children.insert(children.begin()+index, obj);
  82         }
  83
  84         template <typename OutputIterator>
  85         void extractDescendants(OutputIterator descendants,
  86                                 SPObject *obj)
  87         {
  88             Siblings new_children;
  89             bool found_one=false;
  90             for ( Siblings::iterator iter=children.begin()
  91                 ; iter != children.end() ; ++iter )
  92             {
  93                 if (obj->isAncestorOf(*iter)) {
  94                     if (!found_one) {
  95                         found_one = true;
  96                         new_children.insert(new_children.end(),
  97                                             children.begin(), iter);
  98                     }
  99                     *descendants++ = *iter;
 100                 } else if (found_one) {
 101                     new_children.push_back(*iter);
 102                 }
 103             }
 104             if (found_one) {
 105                 children.swap(new_children);
 106             }
 107         }
 108
 109         unsigned removeChild(SPObject *obj) {
 110             Siblings::iterator found;
 111             found = std::find(children.begin(), children.end(), obj);
 112             unsigned index = found - children.begin();
 113             if ( found != children.end() ) {
 114                 children.erase(found);
 115             }
 116             return index;
 117         }
 118     };
 119
 120     typedef std::map<SPObject *, Record> Map;
 121     Map records;
 122
 123     sigc::signal<void ()> changed_signal;
 124     sigc::signal<void (SPObject *)> added_signal;
 125     sigc::signal<void (SPObject *)> removed_signal;
 126
 127     Relations() { records[nullptr]; }
 128
 129     ~Relations() {
 130         for (auto & iter : records)
 131         {
 132             if (iter.first) {
 133                 sp_object_unref(iter.first);
 134                 Record &record=iter.second;
 135                 record.release_connection.disconnect();
 136                 record.position_changed_connection.disconnect();
 137             }
 138         }
 139     }
 140
 141     Record *get(SPObject *obj) {
 142         auto found=records.find(obj);
 143         if ( found != records.end() ) {
 144             return &found->second;
 145         } else {
 146             return nullptr;
 147         }
 148     }
 149
 150     void addOne(SPObject *obj);
 151     void remove(SPObject *obj, bool subtree);
 152     void reorder(SPObject *obj);
 153     void clear();
 154
 155 private:
 156     Record &_doAdd(SPObject *obj) {
 157         sp_object_ref(obj);
 158         Record &record=records[obj];
 159         record.release_connection
 160           = obj->connectRelease(
 161               sigc::mem_fun(*this, &Relations::_release_object)
 162             );
 163         record.position_changed_connection
 164           = obj->connectPositionChanged(
 165               sigc::mem_fun(*this, &Relations::reorder)
 166             );
 167         return record;
 168     }
 169
 170     void _notifyAdded(SPObject *obj) {
 171         added_signal.emit(obj);
 172     }
 173
 174     void _doRemove(SPObject *obj) {
 175         Record &record=records[obj];
 176
 177         if ( record.parent == nullptr ) {
 178             Record &root = records[nullptr];
 179             for ( Siblings::iterator it = root.children.begin(); it != root.children.end(); ++it ) {
 180                 if ( *it == obj ) {
 181                     root.children.erase( it );
 182                     break;
 183                 }
 184             }
 185         }
 186
 187         record.release_connection.disconnect();
 188         record.position_changed_connection.disconnect();
 189         records.erase(obj);
 190         removed_signal.emit(obj);
 191         sp_object_unref(obj);
 192     }
 193
 194     void _doRemoveSubtree(SPObject *obj) {
 195         Record *record=get(obj);
 196         if (record) {
 197             Siblings &children=record->children;
 198             for (auto & iter : children)
 199             {
 200                 _doRemoveSubtree(iter);
 201             }
 202             _doRemove(obj);
 203         }
 204     }
 205
 206     void _release_object(SPObject *obj) {
 207         if (get(obj)) {
 208             remove(obj, true);
 209         }
 210     }
 211 };
 212
 213 DocumentSubset::DocumentSubset()
 214     : _relations(std::make_unique<DocumentSubset::Relations>())
 215 {
 216 }
 217
 218 DocumentSubset::~DocumentSubset() = default;
 219
 220
 221 void DocumentSubset::Relations::addOne(SPObject *obj) {
 222     g_return_if_fail( obj != nullptr );
 223     g_return_if_fail( get(obj) == nullptr );
 224
 225     Record &record=_doAdd(obj);
 226
 227     /* find the nearest ancestor in the subset */
 228     Record *parent_record=nullptr;
 229     for ( SPObject::ParentIterator parent_iter=obj->parent
 230         ; !parent_record && parent_iter ; ++parent_iter )
 231     {
 232         parent_record = get(parent_iter);
 233         if (parent_record) {
 234             record.parent = parent_iter;
 235         }
 236     }
 237     if (!parent_record) {
 238         parent_record = get(nullptr);
 239         g_assert( parent_record != nullptr );
 240     }
 241
 242     Siblings &children=record.children;
 243
 244     /* reparent descendants of obj to obj */
 245     parent_record->extractDescendants(
 246         std::back_insert_iterator<Siblings>(children),
 247         obj
 248     );
 249     for (auto & iter : children)
 250     {
 251         Record *child_record=get(iter);
 252         g_assert( child_record != nullptr );
 253         child_record->parent = obj;
 254     }
 255
 256     /* add obj to the child list */
 257     parent_record->addChild(obj);
 258
 259     _notifyAdded(obj);
 260     changed_signal.emit();
 261 }
 262
 263 void DocumentSubset::Relations::remove(SPObject *obj, bool subtree) {
 264     g_return_if_fail( obj != nullptr );
 265
 266     Record *record=get(obj);
 267     g_return_if_fail( record != nullptr );
 268
 269     Record *parent_record=get(record->parent);
 270     g_assert( parent_record != nullptr );
 271
 272     unsigned index=parent_record->removeChild(obj);
 273
 274     if (subtree) {
 275         _doRemoveSubtree(obj);
 276     } else {
 277         /* reparent obj's orphaned children to their grandparent */
 278         Siblings &siblings=parent_record->children;
 279         Siblings &children=record->children;
 280         siblings.insert(siblings.begin()+index,
 281                         children.begin(), children.end());
 282
 283         for (auto & iter : children)
 284         {
 285             Record *child_record=get(iter);
 286             g_assert( child_record != nullptr );
 287             child_record->parent = record->parent;
 288         }
 289
 290         /* remove obj's record */
 291         _doRemove(obj);
 292     }
 293
 294     changed_signal.emit();
 295 }
 296
 297 void DocumentSubset::Relations::clear() {
 298     Record &root=records[nullptr];
 299
 300     while (!root.children.empty()) {
 301         _doRemoveSubtree(root.children.front());
 302     }
 303
 304     changed_signal.emit();
 305 }
 306
 307 void DocumentSubset::Relations::reorder(SPObject *obj) {
 308     SPObject::ParentIterator parent=obj;
 309
 310     /* find nearest ancestor in the subset */
 311     Record *parent_record=nullptr;
 312     while (!parent_record) {
 313         parent_record = get(++parent);
 314     }
 315
 316     if (get(obj)) {
 317         /* move the object if it's in the subset */
 318         parent_record->removeChild(obj);
 319         parent_record->addChild(obj);
 320         changed_signal.emit();
 321     } else {
 322         /* otherwise, move any top-level descendants */
 323         Siblings descendants;
 324         parent_record->extractDescendants(
 325             std::back_insert_iterator<Siblings>(descendants),
 326             obj
 327         );
 328         if (!descendants.empty()) {
 329             unsigned index=parent_record->findInsertIndex(obj);
 330             Siblings &family=parent_record->children;
 331             family.insert(family.begin()+index,
 332                           descendants.begin(), descendants.end());
 333             changed_signal.emit();
 334         }
 335     }
 336 }
 337
 338 void DocumentSubset::_addOne(SPObject *obj) {
 339     _relations->addOne(obj);
 340 }
 341
 342 void DocumentSubset::_remove(SPObject *obj, bool subtree) {
 343     _relations->remove(obj, subtree);
 344 }
 345
 346 void DocumentSubset::_clear() {
 347     _relations->clear();
 348 }
 349
 350 bool DocumentSubset::includes(SPObject *obj) const {
 351     return _relations->get(obj);
 352 }
 353
 354 SPObject *DocumentSubset::parentOf(SPObject *obj) const {
 355     auto const record = _relations->get(obj);
 356     return ( record ? record->parent : nullptr );
 357 }
 358
 359 unsigned DocumentSubset::childCount(SPObject *obj) const {
 360     auto const record = _relations->get(obj);
 361     return ( record ? record->children.size() : 0 );
 362 }
 363
 364 unsigned DocumentSubset::indexOf(SPObject *obj) const {
 365     SPObject *parent=parentOf(obj);
 366     auto const record = _relations->get(parent);
 367     return ( record ? record->childIndex(obj) : 0 );
 368 }
 369
 370 SPObject *DocumentSubset::nthChildOf(SPObject *obj, unsigned n) const {
 371     auto const record = _relations->get(obj);
 372     return ( record ? record->children[n] : nullptr );
 373 }
 374
 375 sigc::connection DocumentSubset::connectChanged(sigc::slot<void ()> slot) const {
 376     return _relations->changed_signal.connect(slot);
 377 }
 378
 379 sigc::connection
 380 DocumentSubset::connectAdded(sigc::slot<void (SPObject *)> slot) const {
 381     return _relations->added_signal.connect(slot);
 382 }
 383
 384 sigc::connection
 385 DocumentSubset::connectRemoved(sigc::slot<void (SPObject *)> slot) const {
 386     return _relations->removed_signal.connect(slot);
 387 }
 388
 389 }
 390
 391 /*
 392   Local Variables:
 393   mode:c++
 394   c-file-style:"stroustrup"
 395   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 396   indent-tabs-mode:nil
 397   fill-column:99
 398   End:
 399 */
 400 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :