src/document-subset.cpp

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