# Data Structures & Algorithms Fall 2023

#### Instructor:
Dr. Umar Suleman ([e-mail])
#### TAs:
- Saad Ahmed ([e-mail])
- Muhammad Zain Faraz ([e-mail])

## Lab 3 - Implementing Smart Pointers

### Submission Format:
A single .zip file labelled `BSCSXXXXX-Lab-3.zip`
Any other source/text files will need to have `BSCSXXXXX-Lab-3` prepended to it.
For example: `BSCSXXXXX-Lab-3-main.cpp`.

<span style="color: red">Note: Make sure you follow the above format correctly! The below structure is to give you an idea of how these classes would work. You are free to add your own functionality/implementation into it as long as they retain the learning purpose.

### Task 1:
Implement a class `unique_ptr`. Unique pointer in C++ is a smart pointer that represents exclusive ownership of a dynamically allocated object. It ensures that there is only one pointer pointing to the object, making it automatically release the memory when it's no longer needed. Unique pointers cannot be copied but can be moved to transfer ownership.

template <class T>
class unique_ptr
{
private:
    T * _ptr;
public:   
    unique_ptr(); // Initializes with null
    unique_ptr(int bytes); // Allocates memeory
    unique_ptr(const unique_ptr<T>&p); // Throws compiler error
    unique_ptr& operator=(const unique_ptr<T>&p); // Throws compiler error
    unique_ptr(const unique_ptr<T>&&p);
    // This would make _ptr point to the memory p was pointing to-
    // p would start pointing to null
    unique_ptr& operator=(const unique_ptr<T>&&p);
    // Deallocates whatever _ptr is pointing to-
    // This would make _ptr point to the memory p was pointing to-
    // _p would start pointing to null
    T* operator->(); // returns _ptr
    T& operator*(); // returns reference to what _ptr is pointing to-
    T& operator[](int index) // returns reference to value at index
    // Also handles illegal memory access
    static unique_ptr& make_unique(); 
    // returns an instance of unique pointer object-
    void reset(); // deletes the memory and points _ptr to null-
    ~unique_ptr() // Deallocates memory
    
    
};

### Task 2:
Implement the `shared_ptr` and `weak_ptr` class. Shared pointer in C++ allows multiple pointers to share ownership of an object, automatically deallocating the object when it's no longer needed, whereas weak pointer does not affect ownership or object lifetime but is used to prevent circular references between shared pointers and can check the object's existence without extending its lifetime.

template <class T>
class memory{
    private:
    int reference_count;
    
    // You can implement the below attributes as you like
    vector<shared_ptr<T>*> shared_memory;
    vector<weak_ptr<T>*> weak_memory;
    
    public:
    void assign(shared_ptr<T>*& _shared)
    // Assign the shared_ptr to the memory block
    // Increment the count by 1
    void free(shared_ptr<T>*& _shared)
    // Free the shared_ptr from the memory block
    // Decrement the count by 1
    void assign(weak_ptr<T>*& _weak)
    // Assign the weak_ptr to the memory block
    void free(weak_ptr<T>*& _weak)
    // Free the weak_ptr from the memory block
    void free()
    // Free all the shared/weak pointers and point them to nullptr
    int count()
    // Returns reference count
}

template <class T>
class shared_ptr{
private:
    T* _ptr;
    memory<T>* block;
    
public:
    shared_ptr(); //Initializes null pointer-
    shared_ptr(int bytes); // Allocates memory and block-
    shared_ptr(const shared_ptr<T>&p);
    // Copies contents of p into our object(this)-
    // Assign our object to memory block-
    
    shared_ptr& operator=(const shared_ptr<T>&p);
    // Free our object from it's memory block
    // If the count becomes 0, free and delete that memory block-
    // Copies contents of p into our object(this)-
    // Assign our object to memory block of p-
    * operator->(); // returns _ptr
    T& operator*(); // returns reference to what _ptr is pointing to-
     T& operator[](int index) // returns reference to value at index
    // Also handles illegal memory access
    static shared_ptr& make_shared(); 
    // returns an instance of shared pointer object-
    void reset(); // Free the memory block
    ~shared_ptr();
    // Free the object from it's memory block-
    // If the count becomes 0, free and delete that memory block-
    friend class weak_ptr;
}

template <class T>
class weak_ptr{
private:
    T* _ptr;
    memory<T>* block;
    
public:
    weak_ptr(const shared_ptr<T>&p);
    // Copies contents of p into our object(this)-
    // Assign our object to memory block
    
    weak_ptr& operator=(const shared_ptr<T>&p);
    // Copies contents of p into our object(this)-
    // Assign our object to memory block
    
    * operator->(); // returns _ptr
    T& operator*(); // returns reference to what _ptr is pointing to-
    T& operator[](int index) // returns reference to value at index
    // Also handles illegal memory access
}

**Note:** There's a fourth type of smart pointer called auto_pointer. They are not part of this lab but do look them up!

#### Bonus Part:
Since now you have your own memory block and objects pointing to them, use this to tackle fragmentation in your heap class. Good Luck-