---

guma_sorting.h

Go to the documentation of this file.

/* LIBGUL - Geometry Utility Library
 * Copyright (C) 1998-1999 Norbert Irmer
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
 
#ifndef GUMA_SORTING_H
#define GUMA_SORTING_H

namespace guma {

/***************************************************************

  BALANCED BINARY TREE (see Knuth: "Sorting and Searching")

***************************************************************/

/*---------------------------------------------------------------
  Structure for the nodes of a balanced binary tree
----------------------------------------------------------------*/

typedef struct bbt_node
{
  void                 *key;
    
  struct
  {
    int                b : 2;
    int                l : 2;
  }F;

  struct bbt_node  *left;
  struct bbt_node  *right;
  struct bbt_node  *parent;
}
BBTNode;

/*-------------------------------------------------------------
  Creates an empty balanced binary tree
------------------------------------------------------------*/
GULAPI void InitBBT( BBTNode *head );

/*----------------------------------------------------------------------
  Search for an element in a balanced binary tree. If the element was found,
  the address of its node is returned, otherwise the position (address of node
  and side) in the tree is returned, under which the element would be
  inserted.  
------------------------------------------------------------------------*/
GULAPI int SearchElementInBBT( BBTNode *head, void *key,
                               int compare( void *, void * ),
                               BBTNode **element );
/* ---------------------------------------------------------------
  Find the successor of a given element in a balanced binary tree
----------------------------------------------------------------- */
GULAPI BBTNode *SearchSuccessorInBBT( BBTNode *element, BBTNode *head );

/* ---------------------------------------------------------------
  Find the predecessor of a given element in a balanced binary tree
----------------------------------------------------------------- */
GULAPI BBTNode *SearchPredecessorInBBT( BBTNode *element, BBTNode *head );

/*------------------------------------------------------------------------
  Inserts a node 'element' into a balanced binary tree, given by 'head'.
  The node is inserted under the node 'where' on the side 'side'.
  (side == -1 => left,  side == 1 => right )
------------------------------------------------------------------------*/
GULAPI void InsertElementIntoBBT( BBTNode *element, 
                              BBTNode *where, int side, BBTNode *head  );

/*------------------------------------------------------------------------
  Removes a node 'element' from a balanced binary tree 'head'.
  The tree will get rebalanced, if necessary.  
------------------------------------------------------------------------*/
GULAPI void DeleteElementFromBBT( BBTNode *element, BBTNode *head );

/*------------------------------------------------------------------------
  Dump BBT Tree (for debugging)
------------------------------------------------------------------------*/  
GULAPI void DumpBBTTree( BBTNode *node, int level,  
                         void dumpkey_func( void * ) );
GULAPI void DumpBBTNode( BBTNode *node, int level );


/*----------------------------------------------------------
  Heapsort (see "Numerical Recipes in C", or Knuth) 
-----------------------------------------------------------*/
GULAPI void HeapSort( size_t nelem, size_t elsize, void *elptr,
         int (*usrfunc)( void *, void *, void *), void *usrdata );
GULAPI void PtrHeapSort( size_t nelem, void **elptr,
         int (*usrfunc)( void *, void *, void *), void *usrdata );

/*----------------------------------------------------------
  Heapsort as template
-----------------------------------------------------------*/
template< class T >
inline void _heapsort( int nA, gul::Ptr<T>& A )
{
  gul::Ptr<T>& ra = A;
  T rra;
  int n = nA, l, ir, i, j;

  if( n < 2 ) return;
  l = (n >> 1) + 1;
  ir = n;
  
  for(;;)
  {
    if( l > 1 )
    {
      rra = ra[l-2];
      l--;    
    }
    else
    {
      rra = ra[ir-1];
      ra[ir-1] = ra[0];
      
      if( --ir == 1 )
      {
        ra[0] = rra;
        break;
      }
    }
    i = l;
    j = l+l;

    while( j <= ir )
    {
      if( (j < ir) && (ra[j-1] < ra[j]) )
        j++;
  
      if( rra < ra[j-1] )
      {
        ra[i-1] = ra[j-1];
        i = j;
        j <<= 1;
      }
      else
        j = ir + 1;
    }

    ra[i-1] = rra;
  }
}
// these are often used, so they are instantiated in the library
GULAPI void heapsort( int nA, gul::Ptr<void *>& A );
GULAPI void heapsort( int nA, gul::Ptr<int>& A );

/*------------------------------------------------------------------
  Binary search in a sorted array. Returns position of the searched
  element, or -1 if the array doesn't contains the element
------------------------------------------------------------------*/

template< class T >
inline int _BinarySearch( T x, int nA, const gul::Ptr<T>& A )
{
  int mid,right,left;

  if( nA == 0 ) return -1;

  if( A[0] >=  x )
  {
    if( A[0] > x ) return -1;
    return 0;
  }
  if( A[nA-1] <=  x )
  {
    if( A[nA-1] < x ) return -1;
    return nA-1;
  }

  left = 0;
  right = nA;
  mid = (left+right)/2;

  while( (mid!=left) && (mid!=right) )
  {  
    if( A[mid] == x  )
      break;
    else if( A[mid] > x )
    {
      right = mid;
      mid = (left+right)>>1;
    }
    else
    {
      left = mid;
      mid = (left+right)>>1;
    }
  }
  if( A[mid] != x ) return -1;

  return mid;
}

// these are often used, so they are instantiated in the library
GULAPI int BinarySearch( int x, int nA, const gul::Ptr<int>& A );
GULAPI int BinarySearch( void *x, int nA, const gul::Ptr<void *>& A );

/*------------------------------------------------------------------
  another binary search routine, slightly different from the above.
  it returns the indices of the nearest left and right neighbor elements,
  or -1 if one of these doesn't exists
------------------------------------------------------------------*/
template< class T >
inline int _BinarySearch( T x, int nA, const gul::Ptr<T>& A,
                          int *rleft, int *rright )
{
  int mid,right,left;

  if( nA == 0 ) 
  {
    *rleft = -1;
    *rright = -1;
    return -1;
  }

  if( A[0] >=  x )
  {
    *rright = 0;

    if( A[0] > x ) 
    {
      *rleft = -1; 
      return -1;
    }
    else
    {
      *rleft = 0;
      return 0;
    }
  }

  if( A[nA-1] <=  x )
  {
    *rleft = nA-1;

    if( A[nA-1] < x )
    {
      *rright = -1;
      return -1;
    }
    else
    {
      *rright = nA-1;
      return nA-1;
    }
  }

  left = 0;
  right = nA;
  mid = (left+right)/2;

  while( (mid!=left) && (mid!=right) )
  {  
    if( A[mid] == x  )
      break;
    else if( A[mid] > x )
    {
      right = mid;
      mid = (left+right)>>1;
    }
    else
    {
      left = mid;
      mid = (left+right)>>1;
    }
  }
  if( A[mid] != x )
  {
    *rleft = left;
    *rright = right;
    return -1;
  }
  else
  {
    *rleft = mid;
    *rright = mid;
  }
 
  return mid;
}



}

#endif

---