Flood Fill Algorithm

Flood Fill Algorithm

We might have encountered this at many places. Paint tool is one such example, when we say fill with color in paint, it fills the neighboring areas with the same color.
For examples in the below image when we do a fill color on the white area, we would want all the neighboring white areas to be colored.

The algorithm is very simple. We start with the user selected grid, fill it with color and then check the top, bottom, right and left grid and fill them as well. We do this recursively to achieve the end result.

Below is the procedure

floodFill(vector<vector<int>grid>, x, y, oldColor, newColor)

• If x or y is outside the grid, then return.
• If color of grid[x][y] is not same as oldColor, then return
• do the same for top, down, right and left.

    floodFillUtil(grid, x+1, y, oldColor, newColor);
    floodFillUtil(grid, x-1, y, oldColor, newColor);
    floodFillUtil(grid, x, y+1, oldColor, newColor);
    floodFillUtil(grid, x, y-1, oldColor, newColor); 

Lets see a C++ implementation for this algorithm

	#include<vector>
	#include<iostream>
	using namespace std;
	void floodFill(vector<vector<int>>&grid, int x, int y, int oldColor, int newcolor)
	{
	//check boundary conditions
	if (x < 0 || y < 0 || x >= grid.size() || y >= grid.size())
	return;
	//check if current point is previouscolor
	if (grid[x][y] != oldColor)
	return;
	if (grid[x][y] == newcolor)
	return;
	grid[x][y] = newcolor;
	//left
	floodFill(grid,x-1,y,oldColor, newcolor);
	//right
	floodFill(grid, x +1, y, oldColor, newcolor);
	//top
	floodFill(grid, x, y -1, oldColor, newcolor);
	//bottom
	floodFill(grid, x, y + 1, oldColor, newcolor);
	}
	void printgrid(vector<vector<int>>&grid)
	{
	for (int x = 0; x < grid.size(); x++)
	{
	for (int y = 0; y < grid.size(); y++)
	{
	cout << grid[x][y];
	}
	cout << endl;
	}
	}
	int main()
	{
	vector<vector<int>>grid =
	{
	{ 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 1, 0, 0 },
	{ 1, 0, 0, 1, 1, 0, 1, 1 },
	{ 1, 2, 2, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 2, 2, 0 },
	{ 1, 1, 1, 1, 1, 2, 1, 1 },
	{ 1, 1, 1, 1, 1, 2, 2, 1 },
	};
	int x = 4;
	int y = 4;
	printgrid(grid);
	//convert all 2s to 9
	floodFill(grid,x,y,grid[x][y],9);
	printgrid(grid);
	return 0;
	}

view raw FloodFill.cpp hosted with ❤ by GitHub

Multithreading:6.Print odd and even numbers using two threads

In this program we are going to look into how to print odd numbers using one thread and even numbers using another thread, the numbers have to be printed in order.
In the below code we have added two methods one to print odd numbers and the other to print even numbers, we call one from t1 and another from t2.

	#include <iostream>
	#include <string>
	#include <thread>
	#include <mutex>
	#include <condition_variable>
	using namespace std;
	std::mutex mu;
	std::condition_variable cv;
	std::string data;
	bool odddone = false;
	bool evendone = true;
	int num = 0;//lets start the number with 0;
	void print_odd()
	{
	while (num < 100)
	{
	// Wait until main() sends data
	unique_lock<mutex> lock(mu);
	cv.wait(lock, [] {return evendone; });//wait till evendone is made true by main thread
	//thread is adding numbers to data
	cout << ++num << endl;
	// Send data back to main()
	odddone = true;
	evendone = false;
	// Manual unlocking is done before notifying, to avoid waking up
	// the waiting thread only to block again
	lock.unlock();
	cv.notify_all();
	}
	}
	void print_even()
	{
	while (num < 100)
	{
	// Wait until main() sends data
	unique_lock<mutex> lock(mu);
	cv.wait(lock, [] {return odddone; });//wait till evendone is made true by main thread
	//thread is adding numbers to data
	cout << ++num << endl;
	// Send data back to main()
	evendone = true;
	odddone = false;
	//unlocking before notifying
	lock.unlock();
	cv.notify_all();
	}
	}
	int main()
	{
	thread t1(print_odd);
	thread t2(print_even);
	t1.join();
	t2.join();
	return 1;
	}

view raw oddevenmultithread.cpp hosted with ❤ by GitHub

Multithreading:5.condition_variable

Many a times we would want a thread to execute some commands based on some conditions. For this we are going to use std:: condition_variable. This class methods such wait, notify which would either make a thread wait or notify other threads. That is exactly the functionality we would need.

To go into code, we would want to understand to basic methods in the class std::condition_variable. One is wait and the other is notify

Wait 
void wait( std::unique_lock<std::mutex>& lock );
lock:an object of type std::unique_lock<std::mutex>, which must be locked by the current thread. Need not be locked till notify

template< class Predicate >
void wait( std::unique_lock<std::mutex>& lock, Predicate pred );
Pred: predicate which returns ​false if the waiting should be continued.

Notify
void notify_all() noexcept;
Unblocks all threads currently waiting for *this.

In the below code we want the main thread to print abcdef and the thread t1 to print 123456.
For this to happen, we want the main thread to start printing the alphabets and t1 to wait till the main completes its job. And we need some variable to tell that the main is done with this job, in this case we are using a bool alphadone.

	#include <iostream>
	#include <string>
	#include <thread>
	#include <mutex>
	#include <condition_variable>
	std::mutex mu;
	std::condition_variable cv;
	std::string data;
	bool alphadone = false;
	bool numericdone = false;
	void print_number()
	{
	// Wait until main() sends data
	std::unique_lock<std::mutex> lk(mu);
	cv.wait(lk, [] {return alphadone; });//wait till alphadone is made true by main thread
	//thread is adding numbers to data
	data += " 123456";
	// Send data back to main()
	numericdone = true;
	// Manual unlocking is done before notifying, to avoid waking up
	// the waiting thread only to block again
	lk.unlock();
	cv.notify_one();
	}
	int main()
	{
	std::thread t1(print_number);
	//main is adding alphabets to data
	data = "abcdef";
	// send data to the t1 thread
	{
	//print_number thread will wait till alphadone is made true
	std::lock_guard<std::mutex> lk(mu);
	alphadone = true;
	}
	cv.notify_all();
	// wait for print_number
	{
	std::unique_lock<std::mutex> lk(mu);
	cv.wait(lk, [] {return numericdone; }); //wait for numericdone to be made true
	}
	std::cout << data << '\n';
	t1.join();
	return 1;
	}

view raw conditional_variable.cpp hosted with ❤ by GitHub

Multithreading:4.Deadlock

Suppose we want to protect our resource doubly and we introduce two mutex to guard the resource.
Here in the below code we are locking m1 first in thread t1 and m2 first in thread t2. Now to lock m2 in thread t1 it will be waiting for t2 to unlock, which never happens. That is a deadlock situation.

	#include<thread>
	#include<mutex>
	#include<iostream>
	using namepspace std;
	void print(const std::string &s)
	{
	cout << s << endl;
	}
	int main() {
	std::mutex m1;
	std::mutex m2;
	std::thread t1([&] {
	print("From T1");
	m1.lock(); //locking m1 first
	print("From T1");
	m2.lock(); //locking m2 second
	});
	std::thread t2([&] {
	print("From T2");
	m2.lock(); //lcoking m2 first
	print("From T2");
	m1.lock(); //locking m1 second
	});
	t1.join();
	t2.join();
	}

view raw deadlock.cpp hosted with ❤ by GitHub

To avoid this situation

• Prefer locking single mutex at a time 
• Avoid locking a mutex and then calling a user provided function, because the user provided function might crash and we may never be able to unlock it. 
• Use std::lock() to lock more than one mutex. 
• Lock the mutex in same order.

Multithreading: 3.Mutex

When we execute the below code. The output would appear random. We are trying to print 1 to 9 from main and 10 to 19 from the thread.

	#include<thread>
	#include<iostream>
	using namespace std;
	void print()
	{
	//printing frm thread
	for (int i = 10; i < 20; i++)
	{
	cout <<"thread"<< i << endl;
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	for (int i = 1; i <10; i++)
	{
	cout << "Main" << i << endl;
	}
	if (t.joinable()) //check if the thread is joinable
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw datarace.cpp hosted with ❤ by GitHub

The output looks like below

threadMain101
threadMain112
threadMain123
threadMain134
threadMain145
threadMain156
threadMain167
threadMain178
threadMain189
thread19

The output looks haphazard and not understandable. This is because both the main thread and the thread t are fighting for the common resource cout. We have to make a change in our code to control the access of cout. meaning if one thread is accessing cout, other thread has to simply wait for access.
We use std::mutex lock and unlock methods to do that.

	void customcout(std::string&str, int i)
	{
	mut.lock();//locks access
	cout << str << i << endl;
	mut.unlock();//releases access
	}
	void print()
	{
	//printing frm thread
	for (int i = 10; i < 20; i++)
	{
	customcout(string("thread:"), i);
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	for (int i = 1; i <10; i++)
	{
	customcout(string("Main:"), i);
	}
	if (t.joinable()) //check if the thread is joinable
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw mutex.cpp hosted with ❤ by GitHub

below is the output after using mutex

thread:10
thread:11
thread:12
thread:13
thread:14
thread:15
thread:16
thread:17
thread:18
thread:19
Main:1
Main:2
Main:3
Main:4
Main:5
Main:6
Main:7
Main:8
Main:9

Multithreading: 2.Join and Joinable

Most of the times the main thread may execute in a shorter period of time than the child threads.
If the main thread completes before the child thread, then the child thread will be orphaned.
The main thread needs to wait for the child thread to complete.
We need to call t1.join() on the thread instance to make the main thread wait till t1 execution is complete.

	#include<thread>
	#include<iostream>
	using namespace std;
	void print()
	{
	for (int i = 1; i <= 10; i++)
	{
	cout << i << endl;
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw jointhread.cpp hosted with ❤ by GitHub

Also we need to check if a thread is joinable (thread with active code of execution), before calling join.

	#include<thread>
	#include<iostream>
	using namespace std;
	void print()
	{
	for (int i = 1; i <= 10; i++)
	{
	cout << i << endl;
	}
	}
	void main()
	{
	thread t(print);//creating a thread instance
	if (t.joinable()) //check if the thread is joinable
	t.join();//main thread waits till child thread completes the task
	cout << "main thread exiting" << endl;
	}

view raw Joinable.cpp hosted with ❤ by GitHub

Multithreading :1.Create thread

We will be using std::thread class to create threads.
std:thread is introduced in C++11.
We can start creating threads by including the thread header file. To create a thread, we need to pass the code that needs to be executed in the constructor of the thread.
As soon as the thread object is created, a new thread is launched, which will execute the code passed to the constructor.


The constructor takes

• a function object
• a function pointer
• a  lambda expression

	#include<thread>
	#include<iostream>
	using namespace std;
	class print_obj {
	public:
	void operator()(int max)
	{
	cout << "Thread with function object" << endl;;
	for (int i = 0; i < max; i++)
	{
	cout << i << endl;
	}
	}
	};
	void main()
	{
	//creating a thread with a function pointer
	thread t1(print, 50);
	//creating a thread with a function object
	thread t2(print_obj(), 100);
	//below is a lambda expression
	auto printlambda = [](int max) {
	cout << "thread with lambda function" << endl;
	for (int i = 0; i < max; i++)
	cout << i << endl;
	};
	//creating a thread with a lambda
	thread t3(printlambda, 150);
	}

view raw createthread.cpp hosted with ❤ by GitHub