operations_on_datastructures Namespace Reference

for std::vector More...

Functions
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.
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.
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.

Detailed Description

for std::vector

for std::priority_queue

For std::vector.

for assert for IO operations

Operations on Data Structures

for assert for IO Operations

Operations on data structures

for std::sort for assert for IO operations

Operations on Data Structures

For assert For IO operations For std::queue

Operations on Data Structures

for std::count for assert for tolower for string operations for IO Operations

Operations on data structures

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

first	A std::vector of sorted integer values
second	A 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

                                                                        {
    std::vector<int32_t> res;         ///< Vector to hold the intersection
    size_t f_index = 0;               ///< Index for the first array
    size_t s_index = 0;               ///< Index for the second array
    size_t f_length = first.size();   ///< Length of first array
    size_t s_length = second.size();  ///< Length of second array
 
    while (f_index < f_length && s_index < s_length) {
        if (first[f_index] < second[s_index]) {
            f_index++;  ///< Increment index of second array
        } else if (first[f_index] > second[s_index]) {
            s_index++;  ///< Increment index of second array
        } else {
            if ((res.size() == 0) || (first[f_index] != res.back())) {
                res.push_back(
                    first[f_index]);  ///< Add the element if it is unique
            }
            f_index++;  ///< Increment index of first array
            s_index++;  ///< Increment index of second array too
        }
    }
    return res;
}

Here is the call graph for this function:

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

first	A std::vector of sorted integer values
second	A 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

                                                                 {
    std::vector<int32_t> res;         ///< Vector to hold the union
    size_t f_index = 0;               ///< Index for the first array
    size_t s_index = 0;               ///< Index for the second array
    size_t f_length = first.size();   ///< Length of first array
    size_t s_length = second.size();  ///< Length of second array
    int32_t next = 0;  ///< Integer to store value of the next element
 
    while (f_index < f_length && s_index < s_length) {
        if (first[f_index] < second[s_index]) {
            next = first[f_index];  ///< Append from first array
            f_index++;              ///< Increment index of second array
        } else if (first[f_index] > second[s_index]) {
            next = second[s_index];  ///< Append from second array
            s_index++;               ///< Increment index of second array
        } else {
            next = first[f_index];  ///< Element is the same in both
            f_index++;              ///< Increment index of first array
            s_index++;              ///< Increment index of second array too
        }
        if ((res.size() == 0) || (next != res.back())) {
            res.push_back(next);  ///< Add the element if it is unique
        }
    }
    while (f_index < f_length) {
        next = first[f_index];  ///< Add remaining elements
        if ((res.size() == 0) || (next != res.back())) {
            res.push_back(next);  ///< Add the element if it is unique
        }
        f_index++;
    }
    while (s_index < s_length) {
        next = second[s_index];  ///< Add remaining elements
        if ((res.size() == 0) || (next != res.back())) {
            res.push_back(next);  ///< Add the element if it is unique
        }
        s_index++;
    }
    return res;
}

Here is the call graph for this function:

print()

void operations_on_datastructures::print

(

const std::vector< int32_t > &

array

)

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

Parameters

array

Reference 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

Print each value in the array

Print newline

Print each value in the array

Print newline

Print each value in the array

Print newline

Print each value in the array

Print newline

                                            {
    for (int32_t i : array) {
        std::cout << i << " ";  /// Print each value in the array
    }
    std::cout << "\n";  /// Print newline
}

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

array	A reference to the input std::vector
shift	The 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

                                              {
    if (array.size() <= shift) {
        return {};  ///< We got an invalid shift, return empty array
    }
    std::vector<int32_t> res(array.size());  ///< Result array
    for (size_t i = shift; i < array.size(); i++) {
        res[i - shift] = array[i];  ///< Add values after the shift index
    }
    for (size_t i = 0; i < shift; i++) {
        res[array.size() - shift + i] =
            array[i];  ///< Add the values from the start
    }
    return res;
}

Here is the call graph for this function:

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

array	A reference to the input std::vector
shift	The 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

                                               {
    if (array.size() <= shift) {
        return {};  ///< We got an invalid shift, return empty array
    }
    std::vector<int32_t> res(array.size());  ///< Result array
    for (size_t i = shift; i < array.size(); i++) {
        res[i] = array[i - shift];  ///< Add values after the shift index
    }
    for (size_t i = 0; i < shift; i++) {
        res[i] =
            array[array.size() - shift + i];  ///< Add the values from the start
    }
    return res;
}

Here is the call graph for this function: