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 */
11 #include "gc-finalized.h"
12 #include "document-subset.h"
13 #include "document.h"
14 #include "sp-object.h"
16 #include <glib/gmessages.h>
18 #include <sigc++/signal.h>
19 #include <sigc++/functors/mem_fun.h>
21 #include "util/list.h"
22 #include "util/reverse-list.h"
24 #include <vector>
25 #include <map>
26 #include <algorithm>
27 #include <iterator>
29 namespace Inkscape {
31 struct DocumentSubset::Relations : public GC::Managed<GC::ATOMIC>,
32 public GC::Finalized
33 {
34 typedef std::vector<SPObject *> Siblings;
36 struct Record {
37 SPObject *parent;
38 Siblings children;
40 sigc::connection release_connection;
41 sigc::connection position_changed_connection;
43 Record() : parent(NULL) {}
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 }
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;
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 }
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 }
86 return last - children.begin();
87 }
88 }
90 void addChild(SPObject *obj) {
91 unsigned index=findInsertIndex(obj);
92 children.insert(children.begin()+index, obj);
93 }
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 }
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 };
131 typedef std::map<SPObject *, Record> Map;
132 Map records;
134 sigc::signal<void> changed_signal;
135 sigc::signal<void, SPObject *> added_signal;
136 sigc::signal<void, SPObject *> removed_signal;
138 Relations() { records[NULL]; }
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 }
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 }
162 void addOne(SPObject *obj);
163 void remove(SPObject *obj, bool subtree);
164 void reorder(SPObject *obj);
165 void clear();
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 }
182 void _notifyAdded(SPObject *obj) {
183 added_signal.emit(obj);
184 }
186 void _doRemove(SPObject *obj) {
187 Record &record=records[obj];
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 }
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 }
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 }
219 void _release_object(SPObject *obj) {
220 if (get(obj)) {
221 remove(obj, true);
222 }
223 }
224 };
226 DocumentSubset::DocumentSubset()
227 : _relations(new DocumentSubset::Relations())
228 {
229 }
231 void DocumentSubset::Relations::addOne(SPObject *obj) {
232 g_return_if_fail( obj != NULL );
233 g_return_if_fail( get(obj) == NULL );
235 Record &record=_doAdd(obj);
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 }
252 Siblings &children=record.children;
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 }
267 /* add obj to the child list */
268 parent_record->addChild(obj);
270 _notifyAdded(obj);
271 changed_signal.emit();
272 }
274 void DocumentSubset::Relations::remove(SPObject *obj, bool subtree) {
275 g_return_if_fail( obj != NULL );
277 Record *record=get(obj);
278 g_return_if_fail( record != NULL );
280 Record *parent_record=get(record->parent);
281 g_assert( parent_record != NULL );
283 unsigned index=parent_record->removeChild(obj);
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());
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 }
302 /* remove obj's record */
303 _doRemove(obj);
304 }
306 changed_signal.emit();
307 }
309 void DocumentSubset::Relations::clear() {
310 Record &root=records[NULL];
312 while (!root.children.empty()) {
313 _doRemoveSubtree(root.children.front());
314 }
316 changed_signal.emit();
317 }
319 void DocumentSubset::Relations::reorder(SPObject *obj) {
320 SPObject::ParentIterator parent=obj;
322 /* find nearest ancestor in the subset */
323 Record *parent_record=NULL;
324 while (!parent_record) {
325 parent_record = get(++parent);
326 }
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 }
350 void DocumentSubset::_addOne(SPObject *obj) {
351 _relations->addOne(obj);
352 }
354 void DocumentSubset::_remove(SPObject *obj, bool subtree) {
355 _relations->remove(obj, subtree);
356 }
358 void DocumentSubset::_clear() {
359 _relations->clear();
360 }
362 bool DocumentSubset::includes(SPObject *obj) const {
363 return _relations->get(obj);
364 }
366 SPObject *DocumentSubset::parentOf(SPObject *obj) const {
367 Relations::Record *record=_relations->get(obj);
368 return ( record ? record->parent : NULL );
369 }
371 unsigned DocumentSubset::childCount(SPObject *obj) const {
372 Relations::Record *record=_relations->get(obj);
373 return ( record ? record->children.size() : 0 );
374 }
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 }
382 SPObject *DocumentSubset::nthChildOf(SPObject *obj, unsigned n) const {
383 Relations::Record *record=_relations->get(obj);
384 return ( record ? record->children[n] : NULL );
385 }
387 sigc::connection DocumentSubset::connectChanged(sigc::slot<void> slot) const {
388 return _relations->changed_signal.connect(slot);
389 }
391 sigc::connection
392 DocumentSubset::connectAdded(sigc::slot<void, SPObject *> slot) const {
393 return _relations->added_signal.connect(slot);
394 }
396 sigc::connection
397 DocumentSubset::connectRemoved(sigc::slot<void, SPObject *> slot) const {
398 return _relations->removed_signal.connect(slot);
399 }
401 }
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 :