Commit: 24960c389317ab9d6c50dd9ccaef1134e75cd92a - nono_solver (hg)

Nonogram solver

Commit MetaInfo

• Revision: 24960c389317ab9d6c50dd9ccaef1134e75cd92a (tree)
• Time: 2021-03-10 00:57:17
• Author: Alexander Larin <scalar438@gmai...>
• Commiter: Alexander Larin

Log Message

Remove old placeability calculator

Change Summary

• modified: row_solver/impl/row_solver.cpp
• delete: row_solver/impl/reversed_vector.hpp

Incremental Difference

diff -r 8b22bbd65b14 -r 24960c389317 row_solver/impl/reversed_vector.hpp
--- a/row_solver/impl/reversed_vector.hpp	Mon Mar 08 19:49:26 2021 +0300
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,81 +0,0 @@
-#pragma once
-#include <type_traits>
-#include <vector>
-
-namespace impl
-{
-template <class T> class ReversedVectorConst
-{
-public:
-	ReversedVectorConst(const std::vector<T> &data) : : m_data_ptr_const(&data) {}
-	ReversedVectorConst() {}
-
-	typename std::vector<T>::const_reference operator[](size_t index) const
-	{
-		return *(m_data_ptr_const->rbegin() + index);
-	}
-
-	size_t size() const { return m_data_ptr_const->size(); }
-
-protected:
-	const std::vector<T> *m_data_ptr_const;
-};
-
-template <class T> class ReversedVector : public ReversedVectorConst<T>
-{
-public:
-	ReversedVector(std::vector<T> &data) : m_data_ptr(&data) {}
-	ReversedVector() {}
-
-	typename std::vector<T>::reference operator[](size_t index)
-	{
-		return *(m_data_ptr->rbegin() + index);
-	}
-
-	using ReversedVectorConst::operator[];
-
-	void resize(size_t new_size) { m_data_ptr->resize(new_size); }
-
-	void set_data_ptr(std::vector<T> *data_ptr)
-	{
-		m_data_ptr       = data_ptr;
-		m_data_ptr_const = data_ptr;
-	}
-
-protected:
-	std::vector<T> *m_data_ptr;
-};
-
-} // namespace impl
-
-template <class T>
-class ReversedVector : public std::conditional_t<std::is_const_v<T>, impl::ReversedVectorConst<T>,
-                                                 impl::ReversedVector<T>>
-{
-public:
-	explicit ReversedVector(std::vector<T> &data) { set_data_ptr(&data); }
-
-	ReversedVector() { set_data_ptr(&m_data); }
-
-	ReversedVector(ReversedVector<T> &&old) noexcept : m_data(std::move(old.m_data))
-	{
-		if (&old.m_data == old.m_data_ptr)
-		{
-			m_data_ptr = &m_data;
-		}
-		else
-		{
-			m_data_ptr = old.m_data_ptr;
-		}
-	}
-
-	std::vector<T> move_out()
-	{
-		auto old_ptr = m_data_ptr;
-		set_data_ptr(&m_data);
-		return std::move(*old_ptr);
-	}
-
-private:
-	std::vector<T> m_data;
-};
\ No newline at end of file

diff -r 8b22bbd65b14 -r 24960c389317 row_solver/impl/row_solver.cpp
--- a/row_solver/impl/row_solver.cpp	Mon Mar 08 19:49:26 2021 +0300
+++ b/row_solver/impl/row_solver.cpp	Tue Mar 09 18:57:17 2021 +0300
@@ -1,5 +1,4 @@
 #include "row_solver.hpp"
-#include "reversed_vector.hpp"
 #include <algorithm>
 #include <set>
 #include <string>
@@ -27,6 +26,7 @@
 		std::reverse(m_suffix_positions.begin(), m_suffix_positions.end());
 	}
 
+	// return true if we can place first block_index blocks on first cell_index cells
 	bool can_place_prefix(size_t cell_index, size_t block_index) const
 	{
 		if (block_index == 0)
@@ -39,6 +39,7 @@
 		}
 	}
 
+	// return true if we can place last block_index blocks on last n - cell_index cells
 	bool can_place_suffix(size_t cell_index, size_t block_index) const
 	{
 		if (block_index == 0)
@@ -100,48 +101,6 @@
 	}
 };
 
-template <class TCell, class TBlock, class TResult>
-void calc_blocks_placeability(const TCell &cells, const TBlock &blocks, std::vector<TResult> &res)
-{
-	const size_t n = cells.size();
-	if (n == 0) return;
-	const size_t k = blocks.size();
-
-	res.resize(k + 1);
-	res[0].resize(n + 1);
-	res[0][0]      = true;
-	bool cur_value = true;
-	for (size_t i = 0; i != n; ++i)
-	{
-		if (cur_value && !cells[i].is_color_possible(0)) cur_value = false;
-		res[0][i + 1] = cur_value;
-	}
-	for (size_t i = 0; i != k; ++i)
-	{
-		res[i + 1].resize(n + 1);
-		res[i + 1][0] = false;
-
-		int current_allowed_count = 0;
-
-		int delta = i == 0 ? 1 : 0;
-
-		cur_value = false;
-
-		for (size_t j = 0; j < n; ++j)
-		{
-			if (cells[j].is_color_possible(blocks[i].color_number))
-				current_allowed_count += 1;
-			else
-				current_allowed_count = 0;
-			if (!cur_value && j - blocks[i].block_length + delta <= n &&
-			    current_allowed_count >= blocks[i].block_length &&
-			    res[i][j - blocks[i].block_length + delta])
-				cur_value = true;
-			res[i + 1][j + 1] = cur_value;
-		}
-	}
-}
-
 std::vector<size_t> calculate_row(std::vector<Cell> &cells, std::vector<Block> &blocks)
 {
 	const size_t n = cells.size();
@@ -149,18 +108,7 @@
 
 	while (1)
 	{
-		// can_place_prifix[i][j] == true if we can place first i blocks at the first j cells
-		// can_place_suffix - same, but for last i blocks and last n - j cells
-		std::vector<std::vector<bool>> can_place_prefix, can_place_suffix;
-
-		calc_blocks_placeability(cells, blocks, can_place_prefix);
-		{
-			std::vector<ReversedVector<bool>> can_place_suffix_rev;
-			calc_blocks_placeability(ReversedVector(cells), ReversedVector(blocks),
-			                         can_place_suffix_rev);
-			for (auto &rev_vector : can_place_suffix_rev)
-				can_place_suffix.emplace_back(rev_vector.move_out());
-		}
+		PlaceabilityCalculator pc(cells, blocks);
 
 		std::vector<Cell> new_cell_list;
 		{
@@ -178,7 +126,7 @@
 				bool can_place = false;
 				for (size_t j = 0; j <= blocks_count; ++j)
 				{
-					if (can_place_prefix[j][i] && can_place_suffix[blocks_count - j][i + 1])
+					if (pc.can_place_prefix(i, j) && pc.can_place_suffix(i + 1, blocks_count - j))
 					{
 						can_place = true;
 						break;
@@ -216,9 +164,9 @@
 				size_t delta_suffix = k == blocks_count - 1 ? 0 : 1;
 
 				if (int(i) + 1 - blocks[k].block_length - delta_prefix <= n &&
-				    can_place_prefix[k][i + 1 - blocks[k].block_length - delta_prefix] &&
+				    pc.can_place_prefix(i + 1 - blocks[k].block_length - delta_prefix, k) &&
 				    i + delta_suffix + 1 <= n &&
-				    can_place_suffix[blocks_count - k - 1][i + delta_suffix + 1])
+				    pc.can_place_suffix(i + delta_suffix + 1, blocks_count - k - 1))
 				{
 					for (size_t j = i - blocks[k].block_length + 1; j <= i; ++j)
 					{