0001

#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>

#include <algorithm>

// -----------------------------------------------------------------------------------------------
// Definition of simple dynamic array class
template <typename T>
class DynamicArray {
    // The Dynamic Array has an initial capacity. 
    // If more elements will be added, there will be a reallocation with double capacity
    static constexpr unsigned int InitialCapacity{ 8 };

    // Internal data ------------------------------------------------------------------------------
    T* data{};                                 // Dynamic Storage for Data
    unsigned int numberOfElements{};           // Number of elements currently in the container
    unsigned int capacity{ InitialCapacity };  // Current maximum capacity of the container
public:
    // Construction and Destruction ---------------------------------------------------------------
    DynamicArray();                            // Default constructor. Allocate new memory
    DynamicArray(const unsigned int size);     // Constructor for a given size. Allocate new memory
    DynamicArray(const DynamicArray& other);   // Copy constructor. Make a deep copy
    // Special constructors
    template <class Iterator> DynamicArray(Iterator begin, Iterator end);   // Initialize from range   
    template <int N> DynamicArray(const T(&other)[N]);                      // Initialize from C_Sytle array,e.g. a string literal
    template <int N> DynamicArray(T(&other)[N]);
    DynamicArray(const std::initializer_list<T>& list);                     // Take data from initializer list

    ~DynamicArray();                            // Destructor: Release previously allocated memory

    // Housekeeping ---------------------------------------------------------------
    bool empty() const;                         // Do we have elements in the container? Do not mix up with capacity
    void clear();                               // Clear will not delete anything. Just set element count to 0
    unsigned int size() const;                  // How many elements are in the container

    // Main working functions
    void push_back(const T& d);                 // Add a new element at the end

    // Operators for class------------------------ ---------------------------------------------------------------

    T operator[] (const unsigned int i) const;  // Index operator, get data at given index. No boundary check
    T& operator[] (const unsigned int i);       // Index operator, get data at given index. No boundary check
    DynamicArray& operator=(const DynamicArray& other); // Assignment


    // Add iterator properties to class ---------------------------------------------------------------
    class iterator {                           // Local class for iterator
        T* iter{};                             // This will be the iterator 
        T* begin{};                            // For boundary check
        T* end{};                              // For boundary check

    public:                                    // Define alias names necessary for the iterator functionality
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;

        // Constructor
        iterator(T* const i, T* const b, T* const e);          

        // Dereferencing
        reference operator *() const;
        pointer operator ->() const;

        // Aithmetic operations
        iterator& operator ++();
        iterator& operator --();
        iterator operator ++(int);
        iterator operator --(int);
        iterator operator +(const difference_type& n) const;
        iterator& operator +=(const difference_type& n);
        iterator operator -(const difference_type& n) const;
        iterator& operator -=(const difference_type& n);

        // Comparison
        bool operator != (const iterator& other) const;
        bool operator == (const iterator& other) const;
        bool operator < (const iterator& other) const;
        bool operator > (const iterator& other) const;
        bool operator <= (const iterator& other) const;
        bool operator >= (const iterator& other) const;
        
        // Reference and difference
        reference operator[] (const difference_type& n);
        difference_type operator-(const iterator& other) const;
    };

    // Begin and end function to initialize an iterator
    iterator begin() const;
    iterator end() const;

    // Working functions dealing with iterators. More may be added
    iterator erase(iterator pos);

};


// Definition part. Should be in a CPP file
// Default constructor. Allocate new memory
template <typename T>
inline DynamicArray<T>::DynamicArray() { 
    data = new T[capacity]; 
} 
// Constructor for certain size. Allocate new memory
template <typename T>
inline DynamicArray<T>::DynamicArray(const unsigned int size) : data(new T[size]), numberOfElements(0), capacity(size) {
} 

// Copy constructor
template <typename T>
DynamicArray<T>::DynamicArray(const DynamicArray& other) {  // Copy constructor. Make a deep copy
    capacity = numberOfElements = other.numberOfElements;
    data = new T[capacity];                // Get memory, same size as other container
    for (size_t k = 0; k < other.numberOfElements; ++k)
        data[k] = other.data[k];           // Copy data
}

// Range constructor
template <typename T>
template <class Iterator>
DynamicArray<T>::DynamicArray(Iterator begin, Iterator end) {
    data = new T[capacity];
    for (Iterator i = begin; i != end; ++i)
        push_back(*i);
}

// Construct from a const C-Style Array, like for example "Hello"
template <typename T>
template <int N>
DynamicArray<T>::DynamicArray(const T(&other)[N]) {
    capacity = numberOfElements = N;
    data = new T[capacity];                // Get memory, same size as other container
    for (size_t k = 0; k < N; ++k)
        data[k] = other[k];          // Copy data
}
// Construct from a C-Style Array
template <typename T>
template <int N>
DynamicArray<T>::DynamicArray(T(&other)[N]) {
    capacity = numberOfElements = N;
    data = new T[capacity];                // Get memory, same size as other container
    for (size_t k = 0; k < N; ++k)
        data[k] = other[k];          // Copy data
}

// Construct from an initilizer list
template <typename T>
DynamicArray<T>::DynamicArray(const std::initializer_list<T>& list) { 
    data = new T[capacity]; 
    for (const T& t : list) push_back(t); 
}

// Destructor will release the dynamic allocated memory
template <typename T>
inline DynamicArray<T>::~DynamicArray() { 
    delete[] data; 
}         // Destructor: Release previously allocated memory

// Some houskeeping functions
template <typename T>
inline bool DynamicArray<T>::empty() const {
    return numberOfElements == 0; 
}
template <typename T>
inline void DynamicArray<T>::clear() {
    numberOfElements = 0; 
};    // Clear will not delete anything. Just set element count to 0

template <typename T>
inline unsigned int DynamicArray<T>::size() const {
    return numberOfElements; 
} // How many elements are in the container

// Main workhorse for a dynamic array. 
// Store element, and alwaysprovide enough memory
template <typename T>
void DynamicArray<T>::push_back(const T& d) {               // Add a new element at the end
    if (numberOfElements >= capacity) {                     // Check, if capacity of this dynamic array is big enough
        capacity *= 2;                                      // Obviously not, we will double the capacity
        T* temp = new T[capacity];                          // Allocate new and more memory
        for (unsigned int k = 0; k < numberOfElements; ++k)
            temp[k] = data[k];                              // Copy data from old memory to new memory
        delete[] data;                                      // Release old memory
        data = temp;                                        // And assign newly allocated memory to old pointer
    }
    data[numberOfElements++] = d;                           // And finally, store the given data at the end of the container
}

// Operators for class ------------------------ ---------------------------------------------------------------
template <typename T>
inline typename T DynamicArray<T>::operator[] (const unsigned int i) const {
    return data[i]; 
}      // Index operator, get data at given index. No boundary check

template <typename T>
inline typename T& DynamicArray<T>::operator[] (const unsigned int i) {
    return data[i]; 
}  // Index operator, get data at given index. No boundary check

// Assignement operator. Make a deep copy
template <typename T>
DynamicArray<T>& DynamicArray<T>::operator=(const DynamicArray& other) {         
    if (this != &other) {                                    // Prevent self-assignment
        delete[] data;                                       // Release any previosly existing memory
        capacity = numberOfElements = other.numberOfElements;// Take over capacity and number of elements from other container
        data = new T[capacity];                              // Get new memory, depending on size of other 
        for (unsigned int k = 0; k < numberOfElements; ++k)  // Copy other data
            data[k] = other.data[k];
    }
    return *this;
}

// Implementation of iterator functions ---------------------------------------------------------------------
// COnstruction 
template <typename T>
inline DynamicArray<T>::iterator::iterator(T* const i, T* const b, T* const e) : iter(i), begin(b), end(e) {
};  // Constructor for the iterator

// Dereferencing
template <typename T>
inline typename DynamicArray<T>::iterator::reference DynamicArray<T>::iterator::operator *() const {
    return *iter; 
} 

template <typename T>
inline typename DynamicArray<T>::iterator::pointer DynamicArray<T>::iterator::operator ->() const {
    return iter; 
}

// Arithmetic operations
template <typename T>
inline typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator ++() {
    if (iter < end) 
        ++iter; 
    return *this; 
} 

template <typename T>
inline typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator --() {
    if (iter > begin) 
        --iter; 
    return *this; 
} 

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator ++(int) {
    DynamicArray<T>::iterator tmp = *this;  
    if (this->iter < end) 
        ++(*this); 
    return tmp; 
} 

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator --(int) {
    DynamicArray<T>::iterator tmp = *this; 
    if (this->iter > begin) 
        --(*this); 
    return tmp; 
} 

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator +(const DynamicArray<T>::iterator::difference_type& n) const {
    DynamicArray<T>::iterator tmp = *this; 
    DynamicArray<T>::iterator::difference_type k{ n }; 
    while (k--) 
        ++tmp.iter; 
    return tmp; 
}

template <typename T>
typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator +=(const DynamicArray<T>::iterator::difference_type& n) {
    DynamicArray<T>::iterator::difference_type k{ n };  
    while (k--) 
        ++iter; 
    return *this; 
}

template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::iterator::operator- (const DynamicArray<T>::iterator::difference_type& n) const {
    DynamicArray<T>::iterator tmp = *this;
    DynamicArray<T>::iterator::difference_type k{ n };  
    while (k--)  
        --tmp.iter; 
    return tmp; 
}

template <typename T>
typename DynamicArray<T>::iterator& DynamicArray<T>::iterator::operator -=(const typename DynamicArray<T>::iterator::difference_type& n) {
    DynamicArray<T>::iterator::difference_type k{ n };  
    while (k--) 
        --iter;  
    return *this; 
}

// Comparison functions
template <typename T>
inline typename DynamicArray<T>::iterator::reference DynamicArray<T>::iterator::operator[] (const typename DynamicArray<T>::iterator::difference_type& n) {
    return *(iter + n); 
};

template <typename T>
inline bool DynamicArray<T>::iterator::operator != (const iterator& other) const {
    return iter != other.iter; 
}  

template <typename T>
inline bool DynamicArray<T>::iterator::operator == (const iterator& other) const {
    return iter == other.iter; 
}  

template <typename T>
inline bool DynamicArray<T>::iterator::operator < (const iterator& other) const {
    return iter < other.iter; 
}  
template <typename T>
inline bool DynamicArray<T>::iterator::operator > (const iterator& other) const {
    return iter > other.iter; 
}  // Comparison

template <typename T>
inline bool DynamicArray<T>::iterator::operator <= (const iterator& other) const {
    return iter <= other.iter; 
}  // Comparison

template <typename T>
inline bool DynamicArray<T>::iterator::operator >= (const iterator& other) const {
    return iter >= other.iter; 
}  // Comparison

// Delta 
template <typename T>
inline typename DynamicArray<T>::iterator::difference_type DynamicArray<T>::iterator::operator-(const typename DynamicArray<T>::iterator& other) const {
    return iter - other.iter; 
}

// ------------------------------------------------------------------------
// Get iterators for dynamic array
template <typename T>
inline typename DynamicArray<T>::iterator DynamicArray<T>::begin() const {
    return iterator(data, data, data + numberOfElements); 
}

template <typename T>
inline typename DynamicArray<T>::iterator DynamicArray<T>::end() const {
    return iterator(data + numberOfElements, data, data + numberOfElements); 
}

// ------------------------------------------------------------------------
// Any other functions for dynamic array
template <typename T>
typename DynamicArray<T>::iterator DynamicArray<T>::erase(typename DynamicArray<T>::iterator pos) {
    iterator result{ pos };
    if (pos != end()) {
        while (pos != end()) {
            *pos = *(pos + 1);
            ++pos;
        }
        ++result;
        --numberOfElements;
    }
    return result;
}

// --------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------

// Using the dynamic array as a String, by using char as the content
using String = DynamicArray<char>;

// SOme overloads for operators for easier handlinf
std::istream& operator >> (std::istream& is, String& s) {
    s.clear();
    char c{};
    is >> std::ws;
    while (is.peek() != EOF and is.get(c) and not isspace(c)) {
        s.push_back(c);
    }
    if (not s.empty()) s.push_back(0);
    return is;
}
std::ostream& operator << (std::ostream& os, const String& s) {
    std::ostringstream oss;
    for (char c : s)  if (c!='\0') oss << c;
    return os << oss.str();
}
bool operator < (const String& s1, const String& s2) {
    unsigned int length{ (s1.size() < s2.size()) ? s1.size() : s2.size() };
    for (unsigned int k{}; k < length; ++k) {
        if (s1[k] == s2[k]) continue;
        if (s1[k] < s2[k]) return true;
        return false;
    }
    return false;
}
bool operator == (const String& s1, const String& s2) {
    if (s1.size() != s2.size()) return false;
    for (unsigned int k{}; k < s1.size(); ++k) {
        if (s1[k] != s2[k]) return false;
    }
    return true;
}
bool operator != (const String& s1, const String& s2) { return not (s1 == s2);}

// --------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------

// Define a string array. Dynamic array with String as content

using StringArray = DynamicArray<String>;
std::istream& operator >> (std::istream& is, StringArray& sa) {
    sa.clear();
    String temp{};
    while (is >> temp)
        sa.push_back(temp);
    return is;
}

// -------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------
// --------------------------------------------------------------------------------------------------------

// Definition of a Hash Map (Like a std::unordered_map)

// Key and Value
struct Item{
    String key {};
    unsigned int count{};
};

// An entry in one bucket of the hash map will be a dynamic array for key/value pairs
using Entry = DynamicArray<Item>;


class HashMap {
    // Some fixed default number for buckets
    static constexpr unsigned int NumberOfBuckets = 8192;

    Entry *buckets{};                 // Buckets will be created dyanmically.
    unsigned int numberOfElements{};  // NUmber of real elements in hash map

    // Claculate the hash value. Maybe you find a better implementation
    unsigned int getHash(const String& s) const;
    
public:
    // Constructor and destructor
    HashMap();
    ~HashMap();

    // Houskeeping functions
    unsigned int size() const;
    bool empty() const;
    bool contains(const String& s) const;

    // 2 main functions for inserting and/or retrieving Pairs / avlues
    Item& insert(const String& s);
    unsigned int& operator[](const String& s);

    // Add iterator properties to class ---------------------------------------------------------------
    // Local class for iterator
    class iterator {
        int iterBucket{};   // Current position of the bucket                         
        int iterEntry{};    // Current index in the dynamic array in the bucket

        Entry* buckets;     // Reference to buckets of the upper hash map

        void next();        // Get the next entry in the hash map that contains a value                        
        void previous();    // Get the previous entry in the hash map that contains a value                        

    public:                 // Define alias names necessary for the iterator functionality
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = Item;
        using pointer = Item*;

        // Please note: Making this const, will prevent that function like sort can be used.
        // This operation would note make sense, or even destroy the hash map
        using reference = const Item&; 

        // Constructor
        iterator(Entry* const b, const unsigned int start);

        // Dereferencing
        reference operator *() const;
        pointer operator ->() const;

        // Arithmetic operations
        iterator& operator ++();
        iterator& operator --();
        iterator operator ++(int);
        iterator operator --(int);
        iterator operator +(const difference_type& n) const;
        iterator& operator +=(const difference_type& n);
        iterator operator -(const difference_type& n) const;
        iterator& operator -=(const difference_type& n);

        // Comparison
        bool operator == (const iterator& other) const;
        bool operator != (const iterator& other) const;
        bool operator < (const iterator& other) const;
        bool operator > (const iterator& other) const;
        bool operator <= (const iterator& other) const;
        bool operator >= (const iterator& other) const;

        // Get current indices
        int getBucket() const;
        int getEntry() const;

        // Difference between 2 iterators. Not that simple in a hash map
        difference_type operator-(const iterator& other) const;
    };

    // Begin and end function to initiliaze an iterator
    iterator begin() const;
    iterator end() const;

    // Additional functions for working with a hash map
    iterator find(const String& key);
    iterator erase(iterator pos);
};

// ---------------------------------------------------------------------------------------------------------
// Construction and destruction
inline HashMap::HashMap() {
    buckets = new Entry[NumberOfBuckets]; 
}

inline HashMap::~HashMap() {
    delete[]buckets; 
}

// Main hashing function. Find a good one. Has a major impact on number of collisions
inline unsigned int HashMap::getHash(const String& s) const {
    unsigned long result = 5381;
    for (char c : s) result = ((result << 5) + result) + c;
    return result % NumberOfBuckets;
}

// Housekeeping
inline unsigned int HashMap::size() const {
    return numberOfElements; 
}

inline bool HashMap::empty() const { 
    return numberOfElements == 0; 
}

inline bool HashMap::contains(const String& s) const {
    for (Item& i : buckets[getHash(s)])
        if (i.key == s)  return true;
    return false;;
}

// Main functions to dealwith a hash map
Item& HashMap::insert(const String& s) {
    unsigned int hash = getHash(s);
    for (Item& i : buckets[hash]) {
        if (i.key == s)
            return i;
        std::cout << "Collision\n";
    }
    buckets[hash].push_back({ s,0 });
    ++numberOfElements;
    return buckets[hash][buckets[hash].size() - 1];
}
inline unsigned int& HashMap::operator[](const String& s) { 
    return insert(s).count; 
}

// ---------------------------------------------------------------------------------------------------------
// Iterator for hash map

// Constructor
HashMap::iterator::iterator(Entry* const b, const unsigned int start) : iterBucket(start), iterEntry(0), buckets(b) {
    for (; iterBucket < NumberOfBuckets; ++iterBucket)
        if (buckets[iterBucket].size()) return;
};

// Navigation
void HashMap::iterator::next() {
    const int s = buckets[iterBucket].size();
    if ((s > 0) and (iterEntry < (s - 1)))
        ++iterEntry;
    else {
        iterEntry = 0;
        if (iterBucket < NumberOfBuckets) ++iterBucket;
        while ((iterBucket < NumberOfBuckets) and (buckets[iterBucket].size() == 0))
            ++iterBucket;
    }
}
void HashMap::iterator::previous() {
    if (iterEntry > 0)
        --iterEntry;
    else {
        if (iterBucket > 0) --iterBucket;
        while ((iterBucket > 0) and (buckets[iterBucket].size() == 0))
            --iterBucket;
        if (buckets[iterBucket].size() > 0)
            iterEntry = buckets[iterBucket].size() - 1;
    }
}

// Dereferencing
inline HashMap::iterator::reference HashMap::iterator::operator *() const {
    return buckets[iterBucket][iterEntry]; 
}

inline HashMap::iterator::pointer HashMap::iterator::operator ->() const {
    return &buckets[iterBucket][iterEntry]; 
}

// Arithmetic operations
inline HashMap::iterator& HashMap::iterator::operator ++() {
    next(); 
    return *this; 
}

inline HashMap::iterator& HashMap::iterator::operator --() {
    previous(); 
    return *this; 
} 

inline HashMap::iterator HashMap::iterator::operator ++(int) {
    iterator tmp = *this;  
    this->next(); 
    return tmp; 
} 

inline HashMap::iterator HashMap::iterator::operator --(int) {
    iterator tmp = *this; 
    this->previous(); 
    return tmp; 
} 

HashMap::iterator HashMap::iterator::operator +(const HashMap::iterator::difference_type& n) const { 
    iterator tmp = *this; 
    difference_type  k{ n }; 
    while (k--) 
        tmp.next(); 
    return tmp; 
};

HashMap::iterator& HashMap::iterator::operator +=(const HashMap::iterator::difference_type& n) { 
    difference_type k{ n };  
    while (k--) 
        next(); 
    return *this; 
}

HashMap::iterator HashMap::iterator::operator -(const HashMap::iterator::difference_type& n) const { 
    iterator tmp = *this; 
    difference_type k{ n };  
    while (k--)  
        tmp.previous(); 
    return tmp; 
};

HashMap::iterator& HashMap::iterator::operator -=(const HashMap::iterator::difference_type& n) { 
    difference_type k{ n };  
    while (k--) previous();  
    return *this; 
}

// Comparison
inline bool HashMap::iterator::operator == (const iterator& other) const {
    return iterBucket == other.iterBucket and iterEntry == other.iterEntry; 
}

inline bool HashMap::iterator::operator != (const iterator& other) const {
    return not (*this == other); 
}  

inline bool HashMap::iterator::operator < (const iterator& other) const {
    return (iterBucket == other.iterBucket) ? (iterEntry < other.iterEntry) : (iterBucket < other.iterBucket); 
}  

inline bool HashMap::iterator::operator > (const iterator& other) const {
    return (iterBucket == other.iterBucket) ? (iterEntry > other.iterEntry) : (iterBucket > other.iterBucket); }  

inline bool HashMap::iterator::operator <= (const iterator& other) const {
    return *this == other or *this < other; 
}  

inline bool HashMap::iterator::operator >= (const iterator& other) const {
    return *this == other or *this > other; 
}  

// Access to iterator internals
inline int HashMap::iterator::getBucket() const {
    return iterBucket; 
}

inline int HashMap::iterator::getEntry() const {
    return iterEntry; 
}
// Difference
inline HashMap::iterator::difference_type HashMap::iterator::operator-(const HashMap::iterator& other) const {
    difference_type delta{};
    iterator o = other;
    while (o < *this) {
        ++delta;
        ++o;
    }
    return delta;
}

// -----------------------------------------------------------------------------------
// Back tohash map functions
HashMap::iterator HashMap::begin()  const { 
    return iterator(buckets, 0); 
}

HashMap::iterator HashMap::end() const { 
    return iterator(buckets, NumberOfBuckets); 
}

// You may want to add additional functions here
HashMap::iterator HashMap::find(const String& key) {
    iterator iter = begin();
    for (; iter != end(); ++iter) {
        if (iter->key == key)
            return iter;
    }
    return iter;
}
HashMap::iterator HashMap::erase(HashMap::iterator pos) {
    iterator result{ pos };
    if (pos != end()) {
        Entry::iterator i = buckets[pos.getBucket()].begin() + pos.getEntry();
        buckets[pos.getBucket()].erase(i);
        ++result;
        --numberOfElements;
    }
    return result;
}

// ---------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------
// ---------------------------------------------------------------------------------------------------------
int main() {

    // Open file and check, if it could be opened
    std::ifstream ifs{ "r:\\test.txt" };
    if (ifs) {

        // Define a dynamic array for strings
        StringArray stringArray{};

        // Use overwritten extraction operator and read all strings from the file to the dynamic array
        ifs >> stringArray;

        // Create a dynamic hash map
        HashMap hm{};

        // Now count the frequency of words
        for (const String& s : stringArray)
            hm[s]++;

        // Put the resulting key/value pairs into a dynamic array
        DynamicArray<Item> items(hm.begin(), hm.end());

        // Sort in descending order by the frequency
        std::sort(items.begin(), items.end(), [](const Item& i1, const Item& i2) { return i1.count > i2.count; });

        // SHow resulton screen
        for (const auto& [string, count] : items) 
            std::cout << std::left << std::setw(20) << string << '\t' << count << '\n';
    }
    else std::cerr << "\n\nError: Could not open source file\n\n";
}