Chapter 2: Trees, Heaps, and Graphs
Activity 4: Create a Data Structure for a Filesystem
In this activity, we will create a data structure using N-ary tree for a file system. Follow these steps to complete the activity:
- First, let's include the required headers:
#include <iostream>
#include <vector>
#include <algorithm>
- Now, let's write a node to store the data of a directory/file:
struct n_ary_node
{
std::string name;
bool is_dir;
std::vector<n_ary_node*> children;
};
- Now, let's wrap this node in a tree structure for a good interface, and also add a static member so that we can store the current directory:
struct file_system
{
using node = n_ary_node;
using node_ptr = node*;
private:
node_ptr root;
node_ptr cwd;
- Now, let's add a constructor so that we can create a tree with a root directory:
public:
file_system()
{
root = new node{"/", true, {}};
cwd = root; // We'll keep the current directory as root in the beginning
}
- Now, let's add a function to find the directory/file:
node_ptr find(const std::string& path)
{
if(path[0] == '/') // Absolute path
{
return find_impl(root, path.substr(1));
}
else
{
return find_impl(cwd, path);
}
}
private:
node_ptr find_impl(node_ptr directory, const std::string& path)
{
if(path.empty())
return directory;
auto sep = path.find('/');
std::string current_path = sep == std::string::npos ? path : path.substr(0, sep);
std::string rest_path = sep == std::string::npos ? "" : path.substr(sep + 1);
auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
return child->name == current_path;
});
if(found != directory->children.end())
{
return find_impl(*found, rest_path);
}
return NULL;
}
- Now, let's add a function to add a directory:
public:
bool add(const std::string& path, bool is_dir)
{
if(path[0] == '/')
{
return add_impl(root, path.substr(1), is_dir);
}
else
{
return add_impl(cwd, path, is_dir);
}
}
private:
bool add_impl(node_ptr directory, const std::string& path, bool is_dir)
{
if(not directory->is_dir)
{
std::cout << directory->name << " is a file." << std::endl;
return false;
}
auto sep = path.find('/');
// This is the last part of the path for adding directory. It's a base condition of the recursion
if(sep == std::string::npos)
{
auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
return child->name == path;
});
if(found != directory->children.end())
{
std::cout << "There's already a file/directory named " << path << " inside " << directory->name << "." << std::endl;
return false;
}
directory->children.push_back(new node{path, is_dir, {}});
return true;
}
// If the next segment of the path is still a directory
std::string next_dir = path.substr(0, sep);
auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
return child->name == next_dir && child->is_dir;
});
if(found != directory->children.end())
{
return add_impl(*found, path.substr(sep + 1), is_dir);
}
std::cout << "There's no directory named " << next_dir << " inside " << directory->name << "." << std::endl;
return false;
}
- Now, let's add a function to change the current directory. This will be very simple since we already have a function to find the path:
public:
bool change_dir(const std::string& path)
{
auto found = find(path);
if(found && found->is_dir)
{
cwd = found;
std::cout << "Current working directory changed to " << cwd->name << "." << std::endl;
return true;
}
std::cout << "Path not found." << std::endl;
return false;
}
- Now, let's add a function to print a directory or a file. For a file, we'll just print the name of the file. For a directory, we'll print all of its children's names, just like the ls command in Linux:
public:
void show_path(const std::string& path)
{
auto found = find(path);
if(not found)
{
std::cout << "No such path: " << path << "." << std::endl;
return;
}
if(found->is_dir)
{
for(auto child: found->children)
{
std::cout << (child->is_dir ? "d " : "- ") << child->name << std::endl;}
}
else
{
std::cout << "- " << found->name << std::endl;
}
}
};
- Let's write a main function so that we can use the aforementioned functions:
int main()
{
file_system fs;
fs.add("usr", true); // Add directory usr in "/"
fs.add("etc", true); // Add directory etc in "/"
fs.add("var", true); // Add directory var in "/"
fs.add("tmp_file", false); // Add file tmp_file in "/"
std::cout << "Files/Directories under \"/\"" << std::endl;
fs.show_path("/"); // List files/directories in "/"
std::cout << std::endl;
fs.change_dir("usr");
fs.add("Packt", true);
fs.add("Packt/Downloads", true);
fs.add("Packt/Downloads/newFile.cpp", false);
std::cout << "Let's see the contents of dir usr: " << std::endl;
fs.show_path("usr"); // This will not print the path successfully, since we're already inside the dir usr. And there's no directory named usr inside it.
std::cout << "Let's see the contents of \"/usr\"" << std::endl;
fs.show_path("/usr");
std::cout << "Let's see the contents of \"/usr/Packt/Downloads\"" << std::endl;
fs.show_path("/usr/Packt/Downloads");
}
The output of the preceding code is as follows:
Files/Directories under "/"
d usr
d etc
d var
- tmp_file
Current working directory changed to usr.
Let's try to print the contents of usr:
No such path: usr.
Let's see the contents of "/usr"
d Packt
Contents of "/usr/Packt/Downloads"
- newFile.cpp
Activity 5: K-Way Merge Using Heaps
In this activity, we will merge multiple sorted arrays into a single sorted array. These steps will help you complete the activity:
- Start with the required headers:
#include <iostream>
#include <algorithm>
#include <vector>
- Now, implement the main algorithm for merging. It will take a vector of a vector of int as input and will contain the vector of all the sorted vectors. Then, it will return the merged vector of int. First, let's build the heap node:
struct node
{
int data;
int listPosition;
int dataPosition;
};
std::vector<int> merge(const std::vector<std::vector<int>>& input)
{
auto comparator = [] (const node& left, const node& right)
{
if(left.data == right.data)
return left.listPosition > right.listPosition;
return left.data > right.data;
};
As we can see, the heap node will contain three things – data, the position of the list in the input, and the position of the data item inside that list.
- Let's build the heap. The idea is to have a min heap with the smallest element from all the lists. So, when we pop from the heap, we are guaranteed to get the smallest element. After removing that element, we need to insert the next element from the same list, if it's available:
std::vector<node> heap;
for(int i = 0; i < input.size(); i++)
{
heap.push_back({input[i][0], i, 0});
std::push_heap(heap.begin(), heap.end(), comparator);
}
- Now, we'll build the resultant vector. We'll simply remove the elements from the heap until it is empty and replace it with the next element from the same list it belongs to, if available:
std::vector<int> result;
while(!heap.empty())
{
std::pop_heap(heap.begin(), heap.end(), comparator);
auto min = heap.back();
heap.pop_back();
result.push_back(min.data);
int nextIndex = min.dataPosition + 1;
if(nextIndex < input[min.listPosition].size())
{
heap.push_back({input[min.listPosition][nextIndex], min.listPosition, nextIndex});
std::push_heap(heap.begin(), heap.end(), comparator);
}
}
return result;
}
- Let's write a main function so that we can use the preceding function:
int main()
{
std::vector<int> v1 = {1, 3, 8, 15, 105};
std::vector<int> v2 = {2, 3, 10, 11, 16, 20, 25};
std::vector<int> v3 = {-2, 100, 1000};
std::vector<int> v4 = {-1, 0, 14, 18};
auto result = merge({v1, v2, v3, v4});
for(auto i: result)
std::cout << i << ' ';
return 0;
}
You should see the following output:
-2 -1 0 1 2 3 3 8 10 11 14 15 16 18 20 25 100 105 1000