aatrees

[vg.git] / src / vg / vg_store.h

#ifndef VG_STORE_H
#define VG_STORE_H

typedef struct aatree aatree;
typedef struct aatree_node aatree_node;

typedef u32 aatree_ptr;
#define AATREE_PTR_NIL 0xffffffff

struct aatree
{
   u32 offset, stride; /* distance between elements */
   void *base;

   int (*p_cmp)( void *a, void *b );
   int (*p_cmpv)( void *a, void *v );
};

struct aatree_node
{
   aatree_ptr left, right;
   u32 level, count;
};

static void *aatree_get_data( aatree *tree, aatree_ptr t )
{
   return tree->base + tree->stride*t;
}

static aatree_node *aatree_get_node( aatree *tree, aatree_ptr t )
{
   return tree->base + tree->stride*t + tree->offset;
}

static void aatree_recount( aatree *tree, aatree_ptr n )
{
   aatree_node *pnode = aatree_get_node( tree, n );
   pnode->count = 1;

   if( pnode->left != AATREE_PTR_NIL )
      pnode->count += aatree_get_node( tree, pnode->left )->count;

   if( pnode->right != AATREE_PTR_NIL )
      pnode->count += aatree_get_node( tree, pnode->right )->count;
}

/*         .            .
 *         |            |
 *    L <- T            L -> T
 *   / \    \    ->    /    / \
 *  A   B    R        A    B   R
 */
static aatree_ptr aatree_skew( aatree *tree, u32 t )
{
   if( t == AATREE_PTR_NIL ) return t;

   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->left == AATREE_PTR_NIL ) return t;

   aatree_node *plnode = aatree_get_node( tree, ptnode->left );
   if( plnode->level == ptnode->level )
   {
      aatree_ptr l = ptnode->left;
      ptnode->left = plnode->right;
      plnode->right = t;

      aatree_recount( tree, t );
      aatree_recount( tree, l );

      return l;
   }

   return t;
}

/*    .                    .
 *    |                    |
 *    T -> R -> X   ->     R
 *   /    /               / \
 *  A    B               T   X
 *                      / \
 *                     A   B
 */
static aatree_ptr aatree_split( aatree *tree, aatree_ptr t )
{
   if( t == AATREE_PTR_NIL ) return t;

   aatree_node *ptnode = aatree_get_node( tree, t );
   if( ptnode->right == AATREE_PTR_NIL ) return t;

   aatree_node *prnode = aatree_get_node( tree, ptnode->right );
   if( prnode->right == AATREE_PTR_NIL ) return t;

   aatree_node *prrnode = aatree_get_node( tree, prnode->right );
   if( ptnode->level == prrnode->level )
   {
      aatree_ptr r = ptnode->right;
      ptnode->right = prnode->left;
      prnode->left = t;
      prnode->level ++;

      aatree_recount( tree, t );
      aatree_recount( tree, r );

      return r;
   }

   return t;
}

static aatree_ptr aatree_insert( aatree *tree, aatree_ptr t, aatree_ptr x )
{
   aatree_node *pxnode = aatree_get_node( tree, x );

   if( t == AATREE_PTR_NIL )
   {
      pxnode->left = AATREE_PTR_NIL;
      pxnode->right = AATREE_PTR_NIL;
      pxnode->level = 0;
      pxnode->count = 1;
      return x;
   }

   aatree_node *ptnode = aatree_get_node( tree, t );
   int cmp_result = tree->p_cmp( aatree_get_data( tree, t ), 
                                 aatree_get_data( tree, x ) );

   ptnode->count ++;

   if( cmp_result <= 0 )
      ptnode->left = aatree_insert( tree, ptnode->left, x );
   else
      ptnode->right = aatree_insert( tree, ptnode->right, x );

   t = aatree_skew( tree, t );
   t = aatree_split( tree, t );
   return t;
}

static aatree_ptr aatree_del( aatree *tree, aatree_ptr t, aatree_ptr x )
{
   if( t == AATREE_PTR_NIL ) return t;
   return AATREE_PTR_NIL; /*TODO*/
}

/*
 * Accessors
 */

static aatree_ptr aatree_kth( aatree *tree, aatree_ptr t, u32 k )
{
   u32 i = 0;

   while( t != AATREE_PTR_NIL )
   {
      aatree_node *ptnode = aatree_get_node( tree, t );
      
      u32 j = i;
      if( ptnode->left != AATREE_PTR_NIL )
         j += aatree_get_node( tree, ptnode->left )->count;

      if( j < k )
      {
         i = j+1;
         t = ptnode->right;
      }
      else
      {
         if( j > k )
         {
            t = ptnode->left;
         }
         else
         {
            return t;
         }
      }
   }

   return AATREE_PTR_NIL;
}

static aatree_ptr aatree_ptrof( aatree *tree, aatree_ptr t, void *value )
{
   while( t != AATREE_PTR_NIL )
   {
      int cmp_result = tree->p_cmpv( aatree_get_data( tree, t ), value );

      if( cmp_result == 0 )
         return t;
      else 
      {
         aatree_node *ptnode = aatree_get_node( tree, t );

         if( cmp_result < 0 )
            t = ptnode->left;
         else
            t = ptnode->right;
      }
   }
   return t;
}


/*
 * Debugging stuff
 * =============================================================================
 */

static void aatree_show_r( aatree *tree, aatree_ptr t, int lvl, 
                           void(*p_show)(void *data) )
{
   if( t != AATREE_PTR_NIL )
   {
      aatree_node *ptnode = aatree_get_node( tree, t );
      aatree_show_r( tree, ptnode->left, lvl+1, p_show );

      void *data = aatree_get_data( tree, t );

      for( int i=0; i<lvl; i++ )
      {
         printf( "  " );
      }
      p_show( data );
      printf( " (%d) \n", t );

      aatree_show_r( tree, ptnode->right, lvl+1, p_show );
   }
}

static void aatree_show( aatree *tree, aatree_ptr t, void(*p_show)(void *data))
{
   if( t != AATREE_PTR_NIL )
   {
      aatree_node *ptnode = aatree_get_node( tree, t );
      aatree_show( tree, ptnode->left, p_show );
      void *data = aatree_get_data( tree, t );

      for( int i=0; i<ptnode->level; i++ )
      {
         printf( "  " );
      }
      p_show( data );
      printf( " (%d) \n", t );

      aatree_show( tree, ptnode->right, p_show );
   }
}

static void aatree_show_counts( aatree *tree, aatree_ptr t, int lvl, int *ln,
                                void(*p_show)(void *data) )
{
   if( t == AATREE_PTR_NIL ) return;

   aatree_node *ptnode = aatree_get_node( tree, t );
   void *data = aatree_get_data( tree, t );

   aatree_show_counts( tree, ptnode->left, lvl+1, ln, p_show );

   printf( "    %03d| ", *ln );
   *ln = *ln +1;

   for( int i=0; i<lvl; i++ )
   {
      printf( "   " );
   }

   p_show( data );
   printf( " (%d, %d) \n", t, ptnode->count );

   aatree_show_counts( tree, ptnode->right, lvl+1, ln, p_show );
}

#endif /* VG_STORE_H */

#if 0

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <stddef.h>
#include <math.h>

#include "vg/vg_platform.h"
#include "vg/vg_stdint.h"
#include "vg/vg_store.h"
#include "vg/vg_io.h"
#include "vg/vg_m.h"

typedef struct yoyo_t yoyo_t;
struct yoyo_t
{
   int my_data;
   aatree_node anode;
};

static void yoyo_t_show( void *_data )
{
   yoyo_t *data = _data;
   printf( "%d ", data->my_data );
}

static int yoyo_t_cmpv( void *_a, void *_v )
{
   yoyo_t *a = _a;
   int *b = _v;
   return *b - a->my_data;
}

static int yoyo_t_cmp( void *_a, void *_b )
{
   yoyo_t *a = _a, *b = _b;
   return b->my_data - a->my_data;
}

int main(int argc, const char *argv[])
{
   yoyo_t *allsorts = malloc( sizeof(yoyo_t) * 10000 );

   aatree test;
   test.base = allsorts;
   test.offset = offsetof( yoyo_t, anode );
   test.stride = sizeof( yoyo_t );
   test.p_cmp = yoyo_t_cmp;
   test.p_cmpv = yoyo_t_cmpv;
   
   aatree_ptr root = AATREE_PTR_NIL;

   for( int i=0; i<20; i++ )
   {
      yoyo_t *rando = &allsorts[i];
      rando->my_data = vg_randf() * 10.0f;
      root = aatree_insert( &test, root, i );
   }
   
   int ln=0;
   aatree_show_counts( &test, root, 0, &ln, yoyo_t_show );

   int value = 3;
   vg_info( "Ptr of %d: %u\n", value, aatree_ptrof( &test, root, &value ) );

   for( int i=0; i<20; i++ )
   {
      yoyo_t *v = aatree_get_data(&test,aatree_kth( &test, root, i ));
      vg_info( "Value of [%d]: %d\n", i, v->my_data );
   }

   free( allsorts );
   return 0;
}

#endif