-/* 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
- 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/>. */
#ifndef LIBPSPP_ABT_H
#define LIBPSPP_ABT_H 1
part of its data as a function of its immediate children's
data. Furthermore, augmented data defined in this way can be
efficiently maintained as the tree changes over time.
-
+
For example, suppose we define the "size" of a node as the sum
of the "size" of its immediate children, plus 1. In such an
annotated BST with height H, we can find the node that would
The ABT data structure partially abstracts augmentation. The
client passes in a "reaugmentation" function that accepts a
- node and its left and right children. This function must
- recalculate the node's augmentation data based on its own
- contents and the contents of its children, and store the new
- augmentation data in the node.
+ node. This function must recalculate the node's augmentation
+ data based on its own contents and the contents of its
+ children, and store the new augmentation data in the node.
The ABT automatically calls the reaugmentation function
whenever it can tell that a node's augmentation data might
larger tree is rearranged, e.g. via a series of rotations,
then the implementation will not call the reaugmentation
function outside of the subtree, because the overall
- augmentation data for the subtree is assumed not to changed.
+ augmentation data for the subtree is assumed not to change.
This optimization is valid for the forms of augmentation
described in CLR and Knuth (see below), and it is possible
that it is valid for every efficient binary search tree
struct abt_node node; // Embedded binary tree element.
int data; // Primary value.
int count; // Number of nodes in subtree,
- // including this node.
+ // including this node.
};
// Returns the `struct element' that NODE is embedded within.
// strcmp-type return value.
static int
compare_elements (const struct abt_node *a_, const struct abt_node *b_,
- const void *aux)
+ const void *aux)
{
const struct element *a = node_to_element (a_);
const struct element *b = node_to_element (b_);
}
// Recalculates the count for NODE's subtree by adding up the
- // counts for its LEFT and RIGHT child subtrees.
+ // counts for its left and right child subtrees.
static void
- reaugment_elements (struct abt_node *node_,
- const struct abt_node *left,
- const struct abt_node *right,
- const void *aux)
+ reaugment_elements (struct abt_node *node_, const void *aux)
{
struct element *node = node_to_element (node_);
node->count = 1;
- if (left != NULL)
- node->count += node_to_element (left)->count;
- if (right != NULL)
- node->count += node_to_element (right)->count;
+ if (node->node.down[0] != NULL)
+ node->count += node_to_element (node->node.down[0])->count;
+ if (node->node.down[1] != NULL)
+ node->count += node_to_element (node->node.down[1])->count;
}
// Finds and returns the element in ABT that is in the given
// 0-based POSITION in in-order.
static struct element *
- find_by_position (struct abt *abt, int position)
+ find_by_position (struct abt *abt, int position)
{
struct abt_node *p;
- for (p = abt->root; p != NULL; )
+ for (p = abt->root; p != NULL; )
{
int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
if (position == p_pos)
return node_to_element (p);
else if (position < p_pos)
- p = p->down[0];
+ p = p->down[0];
else
{
p = p->down[1];
code and links to other resources, such as the original AA
tree paper. */
+#include <stdbool.h>
#include <stddef.h>
+#include "libpspp/cast.h"
/* Returns the data structure corresponding to the given NODE,
assuming that NODE is embedded as the given MEMBER name in
data type STRUCT. */
-#define abt_data(NODE, STRUCT, MEMBER) \
- ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+#define abt_data(NODE, STRUCT, MEMBER) \
+ (CHECK_POINTER_HAS_TYPE (NODE, struct abt_node *), \
+ UP_CAST (NODE, STRUCT, MEMBER))
/* Node in an augmented binary tree. */
-struct abt_node
+struct abt_node
{
struct abt_node *up; /* Parent (NULL for root). */
struct abt_node *down[2]; /* Left child, right child. */
const struct abt_node *b,
const void *aux);
-/* Recalculates NODE's augmentation based on NODE's data and that
- of its LEFT and RIGHT children, with the tree's AUX. */
-typedef void abt_reaugment_func (struct abt_node *node,
- const struct abt_node *left,
- const struct abt_node *right,
- const void *aux);
+/* Recalculates NODE's augmentation based on NODE's data and that of its left
+ and right children NODE->down[0] and NODE[1], respectively, with the tree's
+ AUX. */
+typedef void abt_reaugment_func (struct abt_node *node, const void *aux);
/* An augmented binary tree. */
-struct abt
+struct abt
{
struct abt_node *root; /* Tree's root, NULL if empty. */
abt_compare_func *compare; /* To compare nodes. */
void abt_init (struct abt *, abt_compare_func *, abt_reaugment_func *,
const void *aux);
+static inline bool abt_is_empty (const struct abt *);
+
struct abt_node *abt_insert (struct abt *, struct abt_node *);
+void abt_insert_after (struct abt *,
+ const struct abt_node *, struct abt_node *);
+void abt_insert_before (struct abt *,
+ const struct abt_node *, struct abt_node *);
void abt_delete (struct abt *, struct abt_node *);
struct abt_node *abt_first (const struct abt *);
struct abt_node *abt_changed (struct abt *, struct abt_node *);
void abt_moved (struct abt *, struct abt_node *);
+/* Returns true if ABT contains no nodes, false if ABT contains at least one
+ node. */
+static inline bool
+abt_is_empty (const struct abt *abt)
+{
+ return abt->root == NULL;
+}
+
#endif /* libpspp/abt.h */
projects / pspp / blobdiff