/***************************************************************************
 *   Copyright (C) 2012 Stefan Bühler <stbuehler@web.de>                   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it 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.                                   *
 *                                                                         *
 *   This program 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 General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/
#include "nonogramsolver.h"
#include "nonogramimage.h"
#include "nonogrammarker.h"
#include "nonogramnumbers.h"

#include <QDebug>

namespace libqnono {
	struct SolverState {
		struct Block {
			int minFirst, maxFirst, length;
		};
		typedef NonogramMarker::Mark Mark;
		
		static const Mark MARK_UNKNOWN = NonogramMarker::NONE;
		static const Mark MARK_BLACK = NonogramMarker::MARKED;
		static const Mark MARK_WHITE = NonogramMarker::CROSSED;
		
		class UndoState {
		private:
			struct UndoOp {
				union {
					struct {
						int *ptr, old;
					} data_int;
					struct {
						Mark *ptr, old;
					} data_mark;
				};
				enum { UNDO_INT, UNDO_MARK } type;
			};
			
			QList<UndoOp> m_ops;
			
		public:
			void trackInt(bool &changed, int &ptr, int val) {
				if (val == ptr) return;
				changed = TRUE;
				if (this) {
					UndoOp op;
					op.type = UndoOp::UNDO_INT;
					op.data_int.ptr = &ptr;
					op.data_int.old = ptr;
					m_ops.push_front(op);
				}
				ptr = val;
			}
			
			void trackMark(bool &changed, Mark &ptr, Mark val) {
				if (val == ptr) return;
				changed = TRUE;
				if (this) {
					UndoOp op;
					op.type = UndoOp::UNDO_MARK;
					op.data_mark.ptr = &ptr;
					op.data_mark.old = ptr;
					m_ops.push_front(op);
				}
				ptr = val;
			}
			
			void undo() {
				foreach (const UndoOp &op, m_ops) {
					switch (op.type) {
					case UndoOp::UNDO_INT:
						*op.data_int.ptr = op.data_int.old;
						break;
					case UndoOp::UNDO_MARK:
						*op.data_mark.ptr = op.data_mark.old;
						break;
					}
				}
				m_ops.clear();
			}
		};
		
		
		NonogramMarker m_marks;
		QVector< QVector<Block> > rows, cols;
		
		inline Mark& pixel(int x, int y) {
			return m_marks.pixel(x, y);
		}
		
		template<typename T>
		struct View : public T {
			View(SolverState & state) : T(state) { }
			
			/* horizontal uses ViewRowColumn, vertical ViewColumnRow */
			
			bool mark(UndoState *undo_state, bool & changed, int m, int from, int to) {
				for (int i = from; i <= to; ++i) {
					if (this->data(m, i) == MARK_WHITE) return FALSE;
					undo_state->trackMark(changed, this->data(m, i), MARK_BLACK);
				}
				return TRUE;
			}
			bool clear(UndoState *undo_state, bool & changed, int m, int from, int to) {
				for (int i = from; i <= to; ++i) {
					if (this->data(m, i) == MARK_BLACK) return FALSE;
					undo_state->trackMark(changed, this->data(m, i), MARK_WHITE);
				}
				return TRUE;
			}
			bool markBlock(UndoState *undo_state, bool & changed, int m, const Block &b) {
				if (b.minFirst == b.maxFirst) {
					if (b.minFirst > 0) {
						if (this->data(m, b.minFirst-1) == MARK_BLACK) return FALSE;
						undo_state->trackMark(changed, this->data(m, b.minFirst-1), MARK_WHITE);
					}
					if (b.minFirst + b.length < this->dimSecond()) {
						if (this->data(m, b.minFirst + b.length) == MARK_BLACK) return FALSE;
						undo_state->trackMark(changed, this->data(m, b.minFirst + b.length), MARK_WHITE);
					}
				}
				return mark(undo_state, changed, m, b.maxFirst, b.minFirst+b.length-1);
			}
		};
		
		struct ViewRowColumn {
			ViewRowColumn(SolverState & state) : state(state) { }
			
			inline Mark& data(int row, int col) { return state.pixel(col, row); }
			inline int dimFirst() const { return state.m_marks.height(); }
			inline int dimSecond() const { return state.m_marks.width(); }
			
			SolverState & state;
		};
		
		struct ViewColumnRow {
			ViewColumnRow(SolverState & state) : state(state) { }
			
			inline Mark& data(int col, int row) { return state.pixel(col, row); }
			inline int dimFirst() const { return state.m_marks.width(); }
			inline int dimSecond() const { return state.m_marks.height(); }
			
			SolverState & state;
		};
		
		SolverState(const NonogramNumbers & numbers)
		: m_marks(numbers.size()) {
			int nrows = m_marks.height(), ncols = m_marks.width();
			rows.resize(nrows);
			cols.resize(ncols);
			for (int row = 0; row < nrows; ++row) {
				foreach (quint16 len, numbers.rows()[row]) {
					Block block = { 0, ncols - len, len };
					rows[row] << block;
				}
			}
			for (int col = 0; col < ncols; ++col) {
				foreach (quint16 len, numbers.columns()[col]) {
					Block block = { 0, nrows - len, len };
					cols[col] << block;
				}
			}
		}
		
		template<typename T>
		bool update(UndoState *undo_state, QVector< QVector<Block> > & lines, View<T> & view, bool & changed) {
			for (int i = 0; i < lines.count(); ++i) {
				QVector<Block> &line(lines[i]);
				int lineLen = line.count();
				
				if (0 == lineLen || (1 == lineLen && 0 == line[0].length)) {
					if (!view.clear(undo_state, changed, i, 0, view.dimSecond()-1)) return FALSE;
					continue;
				}
				
				// first block
				{
					int cell = line[0].minFirst;
					// there must be "length" adjacent non white cells
					for (int cell1 = cell, end = cell + line[0].length; cell <= line[0].maxFirst && cell1 < end; ++cell1) {
						if (MARK_WHITE == view.data(i, cell1)) {
							cell  = cell1 + 1;
							end = cell + line[0].length;
						}
					}
					
					if (cell > line[0].minFirst) {
						if (cell > line[0].maxFirst) return FALSE; // no solution impossible
						undo_state->trackInt(changed, line[0].minFirst, cell);
					}
					// the first black can't be before the first block
					while (cell < line[0].maxFirst && view.data(i, cell) != MARK_BLACK) ++cell;
					if (cell < line[0].maxFirst) {
						undo_state->trackInt(changed, line[0].maxFirst, cell);
					}
				}
				
				// last block
				{
					int len = line.last().length;
					int cell = line.last().maxFirst;
					// there must be "length" adjacent non white cells
					for (int cell1 = cell + len - 1; cell >= line.last().minFirst && cell1 >= cell; --cell1) {
						if (MARK_WHITE == view.data(i, cell1)) {
							cell = cell1 - len;
						}
					}
					
					if (cell < line.last().maxFirst) {
						if (cell < line.last().minFirst) return FALSE; // no solution impossible
						undo_state->trackInt(changed, line.last().maxFirst, cell);
					}
					// the last black can't be after the last block
					while (cell > line.last().minFirst && view.data(i, cell+len-1) != MARK_BLACK) --cell;
					if (cell > line.last().minFirst) {
						undo_state->trackInt(changed, line.last().minFirst, cell);
					}
				}
				
				/* check relative block offsets (min distance 1) */
				for (int j = 1, k = lineLen - 1; j < lineLen; ++j, --k) {
					{
						int minFirst = qMax(line[j].minFirst, 1 + line[j-1].minFirst + line[j-1].length);
						// the cell before first can't be black
						while (minFirst <= line[j].maxFirst && MARK_BLACK == view.data(i, minFirst-1)) ++minFirst;
						// there must be "length" adjacent non white cells
						for (int cell = minFirst, end = minFirst + line[j].length; minFirst <= line[j].maxFirst && cell < end; ++cell) {
							if (MARK_WHITE == view.data(i, cell)) {
								minFirst  = cell + 1;
								end = minFirst + line[j].length;
							}
						}
						
						if (minFirst >= line[j-1].maxFirst + line[j-1].length) {
							int cell = minFirst;
							// next black cell can't be before this block
							while (cell < line[j].maxFirst && view.data(i, cell) != MARK_BLACK) ++cell;
							if (cell < line[j].maxFirst) {
								undo_state->trackInt(changed, line[j].maxFirst, cell);
							}
						}
						
						if (minFirst > line[j].minFirst) {
							if (minFirst > line[j].maxFirst) return FALSE; // no solution impossible
							undo_state->trackInt(changed, line[j].minFirst, minFirst);
						}
					}
					
					{
						int len = line[k-1].length;
						int maxFirst = qMin(line[k-1].maxFirst, line[k].maxFirst - len - 1);
						// the cell after last can't be black
						while (maxFirst >= line[k-1].minFirst && MARK_BLACK == view.data(i, maxFirst + len)) --maxFirst;
						// there must be "length" adjacent non white cells
						for (int cell = maxFirst + len - 1; maxFirst >= line[k-1].minFirst && cell >= maxFirst; --cell) {
							if (MARK_WHITE == view.data(i, cell)) {
								maxFirst = cell - len;
							}
						}
						
						if (maxFirst + len <= line[k].minFirst) {
							int cell = maxFirst;
							// next black cell before maxFirst+len can't be after this block
							while (cell > line[k-1].minFirst && view.data(i, cell+len-1) != MARK_BLACK) --cell;
							if (cell > line[k-1].minFirst) {
								undo_state->trackInt(changed, line[k-1].minFirst, cell);
							}
						}
						
						if (maxFirst < line[k-1].maxFirst) {
							if (maxFirst < line[k-1].minFirst) return FALSE; // no solution impossible
							undo_state->trackInt(changed, line[k-1].maxFirst, maxFirst);
						}
					}
				}
				
				if (!view.clear(undo_state,  changed, i, 0, line[0].minFirst-1)) return FALSE;
				for (int j = 0; j < lineLen; ++j) {
					if (j > 0 && !view.clear(undo_state,  changed, i, line[j-1].maxFirst + line[j-1].length, line[j].minFirst-1)) return FALSE;
					if (!view.markBlock(undo_state, changed, i, line[j])) return FALSE;
				}
				if (!view.clear(undo_state, changed, i, line.last().maxFirst + line.last().length, view.dimSecond()-1)) return FALSE;
				
			}
			return TRUE;
		}
		
		void debugState() {
#ifndef QT_NO_DEBUG_OUTPUT
			for (int j = 0; j < m_marks.height(); ++j) {
				QDebug dbg = qDebug();
				for (int i = 0; i < m_marks.width(); ++i) {
					switch (pixel(i, j)) {
					case MARK_UNKNOWN:
						dbg << "?"; break;
					case MARK_BLACK:
						dbg << "M"; break;
					case MARK_WHITE:
						dbg << " "; break;
					}
				}
			}
			qDebug() << "Row blocks:";
			for (int j = 0; j < rows.count(); ++j) {
				QDebug dbg = qDebug() << j << ":";
				foreach (Block block, rows[j]) {
					dbg << "[" << block.minFirst << block.maxFirst << block.length << "]";
				}
			}
			qDebug() << "Col blocks:";
			for (int j = 0; j < cols.count(); ++j) {
				QDebug dbg = qDebug() << j << ":";
				foreach (Block block, cols[j]) {
					dbg << "[" << block.minFirst << block.maxFirst << block.length << "]";
				}
			}
#endif
		}
		
		void solve(QList<NonogramImage> &solutions, UndoState *undo_state = 0) {
			bool changed = TRUE;
			View<ViewRowColumn> rowColumn(*this);
			View<ViewColumnRow> columnRow(*this);
			while (changed) {
				changed = FALSE;
				if (!update(undo_state, rows, rowColumn, changed)) return;
				if (!update(undo_state, cols, columnRow, changed)) return;
			}
			if (!undo_state) {
				qDebug() << "State after first run:";
				debugState();
			}
			for (int i = 0; i < m_marks.width(); ++i) {
				for (int j = 0; j < m_marks.height(); ++j) {
					if (pixel(i, j) == MARK_UNKNOWN) {
						UndoState subundo;
						
						subundo.trackMark(changed, pixel(i, j), MARK_BLACK);
						solve(solutions, &subundo);
						subundo.undo();
						
						subundo.trackMark(changed, pixel(i, j), MARK_WHITE);
						solve(solutions, &subundo);
						subundo.undo();
						return;
					}
				}
			}
			
			qDebug() << "Found solution:";
			debugState();
			
			solutions.append(NonogramImage());;
			solutions.last().load(m_marks);
		}
		
	};
	
	
	QList<NonogramImage> solve(const NonogramNumbers & numbers) {
		QList<NonogramImage> solutions;
		SolverState solveState(numbers);
		solveState.solve(solutions);
		
		foreach(const NonogramImage& solution, solutions) {
			Q_ASSERT(numbers.check(solution));
		}
		
		return solutions;
	}
}