#include <stdio.h>
/**
* An item stores data in Key Value pairs
* and forms a Linked List
*/
template<class T>
struct LinkedItem {
/**
* The key
*/
int key;
/**
* The value
*/
T value;
/**
* Next item in the linked list
*/
LinkedItem<T>* next = NULL;
/**
* The last item in the linked list
*/
LinkedItem<T>* Last(){
if (this->next == NULL){
return this;
}
return next;
}
/**
* The last item less than the key
*/
LinkedItem<T>* Last(int key){
if (this->next == NULL){
return this;
}
if (this->next->key > key){
return this;
}
return next;
}
/**
* Finds an item based on its key (or returns NULL)
*/
LinkedItem<T>* Find(int key){
if (this->key == key){
return this;
}
if (this->key > key){
// Assuming the list is ordered
return NULL;
}
if (this->next != NULL){
return this->next->Find(key);
}
return NULL;
}
};
/**
* A collection holds several linked lists,
* accessing them through a hash table
* (N can be tuned for performance)
*/
template<class T, int N>
class Collection{
public:
/**
* The collection of linked item collections
*/
LinkedItem<T> *LinkedLists[N];
/**
* The default constructor (sets list to a collection of NULL)
*/
Collection(){
for(int i = 0; i < N; i++){
this->LinkedLists[i] = NULL;
}
}
/**
* Adds or replaces a key value pair
* @param key the key
* @param value the value
*/
void Put(int key, T value){
int index = key % N;
if (LinkedLists[index] == NULL){
// If there are no items, this is the first// Add the new item
LinkedItem<T>* item = new LinkedItem<T>();
item->value = value;
item->key = key;
LinkedLists[index] = item;
return;
}
LinkedItem<T>* found = LinkedLists[index]->Find(index);
if (found != NULL){
found->value = value;
return;
}
LinkedItem<T>* item = new LinkedItem<T>();
item->value = value;
item->key = key;
LinkedItem<T>* last = LinkedLists[index]->Last(key);
if (last->key > key){
LinkedLists[index] = item;
item->next = last;
return;
}
item->next = last->next;
last->next = item;
}
/**
* Gets a value based on a key
* @param key the key
* @returns the value or null/default
*/
T Get(int key){
int index = key % N;
if (LinkedLists[index] == NULL){
// If there are no items, this is the 0
return (T)NULL;
}
LinkedItem<T>* found = LinkedLists[index]->Find(key);
if (found == NULL){
// If there are no items, this is the 0
return (T)NULL;
}
return found->value;
}
};
int main()
{
printf("Alright, let's test this...\n");
printf("First we make a new collection on the stack.\n");
Collection<int, 15> c;
printf("Now we add {1,2} using .Put(1,2)\n");
c.Put(1,2);
printf("Now we try c.Get(1) = %d\n", c.Get(1));
printf("Now we try c.Get(2) = %d\n", c.Get(2));
printf("Now we add {1,3} using .Put(1,3)\n");
c.Put(1,3);
printf("Now we try c.Get(1) = %d\n", c.Get(1));
printf("Now we try c.Get(2) = %d\n", c.Get(2));
printf("Now we add {2,2} using .Put(2,2)\n");
c.Put(2,2);
printf("Now we try c.Get(1) = %d\n", c.Get(1));
printf("Now we try c.Get(2) = %d\n", c.Get(2));
return 0;
}
