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 */
10 #include "gc-finalized.h"
11 #include "document-subset.h"
12 #include "document.h"
13 #include "sp-object.h"
15 #include <glib/gmessages.h>
17 #include <sigc++/signal.h>
18 #include <sigc++/functors/mem_fun.h>
20 #include "util/list.h"
21 #include "util/reverse-list.h"
23 #include <vector>
24 #include <map>
25 #include <algorithm>
26 #include <iterator>
28 namespace Inkscape {
30 struct DocumentSubset::Relations : public GC::Managed<GC::ATOMIC>,
31 public GC::Finalized
32 {
33 typedef std::vector<SPObject *> Siblings;
35 struct Record {
36 SPObject *parent;
37 Siblings children;
39 gulong release_connection;
40 sigc::connection position_changed_connection;
42 Record() : parent(NULL), release_connection(0) {}
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 }
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;
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 }
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 }
85 return last - children.begin();
86 }
87 }
89 void addChild(SPObject *obj) {
90 unsigned index=findInsertIndex(obj);
91 children.insert(children.begin()+index, obj);
92 }
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 }
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 };
130 typedef std::map<SPObject *, Record> Map;
131 Map records;
133 sigc::signal<void> changed_signal;
134 sigc::signal<void, SPObject *> added_signal;
135 sigc::signal<void, SPObject *> removed_signal;
137 Relations() { records[NULL]; }
139 ~Relations() {
140 for ( Map::iterator iter=records.begin()
141 ; iter != records.end() ; ++iter )
142 {
143 sp_object_unref((*iter).first);
144 }
145 }
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 }
156 void addOne(SPObject *obj);
157 void remove(SPObject *obj, bool subtree);
158 void reorder(SPObject *obj);
159 void clear();
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 }
175 void _notifyAdded(SPObject *obj) {
176 added_signal.emit(obj);
177 }
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);
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 }
198 removed_signal.emit(obj);
199 sp_object_unref(obj);
200 }
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 }
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 };
223 DocumentSubset::DocumentSubset()
224 : _relations(new DocumentSubset::Relations())
225 {
226 }
228 void DocumentSubset::Relations::addOne(SPObject *obj) {
229 g_return_if_fail( obj != NULL );
230 g_return_if_fail( get(obj) == NULL );
232 Record &record=_doAdd(obj);
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 }
249 Siblings &children=record.children;
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 }
264 /* add obj to the child list */
265 parent_record->addChild(obj);
267 _notifyAdded(obj);
268 changed_signal.emit();
269 }
271 void DocumentSubset::Relations::remove(SPObject *obj, bool subtree) {
272 g_return_if_fail( obj != NULL );
274 Record *record=get(obj);
275 g_return_if_fail( record != NULL );
277 Record *parent_record=get(record->parent);
278 g_assert( parent_record != NULL );
280 unsigned index=parent_record->removeChild(obj);
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());
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 }
299 /* remove obj's record */
300 _doRemove(obj);
301 }
303 changed_signal.emit();
304 }
306 void DocumentSubset::Relations::clear() {
307 Record &root=records[NULL];
309 while (!root.children.empty()) {
310 _doRemoveSubtree(root.children.front());
311 }
313 changed_signal.emit();
314 }
316 void DocumentSubset::Relations::reorder(SPObject *obj) {
317 SPObject::ParentIterator parent=obj;
319 /* find nearest ancestor in the subset */
320 Record *parent_record=NULL;
321 while (!parent_record) {
322 parent_record = get(++parent);
323 }
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 }
347 void DocumentSubset::_addOne(SPObject *obj) {
348 _relations->addOne(obj);
349 }
351 void DocumentSubset::_remove(SPObject *obj, bool subtree) {
352 _relations->remove(obj, subtree);
353 }
355 void DocumentSubset::_clear() {
356 _relations->clear();
357 }
359 bool DocumentSubset::includes(SPObject *obj) const {
360 return _relations->get(obj);
361 }
363 SPObject *DocumentSubset::parentOf(SPObject *obj) const {
364 Relations::Record *record=_relations->get(obj);
365 return ( record ? record->parent : NULL );
366 }
368 unsigned DocumentSubset::childCount(SPObject *obj) const {
369 Relations::Record *record=_relations->get(obj);
370 return ( record ? record->children.size() : 0 );
371 }
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 }
379 SPObject *DocumentSubset::nthChildOf(SPObject *obj, unsigned n) const {
380 Relations::Record *record=_relations->get(obj);
381 return ( record ? record->children[n] : NULL );
382 }
384 sigc::connection DocumentSubset::connectChanged(sigc::slot<void> slot) const {
385 return _relations->changed_signal.connect(slot);
386 }
388 sigc::connection
389 DocumentSubset::connectAdded(sigc::slot<void, SPObject *> slot) const {
390 return _relations->added_signal.connect(slot);
391 }
393 sigc::connection
394 DocumentSubset::connectRemoved(sigc::slot<void, SPObject *> slot) const {
395 return _relations->removed_signal.connect(slot);
396 }
398 }
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 :