In this assignment, you will implement the Disjoint Set data structure with both the merge-by-rank and path-compression optimizations. You’ll work from the following class:
#pragma once
/*
* disjoint_set.hpp
*/
#include <cassert>
#include <vector>
/* not_implemented
Thrown by functions/methods you haven't written yet, this exception signals
to the test runner to skip any tests involving the relevant functions/
methods. When you write a function/method, delete the
throw not_implemented{};
from it.
*/
struct not_implemented { };
class disjoint_set {
struct node {
int index; // Set index
node* parent; // Parent set (nullptr for roots)
int rank = 0;
};
public:
/* djsoint_set(n)
Constructs a disjoint_set object with (initially) n disjoint sets.
*/
disjoint_set(int elem_count)
{
// Your code here
}
/* ~disjoint_set()
Destructor.
*/
~disjoint_set()
{
// Your code here
}
/* disjoint_set d = c;
Copy constructor.
*/
disjoint_set(const disjoint_set& original)
{
// Your code here
}
/* d = c;
Copy-assignment operator.
*/
disjoint_set& operator= (const disjoint_set& original)
{
// Your code here
return *this;
}
/* elem_count()
Returns the total number of elements, as set in the constructor. This
does not change over the lifetime of the `disjoint_set`.
Must run in O(1) time.
*/
int elem_count() const
{
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* set_count()
Returns the number of disjoint sets that *currently* exist. Initially,
this will be the same as `size()`, but it shrinks each time sets are
merged (eventually to a minimum of 1, if all sets are merged). This is
essentially the number of nodes whose `parent == -1`.
Note that the return value from this can never be less than 1 (when all
sets have been merged together) or greater than the original `elem_count`
(if no sets have been merged).
Must run in O(N) time where N = `elem_count()`, but there is an
optimization which can make this run in O(1) time...
*/
int set_count() const
{
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* singleton()
Returns true if all elements are in the same set (i.e., if
`set_count() == 1`).
*/
bool singleton() const
{
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* rep(n)
Returns the "representative" for set n. n must be ≥ 0 and < `elem_count()`.
This should perform path compression.
Must run in O(N) time where N is the depth of set n within its tree.
(The amortized runtime will be O(α(N)) which is essentially O(1).) Must
run in O(1) space.
*/
int rep(int n)
{
assert(n >= 0 and n < elem_count());
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* rep(n) const
The const version of `rep(n)` still returns the representative for n, but
does NOT do path compression (because, being const, it's not allowed to
modify the data members).
*/
int rep(int n) const
{
assert(n >= 0 and n < elem_count());
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* in_same_set(a,b)
Returns true if a and b are in the same set. Note that a and b are
not necessarily the roots of their sets!
Must run in O(M + N) time, where M and N are the sizes of the sets
containing a and b, respectively.
*/
bool in_same_set(int a, int b)
{
assert(a >= 0 and a < elem_count());
assert(b >= 0 and b < elem_count());
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* merge(a,b)
Merge sets a and b (both must be ≥ 0 and < `size()`). If `a` and `b` are
already in the same set this should do nothing (but may perform path
compression).
This should perform the merge-by-rank optimization.
Returns true if two sets were merged, and false if not (i.e., if a and
b were already in the same set).
Must run in O(M + N) time, where M is the size of a's set and N is the
size of b's set. (The amortized runtime will be O(α(N)) which is
essentially O(1).) Must run in O(1) space.
*/
bool merge(int a, int b)
{
assert(a >= 0 and a < elem_count());
assert(b >= 0 and b < elem_count());
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
/* elements(n)
Returns the vector of elements that are in the same set as n. Note that
n is not necessarily the root of its set!
Must run in O(N²) time (where N == elem_count()).
*/
std::vector<int> elements(int n)
{
assert(n >= 0 and n < elem_count());
// Your code here; delete the following line when you're ready to test.
throw not_implemented{};
}
private:
// Array of nodes; initialize in your constructor
node** forest = nullptr;
// Total number of elements. This should be set in your constructor and then
// never changed after that.
int total_elems = -1;
// This class is defined in the test file; it's a friend so that it can
// access the private members of `disjoint_set` for easier testing.
friend class disjoint_set_tester;
};
(Note that the node**
in the private section is not as scary as it looks: it
is an array of node*
s. You’ll first dynamically allocate an array
(new node*[ ... ]
) and then dynamically allocate each element (new node{ ... }
).)
You can download a copy of this file as disjoint_set.hpp
or find it on the server in /usr/local/class/src/disjoint_set.hpp
. You can
either write all your implementations within the .hpp
, or you can use a
separate .cpp
for the implementations; if you use a separate .cpp
, don’t
forget to link with it when you compile the test runner. You can
download the test runner here or find it on the server
in /usr/local/class/src/assign6_test.cpp
.
Note that you must correctly implement the “Big Three” (destructor, copy constructor, copy-assignment operator) in order for your submission to pass. Submissions that leak memory or are not correctly copied will be considered as failing.
Testing and submission
A test file is available for download as assign6_test.cpp,
or on the server as /usr/local/class/src/assign6_test.cpp
. This file includes
the above disjoint_set.hpp
. Run
./assign6_test
to run the automated tests, or on the server, run
test-assignment
to automatically compile the tests and run them.