sort.c File Reference

#include "../headers/sort.h"

Go to the source code of this file.

Functions
static void	merge_atom_vert (s_vsort *lsort, s_atm **atoms, int natms, s_vvertice **pvert, int nvert)
static void	qsort_dim (s_vect_elem *lst, int len)
static void	qsort_rec (s_vect_elem *lst, int start, int end)
static int	partition_x (s_vect_elem *lst, int start, int end)
s_vsort *	get_sorted_list (s_atm **atoms, int natms, s_vvertice **pvert, int nvert)
void	print_sorted_lst (s_vsort *lsort, FILE *buf)
void	free_s_vsort (s_vsort *lsort)

---

Function Documentation

void free_s_vsort

(

s_vsort *

lsort

)

## FUNCTION: free_s_vsort

## SPECIFICATION: Free memory for s_vsort structure

## PARAMETRES: @ s_vsort *lsort: Structure to free

## RETURN:

Definition at line 328 of file sort.c.

References my_free(), and s_vsort::xsort.

Referenced by count_atm_prop_vert_neigh(), count_pocket_lig_vert_ovlp(), count_vert_neigh_P(), get_mol_atm_neigh(), get_mol_ctd_atm_neigh(), and get_mol_vert_neigh().

{
        if(lsort) {
                if(lsort->xsort) my_free(lsort->xsort) ;
                
                my_free(lsort) ;
        }
}

s_vsort* get_sorted_list	(	s_atm **	atoms,
		int	natms,
		s_vvertice **	pvert,
		int	nvert
	)

## FUNCTION: get_sorted_list

## SPECIFICATION: This function will return a lists which will contains all atoms and vertices sorted on x axis. First, we merge atom and vertice lists into those a single list. Then they will be sorted using a quickSort algorithm, using the x positions of vertices and atoms as criteria for sorting.

## PARAMETRES: @ s_pdb *pdb : PDB structure, basically containing atoms @ s_vvertice **pvert, int nvert : List of vertices (if NULL, only atoms will be sorted)

## RETURN: s_vsort*: pointer to the structure containing all sorted data (see .h)

Definition at line 86 of file sort.c.

References merge_atom_vert(), my_malloc(), s_vsort::nelem, qsort_dim(), and s_vsort::xsort.

Referenced by count_atm_prop_vert_neigh(), count_pocket_lig_vert_ovlp(), count_vert_neigh_P(), get_mol_atm_neigh(), get_mol_ctd_atm_neigh(), and get_mol_vert_neigh().

{
        s_vsort *lsort = (s_vsort *) my_malloc(sizeof(s_vsort)) ;
        
        lsort->nelem = 0 ;

        if(atoms) lsort->nelem += natms ;
        if(pvert) lsort->nelem += nvert ;

        if(lsort->nelem == 0) return NULL ;

        /* Allocate memory */
        lsort->xsort = (s_vect_elem*) my_malloc((lsort->nelem)*sizeof(s_vect_elem)) ;
        
        merge_atom_vert(lsort, atoms, natms, pvert, nvert) ;
        qsort_dim(lsort->xsort, lsort->nelem) ;
        
        return lsort ;

}

static void merge_atom_vert	(	s_vsort *	lsort,
		s_atm **	atoms,
		int	natms,
		s_vvertice **	pvert,
		int	nvert
	)			[static]

## FUNCTION: merge_atom_vert

## SPECIFICATION: Merge atom and vertice lists into three single list that will be sorted next.

## PARAMETRES: @ s_vsort *lsort : Structure that should contains the 3 lists @ s_pdb *pdb : pdb structure containing atoms @ s_vvertice **pvert, int nvert : List of v ertices

## RETURN:

Definition at line 123 of file sort.c.

References s_vect_elem::data, M_ATOM_TYPE, M_VERTICE_TYPE, s_vvertice::sort_x, s_atm::sort_x, s_vect_elem::type, and s_vsort::xsort.

Referenced by get_sorted_list().

{
        s_vect_elem *cur = NULL ;
        
        int i = 0, j = 0,
                pos ;

        if(atoms) {
                for(i = 0 ; i < natms ; i++) {
                        atoms[i]->sort_x = i ;
                        cur = &(lsort->xsort[i]) ;
                        cur->data = atoms[i] ;
                        cur->type = M_ATOM_TYPE ;
                }
        }
        
        if(pvert) {
                for(j = 0 ; j < nvert ; j++) {
                        pos = i + j ;
                        
                        pvert[j]->sort_x = pos ;
                        cur = &(lsort->xsort[pos]) ;
                        cur->data = pvert[j] ;
                        cur->type = M_VERTICE_TYPE ;
                }
        }
}

static int partition_x	(	s_vect_elem *	lst,
		int	start,
		int	end
	)			[static]

## FUNCTION: static partition_x

## SPECIFICATION: Partition function for the qsort on atoms and vertices, using the X coordinate as criteria to sort the list.

## PARAMETRES: @ s_vect_elem *lst : List of vector to sort @ int start : Sort from start @ int end : to end

## RETURN: int: qsort index

Definition at line 213 of file sort.c.

References s_vect_elem::data, M_ATOM_TYPE, s_vvertice::sort_x, s_atm::sort_x, s_vect_elem::type, s_vvertice::x, and s_atm::x.

Referenced by qsort_rec().

{
        s_vect_elem tmp ;
        s_atm *acur      = NULL ;
        s_vvertice *vcur = NULL ;
        
        int c = start,
                i ;
                
        float piv ;      /* TODO: chose randomly the pivot. */
        
        piv = (lst[start].type == M_ATOM_TYPE)? ((s_atm*)lst[start].data)->x : 
                                                                                        ((s_vvertice*)lst[start].data)->x ;
        
        for(i = start+1 ; i <= end ; i++) {
                if(lst[i].type == M_ATOM_TYPE) {
                        acur = ((s_atm*) lst[i].data) ;
                        if(acur->x < piv) {
                                c++ ;
                        
                                /* We have to swap, so change indices, and swap elements. */
                                if(lst[c].type == M_ATOM_TYPE) ((s_atm*)lst[c].data)->sort_x = i ;
                                else ((s_vvertice*)lst[c].data)->sort_x = i ;
                                
                                acur->sort_x = c ;
                                
                                tmp = lst[c] ;
                                lst[c] = lst[i] ; lst[i] = tmp ;
                        }
                }
                else {
                        vcur = ((s_vvertice*)lst[i].data) ;
                        if(vcur->x < piv) {
                                c++ ;
                        
                                /* We have to swap, so change indices, and swap elements. */
                                if(lst[c].type == M_ATOM_TYPE) ((s_atm*)lst[c].data)->sort_x = i ;
                                else ((s_vvertice*)lst[c].data)->sort_x = i ;
                                
                                vcur->sort_x = c ;
                                
                                tmp = lst[c] ;
                                lst[c] = lst[i] ; lst[i] = tmp ;
                        }
                }
        }
        
        if(lst[c].type == M_ATOM_TYPE) ((s_atm*)lst[c].data)->sort_x = start ;
        else ((s_vvertice*)lst[c].data)->sort_x = start ;
        
        if(lst[start].type == M_ATOM_TYPE) ((s_atm*)lst[start].data)->sort_x = c ;
        else ((s_vvertice*)lst[start].data)->sort_x = c ;
                        
        tmp = lst[c] ;
        lst[c] = lst[start] ; lst[start] = tmp ;

        return(c);
}

void print_sorted_lst	(	s_vsort *	lsort,
		FILE *	buf
	)

## FUNCTION: print_sorted_lst

## SPECIFICATION: Print one of the sorted tab of a s_vsort structure

## PARAMETRES: @ s_vsort *lsort : Structure containing tab @ FILE *buf : Buffer to print in.

## RETURN:

Definition at line 286 of file sort.c.

References M_ATOM_TYPE, s_vsort::nelem, s_vvertice::sort_x, s_atm::sort_x, s_vvertice::x, s_atm::x, and s_vsort::xsort.

{
        s_vect_elem *lst = NULL ;
        lst = lsort->xsort ; fprintf(buf, "\n========== Printing list of vertices and atoms sorted on X axe:\n") ;
        
        float cval, prev = -1.0 ;
        int i ;
        
        for(i = 0 ; i < lsort->nelem ; i++) {
                fprintf(buf, "> Element at %d: ", i);
                if(lst[i].type == M_ATOM_TYPE) {
                        s_atm *a = (s_atm*) lst[i].data ;
                        cval = a->x ;
                        fprintf(buf, " ATOM coord = %f, index stored: %d", cval, a->sort_x) ;
                }
                else {
                        s_vvertice *v = (s_vvertice*) lst[i].data ;
                        cval = v->x ;
                        
                        fprintf(buf, " VERTICE coord = %f, index stored: %d", cval, v->sort_x) ;
                }
                
                if(prev > cval) fprintf(buf, " !!!!!!! ") ;
                fprintf(buf, "\n") ;
                
                prev = cval ;   
        }
}

static void qsort_dim	(	s_vect_elem *	lst,
		int	len
	)			[static]

## FUNCTION: qsort_dim

## SPECIFICATION:

## PARAMETRES: @ s_vect_elem *lst : List of vector to sort @ int *len : Length of the list

## RETURN:

Definition at line 164 of file sort.c.

References qsort_rec().

Referenced by get_sorted_list().

{
        qsort_rec(lst, 0,  len-1) ;
}

static void qsort_rec	(	s_vect_elem *	lst,
		int	start,
		int	end
	)			[static]

## FUNCTION: static qsort_rec

## SPECIFICATION: qsort routine adapted to what we wanna do.

## PARAMETRES: @ s_vect_elem *lst : List of vector to sort @ int start : Sort from start @ int end : to end

## RETURN: void

Definition at line 185 of file sort.c.

References partition_x().

Referenced by qsort_dim().

{
        if(start < end) {
                int piv = 0 ;
                piv = partition_x(lst, start, end) ;
                
                qsort_rec(lst, start, piv-1) ;
                qsort_rec(lst, piv+1, end) ;
        }
}