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