Bumping new version of libdepixelize

(bzr r12506.1.3)

9 files changed, 121 insertions, 195 deletions

diff --git a/src/libdepixelize/kopftracer2011.cpp b/src/libdepixelize/kopftracer2011.cpp
index 96a415f2c..26ad8863b 100644
--- a/src/libdepixelize/kopftracer2011.cpp
+++ b/src/libdepixelize/kopftracer2011.cpp
@@ -38,22 +38,40 @@
 #include "priv/homogeneoussplines.h"
 #include "priv/branchless.h"
 #include "priv/splines.h"
+#include "priv/iterator.h"
 
 namespace Tracer {
 namespace Heuristics {
 
-int curves(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b);
-bool islands(PixelGraph &graph, PixelGraph::Node *a, PixelGraph::Node *b);
+int curves(const PixelGraph &graph, PixelGraph::const_iterator a,
+           PixelGraph::const_iterator b);
+bool islands(PixelGraph::const_iterator a, PixelGraph::const_iterator b);
 
 struct SparsePixels
 {
-    typedef std::pair<PixelGraph::Node*, PixelGraph::Node*> Edge;
+    enum Diagonal {
+        /**
+         * From (first) the top left corner to (second) the bottom right.
+         */
+        MAIN_DIAGONAL      = 0,
+        /**
+         * From (first) the top right to (second) the bottom left.
+         */
+        SECONDARY_DIAGONAL = 1
+    };
+
+    typedef std::pair<PixelGraph::const_iterator, PixelGraph::const_iterator>
+    Edge;
     typedef std::pair<Edge, int> EdgeWeight;
 
-    void operator()(PixelGraph &graph, unsigned radius);
+    void operator()(const PixelGraph &graph, unsigned radius);
 
-    static bool similar_colors(PixelGraph::Node *n, Edge edge);
+    static bool similar_colors(PixelGraph::const_iterator n,
+                               const guint8 (&a)[4], const guint8 (&b)[4]);
 
+    /*
+     * Precondition: Must be filled according to Diagonal enum.
+     */
     EdgeWeight diagonals[2];
 };
 
@@ -231,12 +249,13 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph,
             using std::pair;
             using std::make_pair;
 
-            typedef pair<PixelGraph::Node*, PixelGraph::Node*> Edge;
+            typedef pair<PixelGraph::iterator, PixelGraph::iterator> Edge;
             typedef pair<Edge, int> EdgeWeight;
 
             EdgeWeight diagonals[2] = {
-                make_pair(make_pair(&*it, &*(it + graph.width() + 1)), 0),
-                make_pair(make_pair(&*(it + 1), &*(it + graph.width())), 0)
+                make_pair(make_pair(it, graph.nodeBottomRight(it)), 0),
+                make_pair(make_pair(graph.nodeRight(it), graph.nodeBottom(it)),
+                          0)
             };
 
             // Check if there are crossing edges
@@ -248,13 +267,13 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph,
             // Compute weights
             for ( int i = 0 ; i != 2 ; ++i ) {
                 // Curves and islands heuristics
-                PixelGraph::Node *a = diagonals[i].first.first;
-                PixelGraph::Node *b = diagonals[i].first.second;
+                PixelGraph::const_iterator a = diagonals[i].first.first;
+                PixelGraph::const_iterator b = diagonals[i].first.second;
 
                 diagonals[i].second += Heuristics::curves(graph, a, b)
                     * options.curvesMultiplier;
 
-                diagonals[i].second += Heuristics::islands(graph, a, b)
+                diagonals[i].second += Heuristics::islands(a, b)
                     * options.islandsWeight;
             }
 
@@ -290,20 +309,23 @@ void Kopf2011::_remove_crossing_edges_unsafe(PixelGraph &graph,
     }
 }
 
-inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a,
-                              PixelGraph::Node *b)
+inline int Heuristics::curves(const PixelGraph &graph,
+                              PixelGraph::const_iterator a,
+                              PixelGraph::const_iterator b)
 {
     int count = 1;
+    ToPtr<PixelGraph::Node> to_ptr;
+    ToIter<PixelGraph::Node> to_iter(graph.begin());
 
     // b -> a
     // and then a -> b
     for ( int i = 0 ; i != 2 ; ++i ) {
-        PixelGraph::Node *it = i ? a : b;
-        PixelGraph::Node *prev = i ? b : a;
+        PixelGraph::const_iterator it = i ? a : b;
+        PixelGraph::const_iterator prev = i ? b : a;
         int local_count = 0;
 
         // Used to avoid inifinite loops in circular-like edges
-        PixelGraph::Node *const initial = it;
+        const PixelGraph::const_iterator initial = it;
 
         while ( it->adjsize() == 2 ) {
             ++local_count;
@@ -312,18 +334,26 @@ inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a,
             {
                 // There are only two values that won't be zero'ed
                 // and one of them has the same value of prev
-                guintptr aux = guintptr(it);
-                aux = it->adj.top * guintptr(it - graph.width())
-                    + it->adj.topright * guintptr(it - graph.width() + 1)
-                    + it->adj.right * guintptr(it + 1)
-                    + it->adj.bottomright * guintptr(it + graph.width() + 1)
-                    + it->adj.bottom * guintptr(it + graph.width())
-                    + it->adj.bottomleft * guintptr(it + graph.width() - 1)
-                    + it->adj.left * guintptr(it - 1)
-                    + it->adj.topleft * guintptr(it - graph.width() - 1)
-                    - guintptr(prev);
+                guintptr aux = guintptr(to_ptr(it));
+                aux = (it->adj.top
+                       * guintptr(to_ptr(graph.nodeTop(it))))
+                    + (it->adj.topright
+                       * guintptr(to_ptr(graph.nodeTopRight(it))))
+                    + (it->adj.right
+                       * guintptr(to_ptr(graph.nodeRight(it))))
+                    + (it->adj.bottomright
+                       * guintptr(to_ptr(graph.nodeBottomRight(it))))
+                    + (it->adj.bottom
+                       * guintptr(to_ptr(graph.nodeBottom(it))))
+                    + (it->adj.bottomleft
+                       * guintptr(to_ptr(graph.nodeBottomLeft(it))))
+                    + (it->adj.left
+                       * guintptr(to_ptr(graph.nodeLeft(it))))
+                    + (it->adj.topleft
+                       * guintptr(to_ptr(graph.nodeTopLeft(it))))
+                    - guintptr(to_ptr(prev));
                 prev = it;
-                it = reinterpret_cast<PixelGraph::Node*>(aux);
+                it = to_iter(reinterpret_cast<PixelGraph::Node const*>(aux));
             }
 
             // Break infinite loops
@@ -336,7 +366,7 @@ inline int Heuristics::curves(PixelGraph &graph, PixelGraph::Node *a,
     return count;
 }
 
-inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph,
+inline void Heuristics::SparsePixels::operator ()(const PixelGraph &graph,
                                                   unsigned radius)
 {
     if ( !graph.width() || !graph.height() )
@@ -346,72 +376,79 @@ inline void Heuristics::SparsePixels::operator ()(PixelGraph &graph,
     for ( int i = 0 ; i != 2 ; ++i )
         diagonals[i].second = 0;
 
-    // Compute begin and end nodes under a (2*radius)^2 window
-    std::pair<unsigned, unsigned> begin(0, 0);
+    if ( !radius )
+        return;
 
-    // Get midpoint
+    // Fix radius/bounds
     {
-        using branchless::max_consecutive;
-
-        unsigned x1 = graph.toX(diagonals[0].first.first);
-        unsigned x2 = graph.toX(diagonals[0].first.second);
-        begin.first = max_consecutive(x1, x2);
-
-        unsigned y1 = graph.toY(diagonals[0].first.first);
-        unsigned y2 = graph.toY(diagonals[0].first.second);
-        begin.second = max_consecutive(y1, y2);
-    }
-
-    std::pair<unsigned, unsigned> end(begin.first + radius,
-                                      begin.second + radius);
+        unsigned x = graph.toX(diagonals[MAIN_DIAGONAL].first.first);
+        unsigned y = graph.toY(diagonals[MAIN_DIAGONAL].first.first);
+        unsigned minor = std::min(x, y);
+        unsigned displace = radius - 1;
+
+        if ( displace > minor ) {
+            displace = minor;
+            radius = displace + 1;
+        }
 
-    // Get beginning point
-    {
-        using branchless::first_if;
+        displace = radius;
 
-        begin.first = first_if(begin.first - radius, 0u, begin.first >= radius);
+        if ( x + displace >= graph.width() ) {
+            displace = unsigned(graph.width()) - x - 1;
+            radius = displace;
+        }
 
-        begin.second = first_if(begin.second - radius, 0u,
-                                begin.second >= radius);
+        if ( y + displace >= graph.height() ) {
+            displace = unsigned(graph.height()) - y - 1;
+            radius = displace;
+        }
     }
 
-    // Fix ending point if misplaced
-    {
-        using branchless::first_if;
+    if ( !radius )
+        return;
 
-        end.first = first_if(unsigned(graph.width()), end.first,
-                             end.first > graph.width());
+    // Iterate over nodes and count them
+    {
+        PixelGraph::const_iterator it = diagonals[MAIN_DIAGONAL].first.first;
+        for ( unsigned i = radius - 1 ; i ; --i )
+            it = graph.nodeTopLeft(it);
+
+        bool invert = false;
+        for ( unsigned i = 0 ; i != 2 * radius ; ++i ) {
+            for ( unsigned j = 0 ; j != 2 * radius ; ++j ) {
+                for ( int k = 0 ; k != 2 ; ++k ) {
+                    diagonals[k].second
+                        += similar_colors(it, diagonals[k].first.first->rgba,
+                                          diagonals[k].first.second->rgba);
+                }
+                it = (invert ? graph.nodeLeft(it) : graph.nodeRight(it));
+            }
+            it = (invert ? graph.nodeRight(it) : graph.nodeLeft(it));
 
-        end.second = first_if(unsigned(graph.height()), end.second,
-                              end.second > graph.height());
-    }
 
-    // Iterate over nodes and count them
-    for ( int i = begin.second ; i != end.second ; ++i ) {
-        PixelGraph::Node *it = &graph[begin.first][i];
-        for ( int j = begin.first ; j != end.first ; ++j, ++it ) {
-            for ( int k = 0 ; k != 2 ; ++k )
-                diagonals[k].second += similar_colors(it, diagonals[k].first);
+            invert = !invert;
+            it = graph.nodeBottom(it);
         }
     }
 
-    int minor = branchless::min(diagonals[0].second, diagonals[1].second);
+    int minor = std::min(diagonals[0].second, diagonals[1].second);
     for ( int i = 0 ; i != 2 ; ++i )
         diagonals[i].second -= minor;
+
     std::swap(diagonals[0].second, diagonals[1].second);
 }
 
 inline bool
-Heuristics::SparsePixels::similar_colors(PixelGraph::Node *n,
-                                         Heuristics::SparsePixels::Edge edge)
+Heuristics::SparsePixels::similar_colors(PixelGraph::const_iterator n,
+                                         const guint8 (&a)[4],
+                                         const guint8 (&b)[4])
 {
     using colorspace::similar_colors;
-    return (similar_colors(n->rgba, edge.first->rgba)
-            || similar_colors(n->rgba, edge.second->rgba));
+    return similar_colors(n->rgba, a) || similar_colors(n->rgba, b);
 }
 
-inline bool Heuristics::islands(PixelGraph &graph, PixelGraph::Node *a,
-                               PixelGraph::Node *b)
+inline bool Heuristics::islands(PixelGraph::const_iterator a,
+                                PixelGraph::const_iterator b)
 {
     if ( a->adjsize() == 1 || b->adjsize() == 1 )
         return true;
diff --git a/src/libdepixelize/priv/branchless.h b/src/libdepixelize/priv/branchless.h
index f8f041cce..487a9688d 100644
--- a/src/libdepixelize/priv/branchless.h
+++ b/src/libdepixelize/priv/branchless.h
@@ -32,31 +32,13 @@ namespace Tracer {
  */
 namespace branchless {
 
-template<class T>
-T first_if(T first, T second, bool cond)
-{
-    return first * cond + second * (1 - cond);
-}
-
-template<class T>
-T min(T first, T second)
-{
-    return first - (first > second) * (first - second);
-}
-
-template<class T>
-T max(T first, T second)
-{
-    return first + (first < second) * (second - first);
-}
-
-/**
- * When abs(first - second) == 1
+/*
+ * All modern processors optimize the branch to a conditional move
  */
 template<class T>
-T max_consecutive(T first, T second)
+T first_if(T first, T second, bool cond)
 {
-    return first + (first < second);
+    return cond ? first : second;
 }
 
 } // namespace branchless
diff --git a/src/libdepixelize/priv/colorspace.h b/src/libdepixelize/priv/colorspace.h
index 21025b852..4982630ad 100644
--- a/src/libdepixelize/priv/colorspace.h
+++ b/src/libdepixelize/priv/colorspace.h
@@ -25,7 +25,7 @@
 #ifndef LIBDEPIXELIZE_TRACER_YUV_H
 #define LIBDEPIXELIZE_TRACER_YUV_H
 
-#include <glib/gtypes.h>
+#include <glib.h>
 
 namespace Tracer {
 namespace colorspace {
diff --git a/src/libdepixelize/priv/homogeneoussplines.h b/src/libdepixelize/priv/homogeneoussplines.h
index d6860cdf4..57c77a163 100644
--- a/src/libdepixelize/priv/homogeneoussplines.h
+++ b/src/libdepixelize/priv/homogeneoussplines.h
@@ -82,8 +82,6 @@ public:
         return _polygons.end();
     }
 
-    // Capacity
-
     size_type size() const
     {
         return _polygons.size();
diff --git a/src/libdepixelize/priv/pixelgraph.h b/src/libdepixelize/priv/pixelgraph.h
index 0ae4f36b4..32523d8ee 100644
--- a/src/libdepixelize/priv/pixelgraph.h
+++ b/src/libdepixelize/priv/pixelgraph.h
@@ -40,7 +40,7 @@ public:
         /*
          * Hamming weight of \p adj
          */
-        unsigned adjsize()
+        unsigned adjsize() const
         {
             unsigned all[8] = {
                 adj.top,
@@ -145,7 +145,6 @@ public:
         return _nodes.rend();
     }
 
-    // Capacity
     size_t size() const
     {
         return _nodes.size();
@@ -164,14 +163,14 @@ public:
     // Algorithms
     void connectAllNeighbors();
 
-    int toX(Node *n) const
+    int toX(const_iterator n) const
     {
-        return (n - &_nodes[0]) % _width;
+        return (&*n - &_nodes[0]) % _width;
     }
 
-    int toY(Node *n) const
+    int toY(const_iterator n) const
     {
-        return (n - &_nodes[0]) / _width;
+        return (&*n - &_nodes[0]) / _width;
     }
 
     iterator nodeTop(iterator n)
diff --git a/src/libdepixelize/priv/point.h b/src/libdepixelize/priv/point.h
index 037c03de6..6bea752ed 100644
--- a/src/libdepixelize/priv/point.h
+++ b/src/libdepixelize/priv/point.h
@@ -25,8 +25,6 @@
 #ifndef LIBDEPIXELIZE_TRACER_POINT_H
 #define LIBDEPIXELIZE_TRACER_POINT_H
 
-#include <glib/gtypes.h>
-
 namespace Tracer {
 
 template<class T>
diff --git a/src/libdepixelize/priv/simplifiedvoronoi.h b/src/libdepixelize/priv/simplifiedvoronoi.h
index 7c4a6d9fb..a33695ff7 100644
--- a/src/libdepixelize/priv/simplifiedvoronoi.h
+++ b/src/libdepixelize/priv/simplifiedvoronoi.h
@@ -105,7 +105,6 @@ public:
         return _cells.rend();
     }
 
-    // Capacity
     size_t size() const
     {
         return _cells.size();
@@ -1011,7 +1010,7 @@ SimplifiedVoronoi<T>
                 // or it might be 1-color and doesn't matter,
                 // because the current node will disappear
                 vertex.smooth
-                    = !( vertex.smooth = bottom(a_it) ^ bottom(b_it) );
+                    = !( bottom(a_it) ^ bottom(b_it) );
 
                 if ( vertex.smooth ) {
                     vertex.smooth
diff --git a/src/libdepixelize/priv/utils.h b/src/libdepixelize/priv/utils.h
deleted file mode 100644
index 8a8e03352..000000000
--- a/src/libdepixelize/priv/utils.h
+++ /dev/null
@@ -1,87 +0,0 @@
-/*  This file is part of the libdepixelize project
-    Copyright (C) 2013 Vinícius dos Santos Oliveira <vini.ipsmaker@gmail.com>
-
-    GNU Lesser General Public License Usage
-    This library is free software; you can redistribute it and/or modify it
-    under the terms of the GNU Lesser General Public License as published by the
-    Free Software Foundation; either version 2.1 of the License, or (at your
-    option) any later version.
-    You should have received a copy of the GNU Lesser General Public License
-    along with this library.  If not, see <http://www.gnu.org/licenses/>.
-
-    GNU General Public License Usage
-    Alternatively, this library may be used under the terms of the GNU General
-    Public License as published by the Free Software Foundation, either version
-    2 of the License, or (at your option) any later version.
-    You should have received a copy of the GNU General Public License along with
-    this library.  If not, see <http://www.gnu.org/licenses/>.
-
-    This library is distributed in the hope that it will be useful,
-    but WITHOUT ANY WARRANTY; without even the implied warranty of
-    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-    Lesser General Public License for more details.
-*/
-
-#ifndef LIBDEPIXELIZE_TRACER_UTILS_H
-#define LIBDEPIXELIZE_TRACER_UTILS_H
-
-#include "pixelgraph.h"
-#include "simplifiedvoronoi.h"
-#include <iostream>
-#include <ios>
-#include <iomanip>
-
-namespace Tracer {
-namespace Utils {
-
-template<class T>
-Splines to_splines(const SimplifiedVoronoi<T> &diagram)
-{
-    svg << "<svg xmlns=\"http://www.w3.org/2000/svg\""
-        " width=\"" << diagram.width()
-        << "px\" height=\"" << diagram.height()
-        << "px\">";
-
-    for ( typename SimplifiedVoronoi<T>::const_iterator it = diagram.begin()
-              , end = diagram.end() ; it != end ; ++it ) {
-        typename std::vector< Point<T> >::const_iterator
-            it2 = it->vertices.begin(), end2 = it->vertices.end();
-        if ( it2 == end2 )
-            continue;
-
-        svg << "<path d=\"M";
-
-        for ( ; it2 != end2 ; ++it2 )
-            svg << ' ' << it2->x << ' ' << it2->y;
-
-        std::hex(svg);
-        svg << " z\" fill=\"#"
-            << std::setfill('0')
-            << std::setw(2) << int(it->rgba[0])
-            << std::setw(2) << int(it->rgba[1])
-            << std::setw(2) << int(it->rgba[2])
-            << std::setw(0) << std::setfill(' ') << "\" fill-opacity=\""
-            << double(it->rgba[3]) / 255.;
-        std::dec(svg);
-
-        svg << "\" />";
-    }
-
-    svg << "</svg>" << std::endl;
-}
-
-} // namespace Utils
-} // namespace Tracer
-
-#endif // LIBDEPIXELIZE_TRACER_UTILS_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/libdepixelize/splines.h b/src/libdepixelize/splines.h
index 5f592da44..c4b455aae 100644
--- a/src/libdepixelize/splines.h
+++ b/src/libdepixelize/splines.h
@@ -49,8 +49,8 @@ public:
         guint8 rgba[4];
     };
 
-    typedef typename std::vector<Path>::iterator iterator;
-    typedef typename std::vector<Path>::const_iterator const_iterator;
+    typedef std::vector<Path>::iterator iterator;
+    typedef std::vector<Path>::const_iterator const_iterator;
 
     Splines() /* = default */ {}