hilbert.c

贝叶斯算法：盲分离技术

    }

// Collect addresses of two freed leaves
    List[Natoms].Base = del;
    List[Natoms].Free = kill;

// Update depth information back up tree, and equilibrate accordingly
    Balance(sibling);
    return 0;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  FindOrder
//
// Purpose:   Find n'th atom in ordered list, or NULL if out of range.
//            Inverse of OrderNum.
//
// History:   John Skilling   10 Sep 2001
//-----------------------------------------------------------------------------
// 
pAtom FindOrder(          //   O  & required atom
      int       n,        // I    order number (0,1,...,NumAtoms-1)
const Node*     psLink)   // I    Linked list
{
    pNode  node;
    if( n < 0 || n >= NumAtoms(psLink) )
        return NULL;
    n++;
    node = psLink->atom->Free;
    while( node->depth )
    {
        if( n >= node->lo->number )
        {
            n -= node->lo->number;
            node = node->hi;
        }
        else
            node = node->lo;
    }
    return node->atom;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  FindLeft
//
// Purpose:   Find atom at or left of label.
//            If absent,  return NULL.
//            If present, return right-hand such atom.
//
// History:   John Skilling   6 Mar 1996, 30 Dec 1997, 21 Jan 1998, 12 Apr 2001
//-----------------------------------------------------------------------------
// 
pAtom FindLeft(            //   O  & required atom
      coord_t*  Label,     // I    Label limit
const Node*     psLink)    // I    Linked list
{
    int    Ndim = psLink->number;
    pNode  node = psLink->atom->Free;
    if( Ndim <= 0 )
        return NULL;
    while( node->depth )
        node = ( CmpLabel(Label, node->hi->atom->Label, Ndim) < 0 )
              ? node->lo : node->hi;
    return node->lo ? node->atom : NULL;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  FindRight
//
// Purpose:   Find atom at or right of label.
//            If absent,  return NULL.
//            If present, return left-hand such atom.
//
// History:   John Skilling   12 Apr 2001
//-----------------------------------------------------------------------------
// 
pAtom FindRight(           //   O  & required atom
      coord_t*  Label,     // I    Label limit
const Node*     psLink)    // I    Linked list
{
    int    Ndim = psLink->number;
    pNode  node = psLink->atom->Free;
    if( Ndim <= 0 )
        return NULL;
    while( node->depth )
        node = ( CmpLabel(Label, node->hi->atom->Label, Ndim) <= 0 )
              ? node->lo : node->hi;
    return node->hi ? node->hi->atom : NULL;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  FindHere
//
// Purpose:   Find atom exactly at label.
//            If absent,  return NULL.
//            If present, return address.
//
// History:   John Skilling   2 Dec 2001
//-----------------------------------------------------------------------------
// 
pAtom FindHere(            //   O  & required atom
      coord_t*  Label,     // I    Label limit
const Node*     psLink)    // I    Linked list
{
    int    Ndim = psLink->number;
    pNode  node = psLink->atom->Free;
    if( Ndim <= 0 )
        return NULL;
    while( node->depth )
        node = ( CmpLabel(Label, node->hi->atom->Label, Ndim) < 0 )
              ? node->lo : node->hi;
    if( node->lo && CmpLabel(Label, node->atom->Label, Ndim) == 0 )
        return node->atom;
    else
        return NULL;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  EndLink
//
// Purpose:   Find right-most atom.
//
// History:   John Skilling   12 Apr 2001
//-----------------------------------------------------------------------------
// 
pAtom EndLink(             //   O  & atom in required label range
const Node*    psLink)     // I    Linked list
{
    pNode  node;
    if( NumAtoms(psLink) )
    {
        node = psLink->atom->Free;
        while( node->depth )
            node = node->hi;
        return node->atom;
    }
    else
        return NULL;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  Storage
//
// Purpose:   Locate atom in current storage list.  Inverse of FindAtom.
//
// History:   John Skilling   22 Jan 2003
//-----------------------------------------------------------------------------
// 
int Storage(    //   O  location in current storage list 0,,..,NumAtoms-1
pAtom   atom)   // I    & atom in list
{
    pNode  node;
    for( node = atom->Base; node->parent; node = node->parent );
    return  atom - node->atom - 1;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  OrderNum
//
// Purpose:   Order number of atom in linked list.  Inverse of FindOrder.
//
// History:   John Skilling   22 Jan 2003
//-----------------------------------------------------------------------------
// 
int OrderNum(   //   O  location in ordered list 0,1,..,NumAtoms-1
pAtom   atom)   // I    & atom in list
{
    pNode  node;
    int    number = -1;
    for( node = atom->Base; node->parent; node = node->parent )
        if( node == node->parent->hi )
            number += node->parent->lo->number;
    return  number;
}

//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Function:  Balance
//
// Purpose:   Re-balance the tree depths, after insertion or deletion.
//
// History:   John Skilling   25 Jan 1996, 10 Sep 2001
//=============================================================================
//           Original configurations      Final configurations
//  
//  Case A               /                        /
//                     Node                     Node
//                    /    \                    /    \.
//                   /     Node              Node     \.
//                  /     /    \            /    \     \.
//  
//
//  Case B               /                        /
//                     Node                     Node
//                    /    \                   /    \.
//                   /     Node             Node    Node
//                  /     /   \             /  \    /  \.
//                 /   Node    \. 
//                /    /   \    \.
//
//  
//  Case C               /                        /             
//                     Node                     Node
//                    /    \                   /    \.
//                 Node     \                 /     Node
//                /    \     \               /     /    \.
//  
//  
//  Case D               /                        /
//                     Node                     Node
//                    /    \                   /    \.
//                 Node     \               Node    Node
//                 /   \     \              /  \    /  \.
//                /    Node   \. 
//               /    /   \    \.
//  
//-----------------------------------------------------------------------------
// 
static void Balance(
pNode   node)          // I    Base node of revised tree
{
#define DEPTH(x,y)    (((x) > (y) ? (x) : (y)) + 1)
    pNode t;                // Temporary pointer for swapping
    int   asymmetry;        // Depth difference between branches
    int   deep;             // Recalculated depth of node

    for( node = node->parent; node; node = node->parent )
    {
        asymmetry = node->hi->depth - node->lo->depth;
        if( asymmetry > 1 )
        {
            if( node->hi->hi->depth >= node->hi->lo->depth )
            {
// Case A
                t         = node->hi;
                node->hi  = t->hi;       node->hi->parent = node;
                t->hi     = t->lo;
                t->lo     = node->lo;    t->lo->parent    = t;
                node->lo  = t;
                t->atom   = node->atom;
                t->depth  = DEPTH(t->hi->depth, t->lo->depth);
                t->number = t->hi->number + t->lo->number;
            }
            else
            {
// Case B
                t = node->hi->lo;
                node->hi->atom = t->hi->atom;
                t->atom = node->atom;
                node->hi->lo = t->hi;       t->hi->parent = node->hi;
                t->hi = t->lo;
                t->lo = node->lo;           t->lo->parent = t;
                node->lo = t;               t->parent = node;
                t->depth  = DEPTH(t->hi->depth, t->lo->depth);
                t->number = t->hi->number + t->lo->number;
                t = node->hi;
                t->depth  = DEPTH(t->hi->depth, t->lo->depth);
                t->number = t->hi->number + t->lo->number;
            }
        }
        if( asymmetry < -1 )
        {
            if( node->lo->lo->depth >= node->lo->hi->depth )
            {
// Case C
                t         = node->lo;
                node->lo  = t->lo;       node->lo->parent = node;
                t->lo     = t->hi;
                t->hi     = node->hi;    t->hi->parent    = t;
                node->hi  = t;
                t->atom   = t->lo->atom;
                t->depth  = DEPTH(t->hi->depth, t->lo->depth);
                t->number = t->hi->number + t->lo->number;
            }
            else
            {
// Case D
                t = node->lo->hi;
                t->atom = t->hi->atom;
                node->lo->hi = t->lo;       t->lo->parent = node->lo;
                t->lo = t->hi;
                t->hi = node->hi;           t->hi->parent = t;
                node->hi  = t;              t->parent = node;
                t->depth  = DEPTH(t->hi->depth, t->lo->depth);
                t->number = t->hi->number + t->lo->number;
                t = node->lo;
                t->depth  = DEPTH(t->hi->depth, t->lo->depth);
                t->number = t->hi->number + t->lo->number;
            }
        }
        deep = node->depth;
        node->depth  = DEPTH(node->hi->depth, node->lo->depth);
        node->number = node->hi->number + node->lo->number;
        if( node->depth == deep )
            break;
    }
    for( ; node; node = node->parent )
        node->number = node->hi->number + node->lo->number;
}