#ifndef BORDERS_EXTRACTOR_HPP

#define BORDERS_EXTRACTOR_HPP

//Toonz includes

#include "raster_edge_iterator.h"

//tcg includes

#include "tcg/tcg_traits.h"

#include "tcg/tcg_containers_reader.h"

#include "tcg/tcg_hash.h"

#include "tcg/tcg_misc.h"

#include "borders_extractor.h"

namespace TRop

{

namespace borders

{

//*********************************************************************************************************

//    Private stuff

//*********************************************************************************************************

template <typename pixelselector=""></typename>

class _DummyReader

{

public:

	void openContainer(const RasterEdgeIterator<pixelselector> &) {}</pixelselector>

	void addElement(const RasterEdgeIterator<pixelselector> &) {}</pixelselector>

	void closeContainer() {}

};

//*********************************************************************************************************

//    Borders Extraction procedure

//*********************************************************************************************************

inline void _signEdge(RunsMapP &runsMap, int x, int y0, int y1, UCHAR increasingSign, UCHAR decreasingSign)

{

	for (; y0 < y1; ++y0)

		runsMap->runHeader(x, y0) |= increasingSign;

	if (y0 > y1) {

		--x;

		do {

			--y0;

			runsMap->runHeader(x, y0) |= decreasingSign;

		} while (y0 > y1);

	}

}

//---------------------------------------------------------------------------------------------

template <typename containerreader="" pixel,="" pixelselector,="" typename=""></typename>

void _readBorder(const TRasterPT<pixel> &rin, const PixelSelector &selector,</pixel>

				 RunsMapP &runsMap, int x, int y, bool counter, ContainerReader &reader)

{

	typedef typename PixelSelector::value_type value_type;

	UCHAR increasingSign = _BORDER_LEFT, decreasingSign = _BORDER_RIGHT;

	if (!counter)

		increasingSign |= _HIERARCHY_INCREASE, decreasingSign |= _HIERARCHY_DECREASE;

	//First, read the border entirely, while erasing the border from

	//the runsMap.

	RasterEdgeIterator<pixelselector> it(rin, selector, TPoint(x, y), counter ? TPoint(1, 0) : TPoint(0, 1));</pixelselector>

	//++it;   //As we could be in the middle of a straight edge, increment to get a corner

	TPoint start(it.pos()), startDir(it.dir());

	reader.openContainer(it);

	TPoint oldPos(start);

	for (++it; it.pos() != start || it.dir() != startDir; ++it) {

		const TPoint &currPos(it.pos());

		reader.addElement(it);

		//Sign the corresponding (vertical) edge

		_signEdge(runsMap, oldPos.x, oldPos.y, currPos.y, increasingSign, decreasingSign);

		oldPos = currPos;

	}

	_signEdge(runsMap, oldPos.x, oldPos.y, it.pos().y, increasingSign, decreasingSign);

	reader.closeContainer();

}

//---------------------------------------------------------------------------------------------

template <typename containerreader="" pixel,="" pixelselector,="" typename=""></typename>

void readBorders(const TRasterPT<pixel> &rin, const PixelSelector &selector,</pixel>

				 ContainerReader &reader, RunsMapP *rasterRunsMap)

{

	typedef TRasterPT<pixel> RasterTypeP;</pixel>

	typedef _DummyReader<pixelselector> DummyReader;</pixelselector>

	//First, extract the run-length representation for rin

	RunsMapP runsMap;

	if (rasterRunsMap && *rasterRunsMap) {

		//If it was supplied, use it

		runsMap = *rasterRunsMap;

		runsMap->lock();

	} else {

		//In case, build it anew

		runsMap = RunsMapP(rin->getLx(), rin->getLy());

		runsMap->lock();

		buildRunsMap(runsMap, rin, selector);

	}

	if (rasterRunsMap)

		//Return the runsMap if requested

		*rasterRunsMap = runsMap;

	//Build a fake reader for internal borders

	DummyReader dummyReader;

	//Now, use it to extract borders - iterate through runs and, whenever

	//one is found with opaque color (ie not transparent), extract its

	//associated border. The border is erased internally after the read.

	int lx = rin->getLx(), ly = rin->getLy();

	int hierarchyLevel = 0;

	int x, y;

	for (y = 0; y < ly; ++y) {

		Pixel *lineStart = rin->pixels(y), *pix;

		TPixelGR8 *runsStart = runsMap->pixels(y), *run;

		UCHAR nextHeader, prevHeader = 0;

		for (x = 0, pix = lineStart, run = runsStart; x < lx;) {

			nextHeader = run->value;

			if (hierarchyLevel) {

				if (prevHeader & _BORDER_RIGHT) {

					if (prevHeader & _HIERARCHY_DECREASE)

						--hierarchyLevel;

				} else //Every right border in a region should be signed. Do so now.

					_readBorder(rin, selector, runsMap, x, y, true, dummyReader);

			}

			if (hierarchyLevel) {

				if (nextHeader & _BORDER_LEFT) {

					if (nextHeader & _HIERARCHY_INCREASE)

						++hierarchyLevel;

				} else {

					++hierarchyLevel;

					_readBorder(rin, selector, runsMap, x, y, false, reader);

				}

			} else {

				if (!(selector.transparent(*pix))) //External transparent region - do not extract

				{

					++hierarchyLevel;

					if (!(nextHeader & _BORDER_LEFT))

						_readBorder(rin, selector, runsMap, x, y, false, reader);

				}

			}

			//Increment variables

			x += runsMap->runLength(x, y), pix = lineStart + x, run = runsStart + x;

			prevHeader = (run - 1)->value;

		}

		assert(x == lx);

		if (hierarchyLevel) {

			assert((prevHeader & _BORDER_RIGHT) && (prevHeader & _HIERARCHY_DECREASE));

			--hierarchyLevel;

		}

		assert(!hierarchyLevel);

	}

	runsMap->unlock();

}

//*********************************************************************************************************

//    New Mesh Extraction procedure

//*********************************************************************************************************

enum { _PROCESSED = 0x1,

	   _HIERARCHY_UP = 0x2,

	   _HIERARCHY_DN = 0x4,

	   _PROCESSED_AND_HIERARCHY_UP = (_PROCESSED | _HIERARCHY_UP) };

//-------------------------------------------------------------------

template <typename rasteredgeiter=""></typename>

inline bool _isVertex(const RasterEdgeIter &it, const typename RasterEdgeIter::value_type &oldOtherColor)

{

	return (it.otherColor() != oldOtherColor) ||

		   (it.turn() == it.adherence() && (!(it.turn() & RasterEdgeIter::AMBIGUOUS)) &&

			it.elbowColor() != oldOtherColor);

}

//-------------------------------------------------------------------

inline size_t _pointHash(const TPoint &point) { return point.x ^ point.y; }

//-------------------------------------------------------------------

template <typename rasteredgeiter=""></typename>

struct _ExternalEdgeSigner {

	static inline void signAndIncrement(RunsMapP &runsMap, RasterEdgeIter &it)

	{

		if (it.dir().y > 0) {

			TPoint pos = it.pos();

			int newY = (++it).pos().y;

			for (; pos.y != newY; ++pos.y)

				runsMap->runHeader(pos.x, pos.y) |= _PROCESSED_AND_HIERARCHY_UP;

		} else if (it.dir().y < 0) {

			TPoint pos = it.pos();

			int newY = (++it).pos().y;

			TPixelGR8 *pix = runsMap->pixels(pos.y - 1) + pos.x;

			for (; pos.y != newY; --pos.y, --pix) {

				pix->value |= _PROCESSED;

				(--pix)->value |= _HIERARCHY_DN;

			}

		} else

			++it;

	}

};

//-------------------------------------------------------------------

template <typename rasteredgeiter=""></typename>

struct _InternalEdgeSigner {

	static inline void signAndIncrement(RunsMapP &runsMap, RasterEdgeIter &it)

	{

		if (it.dir().y) {

			TPoint pos = it.pos();

			int newY = (++it).pos().y;

			int dir = it.dir().y;

			TPixelGR8 *pix = runsMap->pixels((it.dir().y > 0) ? pos.y : pos.y - 1) + pos.x;

			for (; pos.y != newY; pos.y += dir, pix += dir) {

				pix->value |= _PROCESSED_AND_HIERARCHY_UP;

				(--pix)->value |= _HIERARCHY_DN;

			}

		} else

			++it;

	}

};

//-------------------------------------------------------------------

template <typename containersreader,="" edgesigner="" mesh,="" rasteredgeiter,="" typename=""></typename>

int _readEdge(RasterEdgeIter &it, const RasterEdgeIter &end, RunsMapP runsMap,

			  int &vIdx, Mesh &mesh, tcg::hash<tpoint, int=""> &pointsHash, ContainersReader &reader)</tpoint,>

{

	typedef tcg::container_reader_traits<containersreader, mesh::edge_type="" typename=""> edge_output;</containersreader,>

	typename Mesh::edge_type ed;

	ed.addVertex(vIdx);

	ed.direction(0) = it.dir();

	edge_output::openContainer(reader, it);

	typename RasterEdgeIter::value_type oldOtherColor = it.otherColor();

	do {

		EdgeSigner::signAndIncrement(runsMap, it);

		edge_output::addElement(reader, it);

	} while ((it != end) && !_isVertex(it, oldOtherColor));

	// Identify the newly found vertex. If it's a brand new one, add it

	tcg::hash<tpoint, int="">::iterator ht = pointsHash.find(it.pos());</tpoint,>

	vIdx = (ht == pointsHash.end()) ? pointsHash[it.pos()] = mesh.addVertex(typename Mesh::vertex_type(it.pos())) : ht.m_idx;

	ed.addVertex(vIdx);

	ed.direction(1) = (it.turn() == RasterEdgeIter::STRAIGHT) ? -it.dir() : (it.turn() == RasterEdgeIter::LEFT) ? tcg::point_ops::ortLeft(it.dir()) : tcg::point_ops::ortRight(it.dir());

	int eIdx = mesh.addEdge(ed);

	edge_output::closeContainer(reader, &mesh, eIdx);

	return eIdx;

}

//---------------------------------------------------------------------------------------------

template <typename containersreader="" mesh,="" rasteredgeiter,="" typename=""></typename>

void _readMeshes(const RasterEdgeIter &begin, RunsMapP &runsMap, ContainersReader &reader)

{

	typedef tcg::container_reader_traits<containersreader, mesh::face_type="" typename=""> face_output;</containersreader,>

	// Iterate it clockwise. Process lines with vertical displacement. In each line, search

	// for unprocessed raster edges.

	// Use hierarchy signs in the runsMap to understand the search scope in this sub-region.

	int hierarchyLevel = 0;

	RasterEdgeIter it(begin);

	do {

		if (it.dir().y > 0) {

			// Process line

			TPoint pos = it.pos();

			const TPixelGR8 *pix = runsMap->pixels(pos.y) + pos.x;

			hierarchyLevel = 0;

			assert((pix->value & _PROCESSED) && (pix->value & _HIERARCHY_UP));

			do {

				// Iterate through the line. Extract a mesh each time an unprocessed raster edge is found.

				if (!(pix->value & _PROCESSED)) {

					assert(hierarchyLevel == 1);

					Mesh *meshPtr = new Mesh;

					_readMesh(it.raster(), it.selector(), runsMap, pos.x, pos.y, *meshPtr, reader);

					face_output::addElement(reader, meshPtr);

				}

				if (pix->value & _HIERARCHY_UP)

					++hierarchyLevel;

				TUINT32 l = runsMap->runLength(pos.x, pos.y);

				pos.x += l;

				pix += l;

				if ((pix - 1)->value & _HIERARCHY_DN)

					--hierarchyLevel;

			} while (hierarchyLevel > 0);

		}

		++it;

	} while (it != begin);

}

//-------------------------------------------------------------------

template <typename containersreader="" mesh,="" rasteredgeiter,="" typename=""></typename>

void _readBorder(const RasterEdgeIter &begin, RunsMapP runsMap,

				 int vIdx, Mesh &mesh, tcg::hash<tpoint, int=""> &pointsHash,</tpoint,>

				 ContainersReader &reader)

{

	typedef typename Mesh::face_type face_type;

	typedef typename Mesh::edge_type edge_type;

	typedef tcg::container_reader_traits<containersreader, mesh::face_type="" typename=""> face_output;</containersreader,>

	// As long as we don't get back to the initial iterator, extract edges

	RasterEdgeIter it(begin);

	// Create the face to be extracted at the right of processed border, and add it to

	// the mesh. Observe that insertion is made manually in the mesh's faces list.

	// This prevents the mesh from automatically link edges to the face.

	face_type fc;

	do {

		// Retrieve current vertex

		typename Mesh::vertex_type &vx = mesh.vertex(vIdx);

		// Search in it the edge corresponding to current iterating direction

		int e, edgesCount = vx.edgesCount(), eIdx = -1, side = -1;

		for (e = 0; e < edgesCount; ++e) {

			edge_type &ed = mesh.edge(vx.edge(e));

			side = ed.vertex(0) == vIdx ? 0 : 1;

			if (ed.direction(side) == it.dir()) {

				eIdx = ed.getIndex();

				break;

			}

		}

		if (e == edgesCount) {

			// In case the edge was not found, it needs to be extracted now.

			eIdx = _readEdge<rasteredgeiter, _internaledgesigner<rasteredgeiter="" containersreader,="" mesh,="">>(</rasteredgeiter,>

				it, begin, runsMap, vIdx, mesh, pointsHash, reader);

		} else {

			// The edge was already extracted. We just need to update the iterator then.

			const edge_type &ed = mesh.edge(eIdx);

			vIdx = ed.vertex(1 - side);

			const TPoint &oppositePos = mesh.vertex(vIdx).P();

			const TPoint &oppositeDir = ed.direction(1 - side);

			// We need to perform the last ++it in the already extracted edge since we need

			// to give it the incoming direction.

			it.setEdge(oppositePos + oppositeDir, -oppositeDir), ++it;

		}

		fc.addEdge(eIdx);

	} while (it != begin);

	// The face has now been described (from the mesh viewpoint). Add it to the mesh.

	int fIdx = mesh.addFace(fc);

	// We still need to extract its sub-meshes content now.

	face_output::openContainer(reader, &mesh, fIdx, begin.rightColor());

	_readMeshes<rasteredgeiter, containersreader="" mesh,="">(begin, runsMap, reader);</rasteredgeiter,>

	face_output::closeContainer(reader);

}

//-------------------------------------------------------------------

template <typename containersreader="" mesh,="" pixelselector,="" typename=""></typename>

void _readMesh(const TRasterPT<typename pixelselector::pixel_type=""> &rin,</typename>

			   const PixelSelector &selector, RunsMapP &runsMap, int x, int y,

			   Mesh &mesh, ContainersReader &reader)

{

	typedef typename Mesh::vertex_type vertex_type;

	typedef typename Mesh::edge_type edge_type;

	typedef tcg::container_reader_traits<containersreader, edge_type=""> edge_output;</containersreader,>

	typedef typename PixelSelector::value_type value_type;

	typedef RasterEdgeIterator<pixelselector> raster_edge_iterator;</pixelselector>

	// Iterate silently until a vertex is encountered (or until the initial point is found)

	raster_edge_iterator it(rin, selector, TPoint(x, y), TPoint(0, 1)), begin(it);

	it.setAdherence(raster_edge_iterator::LEFT);

	value_type beginColor = begin.rightColor();

	for (++it; it != begin && !_isVertex(it, beginColor); ++it)

		;

	// Use a hash to keep track of found vertices

	tcg::hash<tpoint, int=""> pointsHash(&_pointHash);</tpoint,>

	int vIdx = pointsHash[it.pos()] = mesh.addVertex(it.pos());

	// The outer edges are extracted first in clockwise orientation.

	begin = it;

	do {

		_readEdge<raster_edge_iterator, _externaledgesigner<raster_edge_iterator="" containersreader,="" mesh,="">>(</raster_edge_iterator,>

			it, begin, runsMap, vIdx, mesh, pointsHash, reader);

	} while (it != begin);

	// Then, their associated faces are extracted.

	it.setAdherence(raster_edge_iterator::RIGHT);

	int e, outerEdgesCount = mesh.edgesCount();

	for (e = 0; e < outerEdgesCount; ++e) {

		const edge_type &ed = mesh.edge(e);

		if (ed.face(0) < 0) {

			vIdx = ed.vertex(0);

			const vertex_type &vx = mesh.vertex(vIdx);

			it.setEdge(vx.P(), ed.direction(0));

			_readBorder(it, runsMap, vIdx, mesh, pointsHash, reader);

		}

	}

	// Edges following those must have either side associated with a face.

	// Which must be extracted too.

	for (e = outerEdgesCount; e < mesh.edgesCount(); ++e) {

		const edge_type &ed = mesh.edge(e);

		if (ed.face(1) < 0) {

			vIdx = ed.vertex(1);

			const vertex_type &vx = mesh.vertex(vIdx);

			it.setEdge(vx.P(), ed.direction(1));

			_readBorder(it, runsMap, vIdx, mesh, pointsHash, reader);

		}

	}

}

//---------------------------------------------------------------------------------------------

template <typename containersreader="" mesh,="" pixelselector,="" typename=""></typename>

void readMeshes(const TRasterPT<typename pixelselector::pixel_type=""> &rin, const PixelSelector &selector,</typename>

				ContainersReader &reader, RunsMapP *rasterRunsMap)

{

	typedef typename PixelSelector::pixel_type pixel_type;

	typedef TRasterPT<pixel_type> RasterTypeP;</pixel_type>

	typedef Mesh mesh_type;

	typedef tcg::container_reader_traits<containersreader, mesh::face_type="" typename=""> face_output;</containersreader,>

	// First, extract the run-length representation for rin

	RunsMapP runsMap;

	if (rasterRunsMap && *rasterRunsMap) {

		// If a runsmap was supplied, use it

		runsMap = *rasterRunsMap;

		runsMap->lock();

		assert((runsMap->getLx() == rin->getLx() + 1) && (runsMap->getLy() == rin->getLy()));

	} else {

		// In case, build it anew

		runsMap = RunsMapP(rin->getLx() + 1, rin->getLy());

		// Observe the +1 on the x-axis. One additional pixel is currently required on the right

		// side of the runsmap - for ease of use in the algorithm.

		runsMap->lock();

		buildRunsMap(runsMap, rin, selector);

	}

	if (rasterRunsMap)

		// Return the runsMap if requested

		*rasterRunsMap = runsMap;

	face_output::openContainer(reader, 0, -1, selector.transparent());

	// Now, use it to extract borders - iterate through runs and, whenever

	// one is found with opaque color (ie not transparent), extract its

	// associated border. The border is erased internally after the read.

	int lx = rin->getLx(), ly = rin->getLy();

	int x, y;

	for (y = 0; y < ly; ++y) {

		// Process each row

		pixel_type *lineStart = rin->pixels(y), *pix;

		TPixelGR8 *runsStart = runsMap->pixels(y), *run;

		UCHAR nextHeader, prevHeader = 0;

		for (x = 0, pix = lineStart, run = runsStart; x < lx;) {

			nextHeader = run->value;

			if (!(selector.transparent(*pix) || nextHeader & _PROCESSED)) {

				mesh_type *meshPtr = new mesh_type;

				// Read the mesh. All its internal sub-meshes are read as well.

				_readMesh(rin, selector, runsMap, x, y, *meshPtr, reader);

				face_output::addElement(reader, meshPtr);

			}

			//Increment variables

			x += runsMap->runLength(x, y), pix = lineStart + x, run = runsStart + x;

			prevHeader = (run - 1)->value;

		}

		assert(x == lx);

	}

	face_output::closeContainer(reader);

	runsMap->unlock();

}

}

} //namespace TRop::borders

#endif //BORDERS_EXTRACTOR_HPP