Changeset 3555 for trunk/kStuff/include/k/kAVLTmpl/kAVLGetBestFit.h

Timestamp:

Aug 26, 2007, 12:43:27 PM (18 years ago)

Author:

bird

Message:

Merging in kAvl enhancements, doing some config simplications and made them inlineable.

File:

• trunk/kStuff/include/k/kAVLTmpl/kAVLGetBestFit.h (modified) (1 diff)

trunk/kStuff/include/k/kAVLTmpl/kAVLGetBestFit.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLGetBestFit - Get Best Fit routine for AVL trees.
- *                  Intended specially on heaps. The tree should allow duplicate keys.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Get Best Fitting Node.
  */
 
-#ifndef _kAVLGetBestFit_h_
-#define _kAVLGetBestFit_h_
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
  * Finds the best fitting node in the tree for the given Key value.
- * @returns   Pointer to the best fitting node found.
- * @param     ppTree  Pointer to Pointer to the tree root node.
- * @param     Key     The Key of which is to be found a best fitting match for..
- * @param     fAbove  TRUE:  Returned node is have the closest key to Key from above.
- *                    FALSE: Returned node is have the closest key to Key from below.
- * @status    completely implemented.
- * @sketch    The best fitting node is always located in the searchpath above you.
- *            >= (above): The node where you last turned left.
- *            <= (below): the node where you last turned right.
- * @author    knut st. osmundsen
+ *
+ * @returns Pointer to the best fitting node found.
+ * @param   ppTree      Pointer to Pointer to the tree root node.
+ * @param   Key         The Key of which is to be found a best fitting match for..
+ * @param   fAbove      K_TRUE:  Returned node is have the closest key to Key from above.
+ *                      K_FALSE: Returned node is have the closest key to Key from below.
+ * @sketch  The best fitting node is always located in the searchpath above you.
+ *          >= (above): The node where you last turned left.
+ *          <= (below): the node where you last turned right.
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(GetBestFit)(PPKAVLNODECORE ppTree, KAVLKEY Key, KBOOL fAbove)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
 {
-    KLOGENTRY3("PKAVLNODECORE","PPKAVLNODECORE ppTree, KAVLKEY Key, KBOOL fAbove", ppTree, Key, fAbove);
-    #ifdef AVL_CMP
-    register int            iDiff;
-    #endif
-    register PKAVLNODECORE   pNode = *ppTree;
-    PKAVLNODECORE            pNodeLast = NULL;
+    register KAVLNODECORE *pNode;
+    KAVLNODECORE *pNodeLast;
 
+    if (*ppTree == KAVL_NULL)
+        return NULL;
+
+    pNode = KAVL_GET_POINTER(ppTree);
+    pNodeLast = NULL;
     if (fAbove)
     {   /* pNode->Key >= Key */
-        #ifndef AVL_CMP
-        while (pNode != NULL && AVL_NE(pNode->Key, Key))
-        #else
-        while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-        #endif
+        while (KAVL_NE(pNode->Key, Key))
         {
-            #ifndef AVL_CMP
-            if (AVL_G(pNode->Key, Key))
-            #else
-            if (iDiff > 0)
-            #endif
+            if (KAVL_G(pNode->Key, Key))
             {
+                if (pNode->pLeft == KAVL_NULL)
+                    return pNode;
                 pNodeLast = pNode;
-                pNode = pNode->pLeft;
+                pNode = KAVL_GET_POINTER(&pNode->pLeft);
             }
             else
-                pNode = pNode->pRight;
+            {
+                if (pNode->pRight == KAVL_NULL)
+                    return pNodeLast;
+                pNode = KAVL_GET_POINTER(&pNode->pRight);
+            }
         }
     }
     else
     {   /* pNode->Key <= Key */
-        #ifndef AVL_CMP
-        while (pNode != NULL && AVL_NE(pNode->Key, Key))
-        #else
-        while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-        #endif
+        while (KAVL_NE(pNode->Key, Key))
         {
-            #ifndef AVL_CMP
-            if (AVL_L(pNode->Key, Key))
-            #else
-            if (iDiff < 0)
-            #endif
+            if (KAVL_G(pNode->Key, Key))
             {
-                pNodeLast = pNode;
-                pNode = pNode->pRight;
+                if (pNode->pLeft == KAVL_NULL)
+                    return pNodeLast;
+                pNode = KAVL_GET_POINTER(&pNode->pLeft);
             }
             else
-                pNode = pNode->pLeft;
+            {
+                if (pNode->pRight == KAVL_NULL)
+                    return pNode;
+                pNodeLast = pNode;
+                pNode = KAVL_GET_POINTER(&pNode->pRight);
+            }
         }
     }
 
-    KLOGEXIT(pNode == NULL ? pNodeLast /* best fit */ : pNode /* perfect match */);
-    return pNode == NULL ? pNodeLast /* best fit */ : pNode /* perfect match */;
+    /* perfect match or nothing. */
+    return pNode;
 }
 
-
-#endif