src/vptree_sequential.c
// Function that recursively builds the binary tree and returns a pointer to its root
Function that recursively builds the binary tree and returns a pointer to its root
Function that recursively builds the binary tree and returns a pointer to its root
vptree * build_tree(double *points, int *ids, int n, int d)
{
    vptree *node = calloc(1, sizeof(vptree));
    if (n == 1)
    {
        node->inner = NULL;
        node->outer = NULL;
        node->idx = ids[0];
        node->md = 0;
        node->vp = calloc(d, sizeof(double));
        memcpy(node->vp, points, sizeof(double) * d);
        free(ids);
        free(points);
        return node;
    }
    double *point = (points + (n-1)*d);
    int id = ids[n-1];
    double *distances = euclidean(point, points, n-1, d);
    double *distancesCopy = calloc(n-1, sizeof(double));
    memcpy(distancesCopy, distances, sizeof(double) * (n-1));
    double median = quickselect_median(distancesCopy, n-1);
    free(distancesCopy);
    int innerLength = 0;
    for (int i = 0; i < n-1; i++)
    {
        if(distances[i] <= median)
        {
            innerLength++;
        }
    }
    int outerLength = n - 1 - innerLength;
    int innerPointer = 0;
    int outerPointer = 0;
    double *innerPoints = calloc(innerLength * d, sizeof(double));
    double *outerPoints = calloc(outerLength * d, sizeof(double));
    int *innerIDs = calloc(innerLength, sizeof(int));
    int *outerIDs = calloc(outerLength, sizeof(int));
    for (int i = 0; i < n-1; i++){
        if(distances[i] <= median){
            memcpy(innerPoints + innerPointer * d, points + i*d, sizeof(double) * d);
            innerIDs[innerPointer] = ids[i];
            innerPointer++;
        }
        else{
            memcpy(outerPoints + outerPointer * d, points + i*d, sizeof(double) * d);
            outerIDs[outerPointer] = ids[i];
            outerPointer++;
        }
    }
    node->vp = calloc(d, sizeof(double));
    node->md = median;
    memcpy(node->vp, point, sizeof(double) * d);
    node->idx = id;
    free(points);
    free(distances);
    free(ids);
    if(innerLength > 0){
        node->inner = build_tree(innerPoints, innerIDs, innerLength, d);
    }
    else{
        node->inner = NULL;
    }
    if(outerLength > 0){
        node->outer = build_tree(outerPoints, outerIDs, outerLength, d);
    }
    else{
        node->outer = NULL;
    }
    return node;
}
vptree * build_tree ( double * points , int * ids , int n , int d ) { vptree * node = calloc ( 1 , sizeof ( vptree ) ) ; if ( n == 1 ) { node -> inner = NULL ; node -> outer = NULL ; node -> idx = ids [ 0 ] ; node -> md = 0 ; node -> vp = calloc ( d , sizeof ( double ) ) ; memcpy ( node -> vp , points , sizeof ( double ) * d ) ; free ( ids ) ; free ( points ) ; return node ; } double * point = ( points + ( n - 1 ) * d ) ; int id = ids [ n - 1 ] ; double * distances = euclidean ( point , points , n - 1 , d ) ; double * distancesCopy = calloc ( n - 1 , sizeof ( double ) ) ; memcpy ( distancesCopy , distances , sizeof ( double ) * ( n - 1 ) ) ; double median = quickselect_median ( distancesCopy , n - 1 ) ; free ( distancesCopy ) ; int innerLength = 0 ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( distances [ i ] <= median ) { innerLength ++ ; } } int outerLength = n - 1 - innerLength ; int innerPointer = 0 ; int outerPointer = 0 ; double * innerPoints = calloc ( innerLength * d , sizeof ( double ) ) ; double * outerPoints = calloc ( outerLength * d , sizeof ( double ) ) ; int * innerIDs = calloc ( innerLength , sizeof ( int ) ) ; int * outerIDs = calloc ( outerLength , sizeof ( int ) ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( distances [ i ] <= median ) { memcpy ( innerPoints + innerPointer * d , points + i * d , sizeof ( double ) * d ) ; innerIDs [ innerPointer ] = ids [ i ] ; innerPointer ++ ; } else { memcpy ( outerPoints + outerPointer * d , points + i * d , sizeof ( double ) * d ) ; outerIDs [ outerPointer ] = ids [ i ] ; outerPointer ++ ; } } node -> vp = calloc ( d , sizeof ( double ) ) ; node -> md = median ; memcpy ( node -> vp , point , sizeof ( double ) * d ) ; node -> idx = id ; free ( points ) ; free ( distances ) ; free ( ids ) ; if ( innerLength > 0 ) { node -> inner = build_tree ( innerPoints , innerIDs , innerLength , d ) ; } else { node -> inner = NULL ; } if ( outerLength > 0 ) { node -> outer = build_tree ( outerPoints , outerIDs , outerLength , d ) ; } else { node -> outer = NULL ; } return node ; }
Function that recursively builds the binary tree and returns a pointer to its root
Function that recursively builds the binary tree and returns a pointer to its root
// Create node to be returned // Check to end recursion: if points array is of size 0 - we are returning a leaf // Build node // Free memory for ids and points arrays // Return node // Choose the last point in X as the vantage point // Create array that holds euclidean distance of point from all other points // At this point distances[i] indicates the distance of point i in points from the vantage point // Find median by creating a copy of distances and passing it to QuickSelect // Sort points into two new arrays // Calculate array sizes for subtrees. Values up to and equal to the median go on the inner tree // Pointers to keep track of inner and outer arrays content while sorting points // Create arrays for inner and outer points. Arrays contain the points and a list of ids (one for each point) // Sort points to inner and outer subtree // Set node fields // Copy the point into vp because we will call free(points) that will also free(point) // De-allocate unused memory // Calculate subtrees