void Preferences::addObserver(Observer &o)
{
    // prevent adding the same observer twice
    if ( _observer_map.find(&o) != _observer_map.end() ) return;
    
    Glib::ustring node_key, attr_key;
    Inkscape::XML::Node *node;
    node = _findObserverNode(o.observed_path, node_key, attr_key, false);
    if (!node) return;
    
    // set additional data
    _ObserverData *priv_data = new _ObserverData;
    priv_data->_node = node;
    priv_data->_is_attr = !attr_key.empty();
    o._data = static_cast<void*>(priv_data);
    
    _observer_map[&o] = new PrefNodeObserver(o, attr_key);
    
    // if we watch a single pref, we want to receive notifications only for a single node
    if (priv_data->_is_attr) {
        node->addObserver( *(_observer_map[&o]) );
    } else {
        node->addSubtreeObserver( *(_observer_map[&o]) );
    }
}

static void
sp_lpe_item_create_original_path_recursive(SPLPEItem *lpeitem)
{
    g_return_if_fail(lpeitem != NULL);

    SPMask * mask = lpeitem->mask_ref->getObject();
    if(mask)
    {
        sp_lpe_item_create_original_path_recursive(SP_LPE_ITEM(mask->firstChild()));
    }
    SPClipPath * clipPath = lpeitem->clip_ref->getObject();
    if(clipPath)
    {
        sp_lpe_item_create_original_path_recursive(SP_LPE_ITEM(clipPath->firstChild()));
    }
    if (SP_IS_GROUP(lpeitem)) {
        GSList const *item_list = sp_item_group_item_list(SP_GROUP(lpeitem));
        for ( GSList const *iter = item_list; iter; iter = iter->next ) {
            SPObject *subitem = static_cast<SPObject *>(iter->data);
            if (SP_IS_LPE_ITEM(subitem)) {
                sp_lpe_item_create_original_path_recursive(SP_LPE_ITEM(subitem));
            }
        }
    }
    else if (SP_IS_PATH(lpeitem)) {
        Inkscape::XML::Node *pathrepr = lpeitem->getRepr();
        if ( !pathrepr->attribute("inkscape:original-d") ) {
            pathrepr->setAttribute("inkscape:original-d", pathrepr->attribute("d"));
        }
    }
}

void SPTextPath::build(SPDocument *doc, Inkscape::XML::Node *repr) {
    this->readAttr( "x" );
    this->readAttr( "y" );
    this->readAttr( "dx" );
    this->readAttr( "dy" );
    this->readAttr( "rotate" );
    this->readAttr( "startOffset" );
    this->readAttr( "xlink:href" );

    bool  no_content = true;

    for (Inkscape::XML::Node* rch = repr->firstChild() ; rch != NULL; rch = rch->next()) {
        if ( rch->type() == Inkscape::XML::TEXT_NODE )
        {
            no_content = false;
            break;
        }
    }

    if ( no_content ) {
        Inkscape::XML::Document *xml_doc = doc->getReprDoc();
        Inkscape::XML::Node* rch = xml_doc->createTextNode("");
        repr->addChild(rch, NULL);
    }

    SPItem::build(doc, repr);
}

/**
 * Writes the gradient's internal vector (whether from its own stops, or
 * inherited from refs) into the gradient repr as svg:stop elements.
 */
void
sp_gradient_repr_write_vector(SPGradient *gr)
{
    g_return_if_fail(gr != NULL);
    g_return_if_fail(SP_IS_GRADIENT(gr));

    Inkscape::XML::Document *xml_doc = gr->document->getReprDoc();
    Inkscape::XML::Node *repr = gr->getRepr();

    /* We have to be careful, as vector may be our own, so construct repr list at first */
    GSList *cl = NULL;

    for (guint i = 0; i < gr->vector.stops.size(); i++) {
        Inkscape::CSSOStringStream os;
        Inkscape::XML::Node *child = xml_doc->createElement("svg:stop");
        sp_repr_set_css_double(child, "offset", gr->vector.stops[i].offset);
        /* strictly speaking, offset an SVG <number> rather than a CSS one, but exponents make no
         * sense for offset proportions. */
        os << "stop-color:" << gr->vector.stops[i].color.toString() << ";stop-opacity:" << gr->vector.stops[i].opacity;
        child->setAttribute("style", os.str().c_str());
        /* Order will be reversed here */
        cl = g_slist_prepend(cl, child);
    }

    sp_gradient_repr_clear_vector(gr);

    /* And insert new children from list */
    while (cl) {
        Inkscape::XML::Node *child = static_cast<Inkscape::XML::Node *>(cl->data);
        repr->addChild(child, NULL);
        Inkscape::GC::release(child);
        cl = g_slist_remove(cl, child);
    }
}

Glib::ustring sp_filter_get_new_result_name(SPFilter *filter) {
    g_assert(filter != NULL);
    int largest = 0;

    SPObject *primitive_obj = filter->children;
    while (primitive_obj) {
        if (SP_IS_FILTER_PRIMITIVE(primitive_obj)) {
            Inkscape::XML::Node *repr = primitive_obj->getRepr();
            char const *result = repr->attribute("result");
            int index;
            if (result)
            {
                if (sscanf(result, "result%5d", &index) == 1)
                {
                    if (index > largest)
                    {
                        largest = index;
                    }
                }
            }
        }
        primitive_obj = primitive_obj->next;
    }

    return "result" + Glib::Ascii::dtostr(largest + 1);
}

// Create a mask element (using passed elements), add it to <defs>
const gchar *SPClipPath::create (GSList *reprs, SPDocument *document, Geom::Affine const* applyTransform)
{
    Inkscape::XML::Node *defsrepr = document->getDefs()->getRepr();

    Inkscape::XML::Document *xml_doc = document->getReprDoc();
    Inkscape::XML::Node *repr = xml_doc->createElement("svg:clipPath");
    repr->setAttribute("clipPathUnits", "userSpaceOnUse");

    defsrepr->appendChild(repr);
    const gchar *id = repr->attribute("id");
    SPObject *clip_path_object = document->getObjectById(id);

    for (GSList *it = reprs; it != NULL; it = it->next) {
        Inkscape::XML::Node *node = (Inkscape::XML::Node *)(it->data);
        SPItem *item = SP_ITEM(clip_path_object->appendChildRepr(node));

        if (NULL != applyTransform) {
            Geom::Affine transform (item->transform);
            transform *= (*applyTransform);
            item->doWriteTransform(item->getRepr(), transform);
        }
    }

    Inkscape::GC::release(repr);
    return id;
}

// Create a mask element (using passed elements), add it to <defs>
const gchar *
sp_clippath_create (GSList *reprs, SPDocument *document, Geom::Matrix const* applyTransform)
{
    Inkscape::XML::Node *defsrepr = SP_OBJECT_REPR (SP_DOCUMENT_DEFS (document));

    Inkscape::XML::Document *xml_doc = sp_document_repr_doc(document);
    Inkscape::XML::Node *repr = xml_doc->createElement("svg:clipPath");
    repr->setAttribute("clipPathUnits", "userSpaceOnUse");

    defsrepr->appendChild(repr);
    const gchar *id = repr->attribute("id");
    SPObject *clip_path_object = document->getObjectById(id);

    for (GSList *it = reprs; it != NULL; it = it->next) {
        Inkscape::XML::Node *node = (Inkscape::XML::Node *)(it->data);
        SPItem *item = SP_ITEM(clip_path_object->appendChildRepr(node));

        if (NULL != applyTransform) {
            Geom::Matrix transform (item->transform);
            transform *= (*applyTransform);
            sp_item_write_transform(item, SP_OBJECT_REPR(item), transform);
        }
    }

    Inkscape::GC::release(repr);
    return id;
}

static void
sp_group_perform_patheffect(SPGroup *group, SPGroup *topgroup, bool write)
{
    GSList const *item_list = sp_item_group_item_list(SP_GROUP(group));
    for ( GSList const *iter = item_list; iter; iter = iter->next ) {
        SPObject *subitem = static_cast<SPObject *>(iter->data);
        if (SP_IS_GROUP(subitem)) {
            sp_group_perform_patheffect(SP_GROUP(subitem), topgroup, write);
        } else if (SP_IS_SHAPE(subitem)) {
            SPCurve * c = NULL;
            if (SP_IS_PATH(subitem)) {
                c = SP_PATH(subitem)->get_original_curve();
            } else {
                c = SP_SHAPE(subitem)->getCurve();
            }
            // only run LPEs when the shape has a curve defined
            if (c) {
                sp_lpe_item_perform_path_effect(SP_LPE_ITEM(topgroup), c);
                SP_SHAPE(subitem)->setCurve(c, TRUE);

                if (write) {
                    Inkscape::XML::Node *repr = subitem->getRepr();
                    gchar *str = sp_svg_write_path(c->get_pathvector());
                    repr->setAttribute("d", str);
#ifdef GROUP_VERBOSE
g_message("sp_group_perform_patheffect writes 'd' attribute");
#endif
                    g_free(str);
                }

                c->unref();
            }
        }
    }
}

std::string NodeTraits::get_type_string(Inkscape::XML::Node const &node)
{
    std::string name;

    switch (node.type()) {
    case Inkscape::XML::TEXT_NODE:
        name = "string";
        break;

    case Inkscape::XML::ELEMENT_NODE: {
        char const *const sptype = node.attribute("sodipodi:type");

        if (sptype) {
            name = sptype;
        } else {
            name = node.name();
        }
        break;
    }
    default:
        name = "";
        break;
    }

    return name;
}

static void
sp_item_create_link(GtkMenuItem *menuitem, SPItem *item)
{
    g_assert(SP_IS_ITEM(item));
    g_assert(!SP_IS_ANCHOR(item));

    SPDesktop *desktop = (SPDesktop*)gtk_object_get_data(GTK_OBJECT(menuitem), "desktop");
    g_return_if_fail(desktop != NULL);

    Inkscape::XML::Document *xml_doc = sp_document_repr_doc(desktop->doc());
    Inkscape::XML::Node *repr = xml_doc->createElement("svg:a");
    SP_OBJECT_REPR(SP_OBJECT_PARENT(item))->addChild(repr, SP_OBJECT_REPR(item));
    SPObject *object = SP_OBJECT_DOCUMENT(item)->getObjectByRepr(repr);
    g_return_if_fail(SP_IS_ANCHOR(object));

    const char *id = SP_OBJECT_REPR(item)->attribute("id");
    Inkscape::XML::Node *child = SP_OBJECT_REPR(item)->duplicate(xml_doc);
    SP_OBJECT(item)->deleteObject(false);
    repr->addChild(child, NULL);
    child->setAttribute("id", id);

    Inkscape::GC::release(repr);
    Inkscape::GC::release(child);

    sp_document_done(SP_OBJECT_DOCUMENT(object), SP_VERB_NONE,
                     _("Create link"));

    sp_object_attributes_dialog(object, "SPAnchor");

    sp_desktop_selection(desktop)->set(SP_ITEM(object));
}

void SPObject::build(SPDocument *document, Inkscape::XML::Node *repr) {
    SPObject* object = this;

    /* Nothing specific here */
    debug("id=%p, typename=%s", object, g_type_name_from_instance((GTypeInstance*)object));

    object->readAttr("xml:space");
    object->readAttr("inkscape:label");
    object->readAttr("inkscape:collect");

    for (Inkscape::XML::Node *rchild = repr->firstChild() ; rchild != NULL; rchild = rchild->next()) {
        const std::string typeString = NodeTraits::get_type_string(*rchild);

        SPObject* child = SPFactory::instance().createObject(typeString);
        if (child == NULL) {
            // Currenty, there are many node types that do not have
            // corresponding classes in the SPObject tree.
            // (rdf:RDF, inkscape:clipboard, ...)
            // Thus, simply ignore this case for now.
            continue;
        }

        object->attach(child, object->lastChild());
        sp_object_unref(child, NULL);
        child->invoke_build(document, rchild, object->cloned);
    }
}

std::vector<Glib::ustring> ResourceManagerImpl::findBrokenLinks( SPDocument *doc )
{
    std::vector<Glib::ustring> result;
    std::set<Glib::ustring> uniques;

    if ( doc ) {
        GSList const *images = doc->getResourceList("image");
        for (GSList const *it = images; it; it = it->next) {
            Inkscape::XML::Node *ir = static_cast<SPObject *>(it->data)->getRepr();

            gchar const *href = ir->attribute("xlink:href");
            if ( href &&  ( uniques.find(href) == uniques.end() ) ) {
                std::string uri;
                if ( extractFilepath( href, uri ) ) {
                    if ( Glib::path_is_absolute(uri) ) {
                        if ( !Glib::file_test(uri, Glib::FILE_TEST_EXISTS) ) {
                            result.push_back(href);
                            uniques.insert(href);
                        }
                    } else {
                        std::string combined = Glib::build_filename(doc->getBase(), uri);
                        if ( !Glib::file_test(uri, Glib::FILE_TEST_EXISTS) ) {
                            result.push_back(href);
                            uniques.insert(href);
                        }
                    }
                }
            }
        }        
    }

    return result;
}

static void
sp_textpath_build(SPObject *object, SPDocument *doc, Inkscape::XML::Node *repr)
{
    //SPTextPath *textpath = SP_TEXTPATH(object);
	
    sp_object_read_attr(object, "x");
    sp_object_read_attr(object, "y");
    sp_object_read_attr(object, "dx");
    sp_object_read_attr(object, "dy");
    sp_object_read_attr(object, "rotate");
    sp_object_read_attr(object, "startOffset");
    sp_object_read_attr(object, "xlink:href");
	
    bool  no_content=true;
    for (Inkscape::XML::Node* rch = repr->firstChild() ; rch != NULL; rch = rch->next()) {
        if ( rch->type() == Inkscape::XML::TEXT_NODE ) {no_content=false;break;}
    }
	
    if ( no_content ) {
        Inkscape::XML::Document *xml_doc = sp_document_repr_doc(doc);
        Inkscape::XML::Node* rch = xml_doc->createTextNode("");
        repr->addChild(rch, NULL);
    }
	
    if (((SPObjectClass *) textpath_parent_class)->build)
        ((SPObjectClass *) textpath_parent_class)->build(object, doc, repr);
}

void spdc_create_single_dot(ToolBase *ec, Geom::Point const &pt, char const *tool, guint event_state) {
    g_return_if_fail(!strcmp(tool, "/tools/freehand/pen") || !strcmp(tool, "/tools/freehand/pencil"));
    Glib::ustring tool_path = tool;

    SPDesktop *desktop = ec->desktop;
    Inkscape::XML::Document *xml_doc = desktop->doc()->getReprDoc();
    Inkscape::XML::Node *repr = xml_doc->createElement("svg:path");
    repr->setAttribute("sodipodi:type", "arc");
    SPItem *item = SP_ITEM(desktop->currentLayer()->appendChildRepr(repr));
    Inkscape::GC::release(repr);

    // apply the tool's current style
    sp_desktop_apply_style_tool(desktop, repr, tool, false);

    // find out stroke width (TODO: is there an easier way??)
    double stroke_width = 3.0;
    gchar const *style_str = repr->attribute("style");
    if (style_str) {
        SPStyle style(SP_ACTIVE_DOCUMENT);
        style.mergeString(style_str);
        stroke_width = style.stroke_width.computed;
    }

    // unset stroke and set fill color to former stroke color
    gchar * str;
    str = g_strdup_printf("fill:#%06x;stroke:none;", sp_desktop_get_color_tool(desktop, tool, false) >> 8);
    repr->setAttribute("style", str);
    g_free(str);

    // put the circle where the mouse click occurred and set the diameter to the
    // current stroke width, multiplied by the amount specified in the preferences
    Inkscape::Preferences *prefs = Inkscape::Preferences::get();

    Geom::Affine const i2d (item->i2dt_affine ());
    Geom::Point pp = pt * i2d.inverse();
    double rad = 0.5 * prefs->getDouble(tool_path + "/dot-size", 3.0);
    if (event_state & GDK_MOD1_MASK) {
        // TODO: We vary the dot size between 0.5*rad and 1.5*rad, where rad is the dot size
        // as specified in prefs. Very simple, but it might be sufficient in practice. If not,
        // we need to devise something more sophisticated.
        double s = g_random_double_range(-0.5, 0.5);
        rad *= (1 + s);
    }
    if (event_state & GDK_SHIFT_MASK) {
        // double the point size
        rad *= 2;
    }

    sp_repr_set_svg_double (repr, "sodipodi:cx", pp[Geom::X]);
    sp_repr_set_svg_double (repr, "sodipodi:cy", pp[Geom::Y]);
    sp_repr_set_svg_double (repr, "sodipodi:rx", rad * stroke_width);
    sp_repr_set_svg_double (repr, "sodipodi:ry", rad * stroke_width);
    item->updateRepr();

    desktop->getSelection()->set(item);

    desktop->messageStack()->flash(Inkscape::NORMAL_MESSAGE, _("Creating single dot"));
    DocumentUndo::done(desktop->getDocument(), SP_VERB_NONE, _("Create single dot"));
}

bool ResourceManagerImpl::fixupBrokenLinks(SPDocument *doc)
{
    bool changed = false;
    if ( doc ) {
        // TODO debug g_message("FIXUP FIXUP FIXUP FIXUP FIXUP FIXUP FIXUP FIXUP FIXUP FIXUP");
        // TODO debug g_message("      base is [%s]", doc->getBase());

        std::vector<Glib::ustring> brokenHrefs = findBrokenLinks(doc);
        if ( !brokenHrefs.empty() ) {
            // TODO debug g_message("    FOUND SOME LINKS %d", static_cast<int>(brokenHrefs.size()));
            for ( std::vector<Glib::ustring>::iterator it = brokenHrefs.begin(); it != brokenHrefs.end(); ++it ) {
                // TODO debug g_message("        [%s]", it->c_str());
            }
        }

        std::map<Glib::ustring, Glib::ustring> mapping = locateLinks(doc->getBase(), brokenHrefs);
        for ( std::map<Glib::ustring, Glib::ustring>::iterator it = mapping.begin(); it != mapping.end(); ++it )
        {
            // TODO debug g_message("     [%s] ==> {%s}", it->first.c_str(), it->second.c_str());
        }

        bool savedUndoState = DocumentUndo::getUndoSensitive(doc);
        DocumentUndo::setUndoSensitive(doc, true);

        GSList const *images = doc->getResourceList("image");
        for (GSList const *it = images; it; it = it->next) {
            Inkscape::XML::Node *ir = static_cast<SPObject *>(it->data)->getRepr();

            gchar const *href = ir->attribute("xlink:href");
            if ( href ) {
                // TODO debug g_message("                  consider [%s]", href);
                
                if ( mapping.find(href) != mapping.end() ) {
                    // TODO debug g_message("                     Found a replacement");

                    ir->setAttribute( "xlink:href", mapping[href].c_str() );
                    if ( ir->attribute( "sodipodi:absref" ) ) {
                        ir->setAttribute( "sodipodi:absref", 0 ); // Remove this attribute
                    }

                    SPObject *updated = doc->getObjectByRepr(ir);
                    if (updated) {
                        // force immediate update of dependant attributes
                        updated->updateRepr();
                    }

                    changed = true;
                }
            }
        }
        if ( changed ) {
            DocumentUndo::done( doc, SP_VERB_DIALOG_XML_EDITOR, _("Fixup broken links") );
        }
        DocumentUndo::setUndoSensitive(doc, savedUndoState);
    }

    return changed;
}

/**
    \brief  This actually draws the grid.
    \param  module   The effect that was called (unused)
    \param  document What should be edited.
*/
void
Grid::effect (Inkscape::Extension::Effect *module, Inkscape::UI::View::View *document, Inkscape::Extension::Implementation::ImplementationDocumentCache * /*docCache*/)
{
    Inkscape::Selection * selection     = ((SPDesktop *)document)->selection;

    Geom::Rect bounding_area = Geom::Rect(Geom::Point(0,0), Geom::Point(100,100));
    if (selection->isEmpty()) {
        /* get page size */
        SPDocument * doc = document->doc();
        bounding_area = Geom::Rect(  Geom::Point(0,0),
                                     Geom::Point(doc->getWidth(), doc->getHeight())  );
    } else {
        Geom::OptRect bounds = selection->visualBounds();
        if (bounds) {
            bounding_area = *bounds;
        }

        gdouble doc_height  =  (document->doc())->getHeight();
        Geom::Rect temprec = Geom::Rect(Geom::Point(bounding_area.min()[Geom::X], doc_height - bounding_area.min()[Geom::Y]),
                                    Geom::Point(bounding_area.max()[Geom::X], doc_height - bounding_area.max()[Geom::Y]));

        bounding_area = temprec;
    }

    float spacings[2] = { module->get_param_float("xspacing"),
                          module->get_param_float("yspacing") };
    float line_width = module->get_param_float("lineWidth");
    float offsets[2] = { module->get_param_float("xoffset"),
                         module->get_param_float("yoffset") };

    Glib::ustring path_data("");

    path_data = build_lines(bounding_area,
                                 offsets, spacings);
    Inkscape::XML::Document * xml_doc = document->doc()->getReprDoc();

    //XML Tree being used directly here while it shouldn't be.
    Inkscape::XML::Node * current_layer = static_cast<SPDesktop *>(document)->currentLayer()->getRepr();
    Inkscape::XML::Node * path = xml_doc->createElement("svg:path");

    path->setAttribute("d", path_data.c_str());

    Glib::ustring style("fill:none;fill-opacity:0.75000000;fill-rule:evenodd;stroke:#000000;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1.0000000");
    style += ";stroke-width:";
    gchar floatstring[64];
    std::ostringstream stringstream;
    stringstream << line_width;
    sprintf(floatstring, "%s", stringstream.str().c_str());
    style += floatstring;
    style += "pt";
    path->setAttribute("style", style.c_str());

    current_layer->appendChild(path);
		Inkscape::GC::release(path);

    return;
}

void Preferences::_setRawValue(Glib::ustring const &path, gchar const *value)
{
    // create node and attribute keys
    Glib::ustring node_key, attr_key;
    _keySplit(path, node_key, attr_key);
    
    // set the attribute
    Inkscape::XML::Node *node = _getNode(node_key, true);
    node->setAttribute(attr_key.data(), value);
}

Inkscape::XML::Node *Parameter::document_param_node(SPDocument * doc)
{
    Inkscape::XML::Document *xml_doc = doc->getReprDoc();
    Inkscape::XML::Node * defs = doc->getDefs()->getRepr();
    Inkscape::XML::Node * params = NULL;

    GQuark const name_quark = g_quark_from_string("inkscape:extension-params");

    for (Inkscape::XML::Node * child = defs->firstChild();
            child != NULL;
            child = child->next()) {
        if ((GQuark)child->code() == name_quark &&
                !strcmp(child->attribute("extension"), extension->get_id())) {
            params = child;
            break;
        }
    }

    if (params == NULL) {
        params = xml_doc->createElement("inkscape:extension-param");
        params->setAttribute("extension", extension->get_id());
        defs->appendChild(params);
        Inkscape::GC::release(params);
    }

    return params;
}

/**
 * @brief Get the paths to all subdirectories of the specified path
 * @param path Preference path to query
 * @return A vector containing absolute paths to all subdirectories in the given path
 */
std::vector<Glib::ustring> Preferences::getAllDirs(Glib::ustring const &path)
{
    std::vector<Glib::ustring> temp;
    Inkscape::XML::Node *node = _getNode(path, false);
    if (!node) return temp;
    
    for (Inkscape::XML::NodeSiblingIterator i = node->firstChild(); i; ++i) {
        temp.push_back(path + '/' + i->attribute("id"));
    }
    return temp;
}

Inkscape::XML::Node *box3d_side_convert_to_path(Box3DSide *side) {
    // TODO: Copy over all important attributes (see sp_selected_item_to_curved_repr() for an example)
    SPDocument *doc = side->document;
    Inkscape::XML::Document *xml_doc = doc->getReprDoc();

    Inkscape::XML::Node *repr = xml_doc->createElement("svg:path");
    repr->setAttribute("d", side->getAttribute("d"));
    repr->setAttribute("style", side->getAttribute("style"));

    return repr;
}