/* inizializza l'inverted index */
INVERTED_INDEX* InitII()
{
	INVERTED_INDEX* first=malloc(  sizeof(INVERTED_INDEX)  *  IISIZE  );
	
	memset(first,0, sizeof(INVERTED_INDEX)  *  IISIZE );

	return first;
}

/* inizializza il lexicon (la lista delle parole) */
OOI_NODE* InitLexicon()
{
	OOI_NODE* first=malloc(  sizeof(OOI_NODE)  *  LEXICONWORDSIZE  );
	
	memset(first,0, sizeof(OOI_NODE)  *  LEXICONWORDSIZE );
	
	return first;
}

/* algoritmo di ordinamento (molto efficente) */
/* ordinamento del lexicon */
void insertion_sort(OOI_NODE* lexicon, int n) 
{
    int i, j;
	unsigned int app;
	
    for (i=1; i<n; i++) {
        app = lexicon[i].value;
		
        j = i-1;
        while ((j>=0) && (lexicon[j].value > app)) 
		{
			swap(lexicon[j+1],lexicon[j]);
            j--;
        }
		
        lexicon[j+1].value = app;
    }
	
}

/* algoritmo di ordinamento (molto efficente) */
/* ordinamento della lista dei documenti per ogni parola del lexicon */
void insertion_sort2(INVERTED_INDEX* ii, int n) 
{
    int i, j;
	unsigned int app;
	
    for (i=1; i<n; i++) {
        app = ii[i].doc_id;
		
        j = i-1;
        while ((j>=0) && (ii[j].doc_id > app)) 
		{
			swap2(ii[j+1],ii[j]);
            j--;
        }
		
        ii[j+1].doc_id = app;
    }
	
}

/* aggiunge una parola al lexicon */
int lstAddWord(OOI_NODE** lexicon,unsigned int wordID)
{
	OOI_NODE* cur;
	
    /* la struttura è piena? */
	if(number_of_elements+1 >= actual_size)
	{
		actual_size = actual_size + LEXICON0INCREMENT;
        /* rialloca lo spazio del lexicon */
		*lexicon = realloc((OOI_NODE*)*lexicon, sizeof(OOI_NODE)*actual_size);

        if(*lexicon == NULL)
            printf("\n\n\nMERR\n\n");

	}
	
	cur = *lexicon;
	
	cur[number_of_elements].id = number_of_elements+1;
	cur[number_of_elements].value = wordID;
	
	cur[number_of_elements].ii = InitII();

    cur[number_of_elements].nii = 0;
    cur[number_of_elements].ii_size = IISIZE;
	
	number_of_elements++;
	
    /* ordina il lexicon (ad ogni inserimento) */
	insertion_sort (*lexicon, number_of_elements);
	
	/* qsort(*lexicon, number_of_elements,sizeof(OOI_NODE),comp); */
	
	return 1;
}


/* binary search */
int ndzLookForWord(OOI_NODE* lexicon, unsigned int wordID)
{
	unsigned int m;
	int p, u;
	p = 0;
	u = number_of_elements-1;
	while(p<u)
	{
		m = (p+u)/2;
		if(lexicon[m].id>0 &&
			lexicon[m].value<wordID)
			p = m+1;
		else
			u = m;
	}
	
	if(u>=0 && lexicon[u].id>0 &&
		lexicon[u].value == wordID)
		return u;
	else
		return -1;
}

int iiLookForDocId(INVERTED_INDEX* ii, unsigned int doc_id, unsigned int elements)
{
	unsigned int m;
	int p, u;
	p = 0;
	u = elements-1;
	while(p<u)
	{
		m = (p+u)/2;
        if(ii[m].doc_id < doc_id)
			p = m+1;
		else
			u = m;
	}
	
	if(u>=0 && ii[u].doc_id == doc_id)
		return u;
	else
		return -1;
}

/* libera la memoria usata dall'indice (lexicon + inverted index) */
void FreeOwsIndex(OOI_NODE* lexicon)
{
	unsigned int i;
	
	for(i=0;i<number_of_elements;i++)
		FREE(lexicon[i].ii);

    FREE(lexicon);

    FREE(glRanks);

}

/* crea un link tra il lexicon e l'inverted index */
void UpdateInvertedIndex(OOI_NODE** lexicon, unsigned int wordID, unsigned int doc_id, unsigned int position)
{
	int pos;
	INVERTED_INDEX* ii;
    OOI_NODE* cur;
    unsigned int last_ii;
    unsigned int ii_size;
	
    /* la parola corrente è nel lexicon*/
	pos = ndzLookForWord(*lexicon, wordID);
	
    /* se no: la aggiunge */
	if(pos==-1)
    {
        lstAddWord(lexicon,wordID);
        pos = ndzLookForWord(*lexicon, wordID);

        if(pos==-1)
		    return;
    }

    cur = *lexicon;

	last_ii = cur[pos].nii;
    ii_size = cur[pos].ii_size;

    /* la struttura è piena? */
	if(last_ii+1 >= ii_size)
	{
    	ii_size = ii_size + IIINCREMENT;
                
		cur[pos].ii = realloc( (INVERTED_INDEX *)cur[pos].ii, sizeof(INVERTED_INDEX) * ii_size );

        if(cur[pos].ii == NULL)
            printf("\n\n\nMERR\n\n");

        cur[pos].ii_size = ii_size;
    }
	
    ii = cur[pos].ii;

    ii[last_ii].doc_id = doc_id;
    ii[last_ii].position = position;
    
    cur[pos].nii++;

    insertion_sort2(cur[pos].ii,cur[pos].nii);
    
}


void printII(INVERTED_INDEX* ii, int elem)
{
int i;
    printf("\n-[ ");
    for(i=0;i<elem;i++)
        printf("%d - ", ii[i].doc_id);

    printf(" ]-\n");
}