Program Listing for File dynamic_array.h

↰ Return to documentation for file (data_structures/dynamic_array.h)

#ifndef DATA_STRUCTURES_DYNAMIC_ARRAY_H
#define DATA_STRUCTURES_DYNAMIC_ARRAY_H

#include <iostream>
#include <stdexcept>

namespace DataStructures {

template <typename T>
class DynamicArray {
public:
        DynamicArray()
        {
                data = new T[init_cap];
                size = 0;
                cap = init_cap;
        }

        DynamicArray(int initial_capacity)
        {
                data = new T[initial_capacity];
                size = 0;
                cap = initial_capacity;
        }

        ~DynamicArray() { delete[] data; }

        void add_last(const T& element)
        {
                if (int(size) == cap) {
                        resize(2 * cap);
                }
                data[size] = element;
                size++;
        }

        void add(int pos_index, const T& element)
        {
                check_position_index(pos_index);
                if (int(size) == cap) {
                        resize(2 * cap);
                }
                for (int i = int(size) - 1; i >= pos_index; i--) {
                        data[i + 1] = data[i];
                }
                data[pos_index] = element;
                size++;
        }

        void add_first(const T& element) { add(0, element); }

        /* Delete functions */
        T del_last()
        {
                if (size == 0) {
                        throw std::out_of_range("The array is empty");
                }
                if (int(size) == cap / 4) {
                        resize(cap / 2);
                }
                T last_element = data[int(size) - 1];
                data[int(size) - 1] = T();
                size--;
                return last_element;
        }

        T del(int index)
        {
                check_element_index(index);
                if (int(size) == cap / 4) {
                        resize(cap / 2);
                }
                T deleted_element = data[index];
                for (int i = index + 1; i < int(size); i++) {
                        data[i - 1] = data[i];
                }
                data[int(size) - 1] = T();
                size--;
                return deleted_element;
        }

        T del_first() { return del(0); }

        /* Get functions */
        T get(int index) const
        {
                check_element_index(index);
                return data[index];
        }

        /* Set functions */
        T set(int index, const T& val)
        {
                check_element_index(index);
                T old_val = data[index];
                data[index] = val;
                return old_val;
        }

        /* Utility functions */
        size_t get_size() const { return size; }

        bool is_empty() const { return size == 0; }

        void resize(int new_cap)
        {
                T* temp = new T[new_cap];
                for (int i = 0; i < int(size); i++) {
                        temp[i] = data[i];
                }
                data = temp;
                cap = new_cap;
        }

        bool is_element_index(int index) const
        {
                return index >= 0 && index < int(size);
        }

        bool is_position_index(int pos_index) const
        {
                return pos_index >= 0 && pos_index <= int(size);
        }

        void check_element_index(int index) const
        {
                if (!is_element_index(index)) {
                        throw std::out_of_range(
                                "Element index is out of bounds");
                }
        }

        void check_position_index(int pos_index) const
        {
                if (!is_position_index(pos_index)) {
                        throw std::out_of_range(
                                "Position index is out of bounds");
                }
        }

        void display()
        {
                std::cout << "Size = " << size << "Capacity = " << cap << '\n';
                for (int i = 0; i < int(size); i++) {
                        std::cout << data[i] << " \n"[i == int(size) - 1];
                }
        }

private:
        T* data = nullptr;
        size_t size = 0;
        int cap = 0;
        static constexpr int init_cap = 1;
};

} // namespace DataStructures

#endif // DATA_STRUCTURES_DYNAMIC_ARRAY_H