/* PSPP - a program for statistical analysis.
- Copyright (C) 2007, 2009 Free Software Foundation, Inc.
+ 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
#include <config.h>
-#include <libpspp/tower.h>
+#include "libpspp/tower.h"
#include <limits.h>
-#include <libpspp/assertion.h>
-#include <libpspp/cast.h>
-#include <libpspp/compiler.h>
+#include "libpspp/assertion.h"
+#include "libpspp/cast.h"
+#include "libpspp/compiler.h"
static struct tower_node *abt_to_tower_node (const struct abt_node *);
static struct tower_node *first_node (const struct tower *);
const struct tower_node *);
static unsigned long int get_subtree_size (const struct abt_node *);
static unsigned long int get_subtree_count (const struct abt_node *);
-static void reaugment_tower_node (struct abt_node *,
- const struct abt_node *,
- const struct abt_node *,
- const void *aux);
+static void reaugment_tower_node (struct abt_node *, const void *aux);
/* Returns the height of the bottom of the given tower NODE.
{
const struct abt_node *p = &node->abt_node;
unsigned long level = get_subtree_size (p->down[0]);
- while (p->up != NULL)
+ while (p->up != NULL)
{
if (p == p->up->down[1])
- level += (get_subtree_size (p->up->down[0])
+ level += (get_subtree_size (p->up->down[0])
+ abt_to_tower_node (p->up)->size);
p = p->up;
}
{
const struct abt_node *p = &node->abt_node;
unsigned long index = get_subtree_count (p->down[0]);
- while (p->up != NULL)
+ while (p->up != NULL)
{
if (p == p->up->down[1])
index += get_subtree_count (p->up->down[0]) + 1;
less than the number of nodes in T (as returned by
tower_count). */
struct tower_node *
-tower_get (const struct tower *t_, unsigned long int index)
+tower_get (const struct tower *t_, unsigned long int index)
{
struct tower *t = CONST_CAST (struct tower *, t_);
struct abt_node *p;
return p != NULL ? abt_to_tower_node (p)->subtree_count : 0;
}
-/* Recalculates the subtree_size of NODE based on its LEFT and
- RIGHT children's subtree_sizes. */
+/* Recalculates the subtree_size of NODE based on the subtree_sizes of its
+ children. */
static void
-reaugment_tower_node (struct abt_node *node_,
- const struct abt_node *left,
- const struct abt_node *right,
- const void *aux UNUSED)
+reaugment_tower_node (struct abt_node *node_, const void *aux UNUSED)
{
struct tower_node *node = abt_to_tower_node (node_);
node->subtree_size = node->size;
node->subtree_count = 1;
- if (left != NULL)
+
+ if (node->abt_node.down[0] != NULL)
{
- struct tower_node *left_node = abt_to_tower_node (left);
- node->subtree_size += left_node->subtree_size;
- node->subtree_count += left_node->subtree_count;
+ struct tower_node *left = abt_to_tower_node (node->abt_node.down[0]);
+ node->subtree_size += left->subtree_size;
+ node->subtree_count += left->subtree_count;
}
- if (right != NULL)
+
+ if (node->abt_node.down[1] != NULL)
{
- struct tower_node *right_node = abt_to_tower_node (right);
- node->subtree_size += right_node->subtree_size;
- node->subtree_count += right_node->subtree_count;
+ struct tower_node *right = abt_to_tower_node (node->abt_node.down[1]);
+ node->subtree_size += right->subtree_size;
+ node->subtree_count += right->subtree_count;
}
}