Move around files to remove some vanity directories.

Also remove the obsolete IDL file stub.

(bzr r9194)

14 files changed, 494 insertions, 229 deletions

diff --git a/src/util/Makefile_insert b/src/util/Makefile_insert
index 1908aea19..259fd762e 100644
--- a/src/util/Makefile_insert
+++ b/src/util/Makefile_insert
@@ -2,23 +2,30 @@
 
 ink_common_sources += \
 	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/unordered-containers.h
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/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 {