#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstddef>
// I wrote this off the top of my head with no consideration, ignore the quirks.
/// Helper Functions ////
/////////////////////////
int compare(const void * a, const void * b){if((int)a < (int)b)return -1; if((int)a == (int)b)return 0; return 1;}
class hashtable { //There is probably something wrong with this, but it works enough to demonstrate the logic.
private:
int * table, * table_accessed; //0 = no access, 1 =access, n+1 = n key collisions
std::size_t length;
int hashy(int element){
std::size_t hash = (element) % this->length;
if(*(this->table+hash) != element)
hashy(element * ++(*(this->table_accessed+hash)));
return hash;
}
public:
hashtable(std::size_t _length)
: table(new int[_length]),
table_accessed(new int[_length]()),
length(_length)
{}
~hashtable(){delete [] table; delete [] table_accessed;}
bool insert(int element){
std::size_t index = hashy(element);
if((*(this->table+index) == element) && (*(this->table_accessed+index) == 1)){
return true;
} else if(*(this->table_accessed+index) > 1) {
if(*(this->table + hashy(element * (*(this->table_accessed+index)))) == element)
return true;
}
*(this->table+index) = element;
(*(this->table_accessed+index))++;
return false;
}
};
//// Array Element is Different Algorithms ////
///////////////////////////////////////////////
//naive, O(n^2)?
const bool ArrElemDif_naive(const int * array_start, std::size_t array_length){
for(std::size_t current = 0; current < array_length; current++){
for(std::size_t offset = current+1; offset < array_length; offset++){
if(*(array_start+current) == *(array_start+offset)){
return false;
}
}
}
return true;
}
//extra computation time necessary for sort, O(n * (n log n))?
const bool ArrElemDif_sort(int * array_start, std::size_t array_length){
int * tmp_array = new int[array_length];
for(std::size_t i = 0; i < array_length; *(tmp_array+i) = *(array_start+i), i++);
qsort(tmp_array, array_length, sizeof(int), compare);
for(std::size_t index = 0; (index+1) != array_length; index++){
if(*(tmp_array+index) == *(tmp_array+index+1)){
return false;
}
}
delete [] tmp_array;
return true;
}
//higher memory usage, O(n)?
const bool ArrElemDif_table(const int * array_start, std::size_t array_length){
class hashtable a(array_length);
for(std::size_t i = 0; i < array_length; i++){
if(a.insert(*(array_start+i))){
return false;
}
}
return true;
}
/////TESTER FUNCTION/////
/////////////////////////
void test(int * array_start, std::size_t array_length, bool isunique){
for(std::size_t i = 0; i < array_length; i++, *(array_start+i) = (isunique ? i : rand() % (i+1)))
printf("%d ",*(array_start+i));
std::cout << std::endl << "naive: " << std::boolalpha << ArrElemDif_naive(array_start, array_length) << std::endl;
std::cout << "sort : " << std::boolalpha << ArrElemDif_sort(array_start, array_length) << std::endl;
std::cout << "table: " << std::boolalpha << ArrElemDif_table(array_start, array_length) << std::endl << std::endl;
}
/////////////////////////
#define LIST_SIZE 50
int main(void){
srand(time(NULL));
int * list = new int[LIST_SIZE];
test(list, LIST_SIZE, false);
test(list, LIST_SIZE, true);
delete [] list;
return 0;
}