TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
tests Namespace Reference

Testcases to check Union of Two Arrays. More...

Classes

class  CircularLinkedList
 A class that implements a Circular Linked List. More...
 
struct  Node
 A Node struct that represents a single Node in a Binary Tree. More...
 

Functions

void test1 ()
 A Test to check an simple case.
 
void test2 ()
 A Test to check an empty vector.
 
void test3 ()
 A Test to check an invalid shift value.
 
void test4 ()
 A Test to check a very large input.
 
void test5 ()
 A Test to check a shift of zero.
 
void test6 ()
 A Test to check correct functionality with an array sorted using std::sort.
 
void print (const std::vector< int32_t > &array)
 Prints the values of a vector sequentially, ending with a newline character.
 
std::vector< int32_t > shift_left (const std::vector< int32_t > &array, size_t shift)
 Shifts the given vector to the left by the shift amount and returns a new vector with the result. The original vector is not mutated.
 
void print (const std::vector< int32_t > &array)
 Prints the values of a vector sequentially, ending with a newline character.
 
std::vector< int32_t > shift_right (const std::vector< int32_t > &array, size_t shift)
 Shifts the given vector to the right by the shift amount and returns a new vector with the result. The original vector is not mutated.
 
std::vector< int32_t > get_intersection (const std::vector< int32_t > &first, const std::vector< int32_t > &second)
 Gets the intersection of two sorted arrays, and returns them in a vector.
 
void print (const std::vector< int32_t > &array)
 Prints the values of a vector sequentially, ending with a newline character.
 
std::vector< int32_t > get_union (const std::vector< int32_t > &first, const std::vector< int32_t > &second)
 Gets the union of two sorted arrays, and returns them in a vector.
 
void print (const std::vector< int32_t > &array)
 Prints the values of a vector sequentially, ending with a newline character.
 

Detailed Description

Testcases to check Union of Two Arrays.

Testcases to check Reversal of Binary Tree.

Testcases to check intersection of Two Arrays.

Testcases to check Circular Linked List.

Function Documentation

◆ get_intersection()

std::vector< int32_t > operations_on_datastructures::get_intersection ( const std::vector< int32_t > & first,
const std::vector< int32_t > & second )

Gets the intersection of two sorted arrays, and returns them in a vector.

An algorithm is used that compares the elements of the two vectors, incrementing the index of the smaller of the two. If the elements are the same, the element is appended to the result array to be returned.

Parameters
firstA std::vector of sorted integer values
secondA std::vector of sorted integer values
Returns
A std::vector of the intersection of the two arrays, in ascending order

< Vector to hold the intersection

< Index for the first array

< Index for the second array

< Length of first array

< Length of second array

< Increment index of second array

< Increment index of second array

< Add the element if it is unique

< Increment index of first array

< Increment index of second array too

Definition at line 49 of file intersection_of_two_arrays.cpp.

50 {
51 std::vector<int32_t> res;
52 size_t f_index = 0;
53 size_t s_index = 0;
54 size_t f_length = first.size();
55 size_t s_length = second.size();
56
57 while (f_index < f_length && s_index < s_length) {
58 if (first[f_index] < second[s_index]) {
59 f_index++;
60 } else if (first[f_index] > second[s_index]) {
61 s_index++;
62 } else {
63 if ((res.size() == 0) || (first[f_index] != res.back())) {
64 res.push_back(
65 first[f_index]);
66 }
67 f_index++;
68 s_index++;
69 }
70 }
71 return res;
72}

◆ get_union()

std::vector< int32_t > operations_on_datastructures::get_union ( const std::vector< int32_t > & first,
const std::vector< int32_t > & second )

Gets the union of two sorted arrays, and returns them in a vector.

An algorithm is used that compares the elements of the two vectors, appending the one that has a lower value, and incrementing the index for that array. If one of the arrays reaches its end, all the elements of the other are appended to the resultant vector.

Parameters
firstA std::vector of sorted integer values
secondA std::vector of sorted integer values
Returns
A std::vector of the union of the two arrays, in ascending order

< Vector to hold the union

< Index for the first array

< Index for the second array

< Length of first array

< Length of second array

< Integer to store value of the next element

< Append from first array

< Increment index of second array

< Append from second array

< Increment index of second array

< Element is the same in both

< Increment index of first array

< Increment index of second array too

< Add the element if it is unique

< Add remaining elements

< Add the element if it is unique

< Add remaining elements

< Add the element if it is unique

Definition at line 49 of file union_of_two_arrays.cpp.

50 {
51 std::vector<int32_t> res;
52 size_t f_index = 0;
53 size_t s_index = 0;
54 size_t f_length = first.size();
55 size_t s_length = second.size();
56 int32_t next = 0;
57
58 while (f_index < f_length && s_index < s_length) {
59 if (first[f_index] < second[s_index]) {
60 next = first[f_index];
61 f_index++;
62 } else if (first[f_index] > second[s_index]) {
63 next = second[s_index];
64 s_index++;
65 } else {
66 next = first[f_index];
67 f_index++;
68 s_index++;
69 }
70 if ((res.size() == 0) || (next != res.back())) {
71 res.push_back(next);
72 }
73 }
74 while (f_index < f_length) {
75 next = first[f_index];
76 if ((res.size() == 0) || (next != res.back())) {
77 res.push_back(next);
78 }
79 f_index++;
80 }
81 while (s_index < s_length) {
82 next = second[s_index];
83 if ((res.size() == 0) || (next != res.back())) {
84 res.push_back(next);
85 }
86 s_index++;
87 }
88 return res;
89}

◆ print() [1/4]

void operations_on_datastructures::print ( const std::vector< int32_t > & array)

Prints the values of a vector sequentially, ending with a newline character.

Parameters
arrayReference to the array to be printed
Returns
void

Print each value in the array

Print newline

Print each value in the array

Print newline

Print each value in the array

Print newline

Definition at line 29 of file array_left_rotation.cpp.

29 {
30 for (int32_t i : array) {
31 std::cout << i << " ";
32 }
33 std::cout << "\n";
34}

◆ print() [2/4]

void operations_on_datastructures::print ( const std::vector< int32_t > & array)

Prints the values of a vector sequentially, ending with a newline character.

Parameters
arrayReference to the array to be printed
Returns
void

Print each value in the array

Print newline

Print each value in the array

Print newline

Print each value in the array

Print newline

Definition at line 29 of file array_left_rotation.cpp.

29 {
30 for (int32_t i : array) {
31 std::cout << i << " ";
32 }
33 std::cout << "\n";
34}

◆ print() [3/4]

void operations_on_datastructures::print ( const std::vector< int32_t > & array)

Prints the values of a vector sequentially, ending with a newline character.

Parameters
arrayReference to the array to be printed
Returns
void

Print each value in the array

Print newline

Print each value in the array

Print newline

Print each value in the array

Print newline

Definition at line 29 of file array_left_rotation.cpp.

29 {
30 for (int32_t i : array) {
31 std::cout << i << " ";
32 }
33 std::cout << "\n";
34}

◆ print() [4/4]

void operations_on_datastructures::print ( const std::vector< int32_t > & array)

Prints the values of a vector sequentially, ending with a newline character.

Parameters
arrayReference to the array to be printed
Returns
void

Print each value in the array

Print newline

Print each value in the array

Print newline

Print each value in the array

Print newline

Definition at line 29 of file array_left_rotation.cpp.

29 {
30 for (int32_t i : array) {
31 std::cout << i << " ";
32 }
33 std::cout << "\n";
34}

◆ shift_left()

std::vector< int32_t > operations_on_datastructures::shift_left ( const std::vector< int32_t > & array,
size_t shift )

Shifts the given vector to the left by the shift amount and returns a new vector with the result. The original vector is not mutated.

Shifts the values of the vector, by creating a new vector and adding values from the shift index to the end, then appending the rest of the elements from the start of the vector.

Parameters
arrayA reference to the input std::vector
shiftThe amount to be shifted to the left
Returns
A std::vector with the shifted values

< We got an invalid shift, return empty array

< Result array

< Add values after the shift index

< Add the values from the start

Definition at line 46 of file array_left_rotation.cpp.

47 {
48 if (array.size() <= shift) {
49 return {};
50 }
51 std::vector<int32_t> res(array.size());
52 for (size_t i = shift; i < array.size(); i++) {
53 res[i - shift] = array[i];
54 }
55 for (size_t i = 0; i < shift; i++) {
56 res[array.size() - shift + i] =
57 array[i];
58 }
59 return res;
60}

◆ shift_right()

std::vector< int32_t > operations_on_datastructures::shift_right ( const std::vector< int32_t > & array,
size_t shift )

Shifts the given vector to the right by the shift amount and returns a new vector with the result. The original vector is not mutated.

Shifts the values of the vector, by creating a new vector and adding values from the shift index to the end, then appending the rest of the elements to the start of the vector.

Parameters
arrayA reference to the input std::vector
shiftThe amount to be shifted to the right
Returns
A std::vector with the shifted values

< We got an invalid shift, return empty array

< Result array

< Add values after the shift index

< Add the values from the start

Definition at line 47 of file array_right_rotation.cpp.

48 {
49 if (array.size() <= shift) {
50 return {};
51 }
52 std::vector<int32_t> res(array.size());
53 for (size_t i = shift; i < array.size(); i++) {
54 res[i] = array[i - shift];
55 }
56 for (size_t i = 0; i < shift; i++) {
57 res[i] =
58 array[array.size() - shift + i];
59 }
60 return res;
61}

◆ test1()

void tests::test1 ( )

A Test to check an simple case.

< Use the BinaryTree

A Test to check an edge case (two empty arrays)

A Test to check a single value.

Returns
void

A Test to check an edge case (single element reversal)

< Should print 3 4 5 1 2

< Should print 4 5 1 2 3

< Check if result is empty

< Should only print newline

< Check for equal sizes

< Ensure that there is only one element

< Check if both elements are same

< Check if result is empty

< Should only print newline

Definition at line 75 of file array_left_rotation.cpp.

75 {
76 std::cout << "TEST CASE 1\n";
77 std::cout << "Initialized arr = {1, 2, 3, 4, 5}\n";
78 std::cout << "Expected result: {3, 4, 5, 1, 2}\n";
79 std::vector<int32_t> arr = {1, 2, 3, 4, 5};
80 std::vector<int32_t> res = shift_left(arr, 2);
81 std::vector<int32_t> expected = {3, 4, 5, 1, 2};
82 assert(res == expected);
83 print(res);
84 std::cout << "TEST PASSED!\n\n";
85}
void print(const std::vector< int32_t > &array)
Prints the values of a vector sequentially, ending with a newline character.
std::vector< int32_t > shift_left(const std::vector< int32_t > &array, size_t shift)
Shifts the given vector to the left by the shift amount and returns a new vector with the result....

◆ test2()

void tests::test2 ( )

A Test to check an empty vector.

A Test to check an edge case (NULL root element)

A Test to check an edge case (one empty array)

A Test to check a few values.

Returns
void

< Should print empty newline

< Check if result is equal to a

< Should only print newline

< Check for equal sizes

< Ensure that there is only one element

< Check if result is equal to b

< Should print 2 3

Definition at line 90 of file array_left_rotation.cpp.

90 {
91 std::cout << "TEST CASE 2\n";
92 std::cout << "Initialized arr = {}\n";
93 std::cout << "Expected result: {}\n";
94 std::vector<int32_t> arr = {};
95 std::vector<int32_t> res = shift_left(arr, 2);
96 std::vector<int32_t> expected = {};
97 assert(res == expected);
98 print(res);
99 std::cout << "TEST PASSED!\n\n";
100}

◆ test3()

void tests::test3 ( )

A Test to check an invalid shift value.

A Test to check correct reversal of a Binary Tree.

A Test to check correct functionality with a simple test case.

A Test to check an input array.

Returns
void

< 7 > 5

< Should print empty newline

< 7 > 5

< Should print empty newline

< Check if result is correct

< Should print 6

< Check for equality

< Check for equality

< Check if result is correct

< Should print 2 3 4 6

Definition at line 105 of file array_left_rotation.cpp.

105 {
106 std::cout << "TEST CASE 3\n";
107 std::cout << "Initialized arr = {1, 2, 3, 4, 5}\n";
108 std::cout << "Expected result: {}\n";
109 std::vector<int32_t> arr = {1, 2, 3, 4, 5};
110 std::vector<int32_t> res = shift_left(arr, 7);
111 std::vector<int32_t> expected = {};
112 assert(res == expected);
113 print(res);
114 std::cout << "TEST PASSED!\n\n";
115}

◆ test4()

void tests::test4 ( )

A Test to check a very large input.

A Test to check correct functionality with duplicate values.

A Test to check using a specific Node as the starting point.

Returns
void

< Should print {4, 6, ..., 420, 2}

< Should print {420, 2, 4, ..., 418}

< Node we will start printing from

< Check if result is correct

< Should print 4 6

< Check if result is correct

< Should print 2 3 4 6 7

Definition at line 120 of file array_left_rotation.cpp.

120 {
121 std::cout << "TEST CASE 4\n";
122 std::cout << "Initialized arr = {2, 4, ..., 420}\n";
123 std::cout << "Expected result: {4, 6, ..., 420, 2}\n";
124 std::vector<int32_t> arr;
125 for (int i = 1; i <= 210; i++) {
126 arr.push_back(i * 2);
127 }
128 print(arr);
129 std::vector<int32_t> res = shift_left(arr, 1);
130 std::vector<int32_t> expected;
131 for (int i = 1; i < 210; i++) {
132 expected.push_back(arr[i]);
133 }
134 expected.push_back(2);
135 assert(res == expected);
136 print(res);
137 std::cout << "TEST PASSED!\n\n";
138}

◆ test5()

void tests::test5 ( )

A Test to check a shift of zero.

A Test to check correct functionality with a harder test case.

A Test to check an empty list.

Returns
void

< Should print 1 2 3 4 5

< Check if result is correct

< Should print 2 3 4

< Check if result is correct

< Should print 1 2 3 4 5 6 7 9

Definition at line 143 of file array_left_rotation.cpp.

143 {
144 std::cout << "TEST CASE 5\n";
145 std::cout << "Initialized arr = {1, 2, 3, 4, 5}\n";
146 std::cout << "Expected result: {1, 2, 3, 4, 5}\n";
147 std::vector<int32_t> arr = {1, 2, 3, 4, 5};
148 std::vector<int32_t> res = shift_left(arr, 0);
149 assert(res == arr);
150 print(res);
151 std::cout << "TEST PASSED!\n\n";
152}

◆ test6()

void tests::test6 ( )

A Test to check correct functionality with an array sorted using std::sort.

Returns
void

< Sort vector a

< Sort vector b

< Check if result is correct

< Should print 3 7

< Sort vector a

< Sort vector b

< Check if result is correct

< Should print 1 2 3 4 5 6 7 8 9 11

Definition at line 166 of file intersection_of_two_arrays.cpp.

166 {
167 std::cout << "TEST CASE 6\n";
168 std::cout << "Intialized a = {1, 3, 3, 2, 5, 9, 4, 7, 3, 2} ";
169 std::cout << "b = {11, 3, 7, 8, 6}\n";
170 std::cout << "Expected result: {3, 7}\n";
171 std::vector<int32_t> a = {1, 3, 3, 2, 5, 9, 4, 7, 3, 2};
172 std::vector<int32_t> b = {11, 3, 7, 8, 6};
173 std::sort(a.begin(), a.end());
174 std::sort(b.begin(), b.end());
175 std::vector<int32_t> result = get_intersection(a, b);
176 std::vector<int32_t> expected = {3, 7};
177 assert(result == expected);
178 print(result);
179 std::cout << "TEST PASSED!\n\n";
180}
uint64_t result(uint64_t n)
std::vector< int32_t > get_intersection(const std::vector< int32_t > &first, const std::vector< int32_t > &second)
Gets the intersection of two sorted arrays, and returns them in a vector.