StatsList.cpp

#include "StatsList.h"
#include<iostream>

long long int slen = 1;
std::pair<long long int, long long int> *sarray = new std::pair<long long int, long long int>[slen];
int j = 0;


long long int Hash(char s[]){
    long long int hash = 0;
    int i = 0;
    while (s[i]!='\0'){
        switch (i%2)
        {
        case 0:
            hash+=(s[i]*239)-2*i+3*s[i]+i*s[i]*9;
            break;
        
        default:
            hash+=(s[i]%239)-9*i+2*s[i]+i*s[i]*2;
            break;
        }
        ++i;
    }
    return hash;
}

void SPush(std::pair<long long int, long long int> el){
    if(j==slen){
        SReRealize();
    }
    sarray[j] = el;
    j++;
}

std::pair<long long int, long long int> SGet(int index){
    return sarray[index];
}

void SSet(std::pair<long long int, long long int> value, int index){
    sarray[index] = value;
}

void SReRealize(){
    std::pair<long long int, long long int> *temp = new std::pair<long long int, long long int>[slen*2];

    for(int ii = 0; ii<slen;++ii){
        temp[ii] = sarray[ii];
    }
    slen*=2;

    delete [] sarray;

    sarray = temp;
}

int SGetLen(){
    return j;
}

void Increase(int i){
    ++sarray[i].second;
}

void glue(
    std::pair<long long, long long> a[], int la,
    std::pair<long long, long long> b[], int lb, 
    std::pair<long long, long long> c[], int lc){

    for(int i = 0; i < la;++i){
        sarray[i] = a[i];
    }
    for(int i = 0; i < lb;++i){
        sarray[la+i] = b[i];
    }
    for(int i = 0; i < lc;++i){
        sarray[la+lb+i] = c[i];
    }
}

void QuickSort(std::pair<long long, long long> a[], int n){

    if(n<2)return;

    std::pair<long long, long long> t = a[int(n*0.3575)];
    int m = 0,l = 0, e = 0;
    for(int i = 0; i<n;++i){
        if (a[i].first<t.first)l++;
        if (a[i].first>t.first)m++;
        if(a[i].first==t.first)e++;
    }

    std::pair<long long, long long> more[m], less[l], equal[e];
    m = 0; l = 0; e = 0;
    for(int i = 0; i<n;++i){
        if (a[i].first<t.first){less[l] = a[i];l++;}
        if (a[i].first>t.first){more[m] = a[i];m++;}
        if(a[i].first==t.first){equal[e] = a[i];e++;}
    }

    QuickSort(more, m);
    QuickSort(less, l);

    

    glue(more, m, equal, e, less, l);
}

void QS(){
    QuickSort(sarray, SGetLen());
}