#ifndef LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H

#define LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H

#include "simplifiedvoronoi.h"

#include "point.h"

#include <algorithm>

#include <utility>

namespace Tracer {

template<typename T>

class HomogeneousSplines

{

public:

struct Polygon

{

Polygon() {}

Polygon(const guint8 (&rgba)[4])

{

for ( int i = 0 ; i != 4 ; ++i )

this->rgba[i] = rgba[i];

}

std::vector< Point<T> > vertices;

/**

std::vector< std::vector< Point<T> > > holes;

guint8 rgba[4];

};

typedef typename std::vector<Polygon>::iterator iterator;

typedef typename std::vector<Polygon>::const_iterator const_iterator;

typedef typename std::vector<Polygon>::size_type size_type;

HomogeneousSplines(const SimplifiedVoronoi<T> &voronoi);

// Iterators

iterator begin()

{

return _polygons.begin();

}

const_iterator begin() const

{

return _polygons.begin();

}

iterator end()

{

return _polygons.end();

}

const_iterator end() const

{

return _polygons.end();

}

size_type size() const

{

return _polygons.size();

}

int width() const

{

return _width;

}

int height() const

{

return _height;

}

private:

typedef typename SimplifiedVoronoi<T>::Cell Cell;

typedef std::vector< Point<T> > Points;

typedef typename SimplifiedVoronoi<T>::iterator voronoi_iter;

typedef typename SimplifiedVoronoi<T>::const_iterator voronoi_citer;

typedef typename Points::iterator points_iter;

typedef typename Points::const_iterator points_citer;

typedef typename Points::reverse_iterator points_riter;

typedef typename Points::const_reverse_iterator points_criter;

typedef std::pair<points_iter, points_iter> points_range;

typedef std::pair<points_citer, points_citer> points_crange;

struct CommonEdge

{

bool ok; //< share an edge

Points *dst;

const Points *src;

// the interval is closed on both ends

// different from [begin, end) STL style

points_iter dst_begin, dst_end;

points_citer src_begin, src_end;

};

struct SelfCommonEdge

{

bool ok; //< share an edge

// Greater range. The one that should be erased from the vector.

points_riter grt_begin, grt_end;

// Smaller range. The one that should be used to create a new vector.

points_riter sml_begin, sml_end;

};

/**

CommonEdge _common_edge(Points &dst, const Points &src);

/**

SelfCommonEdge _common_edge(Points &points, points_riter it);

/*!

void _polygon_union(CommonEdge common_edge);

/**

void _fill_holes(std::vector<Points> &holes, points_iter region_begin,

points_iter region_end);

std::vector<Polygon> _polygons;

int _width;

int _height;

};

template<class T>

HomogeneousSplines<T>::HomogeneousSplines(const SimplifiedVoronoi<T> &voronoi) :

_width(voronoi.width()),

_height(voronoi.height())

{

//if (!voronoi.size())

// return;

using colorspace::same_color;

// Identify visible edges (group polygons with the same color)

for ( voronoi_citer cell_it = voronoi.begin(), cell_end = voronoi.end()

; cell_it != cell_end ; ++cell_it ) {

bool found = false;

for ( iterator polygon_it = _polygons.begin(),

polygon_end = _polygons.end()

; polygon_it != polygon_end ; ++polygon_it ) {

if ( same_color(polygon_it->rgba, cell_it->rgba) ) {

CommonEdge common_edge = _common_edge(polygon_it->vertices,

cell_it->vertices);

if ( common_edge.ok ) {

_polygon_union(common_edge);

found = true;

for ( iterator polygon2_it = polygon_it + 1

; polygon2_it != polygon_end ; ++polygon2_it ) {

if ( same_color(polygon_it->rgba, polygon2_it->rgba) ) {

CommonEdge common_edge2

= _common_edge(polygon_it->vertices,

polygon2_it->vertices);

if ( common_edge2.ok ) {

_polygon_union(common_edge2);

_polygons.erase(polygon2_it);

break;

}

}

}

break;

}

}

}

if ( !found ) {

Polygon polygon(cell_it->rgba);

polygon.vertices = cell_it->vertices;

_polygons.insert(_polygons.end(), polygon);

}

}

// Find polygons with holes and fix them

// This iteration runs such complex time-consuming algorithm, but each

// polygon has an independent result. They wouldn't even need to share/sync

// results and the only waste would be a join at the end of the for.

for ( typename std::vector<Polygon>::iterator it = _polygons.begin(),

end = _polygons.end() ; it != end ; ++it ) {

SelfCommonEdge ce = _common_edge(it->vertices, it->vertices.rbegin());

while ( ce.ok ) {

_fill_holes(it->holes, ce.sml_end.base(), ce.sml_begin.base());

it->vertices.erase(ce.grt_end.base() + 1, ce.grt_begin.base());

ce = _common_edge(it->vertices, ce.grt_end);

}

}

}

template<class T>

typename HomogeneousSplines<T>::CommonEdge

HomogeneousSplines<T>::_common_edge(Points &dst, const Points &src)

{

// It's an edge, then the points are closer together. After we find the

// first point, there is no need for check against all points of the src

// a second time

const points_iter dst_begin = dst.begin();

const points_iter dst_end = dst.end();

const points_citer src_begin = src.begin();

const points_citer src_end = src.end();

for ( points_iter it = dst_begin ; it != dst_end ; ++it ) {

points_citer src_it = std::find(src_begin, src_end, *it);

if ( src_it == src_end )

continue;

points_iter dst_common_edge_begin = it;

points_citer src_common_edge_end = src_it;

// iterate until find the beginning of the common edge range

while ( *dst_common_edge_begin == *src_common_edge_end ) {

if ( dst_common_edge_begin == dst_begin )

dst_common_edge_begin = dst_end - 1;

else

--dst_common_edge_begin;

++src_common_edge_end;

if ( src_common_edge_end == src_end )

src_common_edge_end = src_begin;

}

// fix {dst_begin, src_end} range

++dst_common_edge_begin;

if ( dst_common_edge_begin == dst_end )

dst_common_edge_begin = dst_begin;

if ( src_common_edge_end == src_begin )

src_common_edge_end = src_end - 1;

else

--src_common_edge_end;

points_iter dst_common_edge_end = it;

points_citer src_common_edge_begin = src_it;

// find the end of the common edge range

while ( *dst_common_edge_end == *src_common_edge_begin ) {

++dst_common_edge_end;

if ( dst_common_edge_end == dst_end )

dst_common_edge_end = dst_begin;

if ( src_common_edge_begin == src_begin )

src_common_edge_begin = src_end - 1;

else

--src_common_edge_begin;

}

// fix {dst_end, src_begin} range

if ( dst_common_edge_end == dst_begin )

dst_common_edge_end = dst_end - 1;

else

--dst_common_edge_end;

++src_common_edge_begin;

if ( src_common_edge_begin == src_end )

src_common_edge_begin = src_begin;

CommonEdge ret;

// if only one point in common

if ( dst_common_edge_begin == dst_common_edge_end )

continue;

ret.ok = true;

ret.dst = &dst;

ret.dst_begin = dst_common_edge_begin;

ret.dst_end = dst_common_edge_end;

ret.src = &src;

ret.src_begin = src_common_edge_begin;

ret.src_end = src_common_edge_end;

return ret;

}

CommonEdge ret;

ret.ok = false;

return ret;

}

template<class T>

typename HomogeneousSplines<T>::SelfCommonEdge

HomogeneousSplines<T>::_common_edge(Points &points, points_riter it)

{

SelfCommonEdge ret;

ret.grt_end = points.rend();

for ( ; it != ret.grt_end ; ++it ) {

ret.sml_end = std::find(it + 1, ret.grt_end, *it);

if ( ret.sml_end == ret.grt_end )

continue;

ret.grt_begin = it;

ret.grt_end = ret.sml_end + 1;

ret.sml_begin = it;

while ( *ret.sml_begin == *ret.sml_end ) {

++ret.sml_begin;

--ret.sml_end;

}

--ret.sml_begin;

++ret.sml_end;

++ret.sml_end;

ret.ok = true;

return ret;

}

ret.ok = false;

return ret;

}

template<class T>

void HomogeneousSplines<T>::_polygon_union(CommonEdge common_edge)

{

Points &dst = *common_edge.dst;

const Points &src = *common_edge.src;

// the rotated cell must be inserted before (dst.begin() + index)

typename Points::difference_type index;

// first, we remove the common edge in dst

if ( common_edge.dst_begin < common_edge.dst_end ) {

// common edge is in the middle of dst

index = dst.erase(common_edge.dst_begin,

common_edge.dst_end + 1) - dst.begin();

} else {

// common edge cross the end of dst

dst.erase(common_edge.dst_begin, dst.end());

dst.erase(dst.begin(), common_edge.dst_end);

index = dst.end() - dst.begin();

}

// second, we copy src points to polygon

if ( common_edge.src_begin < common_edge.src_end ) {

// common edge is in the middle of src

const typename Points::difference_type nfirstinserted

= src.end() - common_edge.src_end;

const typename Points::difference_type nsecondinserted

= 1 + (common_edge.src_begin - src.begin());

dst.reserve(dst.size() + nfirstinserted + nsecondinserted);

dst.insert(dst.begin() + index, common_edge.src_end, src.end());

dst.insert(dst.begin() + index + nfirstinserted,

src.begin(), common_edge.src_begin + 1);

} else {

// common edge cross the end of src

dst.reserve(dst.size() + 1

+ (common_edge.src_begin - common_edge.src_end));

dst.insert(dst.begin() + index,

common_edge.src_end, common_edge.src_begin + 1);

}

}

template<class T>

void HomogeneousSplines<T>::_fill_holes(std::vector<Points> &holes,

points_iter region_begin,

points_iter region_end)

{

// the exact location might not always be back and iterators will be

// invalidated after some insertions, then the index is required

const typename std::vector<Points>::size_type hole_index = holes.size();

holes.resize(hole_index + 1);

for ( points_iter it = region_begin + 1 ; it != region_end ; ++it ) {

points_iter res = std::find(it + 1, region_end, *it);

if ( res == region_end )

continue;

holes[hole_index].insert(holes[hole_index].end(), region_begin,

it);

region_begin = res;

do {

++it;

--res;

} while ( *it == *res );

_fill_holes(holes, it - 1, res + 2);

it = region_begin;

}

holes[hole_index].insert(holes[hole_index].end(), region_begin,

region_end - 1);

}

} // namespace Tracer

#endif // LIBDEPIXELIZE_TRACER_HOMOGENEOUSSPLINES_H