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