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 sigc::connection release_connection;
40 sigc::connection position_changed_connection;
42 Record() : parent(NULL) {}
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 if ((*iter).first)
144 sp_object_unref((*iter).first);
145 }
146 }
148 Record *get(SPObject *obj) {
149 Map::iterator found=records.find(obj);
150 if ( found != records.end() ) {
151 return &(*found).second;
152 } else {
153 return NULL;
154 }
155 }
157 void addOne(SPObject *obj);
158 void remove(SPObject *obj, bool subtree);
159 void reorder(SPObject *obj);
160 void clear();
162 private:
163 Record &_doAdd(SPObject *obj) {
164 sp_object_ref(obj);
165 Record &record=records[obj];
166 record.release_connection
167 = obj->connectRelease(
168 sigc::mem_fun(this, &Relations::_release_object)
169 );
170 record.position_changed_connection
171 = obj->connectPositionChanged(
172 sigc::mem_fun(this, &Relations::reorder)
173 );
174 return record;
175 }
177 void _notifyAdded(SPObject *obj) {
178 added_signal.emit(obj);
179 }
181 void _doRemove(SPObject *obj) {
182 Record &record=records[obj];
183 record.release_connection.disconnect();
184 record.position_changed_connection.disconnect();
185 records.erase(obj);
187 if ( record.parent == NULL ) {
188 Record &root = records[NULL];
189 for ( Siblings::iterator it = root.children.begin(); it != root.children.end(); ++it ) {
190 if ( *it == obj ) {
191 root.children.erase( it );
192 break;
193 }
194 }
195 }
197 removed_signal.emit(obj);
198 sp_object_unref(obj);
199 }
201 void _doRemoveSubtree(SPObject *obj) {
202 Record *record=get(obj);
203 if (record) {
204 Siblings &children=record->children;
205 for ( Siblings::iterator iter=children.begin()
206 ; iter != children.end() ; ++iter )
207 {
208 _doRemoveSubtree(*iter);
209 }
210 _doRemove(obj);
211 }
212 }
214 void _release_object(SPObject *obj) {
215 if (get(obj)) {
216 remove(obj, true);
217 }
218 }
219 };
221 DocumentSubset::DocumentSubset()
222 : _relations(new DocumentSubset::Relations())
223 {
224 }
226 void DocumentSubset::Relations::addOne(SPObject *obj) {
227 g_return_if_fail( obj != NULL );
228 g_return_if_fail( get(obj) == NULL );
230 Record &record=_doAdd(obj);
232 /* find the nearest ancestor in the subset */
233 Record *parent_record=NULL;
234 for ( SPObject::ParentIterator parent_iter=obj->parent
235 ; !parent_record && parent_iter ; ++parent_iter )
236 {
237 parent_record = get(parent_iter);
238 if (parent_record) {
239 record.parent = parent_iter;
240 }
241 }
242 if (!parent_record) {
243 parent_record = get(NULL);
244 g_assert( parent_record != NULL );
245 }
247 Siblings &children=record.children;
249 /* reparent descendants of obj to obj */
250 parent_record->extractDescendants(
251 std::back_insert_iterator<Siblings>(children),
252 obj
253 );
254 for ( Siblings::iterator iter=children.begin()
255 ; iter != children.end() ; ++iter )
256 {
257 Record *child_record=get(*iter);
258 g_assert( child_record != NULL );
259 child_record->parent = obj;
260 }
262 /* add obj to the child list */
263 parent_record->addChild(obj);
265 _notifyAdded(obj);
266 changed_signal.emit();
267 }
269 void DocumentSubset::Relations::remove(SPObject *obj, bool subtree) {
270 g_return_if_fail( obj != NULL );
272 Record *record=get(obj);
273 g_return_if_fail( record != NULL );
275 Record *parent_record=get(record->parent);
276 g_assert( parent_record != NULL );
278 unsigned index=parent_record->removeChild(obj);
280 if (subtree) {
281 _doRemoveSubtree(obj);
282 } else {
283 /* reparent obj's orphaned children to their grandparent */
284 Siblings &siblings=parent_record->children;
285 Siblings &children=record->children;
286 siblings.insert(siblings.begin()+index,
287 children.begin(), children.end());
289 for ( Siblings::iterator iter=children.begin()
290 ; iter != children.end() ; iter++ )
291 {
292 Record *child_record=get(*iter);
293 g_assert( child_record != NULL );
294 child_record->parent = record->parent;
295 }
297 /* remove obj's record */
298 _doRemove(obj);
299 }
301 changed_signal.emit();
302 }
304 void DocumentSubset::Relations::clear() {
305 Record &root=records[NULL];
307 while (!root.children.empty()) {
308 _doRemoveSubtree(root.children.front());
309 }
311 changed_signal.emit();
312 }
314 void DocumentSubset::Relations::reorder(SPObject *obj) {
315 SPObject::ParentIterator parent=obj;
317 /* find nearest ancestor in the subset */
318 Record *parent_record=NULL;
319 while (!parent_record) {
320 parent_record = get(++parent);
321 }
323 if (get(obj)) {
324 /* move the object if it's in the subset */
325 parent_record->removeChild(obj);
326 parent_record->addChild(obj);
327 changed_signal.emit();
328 } else {
329 /* otherwise, move any top-level descendants */
330 Siblings descendants;
331 parent_record->extractDescendants(
332 std::back_insert_iterator<Siblings>(descendants),
333 obj
334 );
335 if (!descendants.empty()) {
336 unsigned index=parent_record->findInsertIndex(obj);
337 Siblings &family=parent_record->children;
338 family.insert(family.begin()+index,
339 descendants.begin(), descendants.end());
340 changed_signal.emit();
341 }
342 }
343 }
345 void DocumentSubset::_addOne(SPObject *obj) {
346 _relations->addOne(obj);
347 }
349 void DocumentSubset::_remove(SPObject *obj, bool subtree) {
350 _relations->remove(obj, subtree);
351 }
353 void DocumentSubset::_clear() {
354 _relations->clear();
355 }
357 bool DocumentSubset::includes(SPObject *obj) const {
358 return _relations->get(obj);
359 }
361 SPObject *DocumentSubset::parentOf(SPObject *obj) const {
362 Relations::Record *record=_relations->get(obj);
363 return ( record ? record->parent : NULL );
364 }
366 unsigned DocumentSubset::childCount(SPObject *obj) const {
367 Relations::Record *record=_relations->get(obj);
368 return ( record ? record->children.size() : 0 );
369 }
371 unsigned DocumentSubset::indexOf(SPObject *obj) const {
372 SPObject *parent=parentOf(obj);
373 Relations::Record *record=_relations->get(parent);
374 return ( record ? record->childIndex(obj) : 0 );
375 }
377 SPObject *DocumentSubset::nthChildOf(SPObject *obj, unsigned n) const {
378 Relations::Record *record=_relations->get(obj);
379 return ( record ? record->children[n] : NULL );
380 }
382 sigc::connection DocumentSubset::connectChanged(sigc::slot<void> slot) const {
383 return _relations->changed_signal.connect(slot);
384 }
386 sigc::connection
387 DocumentSubset::connectAdded(sigc::slot<void, SPObject *> slot) const {
388 return _relations->added_signal.connect(slot);
389 }
391 sigc::connection
392 DocumentSubset::connectRemoved(sigc::slot<void, SPObject *> slot) const {
393 return _relations->removed_signal.connect(slot);
394 }
396 }
398 /*
399 Local Variables:
400 mode:c++
401 c-file-style:"stroustrup"
402 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
403 indent-tabs-mode:nil
404 fill-column:99
405 End:
406 */
407 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :