Merge from trunk

(bzr r8254.1.53)

18 files changed, 989 insertions, 230 deletions

diff --git a/src/util/Makefile_insert b/src/util/Makefile_insert
index b76a4dcdb..d2f005531 100644
--- a/src/util/Makefile_insert
+++ b/src/util/Makefile_insert
@@ -1,24 +1,35 @@
 ## Makefile.am fragment sourced by src/Makefile.am.
 
 ink_common_sources += \
+	util/accumulators.h	\
 	util/compose.hpp	\
-	util/ucompose.hpp	\
+	util/copy.h \
 	util/enums.h \
+	util/ege-tags.h \
+	util/ege-tags.cpp \
 	util/filter-list.h \
+	util/find-if-before.h \
+	util/find-last-if.h \
 	util/fixed_point.h \
 	util/format.h	\
 	util/forward-pointer-iterator.h \
+	util/function.h \
 	util/glib-list-iterators.h \
 	util/list.h \
 	util/list-container.h \
+	util/list-copy.h \
+	util/longest-common-suffix.h \
 	util/map-list.h \
 	util/mathfns.h \
+	util/reference.h \
 	util/reverse-list.h \
 	util/share.h \
 	util/share.cpp \
 	util/tuple.h \
+	util/ucompose.hpp \
 	util/units.cpp \
-	util/units.h
+	util/units.h \
+	util/unordered-containers.h
 
 # ######################
 # ### CxxTest stuff ####
diff --git a/src/util/accumulators.h b/src/util/accumulators.h
new file mode 100644
index 000000000..c627786b1
--- /dev/null
+++ b/src/util/accumulators.h
@@ -0,0 +1,113 @@
+/** @file
+ * Frequently used accumulators for use with libsigc++
+ */
+/* Authors:
+ *   Krzysztof Kosiński <tweenk.pl@gmail.com>
+ *
+ * Copyright (C) 2009 Authors
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_UTIL_ACCUMULATORS_H
+#define SEEN_UTIL_ACCUMULATORS_H
+
+#include <iterator>
+
+namespace Inkscape {
+namespace Util {
+
+/**
+ * Accumulator which evaluates slots in reverse connection order.
+ * The slot that was connected last is evaluated first.
+ */
+struct Reverse {
+    typedef void result_type;
+    template <typename T_iterator>
+    result_type operator()(T_iterator first, T_iterator last) const {
+        while (first != last) *(--last);
+    }
+};
+
+/**
+ * Accumulator type for interruptible signals. Slots return a boolean value; emission
+ * is stopped when true is returned from a slot.
+ */
+struct Interruptible {
+    typedef bool result_type;
+    template <typename T_iterator>
+    result_type operator()(T_iterator first, T_iterator last) const {
+        for (; first != last; ++first)
+            if (*first) return true;
+        return false;
+    }
+};
+
+/**
+ * Same as Interruptible, but the slots are called in reverse order of connection,
+ * e.g. the slot that was connected last is evaluated first.
+ */
+struct ReverseInterruptible {
+    typedef bool result_type;
+    template <typename T_iterator>
+    result_type operator()(T_iterator first, T_iterator last) const {
+        while (first != last) {
+            if (*(--last)) return true;
+        }
+        return false;
+    }
+};
+
+/**
+ * The template parameter specifies how many slots from the beginning of the list
+ * should be evaluated after other slots. Useful for signals which invoke other signals
+ * once complete. Undefined results if the signal does not have at least @c num_chained
+ * slots before first emission.
+ *
+ * For example, if template param = 3, the execution order is as follows:
+ * @verbatim
+   8. 1. 2. 3. 4. 5. 6. 7.
+   S1 S2 S3 S4 S5 S6 S7 S8 @endverbatim
+ */
+template <unsigned num_chained = 1>
+struct Chained {
+    typedef void result_type;
+    template <typename T_iterator>
+    result_type operator()(T_iterator first, T_iterator last) const {
+        T_iterator save_first = first;
+        // ARGH, iterator_traits is not defined for slot iterators!
+        //std::advance(first, num_chained);
+        for (unsigned i = 0; i < num_chained && first != last; ++i) ++first;
+        for (; first != last; ++first) *first;
+        for (unsigned i = 0; i < num_chained && save_first != last; ++i, ++save_first)
+            *save_first;
+    }
+};
+
+/**
+ * Executes a logical OR on the results from slots.
+ */
+struct LogicalOr {
+    typedef bool result_type;
+    template <typename T_iterator>
+    result_type operator()(T_iterator first, T_iterator last) const {
+        bool ret = false;
+        for (; first != last; ++first) ret |= *first;
+        return ret;
+    }
+};
+
+} // namespace Util
+} // namespace Inkscape
+
+#endif
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/copy.h b/src/util/copy.h
new file mode 100644
index 000000000..27038ff2d
--- /dev/null
+++ b/src/util/copy.h
@@ -0,0 +1,48 @@
+/*
+ * Inkscape::Traits::Copy - traits class to determine types to use when copying
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2004 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_TRAITS_COPY_H
+#define SEEN_INKSCAPE_TRAITS_COPY_H
+
+namespace Inkscape {
+
+namespace Traits {
+
+template <typename T>
+struct Copy {
+    typedef T Type;
+};
+
+template <typename T>
+struct Copy<T const> {
+    typedef T Type;
+};
+
+template <typename T>
+struct Copy<T &> {
+    typedef T &Type;
+};
+
+}
+
+}
+
+#endif
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/ege-tags.cpp b/src/util/ege-tags.cpp
new file mode 100644
index 000000000..5d33c85a3
--- /dev/null
+++ b/src/util/ege-tags.cpp
@@ -0,0 +1,178 @@
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is EGE Tagging Support.
+ *
+ * The Initial Developer of the Original Code is
+ * Jon A. Cruz.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#if HAVE_CONFIG_H
+#include "config.h"
+#endif // HAVE_CONFIG_H
+
+#if HAVE_LIBINTL_H
+#include <libintl.h>
+#endif // HAVE_LIBINTL_H
+
+#if !defined(_)
+#define _(s) gettext(s)
+#endif // !defined(_)
+
+#include <set>
+#include <algorithm>
+#include <functional>
+
+#include "ege-tags.h"
+
+#include <glib.h>
+
+namespace ege
+{
+
+Label::Label(std::string const& lang, std::string const& value) :
+    lang(lang),
+    value(value)
+{
+}
+
+Label::~Label()
+{
+}
+
+// =========================================================================
+
+Tag::~Tag()
+{
+}
+
+Tag::Tag(std::string const& key) :
+    key(key)
+{
+}
+
+// =========================================================================
+
+TagSet::TagSet() :
+    lang(),
+    tags(),
+    counts()
+{
+}
+
+TagSet::~TagSet()
+{
+}
+
+void TagSet::setLang(std::string const& lang)
+{
+    if (lang != this->lang) {
+        this->lang = lang;
+    }
+}
+
+
+struct sameLang : public std::binary_function<Label, Label, bool> {
+    bool operator()(Label const& x, Label const& y) const { return (x.lang == y.lang); }
+};
+
+
+bool TagSet::addTag(Tag const& tag)
+{
+    bool present = false;
+
+    for ( std::vector<Tag>::iterator it = tags.begin(); (it != tags.end()) && !present; ++it ) {
+        if (tag.key == it->key) {
+            present = true;
+
+            for ( std::vector<Label>::const_iterator it2 = tag.labels.begin(); it2 != tag.labels.end(); ++it2 ) {
+                std::vector<Label>::iterator itOld = std::find_if( it->labels.begin(), it->labels.end(), std::bind2nd(sameLang(), *it2) );
+                if (itOld != it->labels.end()) {
+                    itOld->value = it2->value;
+                } else {
+                    it->labels.push_back(*it2);
+                }
+            }
+        }
+    }
+
+    if (!present) {
+        tags.push_back(tag);
+        counts[tag.key] = 0;
+    }
+
+    return present;
+}
+
+
+std::vector<Tag> const& TagSet::getTags()
+{
+    return tags;
+}
+
+int TagSet::getCount( std::string const& key )
+{
+    int count = 0;
+    if ( counts.find(key) != counts.end() ) {
+        count = counts[key];
+    }
+    return count;
+}
+
+void TagSet::increment( std::string const& key )
+{
+    if ( counts.find(key) != counts.end() ) {
+        counts[key]++;
+    } else {
+        Tag tag(key);
+        tags.push_back(tag);
+        counts[key] = 1;
+    }
+}
+
+void TagSet::decrement( std::string const& key )
+{
+    if ( counts.find(key) != counts.end() ) {
+        counts[key]--;
+    }
+}
+
+} // namespace ege
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/ege-tags.h b/src/util/ege-tags.h
new file mode 100644
index 000000000..eaba6a00a
--- /dev/null
+++ b/src/util/ege-tags.h
@@ -0,0 +1,121 @@
+#ifndef SEEN_EGE_TAGS_H
+#define SEEN_EGE_TAGS_H
+
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is EGE Tagging Support.
+ *
+ * The Initial Developer of the Original Code is
+ * Jon A. Cruz.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include <string>
+#include <vector>
+#include <map>
+
+/*
+ * Implements base tagging of http://create.freedesktop.org/wiki/ResourceTagging .
+ */
+
+// Note that this API is preliminary and subject to frequent change:
+
+namespace ege
+{
+
+class Label
+{
+public:
+    Label();
+    Label(std::string const& lang, std::string const& value);
+    ~Label();
+
+    std::string lang;
+    std::string value;
+};
+
+class Tag
+{
+public:
+    Tag();
+    Tag(std::string const& key);
+    ~Tag();
+
+    std::string key;
+    std::vector<Label> labels;
+};
+
+
+/**
+ * Contains a set of tags with unique keys, and with locale support.
+ *
+ */
+class TagSet
+{
+public:
+    TagSet();
+    ~TagSet();
+
+    std::string const & getLang() const;
+    void setLang(std::string const& lang);
+
+    /**
+     * Adds or updates a tag.
+     *
+     * @return true if a tag was updated, false if it was added.
+     */
+    bool addTag(Tag const& tag);
+    std::vector<Tag> const& getTags();
+
+    int getCount( std::string const& key );
+    void increment( std::string const& key );
+    void decrement( std::string const& key );
+
+private:
+
+    std::string lang;
+    std::vector<Tag> tags;
+    std::map<std::string, int> counts;
+};
+
+} // namespace ege
+
+
+#endif // SEEN_EGE_TAGS_H
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/filter-list.h b/src/util/filter-list.h
index e00c33b08..50aba12fa 100644
--- a/src/util/filter-list.h
+++ b/src/util/filter-list.h
@@ -13,7 +13,7 @@
 #define SEEN_INKSCAPE_UTIL_FILTER_LIST_H
 
 #include "util/list.h"
-#include "traits/list-copy.h"
+#include "util/list-copy.h"
 
 namespace Inkscape {
 
diff --git a/src/util/find-if-before.h b/src/util/find-if-before.h
new file mode 100644
index 000000000..6a0f63be6
--- /dev/null
+++ b/src/util/find-if-before.h
@@ -0,0 +1,51 @@
+/*
+ * Inkscape::Algorithms::find_if_before - finds the position before
+ *                                        the first value that satisifes
+ *                                        the predicate
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2005 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_ALGORITHMS_FIND_IF_BEFORE_H
+#define SEEN_INKSCAPE_ALGORITHMS_FIND_IF_BEFORE_H
+
+#include <algorithm>
+
+namespace Inkscape {
+
+namespace Algorithms {
+
+template <typename ForwardIterator, typename UnaryPredicate>
+inline ForwardIterator find_if_before(ForwardIterator start,
+                                      ForwardIterator end,
+                                      UnaryPredicate pred)
+{
+    ForwardIterator before=end;
+    while ( start != end && !pred(*start) ) {
+        before = start;
+        ++start;
+    }
+    return ( start != end ) ? before : end;
+}
+
+}
+
+}
+
+#endif
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/util/find-last-if.h b/src/util/find-last-if.h
new file mode 100644
index 000000000..1ffd63b9c
--- /dev/null
+++ b/src/util/find-last-if.h
@@ -0,0 +1,51 @@
+/*
+ * Inkscape::Algorithms::find_last_if
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2004 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_ALGORITHMS_FIND_LAST_IF_H
+#define SEEN_INKSCAPE_ALGORITHMS_FIND_LAST_IF_H
+
+#include <algorithm>
+
+namespace Inkscape {
+
+namespace Algorithms {
+
+template <typename ForwardIterator, typename UnaryPredicate>
+inline ForwardIterator find_last_if(ForwardIterator start, ForwardIterator end,
+                                    UnaryPredicate pred)
+{
+    ForwardIterator last_found(end);
+    while ( start != end ) {
+        start = std::find_if(start, end, pred);
+        if ( start != end ) {
+            last_found = start;
+            ++start;
+        }
+    }
+    return last_found;
+}
+
+}
+
+}
+
+#endif
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/util/fixed_point.h b/src/util/fixed_point.h
index 6afec5e3c..05a73dab5 100644
--- a/src/util/fixed_point.h
+++ b/src/util/fixed_point.h
@@ -12,229 +12,7 @@
 #ifndef SEEN_INKSCAPE_UTIL_FIXED_POINT_H
 #define SEEN_INKSCAPE_UTIL_FIXED_POINT_H
 
-#include "traits/reference.h"
-#include <math.h>
-#include <algorithm>
-#include <limits>
-
-namespace Inkscape {
-
-namespace Util {
-
-template <typename T, unsigned int precision>
-class FixedPoint {
-public:
-    FixedPoint() {}
-    FixedPoint(const FixedPoint& value) : v(value.v) {}
-    FixedPoint(char value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(unsigned char value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(short value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(unsigned short value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(int value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(unsigned int value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(double value) : v(static_cast<T>(floor(value*(1<<precision)))) {}
-
-    FixedPoint& operator+=(FixedPoint val) { v += val.v; return *this; }
-    FixedPoint& operator-=(FixedPoint val) { v -= val.v; return *this; }
-    FixedPoint& operator*=(FixedPoint val) {
-        const unsigned int half_size = 8*sizeof(T)/2;
-        const T al = v&((1<<half_size)-1), bl = val.v&((1<<half_size)-1);
-        const T ah = v>>half_size, bh = val.v>>half_size;
-        v = static_cast<unsigned int>(al*bl)>>precision;
-        if ( half_size >= precision ) {
-            v += ((al*bh)+(ah*bl)+((ah*bh)<<half_size))<<(half_size-precision);
-        } else {
-            v += ((al*bh)+(ah*bl))>>(precision-half_size);
-            v += (ah*bh)<<(2*half_size-precision);
-        }
-        return *this;
-    }
-
-    FixedPoint& operator*=(char val) { v *= val; return *this; }
-    FixedPoint& operator*=(unsigned char val) { v *= val; return *this; }
-    FixedPoint& operator*=(short val) { v *= val; return *this; }
-    FixedPoint& operator*=(unsigned short val) { v *= val; return *this; }
-    FixedPoint& operator*=(int val) { v *= val; return *this; }
-    FixedPoint& operator*=(unsigned int val) { v *= val; return *this; }
-
-    FixedPoint operator+(FixedPoint val) const { FixedPoint r(*this); return r+=val; }
-    FixedPoint operator-(FixedPoint val) const { FixedPoint r(*this); return r-=val; }
-    FixedPoint operator*(FixedPoint val) const { FixedPoint r(*this); return r*=val; }
-
-    FixedPoint operator*(char val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(unsigned char val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(short val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(unsigned short val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(int val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(unsigned int val) const { FixedPoint r(*this); return r*=val; }
-
-    float operator*(float val) const { return static_cast<float>(*this)*val; }
-    double operator*(double val) const { return static_cast<double>(*this)*val; }
-
-    operator char() const { return v>>precision; }
-    operator unsigned char() const { return v>>precision; }
-    operator short() const { return v>>precision; }
-    operator unsigned short() const { return v>>precision; }
-    operator int() const { return v>>precision; }
-    operator unsigned int() const { return v>>precision; }
-
-    operator float() const { return ldexpf(v,-precision); }
-    operator double() const { return ldexp(v,-precision); }
-private:
-    T v;
-};
-
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(char a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(unsigned char a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(short a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(unsigned short a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(int a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(unsigned int a, FixedPoint<T,precision> b) { return b*=a; }
-
-template<typename T, unsigned int precision> float operator *(float a, FixedPoint<T,precision> b) { return b*a; }
-template<typename T, unsigned int precision> double operator *(double a, FixedPoint<T,precision> b) { return b*a; }
-
-}
-
-}
-
-#endif
-/*
-  Local Variables:
-  mode:c++
-  c-file-style:"stroustrup"
-  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
-  indent-tabs-mode:nil
-  fill-column:99
-  End:
-*/
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
-/*
- * Inkscape::Util::FixedPoint - fixed point type
- *
- * Authors:
- *   Jasper van de Gronde <th.v.d.gronde@hccnet.net>
- *
- * Copyright (C) 2006 Jasper van de Gronde
- *
- * Released under GNU GPL, read the file 'COPYING' for more information
- */
-
-#ifndef SEEN_INKSCAPE_UTIL_FIXED_POINT_H
-#define SEEN_INKSCAPE_UTIL_FIXED_POINT_H
-
-#include "traits/reference.h"
-#include <math.h>
-#include <algorithm>
-#include <limits>
-
-namespace Inkscape {
-
-namespace Util {
-
-template <typename T, unsigned int precision>
-class FixedPoint {
-public:
-    FixedPoint() {}
-    FixedPoint(const FixedPoint& value) : v(value.v) {}
-    FixedPoint(char value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(unsigned char value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(short value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(unsigned short value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(int value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(unsigned int value) : v(static_cast<T>(value)<<precision) {}
-    FixedPoint(double value) : v(static_cast<T>(floor(value*(1<<precision)))) {}
-
-    FixedPoint& operator+=(FixedPoint val) { v += val.v; return *this; }
-    FixedPoint& operator-=(FixedPoint val) { v -= val.v; return *this; }
-    FixedPoint& operator*=(FixedPoint val) {
-        const unsigned int half_size = 8*sizeof(T)/2;
-        const T al = v&((1<<half_size)-1), bl = val.v&((1<<half_size)-1);
-        const T ah = v>>half_size, bh = val.v>>half_size;
-        v = static_cast<unsigned int>(al*bl)>>precision;
-        if ( half_size >= precision ) {
-            v += ((al*bh)+(ah*bl)+((ah*bh)<<half_size))<<(half_size-precision);
-        } else {
-            v += ((al*bh)+(ah*bl))>>(precision-half_size);
-            v += (ah*bh)<<(2*half_size-precision);
-        }
-        return *this;
-    }
-
-    FixedPoint& operator*=(char val) { v *= val; return *this; }
-    FixedPoint& operator*=(unsigned char val) { v *= val; return *this; }
-    FixedPoint& operator*=(short val) { v *= val; return *this; }
-    FixedPoint& operator*=(unsigned short val) { v *= val; return *this; }
-    FixedPoint& operator*=(int val) { v *= val; return *this; }
-    FixedPoint& operator*=(unsigned int val) { v *= val; return *this; }
-
-    FixedPoint operator+(FixedPoint val) const { FixedPoint r(*this); return r+=val; }
-    FixedPoint operator-(FixedPoint val) const { FixedPoint r(*this); return r-=val; }
-    FixedPoint operator*(FixedPoint val) const { FixedPoint r(*this); return r*=val; }
-
-    FixedPoint operator*(char val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(unsigned char val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(short val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(unsigned short val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(int val) const { FixedPoint r(*this); return r*=val; }
-    FixedPoint operator*(unsigned int val) const { FixedPoint r(*this); return r*=val; }
-
-    float operator*(float val) const { return static_cast<float>(*this)*val; }
-    double operator*(double val) const { return static_cast<double>(*this)*val; }
-
-    operator char() const { return v>>precision; }
-    operator unsigned char() const { return v>>precision; }
-    operator short() const { return v>>precision; }
-    operator unsigned short() const { return v>>precision; }
-    operator int() const { return v>>precision; }
-    operator unsigned int() const { return v>>precision; }
-
-    operator float() const { return ldexpf(v,-precision); }
-    operator double() const { return ldexp(v,-precision); }
-private:
-    T v;
-};
-
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(char a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(unsigned char a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(short a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(unsigned short a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(int a, FixedPoint<T,precision> b) { return b*=a; }
-template<typename T, unsigned int precision> FixedPoint<T,precision> operator *(unsigned int a, FixedPoint<T,precision> b) { return b*=a; }
-
-template<typename T, unsigned int precision> float operator *(float a, FixedPoint<T,precision> b) { return b*a; }
-template<typename T, unsigned int precision> double operator *(double a, FixedPoint<T,precision> b) { return b*a; }
-
-}
-
-}
-
-#endif
-/*
-  Local Variables:
-  mode:c++
-  c-file-style:"stroustrup"
-  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
-  indent-tabs-mode:nil
-  fill-column:99
-  End:
-*/
-// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
-/*
- * Inkscape::Util::FixedPoint - fixed point type
- *
- * Authors:
- *   Jasper van de Gronde <th.v.d.gronde@hccnet.net>
- *
- * Copyright (C) 2006 Jasper van de Gronde
- *
- * Released under GNU GPL, read the file 'COPYING' for more information
- */
-
-#ifndef SEEN_INKSCAPE_UTIL_FIXED_POINT_H
-#define SEEN_INKSCAPE_UTIL_FIXED_POINT_H
-
-#include "traits/reference.h"
+#include "util/reference.h"
 #include <math.h>
 #include <algorithm>
 #include <limits>
diff --git a/src/util/forward-pointer-iterator.h b/src/util/forward-pointer-iterator.h
index 2c2345c81..1603fed27 100644
--- a/src/util/forward-pointer-iterator.h
+++ b/src/util/forward-pointer-iterator.h
@@ -15,7 +15,7 @@
 #define SEEN_INKSCAPE_UTIL_FORWARD_POINTER_ITERATOR_H
 
 #include <iterator>
-#include "traits/reference.h"
+#include "util/reference.h"
 
 namespace Inkscape {
 
diff --git a/src/util/function.h b/src/util/function.h
new file mode 100644
index 000000000..d0dd5d87c
--- /dev/null
+++ b/src/util/function.h
@@ -0,0 +1,122 @@
+/*
+ * Inkscape::Traits::Function - traits class for C++ "functors"
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2004 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_TRAITS_FUNCTION_H
+#define SEEN_INKSCAPE_TRAITS_FUNCTION_H
+
+namespace Inkscape {
+
+namespace Traits {
+
+template <typename F> struct Function;
+
+template <typename R>
+struct Function<R (*)()> {
+    typedef R Result;
+
+    typedef void Arg0;
+    typedef void Arg1;
+    typedef void Arg2;
+    typedef void Arg3;
+    typedef void Arg4;
+    typedef void Arg5;
+};
+
+template <typename R, typename A0>
+struct Function<R (*)(A0)> {
+    typedef R Result;
+
+    typedef A0 Arg0;
+    typedef void Arg1;
+    typedef void Arg2;
+    typedef void Arg3;
+    typedef void Arg4;
+    typedef void Arg5;
+};
+
+template <typename R, typename A0, typename A1>
+struct Function<R (*)(A0, A1)> {
+    typedef R Result;
+
+    typedef A0 Arg0;
+    typedef A1 Arg1;
+    typedef void Arg2;
+    typedef void Arg3;
+    typedef void Arg4;
+    typedef void Arg5;
+};
+
+template <typename R, typename A0, typename A1, typename A2>
+struct Function<R (*)(A0, A1, A2)> {
+    typedef R Result;
+
+    typedef A0 Arg0;
+    typedef A1 Arg1;
+    typedef A2 Arg2;
+    typedef void Arg3;
+    typedef void Arg4;
+    typedef void Arg5;
+};
+
+template <typename R, typename A0, typename A1, typename A2,
+                      typename A3>
+struct Function<R (*)(A0, A1, A2, A3)> {
+    typedef R Result;
+
+    typedef A0 Arg0;
+    typedef A1 Arg1;
+    typedef A2 Arg2;
+    typedef A3 Arg3;
+    typedef void Arg4;
+    typedef void Arg5;
+};
+
+template <typename R, typename A0, typename A1, typename A2,
+                      typename A3, typename A4>
+struct Function<R (*)(A0, A1, A2, A3, A4)> {
+    typedef R Result;
+
+    typedef A0 Arg0;
+    typedef A1 Arg1;
+    typedef A2 Arg2;
+    typedef A3 Arg3;
+    typedef A4 Arg4;
+    typedef void Arg5;
+};
+
+template <typename R, typename A0, typename A1, typename A2,
+                      typename A3, typename A4, typename A5>
+struct Function<R (*)(A0, A1, A2, A3, A4, A5)> {
+    typedef R Result;
+
+    typedef A0 Arg0;
+    typedef A1 Arg1;
+    typedef A2 Arg2;
+    typedef A3 Arg3;
+    typedef A4 Arg4;
+    typedef A5 Arg5;
+};
+
+}
+
+}
+
+#endif
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/list-copy.h b/src/util/list-copy.h
new file mode 100644
index 000000000..811f93b77
--- /dev/null
+++ b/src/util/list-copy.h
@@ -0,0 +1,45 @@
+/*
+ * Inkscape::Traits::ListCopy - helper traits class for copying lists
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2004 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_TRAITS_LIST_COPY_H
+#define SEEN_INKSCAPE_TRAITS_LIST_COPY_H
+
+#include <iterator>
+#include "util/copy.h"
+#include "util/list.h"
+
+namespace Inkscape {
+
+namespace Traits {
+
+template <typename InputIterator>
+struct ListCopy {
+    typedef typename Copy<
+        typename std::iterator_traits<InputIterator>::value_type
+    >::Type ResultValue;
+    typedef typename Util::MutableList<ResultValue> ResultList;
+};
+
+}
+
+}
+
+#endif
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/list.h b/src/util/list.h
index 86a73711a..ebe3a9773 100644
--- a/src/util/list.h
+++ b/src/util/list.h
@@ -15,7 +15,7 @@
 #include <cstddef>
 #include <iterator>
 #include "gc-managed.h"
-#include "traits/reference.h"
+#include "util/reference.h"
 
 namespace Inkscape {
 
diff --git a/src/util/longest-common-suffix.h b/src/util/longest-common-suffix.h
new file mode 100644
index 000000000..04d2b179d
--- /dev/null
+++ b/src/util/longest-common-suffix.h
@@ -0,0 +1,114 @@
+/*
+ * Inkscape::Algorithms::longest_common_suffix 
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2004 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
+#define SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H
+
+#include <iterator>
+#include <functional>
+#include "util/list.h"
+
+namespace Inkscape {
+
+namespace Algorithms {
+
+/**
+ * Time costs:
+ *
+ * The case of sharing a common successor is handled in O(1) time.
+ *
+ * If \a a is the longest common suffix, then runs in O(len(rest of b)) time.
+ *
+ * Otherwise, runs in O(len(a) + len(b)) time.
+ */
+
+template <typename ForwardIterator>
+ForwardIterator longest_common_suffix(ForwardIterator a, ForwardIterator b,
+                                      ForwardIterator end)
+{
+    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
+    return longest_common_suffix(a, b, end, std::equal_to<value_type>());
+}
+
+template <typename ForwardIterator, typename BinaryPredicate>
+ForwardIterator longest_common_suffix(ForwardIterator a, ForwardIterator b,
+                                      ForwardIterator end, BinaryPredicate pred)
+{
+    if ( a == end || b == end ) {
+        return end;
+    }
+
+    /* Handle in O(1) time the common cases of identical lists or tails. */
+    {
+        /* identical lists? */
+        if ( a == b ) {
+            return a;
+        }
+
+        /* identical tails? */
+        ForwardIterator tail_a(a);
+        ForwardIterator tail_b(b);
+        if ( ++tail_a == ++tail_b ) {
+            return tail_a;
+        }
+    }
+
+    /* Build parallel lists of suffixes, ordered by increasing length. */
+
+    using Inkscape::Util::List;
+    using Inkscape::Util::cons;
+    ForwardIterator lists[2] = { a, b };
+    List<ForwardIterator> suffixes[2];
+
+    for ( int i=0 ; i < 2 ; i++ ) {
+        for ( ForwardIterator iter(lists[i]) ; iter != end ; ++iter ) {
+            if ( iter == lists[1-i] ) {
+                // the other list is a suffix of this one
+                return lists[1-i];
+            }
+
+            suffixes[i] = cons(iter, suffixes[i]);
+        }
+    }
+
+    /* Iterate in parallel through the lists of suffix lists from shortest to
+     * longest, stopping before the first pair of suffixes that differs
+     */
+
+    ForwardIterator longest_common(end);
+
+    while ( suffixes[0] && suffixes[1] &&
+            pred(**suffixes[0], **suffixes[1]) )
+    {
+        longest_common = *suffixes[0];
+        ++suffixes[0];
+        ++suffixes[1];
+    }
+
+    return longest_common;
+}
+
+}
+
+}
+
+#endif /* !SEEN_INKSCAPE_ALGORITHMS_LONGEST_COMMON_SUFFIX_H */
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
diff --git a/src/util/reference.h b/src/util/reference.h
new file mode 100644
index 000000000..199ae8929
--- /dev/null
+++ b/src/util/reference.h
@@ -0,0 +1,49 @@
+/*
+ * Inkscape::Traits::Reference - traits class for dealing with reference types
+ *
+ * Authors:
+ *   MenTaLguY <mental@rydia.net>
+ *
+ * Copyright (C) 2004 MenTaLguY
+ *
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INKSCAPE_TRAITS_REFERENCE_H
+#define SEEN_INKSCAPE_TRAITS_REFERENCE_H
+
+namespace Inkscape {
+
+namespace Traits {
+
+template <typename T>
+struct Reference {
+    typedef T const &RValue;
+    typedef T &LValue;
+    typedef T *Pointer;
+    typedef T const *ConstPointer;
+};
+
+template <typename T>
+struct Reference<T &> {
+    typedef T &RValue;
+    typedef T &LValue;
+    typedef T *Pointer;
+    typedef T const *ConstPointer;
+};
+
+}
+
+}
+
+#endif
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :
diff --git a/src/util/reverse-list.h b/src/util/reverse-list.h
index 586f706c7..798b15701 100644
--- a/src/util/reverse-list.h
+++ b/src/util/reverse-list.h
@@ -13,7 +13,7 @@
 #define SEEN_INKSCAPE_UTIL_REVERSE_LIST_H
 
 #include "util/list.h"
-#include "traits/list-copy.h"
+#include "util/list-copy.h"
 
 namespace Inkscape {
 
diff --git a/src/util/tuple.h b/src/util/tuple.h
index bf9338366..42266c8d2 100644
--- a/src/util/tuple.h
+++ b/src/util/tuple.h
@@ -12,7 +12,7 @@
 #ifndef SEEN_INKSCAPE_UTIL_TUPLE_H
 #define SEEN_INKSCAPE_UTIL_TUPLE_H
 
-#include "traits/reference.h"
+#include "util/reference.h"
 
 namespace Inkscape {
 
diff --git a/src/util/unordered-containers.h b/src/util/unordered-containers.h
new file mode 100644
index 000000000..aaf771959
--- /dev/null
+++ b/src/util/unordered-containers.h
@@ -0,0 +1,78 @@
+/** @file
+ * @brief Compatibility wrapper for unordered containers.
+ */
+/* Authors:
+ *   Jon A. Cruz <jon@joncruz.org>
+ *   Krzysztof Kosiński <tweenk.pl@gmail.com>
+ *
+ * Copyright (C) 2010 Authors
+ * Released under GNU GPL, read the file 'COPYING' for more information
+ */
+
+#ifndef SEEN_INK_UTIL_UNORDERED_CONTAINERS_H
+#define SEEN_INK_UTIL_UNORDERED_CONTAINERS_H
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#ifndef DOXYGEN_SHOULD_SKIP_THIS
+#if defined(HAVE_TR1_UNORDERED_SET)
+
+# include <tr1/unordered_set>
+# include <tr1/unordered_map>
+# define INK_UNORDERED_SET std::tr1::unordered_set
+# define INK_UNORDERED_MAP std::tr1::unordered_map
+# define INK_HASH std::tr1::hash
+
+#elif defined(HAVE_BOOST_UNORDERED_SET)
+# include <boost/unordered_set.hpp>
+# include <boost/unordered_map.hpp>
+# define INK_UNORDERED_SET boost::unordered_set
+# define INK_UNORDERED_MAP boost::unordered_map
+# define INK_HASH boost::hash
+
+#elif defined(HAVE_EXT_HASH_SET)
+
+# include <functional>
+# include <ext/hash_set>
+# include <ext/hash_map>
+# define INK_UNORDERED_SET __gnu_cxx::hash_set
+# define INK_UNORDERED_MAP __gnu_cxx::hash_map
+# define INK_HASH __gnu_cxx::hash
+
+namespace __gnu_cxx {
+// hash function for pointers
+// TR1 and Boost have this defined by default, __gnu_cxx doesn't
+template<typename T>
+struct hash<T *> : public std::unary_function<T *, std::size_t> {
+    std::size_t operator()(T *p) const {
+        // Taken from Boost
+        std::size_t x = static_cast<std::size_t>(reinterpret_cast<std::ptrdiff_t>(p));
+        return x + (x >> 3);
+    }
+};
+} // namespace __gnu_cxx
+#endif
+
+#else
+/// Name (with namespace) of the unordered set template.
+#define INK_UNORDERED_SET
+/// Name (with namespace) of the unordered map template.
+#define INK_UNORDERED_MAP
+/// Name (with namespace) of the hash template.
+#define INK_HASH
+
+#endif
+
+#endif // SEEN_SET_TYPES_H
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :