0
\$\begingroup\$

I'm new to programming and I would really appreciate some tips about how to improve my design and my writing.

I tried to implement Dictionary data structure, which supports 3 main methods - insert,remove and findData.

The idea is to implement in the most efficient way I could think about (and it is probably not considered as efficient for experienced programmers).

So, the idea is to implement with a sorted array which can dynamically change its size. The capacity at the beginning is a constant value, say 15, and each time we fill all of the cells, we create a new array and copy the elements.

But, we do not copy all of the elements. In my implementation, each cell contains data structure with 3 fields: key,value and a boolean variable that indicates if the element is actually in the dictionary or whether it has been removed. In that way, if to remove an element from the dictionary we only need to search for it (which takes O(log(n))) and then change its boolean variable to false.

Also, inserting an item to a regular sorted array requires to shift right all of the elements that are bigger than the inserted element, in my implementation we only need to shift up to the next empty cell (which can be an item that was removed before).

Here's my implementation:

#ifndef POOLDICTIONARY_H
#define POOLDICTIONARY_H
#include <iostream>
#define CAPACITY 15

template <class T, class U>
class PoolDictionary
{
private:
//|--------------------- Inner struct ----------------------|
    typedef struct PoolPair{
        T key;
        U data;
        bool valid = false;
    }PoolPair;

//|--------------------- Constructors ----------------------|
public:
    PoolDictionary():m_size(0),m_validSize(0),m_capacity(CAPACITY){             //|Default constructor.
        dictionary = new PoolPair[CAPACITY];
    }

    PoolDictionary(const PoolDictionary<T,U>& other) {                          //|Copy constructor.
        dictionary = new PoolPair[other.m_capacity];

        for (int i=0; i<other.m_size ;i++)
            dictionary[i] = other.dictionary[i];

        m_capacity = other.m_capacity;
        this->m_size = other.m_size;
        this-m_validSize = other.m_validSize;
    }
//|------------------------ Methods ------------------------|
    int getSize(){return m_validSize;}                                         //|Return the size of the valid elements in the dictionary.

    void poolRemove(const T& key){                                             //|Removes the element with given key from the dictionary.
        int i = poolSearch(key);
        if (!(dictionary[i].key == key) || !dictionary[i].valid )
             throw "Error: There is no such key in the dictionary.";
        dictionary[i].valid = false;
        m_validSize--;
    }


    /* The idea is to find the correct index of an element we wish to append while conserving the sorted array.
        We want to shift right the element that are bigger than the key of the data we wish to append.
        Note that we only need to shift up to the closest free space, which we recognise by the "valid" boolean field.
        If the closest free space was not the end of the list, meaning we did not override a new data space, than we set
        the boolean "added" to 1. That way we know that if added=1, we do not need to increase the value of m_size.
    */
    void poolInsert(const T u_key, const U& u_data ){ //throw (char*)        //|Inserts a new element to the dictionary.

        int j = poolSearch(u_key);                                          //|The function poolSearch returns the index of the element in the dictionary
        if(dictionary[j].key == u_key)                                      //|with the maximal key such that its key is less than or equal to u_key.
            throw "Error: This key already exists in the dictionary";       //|If we have equality - we throw an error because we want the map between data and keys
                                                                            //|to be injective.
        PoolPair toAdd = {u_key, u_data, true};
        int appended = 0;


        int index;                                                          //|Find the correct index to insert our data.
        if(j==0 && u_key < dictionary[0].key)                               //|We seperate into 2 cases because if the returned index is 0
            index = 0;                                                      //|It might indicate that u_key is smaller than any other key in the list
        else                                                                //|or that the 0 is the maximal key which is smaller than u_key, so that the correct
            index = j+1;                                                    //|index is 1.

        if(!dictionary[j].valid){                                           //|Now note that if j or j+1 is empty (valid=0), we can actually override one of them
            dictionary[j] = toAdd;                                          //|and avoid the loop. Note though that it is the only 2 indexes we can override and keep
            appended=1;                                                     //|the array sorted.
        }
        else if(!dictionary[index].valid){
            dictionary[index] = toAdd;
            appended=1;
        }
        if (index == m_size){
            dictionary[m_size] = toAdd;
            m_size++;
            appended=1;
        }

        PoolPair next, prev = dictionary[index];
        for(int i=index; i<m_size-1 && !appended ; i++){
                next = dictionary[i+1];
                dictionary[i+1] = prev;
                prev = next;
                appended = !(prev.valid);
        }
        dictionary[index] = toAdd;
        if (!appended){
            dictionary[m_size] = prev;
            m_size++;
        }
        m_validSize++;

        if(m_size == m_capacity)
            poolResize();
    }

    U findData(const T u_key) const{   //throw(char*)                             //|As mentioned before, poolSearch returns the index of the maximal
        int i = poolSearch(u_key);                                                //|key which is smaller or equal to u_key.
        if(!(dictionary[i].key == u_key) || !dictionary[i].valid)                 //|So if the key of the element at the returned index is exactly u_key,
            throw "Error: There is no such key in the dictionary.";               //|we found the element. Otherwise, the element does not exists in the dictionary.
        return dictionary[i].data;
    }

//|------------------- Friend functions --------------------|
    friend std::ostream& operator<<(std::ostream& out, const PoolDictionary<T,U>& myDict){
        out<<"{";
        int i=0,j=0;
        while(i<myDict.m_size){
            if(myDict.dictionary[i].valid){
                if(j == myDict.m_validSize -1){
                    out<<myDict.dictionary[i].data<<"}";
                    return out;
            }
                out<<myDict.dictionary[i].data<<", ";
                j++;
            }
            i++;
        }
        return out;
    }

//|---------------------- Destructor -----------------------|
    ~PoolDictionary(){delete[] dictionary;}

 private:
//|-------------------- Private fields ---------------------|
    PoolPair* dictionary;
    int m_capacity;
    int m_size;
    int m_validSize;

//|------------- Private auxiliary functions ---------------|
    int poolSearch(const T& key) const {                      //|This function receives key as an argument, and returns the
                                                              //|index of the PoolPair with the maximal key which is smaller or equal to the argument key.
        int first = 0, last = m_size-1;                       //|The function assumes that the argument key is greater than the minimal key currently in the dictionary.

        while(first<last){
            int middle = (first+last+1)/2;
            T middleKey = dictionary[middle].key;

            if(key == middleKey)
                return middle;

            else if(key < middleKey)
                last = middle-1;

            else
                first = middle;
        }
        return first;
    }

    void poolResize(){                                         //|This is the resize function. When we are out of empty cells we create new bigger array
        PoolPair* tmp = dictionary;                            //|And copy only the valid elements to this new array.
        dictionary = new PoolPair[m_validSize + CAPACITY];

        int i=0,j=0;

        while(i<m_size){
            if(tmp[i].valid){
                dictionary[j] = tmp[i];
                j++;
            }
            i++;
        }
        m_capacity = m_validSize + CAPACITY;
        m_size = m_validSize;
        delete[] tmp;
    }

};

#endif // POOLDICTIONARY_H

Here are some tests I tried:

using namespace std;

int main(){

    PoolDictionary<int,char*> Dict;

    char* strings[18]={"Riemman","Hypothesis","Is","Probably","Truth","But","According","To","Terry","Tao","We","Are","Not","Able","To","Prove","It","Yet"};
    for(int i=0; i<18 ;i++){
        if(i%2==1)
            Dict.poolInsert(i+156,strings[i]);
        else
            Dict.poolInsert((-1*i)-156,strings[i]);
    }
    cout<<Dict<<endl;

    cout<<Dict.findData(-156)<<endl;
    cout<<Dict.findData(157)<<endl;
    cout<<Dict.findData(159)<<endl;
    cout<<Dict.findData(-160)<<endl;

    try{
        cout<<Dict.findData(160)<<endl;      //There is no such a key in the dictionary, should throw an error.
    }

    catch(const char* c){
        cout<<c<<endl;
    }
    cout<<"The size is: "<<Dict.getSize()<<endl;
    Dict.poolRemove(-156);
    Dict.poolRemove(157);
    Dict.poolRemove(159);
    Dict.poolRemove(-160);
    cout<<Dict<<endl;
    cout<<"The size is: "<<Dict.getSize()<<endl;

    return 0;
}

The output:

{It, To, Not, We, Terry, According, Truth, Is, Riemman, Hypothesis, Probably, But, To, Tao, Are, Able, Prove, Yet}
Riemman
Hypothesis
Probably
Truth
Error: There is no such key in the dictionary.
The size is: 18
{It, To, Not, We, Terry, According, Is, But, To, Tao, Are, Able, Prove, Yet}
The size is: 14

I'd really appreciate any kind of tip/note in order to improve my code. Particularly, do you guys think the usage of an inner structure is fine? I thought about implementing this data structure separately and writing it as a friend class in the PoolDictionary class, but could not decide what would be better.

Also, I'd really want to hear what you think about the choice of passing/returning arguments by value/reference in each method. I assumed that since we usually use integers as keys it would be okay to pass them by values, and the rest of the arguments would be by reference.

\$\endgroup\$
2
  • \$\begingroup\$ Is there some good reason not to simply use std::map? What advantages does this implementation have? \$\endgroup\$ Feb 2, 2022 at 7:59
  • \$\begingroup\$ @TobySpeight I'm trying to experience more and improve my codin skills, using existing libraries will not help me with that (probably the existing library would be more efficient than mine). By the way, what's the time complexity of the basic methods in the library you mentioned? \$\endgroup\$ Feb 2, 2022 at 11:32

1 Answer 1

1
\$\begingroup\$
  • poolSearch

    assumes that the argument key is greater than the minimal key currently in the dictionary.

    I don't see how this assumption is held. It is up to the client of poolRemove, poolInsert, findData to specify the key, and it could be quite arbitrary.

  • poolSearch pays no attention to the valid state, and poolInsert does not test it either. It means that pooInsert throws at an attempt to reinsert the kay after it has been deleted. Try

          Dict.poolRemove(-156);
          Dict.poolInsert(-156, "whatever");
    
  • Throwing exceptions seems drastic. There is nothing exceptional in key existence or non-existence. Consider returning a success flag, STL style.

  • A pool prefix to poolInsert and poolRemove is redundant. Consider insert, remove, find.

  • first+last may overflow. A first + (last - first)/2 is more prudent.

  • m_capacity, m_size, m_validSize shall be size_t rather than int.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.