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.
std::map? What advantages does this implementation have? \$\endgroup\$