Adding upstream version 1.2.2.upstream/1.2.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 555 insertions, 0 deletions

diff --git a/src/3rdparty/libdepixelize/priv/pixelgraph.h b/src/3rdparty/libdepixelize/priv/pixelgraph.h
new file mode 100644
index 0000000..1122426
--- /dev/null
+++ b/src/3rdparty/libdepixelize/priv/pixelgraph.h
@@ -0,0 +1,555 @@
+/*  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_PIXELGRAPH_H
+#define LIBDEPIXELIZE_TRACER_PIXELGRAPH_H
+
+#include <gdkmm/pixbuf.h>
+#include <vector>
+#include <cassert>
+#include <utility>
+
+namespace Tracer {
+
+class PixelGraph
+{
+public:
+    class Node
+    {
+    public:
+        /*
+         * Hamming weight of \p adj
+         */
+        unsigned adjsize() const
+        {
+            unsigned all[8] = {
+                adj.top,
+                adj.topright,
+                adj.right,
+                adj.bottomright,
+                adj.bottom,
+                adj.bottomleft,
+                adj.left,
+                adj.topleft
+            };
+            return all[0] + all[1] + all[2] + all[3]
+                + all[4] + all[5] + all[6] + all[7];
+        }
+
+        guint8 rgba[4];
+        // Nodes pointing from this
+        struct Adj
+        {
+            unsigned top: 1;
+            unsigned topright: 1;
+            unsigned right: 1;
+            unsigned bottomright: 1;
+            unsigned bottom: 1;
+            unsigned bottomleft: 1;
+            unsigned left: 1;
+            unsigned topleft: 1;
+        } adj;
+    };
+
+    typedef std::vector<Node>::iterator iterator;
+    typedef std::vector<Node>::const_iterator const_iterator;
+    typedef std::vector<Node>::reverse_iterator reverse_iterator;
+    typedef std::vector<Node>::const_reverse_iterator const_reverse_iterator;
+
+    typedef std::pair<iterator, iterator> Edge;
+    typedef std::pair<Edge, Edge> EdgePair;
+    typedef std::vector<EdgePair> EdgePairContainer;
+
+    class ColumnView
+    {
+    public:
+        ColumnView(std::vector<Node> &nodes, int width, int column) :
+            _nodes(nodes), _width(width), _column(column)
+        {}
+
+        Node &operator[](int line);
+
+    private:
+        std::vector<Node> &_nodes;
+        const int _width;
+        const int _column;
+    };
+
+    PixelGraph(Glib::RefPtr<Gdk::Pixbuf const> pixbuf);
+
+    void checkConsistency();
+
+    /**
+     * It'll let you access the nodes using the syntax:
+     *
+     *     graph[x][y]
+     *
+     * Where x is the column and y is the line.
+     */
+    ColumnView operator[](int column);
+
+    // Iterators
+    iterator begin()
+    {
+        return _nodes.begin();
+    }
+
+    const_iterator begin() const
+    {
+        return _nodes.begin();
+    }
+
+    iterator end()
+    {
+        return _nodes.end();
+    }
+
+    const_iterator end() const
+    {
+        return _nodes.end();
+    }
+
+    reverse_iterator rbegin()
+    {
+        return _nodes.rbegin();
+    }
+
+    const_reverse_iterator rbegin() const
+    {
+        return _nodes.rbegin();
+    }
+
+    reverse_iterator rend()
+    {
+        return _nodes.rend();
+    }
+
+    const_reverse_iterator rend() const
+    {
+        return _nodes.rend();
+    }
+
+    size_t size() const
+    {
+        return _nodes.size();
+    }
+
+    int width() const
+    {
+        return _width;
+    }
+
+    int height() const
+    {
+        return _height;
+    }
+
+    // Algorithms
+    void connectAllNeighbors();
+    EdgePairContainer crossingEdges();
+
+    int toX(const_iterator n) const
+    {
+        return (&*n - &_nodes[0]) % _width;
+    }
+
+    int toY(const_iterator n) const
+    {
+        return (&*n - &_nodes[0]) / _width;
+    }
+
+    iterator nodeTop(iterator n)
+    {
+        return n - _width;
+    }
+
+    iterator nodeBottom(iterator n)
+    {
+        return n + _width;
+    }
+
+    iterator nodeLeft(iterator n)
+    {
+        return n - 1;
+    }
+
+    iterator nodeRight(iterator n)
+    {
+        return n + 1;
+    }
+
+    iterator nodeTopLeft(iterator n)
+    {
+        return n - _width - 1;
+    }
+
+    iterator nodeTopRight(iterator n)
+    {
+        return n - _width + 1;
+    }
+
+    iterator nodeBottomLeft(iterator n)
+    {
+        return n + _width - 1;
+    }
+
+    iterator nodeBottomRight(iterator n)
+    {
+        return n + _width + 1;
+    }
+
+    const_iterator nodeTop(const_iterator n) const
+    {
+        return n - _width;
+    }
+
+    const_iterator nodeBottom(const_iterator n) const
+    {
+        return n + _width;
+    }
+
+    const_iterator nodeLeft(const_iterator n) const
+    {
+        return n - 1;
+    }
+
+    const_iterator nodeRight(const_iterator n) const
+    {
+        return n + 1;
+    }
+
+    const_iterator nodeTopLeft(const_iterator n) const
+    {
+        return n - _width - 1;
+    }
+
+    const_iterator nodeTopRight(const_iterator n) const
+    {
+        return n - _width + 1;
+    }
+
+    const_iterator nodeBottomLeft(const_iterator n) const
+    {
+        return n + _width - 1;
+    }
+
+    const_iterator nodeBottomRight(const_iterator n) const
+    {
+        return n + _width + 1;
+    }
+
+private:
+    PixelGraph(const PixelGraph&);
+
+    int _width;
+    int _height;
+
+    // The data representation follows the image data pattern from gdk-pixbuf.
+    //
+    // Quoting:
+    // "Image data in a pixbuf is stored in memory in uncompressed, packed
+    // format. Rows in the image are stored top to bottom, and in each row
+    // pixels are stored from left to right. There may be padding at the end of
+    // a row."
+    //
+    // Differently, _nodes don't put padding among rows.
+    std::vector<Node> _nodes;
+};
+
+inline PixelGraph::PixelGraph(Glib::RefPtr<Gdk::Pixbuf const> pixbuf) :
+    _width(pixbuf->get_width()),
+    _height(pixbuf->get_height()),
+    _nodes(size_t(_width) * _height)
+{
+    if ( !_width || !_height )
+        return;
+
+    // Initialize the graph using the pixels' color data
+    guint8 *pixels = pixbuf->get_pixels();
+    Node *dest = &_nodes[0];
+    const int n_channels = pixbuf->get_n_channels();
+    const int rowpadding = pixbuf->get_rowstride() - _width * n_channels;
+
+    if ( n_channels == 4 ) {
+        for ( int i = 0 ; i != _height ; ++i ) {
+            for ( int j = 0 ; j != _width ; ++j ) {
+                for ( int k = 0 ; k != 4 ; ++k )
+                    dest->rgba[k] = pixels[k];
+                {
+                    dest->adj.top = 0;
+                    dest->adj.topright = 0;
+                    dest->adj.right = 0;
+                    dest->adj.bottomright = 0;
+                    dest->adj.bottom = 0;
+                    dest->adj.bottomleft = 0;
+                    dest->adj.left = 0;
+                    dest->adj.topleft = 0;
+                }
+                pixels += n_channels;
+                ++dest;
+            }
+            pixels += rowpadding;
+        }
+    } else {
+        assert(n_channels == 3);
+        for ( int i = 0 ; i != _height ; ++i ) {
+            for ( int j = 0 ; j != _width ; ++j ) {
+                for ( int k = 0 ; k != 3 ; ++k )
+                    dest->rgba[k] = pixels[k];
+                dest->rgba[3] = '\xFF';
+                {
+                    dest->adj.top = 0;
+                    dest->adj.topright = 0;
+                    dest->adj.right = 0;
+                    dest->adj.bottomright = 0;
+                    dest->adj.bottom = 0;
+                    dest->adj.bottomleft = 0;
+                    dest->adj.left = 0;
+                    dest->adj.topleft = 0;
+                }
+                pixels += n_channels;
+                ++dest;
+            }
+            pixels += rowpadding;
+        }
+    }
+}
+
+inline void PixelGraph::checkConsistency()
+{
+    PixelGraph::Node *it = &_nodes.front();
+    for ( int i = 0 ; i != _height ; ++i ) {
+        for ( int j = 0 ; j != _width ; ++j, ++it ) {
+            if ( it->adj.top )
+                assert((it - _width)->adj.bottom);
+            if ( it->adj.topright )
+                assert((it - _width + 1)->adj.bottomleft);
+            if ( it->adj.right )
+                assert((it + 1)->adj.left);
+            if ( it->adj.bottomright )
+                assert((it + _width + 1)->adj.topleft);
+            if ( it->adj.bottom )
+                assert((it + _width)->adj.top);
+            if ( it->adj.bottomleft )
+                assert((it + _width - 1)->adj.topright);
+            if ( it->adj.left )
+                assert((it - 1)->adj.right);
+            if ( it->adj.topleft )
+                assert((it - _width - 1)->adj.bottomright);
+        }
+    }
+}
+
+inline PixelGraph::ColumnView PixelGraph::operator[](int column)
+{
+    return ColumnView(_nodes, _width, column);
+}
+
+inline void PixelGraph::connectAllNeighbors()
+{
+    //  ...the "center" nodes first...
+    if ( _width > 2 && _height > 2 ) {
+        iterator it = nodeBottomRight(begin()); // [1][1]
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            for ( int j = 1 ; j != _width - 1 ; ++j ) {
+                it->adj.top = 1;
+                it->adj.topright = 1;
+                it->adj.right = 1;
+                it->adj.bottomright = 1;
+                it->adj.bottom = 1;
+                it->adj.bottomleft = 1;
+                it->adj.left = 1;
+                it->adj.topleft = 1;
+
+                it = nodeRight(it);
+            }
+            // After the previous loop, 'it' is pointing to the last node from
+            // the row.
+            // Go south, then first node in the row (increment 'it' by 1)
+            // Go to the second node in the line (increment 'it' by 1)
+            it += 2;
+        }
+    }
+
+    //  ...then the "top" nodes...
+    if ( _width > 2 ) {
+        Node *it = &_nodes[1];
+        if ( _height > 1 ) {
+            for ( int i = 1 ; i != _width - 1 ; ++i ) {
+                it->adj.right = 1;
+                it->adj.bottomright = 1;
+                it->adj.bottom = 1;
+                it->adj.bottomleft = 1;
+                it->adj.left = 1;
+
+                ++it;
+            }
+        } else {
+            for ( int i = 1 ; i != _width - 1 ; ++i ) {
+                it->adj.right = 1;
+                it->adj.left = 1;
+
+                ++it;
+            }
+        }
+    }
+
+    //  ...then the "bottom" nodes...
+    if ( _width > 2 && _height > 1 ) {
+        Node *it = &((*this)[1][_height - 1]);
+        for ( int i = 1 ; i != _width - 1 ; ++i ) {
+            it->adj.left = 1;
+            it->adj.topleft = 1;
+            it->adj.top = 1;
+            it->adj.topright = 1;
+            it->adj.right = 1;
+
+            ++it;
+        }
+    }
+
+    //  ...then the "left" nodes...
+    if ( _height > 2 ) {
+        iterator it = nodeBottom(begin()); // [0][1]
+        if ( _width > 1 ) {
+            for ( int i = 1 ; i != _height - 1 ; ++i ) {
+                it->adj.top = 1;
+                it->adj.topright = 1;
+                it->adj.right = 1;
+                it->adj.bottomright = 1;
+                it->adj.bottom = 1;
+
+                it = nodeBottom(it);
+            }
+        } else {
+            for ( int i = 1 ; i != _height - 1 ; ++i ) {
+                it->adj.top = 1;
+                it->adj.bottom = 1;
+
+                it = nodeBottom(it);
+            }
+        }
+    }
+
+    //  ...then the "right" nodes...
+    if ( _height > 2 && _width > 1 ) {
+        iterator it = nodeBottom(begin() + _width - 1);// [_width - 1][1]
+        for ( int i = 1 ; i != _height - 1 ; ++i ) {
+            it->adj.bottom = 1;
+            it->adj.bottomleft = 1;
+            it->adj.left = 1;
+            it->adj.topleft = 1;
+            it->adj.top = 1;
+
+            it = nodeBottom(it);
+        }
+    }
+
+    //  ...and the 4 corner nodes
+    {
+        Node *const top_left = &(*this)[0][0];
+
+        if ( _width > 1 )
+            top_left->adj.right = 1;
+
+        if ( _width > 1 && _height > 1 )
+            top_left->adj.bottomright = 1;
+
+        if ( _height > 1 )
+            top_left->adj.bottom = 1;
+    }
+    if ( _width > 1 ) {
+        Node *const top_right = &(*this)[_width - 1][0];
+
+        if ( _height > 1 ) {
+            top_right->adj.bottom = 1;
+            top_right->adj.bottomleft = 1;
+        }
+
+        top_right->adj.left = 1;
+    }
+    if ( _height > 1 ) {
+        Node *const down_left = &(*this)[0][_height - 1];
+        down_left->adj.top = 1;
+
+        if ( _width > 1 ) {
+            down_left->adj.topright = 1;
+            down_left->adj.right = 1;
+        }
+    }
+    if ( _width > 1 && _height > 1 ) {
+        Node *const down_right = &(*this)[_width - 1][_height - 1];
+        down_right->adj.left = 1;
+        down_right->adj.topleft = 1;
+        down_right->adj.top = 1;
+    }
+}
+
+PixelGraph::EdgePairContainer PixelGraph::crossingEdges()
+{
+    EdgePairContainer ret;
+
+    if ( width() < 2 || height() < 2 )
+        return ret;
+
+    // Iterate over the graph, 2x2 blocks at time
+    PixelGraph::iterator it = begin();
+    for (int i = 0 ; i != height() - 1 ; ++i, ++it ) {
+        for ( int j = 0 ; j != width() - 1 ; ++j, ++it ) {
+            EdgePair diagonals(
+                Edge(it, nodeBottomRight(it)),
+                Edge(nodeRight(it), nodeBottom(it)));
+
+            // Check if there are crossing edges
+            if ( !diagonals.first.first->adj.bottomright
+                 || !diagonals.second.first->adj.bottomleft ) {
+                continue;
+            }
+
+            ret.push_back(diagonals);
+        }
+    }
+
+    return ret;
+}
+
+inline PixelGraph::Node &PixelGraph::ColumnView::operator[](int line)
+{
+    return _nodes[line * _width + _column];
+}
+
+} // namespace Tracer
+
+#endif // LIBDEPIXELIZE_TRACER_PIXELGRAPH_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 :