klish/lub/bintree/bintree_splay.c

/*********************** -*- Mode: C -*- ***********************
 * File            : bintree_splay.c
 *---------------------------------------------------------------
 * Description
 * ===========
 *              An implementation of top-down splaying
 *                  D. Sleator <sleator@cs.cmu.edu>
 *  	                     March 1992
 *
 * "Splay trees", or "self-adjusting search trees" are a simple and
 * efficient data structure for storing an ordered set.  The data
 * structure consists of a binary tree, without parent pointers, and
 * no additional fields.  It allows searching, insertion, deletion,
 * deletemin, deletemax, splitting, joining, and many other
 * operations, all with amortized logarithmic performance.  Since the
 * trees adapt to the sequence of requests, their performance on real
 * access patterns is typically even better.  Splay trees are
 * described in a number of texts and papers [1,2,3,4,5].
 *
 * The code here is adapted from simple top-down splay, at the bottom
 * of page 669 of [3].  It can be obtained via anonymous ftp from
 * spade.pc.cs.cmu.edu in directory /usr/sleator/public.
 * 
 * The chief modification here is that the splay operation works even
 * if the item being splayed is not in the tree, and even if the tree
 * root of the tree is NULL.  So the line:
 *
 *                            t = splay(i, t);
 *
 * causes it to search for item with key i in the tree rooted at t.
 * If it's there, it is splayed to the root.  If it isn't there,
 * then the node put at the root is the last one before NULL that
 * would have been reached in a normal binary search for i.  (It's a
 * neighbor of i in the tree.)  This allows many other operations to
 * be easily implemented, as shown below.
 *
 * [1] "Fundamentals of data structures in C", Horowitz, Sahni,
 *      and Anderson-Freed, Computer Science Press, pp 542-547.
 * [2] "Data Structures and Their Algorithms", Lewis and Denenberg,
 *      Harper Collins, 1991, pp 243-251.
 * [3] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
 *     JACM Volume 32, No 3, July 1985, pp 652-686.
 * [4] "Data Structure and Algorithm Analysis", Mark Weiss,
 *      Benjamin Cummins, 1992, pp 119-130.
 * [5] "Data Structures, Algorithms, and Performance", Derick Wood,
 *      Addison-Wesley, 1993, pp 367-375.
 *
 * The following code was written by Daniel Sleator, and is released
 * in the public domain.
 *
 *---------------------------------------------------------------
 * Author          : Graeme McKerrell
 * Created On      : Wed Jan 28 16:29:28 2004
 * Status          : TESTED
 *---------------------------------------------------------------
 * HISTORY
 * 7-Dec-2004		Graeme McKerrell	
 *    Renamed to the "lub_" namespace
 * 5-May-2004		Graeme McKerrell	
 *    updates following review
 * 2-Mar-2004		Graeme McKerrell	
 *    Fixed to account for comparision logic being (node - key)
 *    original algorithm expected (key - node)
 * 9-Feb-2004		Graeme McKerrell	
 *    updated to use new node,key comparison ordering
 * 28-Jan-2004		Graeme McKerrell	
 *    Adapted from original public domain code
 *---------------------------------------------------------------
 * Copyright (C) 2004 3Com Corporation. All Rights Reserved.
 **************************************************************** */
#include "private.h"

/*--------------------------------------------------------- */
lub_bintree_node_t *
lub_bintree_splay (const lub_bintree_t *this,
                   lub_bintree_node_t  *t,
                   const void          *key)
{
        /* Simple top down splay, not requiring "key" to be in the tree t.  */
        /* What it does is described above.                                 */
        lub_bintree_node_t N, *leftTreeMax, *rightTreeMin, *y;
        int                comp;
        
        if (t == NULL)
                return t;
        N.left = N.right = NULL;
        leftTreeMax = rightTreeMin = &N;
        
        for (;;)
        {
                comp = lub_bintree_compare(this,t,key);
                if (comp > 0)
                {
                        if (t->left == NULL)
                                break;
                        if (lub_bintree_compare(this,t->left,key) > 0)
                        {
                                y        = t->left; /* rotate right */
                                t->left  = y->right;
                                y->right = t;
                                t        = y;
                                if (t->left == NULL)
                                        break;
                        }
                        rightTreeMin->left = t; /* link right */
                        rightTreeMin       = t;
                        t                  = t->left;
                }
                else if (comp < 0)
                {
                        if (t->right == NULL)
                                break;
                        if (lub_bintree_compare(this,t->right,key) < 0)
                        {
                                y        = t->right; /* rotate left */
                                t->right = y->left;
                                y->left  = t;
                                t        = y;
                                if (t->right == NULL)
                                        break;
                        }
                        leftTreeMax->right = t; /* link left */
                        leftTreeMax        = t;
                        t                  = t->right;
                }
                else
                {
                        break;
                }
        }
        leftTreeMax->right = t->left; /* assemble */
        rightTreeMin->left = t->right;
        t->left            = N.right;
        t->right           = N.left;
        
        /* return the new root */
        return t;
}
/*--------------------------------------------------------- */