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