Update all #include directives to the currently preferred style.

[pspp-builds.git] / src / libpspp / abt.c

diff --git a/src/libpspp/abt.c b/src/libpspp/abt.c
index c181b90473f84b19590c572de6d9961aa40115c4..c06047b4abdbb8e128910a17049f972893abd295 100644 (file)
--- a/src/libpspp/abt.c
+++ b/src/libpspp/abt.c
@@ -1,20 +1,18 @@
-/* PSPP - computes sample statistics.
-   Copyright (C) 2007 Free Software Foundation, Inc.
+/* PSPP - a program for statistical analysis.
+   Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.

 
 

-   This program is free software; you can redistribute it and/or
-   modify it under the terms of the GNU General Public License as
-   published by the Free Software Foundation; either version 2 of the
-   License, or (at your option) any later version.
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.

 
 

-   This program 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
-   General Public License for more details.
+   This program 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 General Public License for more details.

 
    You should have received a copy of the GNU General Public License
 
    You should have received a copy of the GNU General Public License

-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-   02110-1301, USA. */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

 
 /* Augmented binary tree (ABT) data structure. */
 
 
 /* Augmented binary tree (ABT) data structure. */
 


@@ -30,20 +28,34 @@
 #include <config.h>
 #endif
 
 #include <config.h>
 #endif
 

-#include <libpspp/abt.h>
+#include "libpspp/abt.h"
+
+#include <stdbool.h>
+
+#include "libpspp/cast.h"
+#include "libpspp/assertion.h"

 
 static struct abt_node **down_link (struct abt *, struct abt_node *);
 static struct abt_node *skew (struct abt *, struct abt_node *);
 static struct abt_node *split (struct abt *, struct abt_node *);
 
 /* Initializes ABT as an empty ABT that uses COMPARE and
 
 static struct abt_node **down_link (struct abt *, struct abt_node *);
 static struct abt_node *skew (struct abt *, struct abt_node *);
 static struct abt_node *split (struct abt *, struct abt_node *);
 
 /* Initializes ABT as an empty ABT that uses COMPARE and

-   REAUGMENT functions, passing in AUX as auxiliary data. */
+   REAUGMENT functions, passing in AUX as auxiliary data.
+
+   The comparison function is optional.  If it is null, this
+   indicates that the tree is being used for its augmentations
+   only.  ABT functions that compare nodes may not be used with
+   trees that lack comparison functions; contrariwise, other
+   functions that could disrupt the ordering of a tree may not be
+   used if a comparison function is specified.  Refer to
+   individual function descriptions for details. */

 void
 abt_init (struct abt *abt,
           abt_compare_func *compare,
           abt_reaugment_func *reaugment,
 void
 abt_init (struct abt *abt,
           abt_compare_func *compare,
           abt_reaugment_func *reaugment,

-          const void *aux) 
+          const void *aux)

 {
 {

+  assert (reaugment != NULL);

   abt->root = NULL;
   abt->compare = compare;
   abt->reaugment = reaugment;
   abt->root = NULL;
   abt->compare = compare;
   abt->reaugment = reaugment;


@@ -53,24 +65,26 @@ abt_init (struct abt *abt,
 /* Inserts the given NODE into ABT.
    Returns a null pointer if successful.
    Returns the existing node already in ABT equal to NODE, on
 /* Inserts the given NODE into ABT.
    Returns a null pointer if successful.
    Returns the existing node already in ABT equal to NODE, on

-   failure. */
+   failure.
+   This function may be used only if ABT has a comparison
+   function. */

 struct abt_node *
 struct abt_node *

-abt_insert (struct abt *abt, struct abt_node *node) 
+abt_insert (struct abt *abt, struct abt_node *node)

 {
   node->down[0] = NULL;
   node->down[1] = NULL;
   node->level = 1;
 
 {
   node->down[0] = NULL;
   node->down[1] = NULL;
   node->level = 1;
 

-  if (abt->root == NULL) 
+  if (abt->root == NULL)

     {
       abt->root = node;
       node->up = NULL;
       abt_reaugmented (abt, node);
     }
     {
       abt->root = node;
       node->up = NULL;
       abt_reaugmented (abt, node);
     }

-  else 
+  else

     {
       struct abt_node *p = abt->root;
     {
       struct abt_node *p = abt->root;

-      for (;;) 
+      for (;;)

         {
           int cmp, dir;
 
         {
           int cmp, dir;
 


@@ -87,10 +101,10 @@ abt_insert (struct abt *abt, struct abt_node *node)
               break;
             }
           p = p->down[dir];
               break;
             }
           p = p->down[dir];

-        } 
+        }

     }
 
     }
 

-  while ((node = node->up) != NULL) 
+  while ((node = node->up) != NULL)

     {
       node = skew (abt, node);
       node = split (abt, node);
     {
       node = skew (abt, node);
       node = split (abt, node);


@@ -99,6 +113,77 @@ abt_insert (struct abt *abt, struct abt_node *node)
   return NULL;
 }
 
   return NULL;
 }
 

+/* Inserts NODE before or after node P in ABT, depending on the
+   value of AFTER.
+   If P is null, then the node is inserted as the first node in
+   the tree, if AFTER is true, or the last node, if AFTER is
+   false. */
+static inline void
+insert_relative (struct abt *abt, const struct abt_node *p, bool after,
+                 struct abt_node *node)
+{
+  node->down[0] = NULL;
+  node->down[1] = NULL;
+  node->level = 1;
+
+  if (abt->root == NULL)
+    {
+      assert (p == NULL);
+      abt->root = node;
+      node->up = NULL;
+      abt_reaugmented (abt, node);
+    }
+  else
+    {
+      int dir = after;
+      if (p == NULL)
+        {
+          p = abt->root;
+          dir = !after;
+        }
+      while (p->down[dir] != NULL)
+        {
+          p = p->down[dir];
+          dir = !after;
+        }
+      CONST_CAST (struct abt_node *, p)->down[dir] = node;
+      node->up = CONST_CAST (struct abt_node *, p);
+      abt_reaugmented (abt, node);
+    }
+
+  while ((node = node->up) != NULL)
+    {
+      node = skew (abt, node);
+      node = split (abt, node);
+    }
+}
+
+/* Inserts NODE after node P in ABT.
+   If P is null, then the node is inserted as the first node in
+   the tree.
+   This function may be used only if ABT lacks a comparison
+   function. */
+void
+abt_insert_after (struct abt *abt,
+                  const struct abt_node *p, struct abt_node *node)
+{
+  assert (abt->compare == NULL);
+  insert_relative (abt, p, true, node);
+}
+
+/* Inserts NODE before node P in ABT.
+   If P is null, then the node is inserted as the last node in
+   the tree.
+   This function may be used only if ABT lacks a comparison
+   function. */
+void
+abt_insert_before (struct abt *abt,
+                   const struct abt_node *p, struct abt_node *node)
+{
+  assert (abt->compare == NULL);
+  insert_relative (abt, p, false, node);
+}
+

 /* Deletes P from ABT. */
 void
 abt_delete (struct abt *abt, struct abt_node *p)
 /* Deletes P from ABT. */
 void
 abt_delete (struct abt *abt, struct abt_node *p)


@@ -159,44 +244,46 @@ abt_delete (struct abt *abt, struct abt_node *p)
 }
 
 /* Returns the node with minimum value in ABT, or a null pointer
 }
 
 /* Returns the node with minimum value in ABT, or a null pointer

-   if ABT is empty. */ 
+   if ABT is empty. */

 struct abt_node *
 struct abt_node *

-abt_first (const struct abt *abt) 
+abt_first (const struct abt *abt)

 {
   struct abt_node *p = abt->root;
 {
   struct abt_node *p = abt->root;

-  if (p != NULL) 
+  if (p != NULL)

     while (p->down[0] != NULL)
       p = p->down[0];
   return p;
 }
 
 /* Returns the node with maximum value in ABT, or a null pointer
     while (p->down[0] != NULL)
       p = p->down[0];
   return p;
 }
 
 /* Returns the node with maximum value in ABT, or a null pointer

-   if ABT is empty. */ 
+   if ABT is empty. */

 struct abt_node *
 struct abt_node *

-abt_last (const struct abt *abt) 
+abt_last (const struct abt *abt)

 {
   struct abt_node *p = abt->root;
 {
   struct abt_node *p = abt->root;

-  if (p != NULL) 
+  if (p != NULL)

     while (p->down[1] != NULL)
       p = p->down[1];
   return p;
 }
 
 /* Searches ABT for a node equal to TARGET.
     while (p->down[1] != NULL)
       p = p->down[1];
   return p;
 }
 
 /* Searches ABT for a node equal to TARGET.

-   Returns the node if found, or a null pointer otherwise. */
+   Returns the node if found, or a null pointer otherwise.
+   This function may be used only if ABT has a comparison
+   function. */

 struct abt_node *
 abt_find (const struct abt *abt, const struct abt_node *target)
 {
   const struct abt_node *p;
   int cmp;
 struct abt_node *
 abt_find (const struct abt *abt, const struct abt_node *target)
 {
   const struct abt_node *p;
   int cmp;

-  
+

   for (p = abt->root; p != NULL; p = p->down[cmp > 0])
     {
       cmp = abt->compare (target, p, abt->aux);
       if (cmp == 0)
   for (p = abt->root; p != NULL; p = p->down[cmp > 0])
     {
       cmp = abt->compare (target, p, abt->aux);
       if (cmp == 0)

-        return (struct abt_node *) p;
+        return CONST_CAST (struct abt_node *, p);

     }
     }

-  
+

   return NULL;
 }
 
   return NULL;
 }
 


@@ -205,9 +292,9 @@ abt_find (const struct abt *abt, const struct abt_node *target)
    Returns a null pointer if P is the maximum node in ABT or if P
    is null and ABT is empty. */
 struct abt_node *
    Returns a null pointer if P is the maximum node in ABT or if P
    is null and ABT is empty. */
 struct abt_node *

-abt_next (const struct abt *abt, const struct abt_node *p) 
+abt_next (const struct abt *abt, const struct abt_node *p)

 {
 {

-  if (p == NULL) 
+  if (p == NULL)

     return abt_first (abt);
   else if (p->down[1] == NULL)
     {
     return abt_first (abt);
   else if (p->down[1] == NULL)
     {


@@ -221,7 +308,7 @@ abt_next (const struct abt *abt, const struct abt_node *p)
       p = p->down[1];
       while (p->down[0] != NULL)
         p = p->down[0];
       p = p->down[1];
       while (p->down[0] != NULL)
         p = p->down[0];

-      return (struct abt_node *) p;
+      return CONST_CAST (struct abt_node *, p);

     }
 }
 
     }
 }
 


@@ -230,9 +317,9 @@ abt_next (const struct abt *abt, const struct abt_node *p)
    Returns a null pointer if P is the minimum node in ABT or if P
    is null and ABT is empty. */
 struct abt_node *
    Returns a null pointer if P is the minimum node in ABT or if P
    is null and ABT is empty. */
 struct abt_node *

-abt_prev (const struct abt *abt, const struct abt_node *p) 
+abt_prev (const struct abt *abt, const struct abt_node *p)

 {
 {

-  if (p == NULL) 
+  if (p == NULL)

     return abt_last (abt);
   else if (p->down[0] == NULL)
     {
     return abt_last (abt);
   else if (p->down[0] == NULL)
     {


@@ -246,7 +333,7 @@ abt_prev (const struct abt *abt, const struct abt_node *p)
       p = p->down[0];
       while (p->down[1] != NULL)
         p = p->down[1];
       p = p->down[0];
       while (p->down[1] != NULL)
         p = p->down[1];

-      return (struct abt_node *) p;
+      return CONST_CAST (struct abt_node *, p);

     }
 }
 
     }
 }
 


@@ -261,7 +348,7 @@ abt_prev (const struct abt *abt, const struct abt_node *p)
    affected nodes from the tree, update their values, then
    re-insert all of them. */
 void
    affected nodes from the tree, update their values, then
    re-insert all of them. */
 void

-abt_reaugmented (const struct abt *abt, struct abt_node *p) 
+abt_reaugmented (const struct abt *abt, struct abt_node *p)

 {
   for (; p != NULL; p = p->up)
     abt->reaugment (p, p->down[0], p->down[1], abt->aux);
 {
   for (; p != NULL; p = p->up)
     abt->reaugment (p, p->down[0], p->down[1], abt->aux);


@@ -276,29 +363,33 @@ abt_reaugmented (const struct abt *abt, struct abt_node *p)
    can actually retain its relative position in ABT, e.g. its key
    has only been adjusted slightly.  Otherwise, it is more
    efficient to simply remove P from ABT, change its key, and
    can actually retain its relative position in ABT, e.g. its key
    has only been adjusted slightly.  Otherwise, it is more
    efficient to simply remove P from ABT, change its key, and

-   re-insert P.  
+   re-insert P.

 
    It is not safe to update more than one node's key, then to
    call this function for each node.  Instead, update a single
    node's key, call this function, update another node's key, and
    so on.  Alternatively, remove all affected nodes from the
 
    It is not safe to update more than one node's key, then to
    call this function for each node.  Instead, update a single
    node's key, call this function, update another node's key, and
    so on.  Alternatively, remove all affected nodes from the

-   tree, update their keys, then re-insert all of them. */
+   tree, update their keys, then re-insert all of them.
+
+   This function may be used only if ABT has a comparison
+   function.  If it doesn't, then you probably just want
+   abt_reaugmented. */

 struct abt_node *
 struct abt_node *

-abt_changed (struct abt *abt, struct abt_node *p) 
+abt_changed (struct abt *abt, struct abt_node *p)

 {
   struct abt_node *prev = abt_prev (abt, p);
   struct abt_node *next = abt_next (abt, p);
 
   if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
 {
   struct abt_node *prev = abt_prev (abt, p);
   struct abt_node *next = abt_next (abt, p);
 
   if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)

-      || (next != NULL && abt->compare (p, next, abt->aux) >= 0)) 
+      || (next != NULL && abt->compare (p, next, abt->aux) >= 0))

     {
       abt_delete (abt, p);
       return abt_insert (abt, p);
     }
     {
       abt_delete (abt, p);
       return abt_insert (abt, p);
     }

-  else 
+  else

     {
       abt_reaugmented (abt, p);
     {
       abt_reaugmented (abt, p);

-      return NULL; 
+      return NULL;

     }
 }
 
     }
 }
 


@@ -312,14 +403,17 @@ abt_changed (struct abt *abt, struct abt_node *p)
    function for each node.  Instead, move a single node, call
    this function, move another node, and so on.  Alternatively,
    remove all affected nodes from the tree, move them, then
    function for each node.  Instead, move a single node, call
    this function, move another node, and so on.  Alternatively,
    remove all affected nodes from the tree, move them, then

-   re-insert all of them. */
+   re-insert all of them.
+
+   This function may be used only if ABT has a comparison
+   function. */

 void
 void

-abt_moved (struct abt *abt, struct abt_node *p) 
+abt_moved (struct abt *abt, struct abt_node *p)

 {
 {

-  if (p->up != NULL) 
+  if (p->up != NULL)

     {
       int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
     {
       int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;

-      p->up->down[d] = p; 
+      p->up->down[d] = p;

     }
   else
     abt->root = p;
     }
   else
     abt->root = p;


@@ -332,7 +426,7 @@ abt_moved (struct abt *abt, struct abt_node *p)
 /* Returns the address of the pointer that points down to P
    within ABT. */
 static struct abt_node **
 /* Returns the address of the pointer that points down to P
    within ABT. */
 static struct abt_node **

-down_link (struct abt *abt, struct abt_node *p) 
+down_link (struct abt *abt, struct abt_node *p)

 {
   return (p->up != NULL
           ? &p->up->down[p->up->down[0] != p]
 {
   return (p->up != NULL
           ? &p->up->down[p->up->down[0] != p]