/* 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 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.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

/* Bitmap, implemented as a balanced binary tree. */

/* If you add routines in this file, please add a corresponding
   test to range-tower-test.c.  This test program should achieve
   100% coverage of lines and branches in this code, as reported
   by "gcov -b". */

#include <config.h>

#include "libpspp/range-tower.h"

#include <limits.h>
#include <stdlib.h>

#include "libpspp/assertion.h"
#include "libpspp/compiler.h"
#include "libpspp/pool.h"

#include "gl/minmax.h"
#include "gl/xalloc.h"

static void reaugment_range_tower_node (struct abt_node *, const void *aux);
static void delete_node (struct range_tower *, struct range_tower_node *);

static void destroy_pool (void *);

static void
print_structure (const struct abt_node *node_)
{
  struct range_tower_node *node;

  if (node_ == NULL)
    return;
  node = abt_data (node_, struct range_tower_node, abt_node);
  printf ("%lu+%lu/%d", node->n_zeros, node->n_ones, node->abt_node.level);
  if (node->abt_node.down[0] || node->abt_node.down[1])
    {
      printf ("(");
      print_structure (node->abt_node.down[0]);
      printf (",");
      print_structure (node->abt_node.down[1]);
      printf (")");
    }
}

/* Prints the regions in RT to stdout. */
static void UNUSED
print_regions (const char *title, const struct range_tower *rt)
{
  const struct range_tower_node *node;

  printf ("%s:", title);
  for (node = range_tower_first__ (rt); node != NULL;
       node = range_tower_next__ (rt, node))
    printf (" (%lu,%lu)", node->n_zeros, node->n_ones);
  printf ("\n");
  printf ("structure:");
  print_structure (rt->abt.root);
  printf ("\n");
}

static struct range_tower_node *
range_tower_node_from_abt_node (const struct abt_node *abt_node)
{
  return abt_data (abt_node, struct range_tower_node, abt_node);
}

/* Returns the total width (zeros and ones) of the nodes in the subtree rooted
   at P, or 0 if P is null. */
static unsigned long int
subtree_width (const struct abt_node *p)
{
  return p != NULL ? range_tower_node_from_abt_node (p)->subtree_width : 0;
}

/* Returns the position of the first 1-bit in NODE.

   The performance of this function is O(lg n) in the number of nodes in the
   range tower.  It is often possible to avoid calling this function, either by
   taking advantage of the NODE_START parameter to tower_lookup or by
   incrementally keeping track of height while iterating through a tower.  In
   the former case the asymptotic performance is no different, since
   tower_lookup is also O(lg n), but in the latter case performance improves
   from O(lg n) to O(1). */
unsigned long int
range_tower_node_get_start (const struct range_tower_node *node)
{
  const struct abt_node *p = &node->abt_node;
  unsigned long start = subtree_width (p->down[0]) + range_tower_node_from_abt_node (p)->n_zeros;
  while (p->up != NULL)
    {
      if (p == p->up->down[1])
        {
          const struct range_tower_node *up
            = range_tower_node_from_abt_node (p->up);
          start += subtree_width (p->up->down[0]) + up->n_zeros + up->n_ones;
        }
      p = p->up;
    }
  return start;
}

/* Returns one past the position of the last 1-bit in NODE.

   Like range_tower_node_get_start(), the performance of this function is O(lg
   n) in the number of nodes in the range tower. */
unsigned long int
range_tower_node_get_end (const struct range_tower_node *node)
{
  return range_tower_node_get_start (node) + node->n_ones;
}

/* Creates and returns a new, empty range tower. */
struct range_tower *
range_tower_create (void)
{
  return range_tower_create_pool (NULL);
}

static struct range_tower *
range_tower_create_pool__ (struct pool *pool)
{
  struct range_tower *rt = xmalloc (sizeof *rt);

  rt->pool = pool;
  if (pool != NULL)
    pool_register (pool, destroy_pool, rt);

  abt_init (&rt->abt, NULL, reaugment_range_tower_node, NULL);
  rt->cache_end = 0;

  return rt;
}

/* Creates and returns a new, empty range tower in the given POOL. */
struct range_tower *
range_tower_create_pool (struct pool *pool)
{
  struct range_tower_node *node;
  struct range_tower *rt;

  rt = range_tower_create_pool__ (pool);

  node = xmalloc (sizeof *node);
  node->n_zeros = ULONG_MAX;
  node->n_ones = 0;
  abt_insert_after (&rt->abt, NULL, &node->abt_node);

  return rt;
}

/* Creates and returns a clone of OLD range tower in the given POOL
   (which may be null). */
struct range_tower *
range_tower_clone (const struct range_tower *old, struct pool *pool)
{
  const struct range_tower_node *old_node;
  struct abt_node *prev_node;
  struct range_tower *new;

  new = range_tower_create_pool__ (pool);
  prev_node = NULL;
  for (old_node = range_tower_first__ (old); old_node != NULL;
       old_node = range_tower_next__ (old, old_node))
    {
      struct range_tower_node *new_node;

      new_node = xmalloc (sizeof *new_node);
      new_node->n_zeros = old_node->n_zeros;
      new_node->n_ones = old_node->n_ones;

      abt_insert_after (&new->abt, prev_node, &new_node->abt_node);
      prev_node = &new_node->abt_node;
    }
  return new;
}

/* Destroys range tower RT. */
void
range_tower_destroy (struct range_tower *rt)
{
  if (rt != NULL)
    {
      if (rt->pool != NULL)
        pool_unregister (rt->pool, rt);
      while (!abt_is_empty (&rt->abt))
        delete_node (rt, range_tower_first__ (rt));
      free (rt);
    }
}

/* Sets the WIDTH bits starting at START in RT to 1-bits. */
void
range_tower_set1 (struct range_tower *rt,
                    unsigned long int start, unsigned long int width)
{
  struct range_tower_node *node;
  unsigned long int node_start;

  assert (width == 0 || start + width - 1 >= start);

  node = range_tower_lookup (rt, start, &node_start);
  while (width > 0)
    {
      unsigned long int node_ofs = start - node_start;

      if (node_ofs >= node->n_zeros)
        {
          /* There are already some 1-bits here, so skip them. */
          unsigned long ones_left = (node->n_zeros + node->n_ones) - node_ofs;
          if (width <= ones_left)
            return;

          start += ones_left;
          width -= ones_left;
          node_start += node->n_zeros + node->n_ones;
          node_ofs = 0;
          node = range_tower_next__ (rt, node);
        }

      /* Invalidate cache. */
      rt->cache_end = 0;

      if (node_ofs == 0)
        {
          if (node_start > 0)
            {
              struct range_tower_node *prev = range_tower_prev__ (rt, node);
              if (width >= node->n_zeros)
                {
                  /* All zeros in NODE are replaced by ones.  Change NODE's
                     entire width into PREV's trailing ones, e.g. 00001111
                     00001111 becomes 0000111111111111. */
                  int node_width = node->n_zeros + node->n_ones;
                  abt_delete (&rt->abt, &node->abt_node);
                  prev->n_ones += node_width;
                  abt_reaugmented (&rt->abt, &prev->abt_node);
                  if (width <= node_width)
                    return;

                  /* Go around again with NODE replaced by PREV's new
                     successor. */
                  width -= node_width;
                  start += node_width;
                  node = range_tower_next__ (rt, prev);
                  node_start += node_width;
                }
              else
                {
                  /* Leading zeros in NODE change into trailing ones in PREV,
                     but trailing zeros in NODE remain, e.g. 00001111 00001111
                     becomes 0000111111 001111.  */
                  node->n_zeros -= width;
                  abt_reaugmented (&rt->abt, &node->abt_node);

                  prev->n_ones += width;
                  abt_reaugmented (&rt->abt, &prev->abt_node);
                  return;
                }
            }
          else
            {
              if (width >= node->n_zeros)
                {
                  /* All zeros in NODE are replaced by ones, e.g. 00001111
                     becomes 11111111. */
                  node->n_ones += node->n_zeros;
                  node->n_zeros = 0;
                  if (width <= node->n_ones)
                    return;

                  start += node->n_ones;
                  node_start += node->n_ones;
                  width -= node->n_ones;
                  node = range_tower_next__ (rt, node);
                }
              else
                {
                  /* Leading zeros in NODE (which starts at offset 0) are
                     replaced by ones, but some zeros remain.  This requires a
                     node split, e.g. 00001111 becomes 11 001111. */
                  struct range_tower_node *new_node;

                  node->n_zeros -= width;
                  abt_reaugmented (&rt->abt, &node->abt_node);

                  new_node = xmalloc (sizeof *new_node);
                  new_node->n_zeros = 0;
                  new_node->n_ones = width;
                  abt_insert_before (&rt->abt, &node->abt_node,
                                     &new_node->abt_node);
                  return;
                }
            }
        }
      else
        {
          unsigned long int zeros_left = node->n_zeros - node_ofs;
          if (width >= zeros_left)
            {
              /* Trailing zeros in NODE are replaced by ones, but leading
                 zeros remain, e.g. 00001111 becomes 00111111. */
              node->n_zeros -= zeros_left;
              node->n_ones += zeros_left;
              if (width <= node->n_ones)
                return;
              start += node->n_ones;
              width -= node->n_ones;
              node_start += node->n_zeros + node->n_ones;
              node = range_tower_next__ (rt, node);
            }
          else
            {
              /* Zeros that are neither leading or trailing turn into ones.
                 Split the node into two nodes, e.g. 00001111 becomes 011
                 01111.  */
              struct range_tower_node *new_node;

              new_node = xmalloc (sizeof *new_node);
              new_node->n_ones = node->n_ones;
              new_node->n_zeros = zeros_left - width;

              node->n_zeros = node_ofs;
              node->n_ones = width;
              abt_reaugmented (&rt->abt, &node->abt_node);

              abt_insert_after (&rt->abt, &node->abt_node,
                                &new_node->abt_node);
              return;
            }
        }
    }
}

/* Sets the WIDTH bits starting at START in RT to 0-bits. */
void
range_tower_set0 (struct range_tower *rt,
                    unsigned long int start, unsigned long int width)
{
  struct range_tower_node *node;
  unsigned long int node_start;

  assert (width == 0 || start + width - 1 >= start);

  node = range_tower_lookup (rt, start, &node_start);
  while (width > 0)
    {
      unsigned long int node_ofs = start - node_start;

      if (node_ofs < node->n_zeros)
        {
          /* Deleting zeros is a no-op, so skip them. */
          unsigned long zeros_left = node->n_zeros - node_ofs;
          if (zeros_left >= width)
            {
              /* We are deleting only existing zeros.  Nothing to do. */
              return;
            }

          width -= zeros_left;
          start += zeros_left;
          node_ofs = node->n_zeros;
        }

      rt->cache_end = 0;

      if (node_ofs == node->n_zeros)
        {
          if (node->n_ones > width)
            {
              /* DELTA leading ones within NODE turn into zeros, but some ones
                 remain, e.g. 00001111 becomes 00111111.  No reaugmentation
                 because n_zeros + n_ones doesn't change. */
              node->n_zeros += width;
              node->n_ones -= width;
              return;
            }
          else
            {
              /* All ones in NODE turn into zeros, so merge NODE with the
                 following node, e.g. 00001111 00001111 becomes
                 0000000000001111, and then do it again with the merged
                 node. */
              unsigned long int next_zeros, next_ones;
              struct range_tower_node *next;

              next = range_tower_next__ (rt, node);
              if (next == NULL)
                {
                  node->n_zeros += node->n_ones;
                  node->n_ones = 0;
                  return;
                }

              next_zeros = next->n_zeros;
              next_ones = next->n_ones;
              abt_delete (&rt->abt, &next->abt_node);

              node->n_zeros += node->n_ones + next_zeros;
              node->n_ones = next_ones;
              abt_reaugmented (&rt->abt, &node->abt_node);
            }
        }
      else if (node_ofs + width >= node->n_zeros + node->n_ones)
        {
          /* Trailing ones in NODE turn into zeros, but leading ones remain,
             e.g. 000011{11} 00001111 becomes 000011 {00}00001111.  Give the
             trailing ones to the next node as zeros and go around again with
             the next node. */
          struct range_tower_node *next;
          unsigned long int delta;

          delta = node->n_ones - (node_ofs - node->n_zeros);
          node->n_ones -= delta;
          abt_reaugmented (&rt->abt, &node->abt_node);

          next = range_tower_next__ (rt, node);
          if (next == NULL)
            {
              struct range_tower_node *new_node;

              new_node = xmalloc (sizeof *new_node);
              new_node->n_zeros = delta;
              new_node->n_ones = 0;

              abt_insert_before (&rt->abt, NULL, &new_node->abt_node);
              return;
            }

          next->n_zeros += delta;
          abt_reaugmented (&rt->abt, &next->abt_node);

          node_start += node->n_zeros + node->n_ones;
          start = node_start;
          node = next;
        }
      else
        {
          /* Ones that are neither leading or trailing turn into zeros,
             e.g. 00001111 becomes 00001 001.  Split the node into two nodes
             and we're done. */
          unsigned long int end = start + width;
          struct range_tower_node *new_node;

          new_node = xmalloc (sizeof *new_node);
          new_node->n_zeros = width;
          new_node->n_ones = (node_start + node->n_zeros + node->n_ones) - end;

          node->n_ones = node_ofs - node->n_zeros;
          abt_reaugmented (&rt->abt, &node->abt_node);

          abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);
          return;
        }
    }
}

static void
range_tower_delete__ (struct range_tower *rt,
                      unsigned long int start, unsigned long int width)
{
  struct range_tower_node *node;
  unsigned long int node_start;

  rt->cache_end = 0;
  node = range_tower_lookup (rt, start, &node_start);
  for (;;)
    {
      unsigned long int node_ofs = start - node_start;

      if (node_ofs < node->n_zeros)
        {
          if (node_ofs + width < node->n_zeros)
            {
              node->n_zeros -= width;
              abt_reaugmented (&rt->abt, &node->abt_node);
              break;
            }
          else if (node_ofs > 0)
            {
              width -= node->n_zeros - node_ofs;
              node->n_zeros = node_ofs;
              abt_reaugmented (&rt->abt, &node->abt_node);
              if (width == 0)
                break;
              /* Continue with 1-bits. */
            }
          else if (width < node->n_zeros + node->n_ones)
            {
              struct range_tower_node *prev = range_tower_prev__ (rt, node);
              unsigned long int ones_left;

              ones_left = (node->n_zeros + node->n_ones) - width;
              if (prev != NULL)
                {
                  abt_delete (&rt->abt, &node->abt_node);
                  prev->n_ones += ones_left;
                  abt_reaugmented (&rt->abt, &prev->abt_node);
                }
              else
                {
                  node->n_zeros = 0;
                  node->n_ones = ones_left;
                  abt_reaugmented (&rt->abt, &node->abt_node);
                }
              break;
            }
          else
            {
              /* Delete entire node. */
              struct range_tower_node *next = range_tower_next__ (rt, node);

              width -= node->n_zeros + node->n_ones;
              abt_delete (&rt->abt, &node->abt_node);
              if (next == NULL)
                break;

              node = next;
              continue;
            }
        }

      if (node_ofs + width < node->n_zeros + node->n_ones)
        {
          node->n_ones -= width;
          abt_reaugmented (&rt->abt, &node->abt_node);
          break;
        }
      else if (node_ofs > node->n_zeros)
        {
          unsigned long int ones_ofs = node_ofs - node->n_zeros;
          width -= node->n_ones - ones_ofs;
          node->n_ones = ones_ofs;
          abt_reaugmented (&rt->abt, &node->abt_node);
          if (width == 0)
            break;
          /* continue with next node */
          node_start += node->n_zeros + node->n_ones;
          node = range_tower_next__ (rt, node);
        }
      else
        {
          /* Merge with next node */
          struct range_tower_node *next = range_tower_next__ (rt, node);
          if (next != NULL)
            {
              unsigned long int next_zeros = next->n_zeros;
              unsigned long int next_ones = next->n_ones;

              abt_delete (&rt->abt, &next->abt_node);

              width -= node->n_ones;

              node->n_zeros += next_zeros;
              node->n_ones = next_ones;
              abt_reaugmented (&rt->abt, &node->abt_node);

              if (width == 0)
                break;
            }
          else
            {
              node->n_ones = 0;
              abt_reaugmented (&rt->abt, &node->abt_node);
              break;
            }
        }
    }
}

void
range_tower_delete (struct range_tower *rt,
                    unsigned long int start, unsigned long int width)
{
  struct range_tower_node *node;

  if (width == 0)
    return;

  assert (start + width - 1 >= start);

  range_tower_delete__ (rt, start, width);

  node = range_tower_last__ (rt);
  if (node != NULL && node->n_ones == 0)
    {
      node->n_zeros += width;
      abt_reaugmented (&rt->abt, &node->abt_node);
    }
  else
    {
      struct range_tower_node *new_node;

      new_node = xmalloc (sizeof *new_node);
      new_node->n_zeros = width;
      new_node->n_ones = 0;

      abt_insert_before (&rt->abt, NULL, &new_node->abt_node);
    }
}

static struct range_tower_node *
range_tower_insert0__ (struct range_tower *rt, struct range_tower_node *node,
                       unsigned long int *node_startp,
                       unsigned long int start, unsigned long int width)
{
  unsigned long int node_ofs = start - *node_startp;

  if (node_ofs <= node->n_zeros)
    {
      /* 00+00+001111 => 0000001111. */
      node->n_zeros += width;
      abt_reaugmented (&rt->abt, &node->abt_node);

      return node;
    }
  else
    {
      /* 000011+00+11 => 000011 0011. */
      struct range_tower_node *new_node;

      new_node = xmalloc (sizeof *new_node);
      new_node->n_zeros = width;
      new_node->n_ones = node->n_zeros + node->n_ones - node_ofs;

      node->n_ones -= new_node->n_ones;
      abt_reaugmented (&rt->abt, &node->abt_node);
      abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);

      *node_startp += node->n_zeros + node->n_ones;
      return new_node;
    }
}

void
range_tower_insert0 (struct range_tower *rt,
                     unsigned long int start, unsigned long int width)
{
  if (width == 0)
    return;

  assert (width == 0 || start + width - 1 >= start);

  if (start + width == ULONG_MAX)
    range_tower_set0 (rt, start, width);
  else
    {
      struct range_tower_node *node;
      unsigned long int node_start;

      range_tower_delete__ (rt, ULONG_MAX - width, width);

      node = range_tower_lookup (rt, start, &node_start);
      range_tower_insert0__ (rt, node, &node_start, start, width);
    }
}

static struct range_tower_node *
range_tower_insert1__ (struct range_tower *rt, struct range_tower_node *node,
                       unsigned long int *node_startp,
                       unsigned long int start, unsigned long int width)
{

  unsigned long int node_start = *node_startp;
  unsigned long int node_ofs = start - node_start;

  if (node_ofs >= node->n_zeros)
    {
      node->n_ones += width;
      abt_reaugmented (&rt->abt, &node->abt_node);
      return node;
    }
  else if (node_ofs == 0 && node_start > 0)
    {
      struct range_tower_node *prev = range_tower_prev__ (rt, node);

      prev->n_ones += width;
      abt_reaugmented (&rt->abt, &prev->abt_node);

      *node_startp += width;
      return node;
    }
  else
    {
      /* 00001111 => 0+11+0001111 => 011 0001111 */
      struct range_tower_node *new_node;

      new_node = xmalloc (sizeof *new_node);
      new_node->n_zeros = node->n_zeros - node_ofs;
      new_node->n_ones = node->n_ones;

      node->n_zeros = node_ofs;
      node->n_ones = width;
      abt_reaugmented (&rt->abt, &node->abt_node);

      abt_insert_after (&rt->abt, &node->abt_node, &new_node->abt_node);

      *node_startp += node->n_zeros + node->n_ones;
      return new_node;
    }
}

void
range_tower_insert1 (struct range_tower *rt,
                     unsigned long int start, unsigned long int width)
{
  struct range_tower_node *node;
  unsigned long int node_start;

  if (width == 0)
    return;

  range_tower_delete__ (rt, ULONG_MAX - width, width);

  assert (width == 0 || start + width - 1 >= start);

  node = range_tower_lookup (rt, start, &node_start);
  range_tower_insert1__ (rt, node, &node_start, start, width);
}

void
range_tower_move (struct range_tower *rt,
                  unsigned long int old_start,
                  unsigned long int new_start,
                  unsigned long int width)
{
  unsigned long int node_start;
  int i;

  if (width == 0 || old_start == new_start)
    return;

  assert (old_start + width - 1 >= old_start);
  assert (new_start + width - 1 >= new_start);

  i = 0;
  do
    {
      struct range_tower_node *node;
      unsigned long int node_ofs;
      unsigned long int zeros, ones;

      node = range_tower_lookup (rt, old_start, &node_start);
      node_ofs = old_start - node_start;

      if (node_ofs >= node->n_zeros)
        {
          unsigned long int max_ones;

          zeros = 0;
          max_ones = (node->n_zeros + node->n_ones) - node_ofs;
          ones = MIN (width, max_ones);
        }
      else
        {
          unsigned long int max_zeros;

          max_zeros = node->n_zeros - node_ofs;
          zeros = MIN (width, max_zeros);
          if (zeros < width)
            ones = MIN (width - zeros, node->n_ones);
          else
            ones = 0;
        }

      node->n_zeros -= zeros;
      node->n_ones -= ones;
      abt_reaugmented (&rt->abt, &node->abt_node);

      if (node->n_zeros == 0)
        {
          if (node->n_ones == 0)
            abt_delete (&rt->abt, &node->abt_node);
          else if (node_start > 0)
            {
              /* Merge with previous. */
              unsigned long int n_ones = node->n_ones;
              struct range_tower_node *prev = range_tower_prev__ (rt, node);

              abt_delete (&rt->abt, &node->abt_node);
              prev->n_ones += n_ones;
              abt_reaugmented (&rt->abt, &prev->abt_node);
            }
        }
      else if (node->n_ones == 0)
        {
          struct range_tower_node *next = range_tower_next__ (rt, node);
          if (next != NULL)
            {
              /* Merge with next. */
              unsigned long int n_zeros = node->n_zeros;

              abt_delete (&rt->abt, &node->abt_node);
              next->n_zeros += n_zeros;
              abt_reaugmented (&rt->abt, &next->abt_node);
            }
        }

      if (new_start < old_start)
        {
          node = range_tower_lookup (rt, new_start, &node_start);
          if (zeros)
            {
              node = range_tower_insert0__ (rt, node, &node_start,
                                            new_start, zeros);
              old_start += zeros;
              new_start += zeros;
            }

          if (ones)
            {
              node = range_tower_insert1__ (rt, node, &node_start,
                                            new_start, ones);
              old_start += ones;
              new_start += ones;
            }
        }
      else
        {
          unsigned long int remaining = width - (zeros + ones);

          if (new_start + remaining < ULONG_MAX - (zeros + ones))
            {
              node = range_tower_lookup (rt, new_start + remaining,
                                         &node_start);
              if (zeros)
                {
                  node = range_tower_insert0__ (rt, node, &node_start,
                                                new_start + remaining, zeros);
                  new_start += zeros;
                }

              if (ones)
                {
                  node = range_tower_insert1__ (rt, node, &node_start,
                                                new_start + remaining, ones);
                  new_start += ones;
                }
            }
          else
            {
              node = range_tower_last__ (rt);
              if (zeros)
                {
                  if (node->n_ones)
                    {
                      struct range_tower_node *new_node;

                      new_node = xmalloc (sizeof *new_node);
                      new_node->n_zeros = zeros;
                      new_node->n_ones = 0;

                      abt_insert_after (&rt->abt, &node->abt_node,
                                        &new_node->abt_node);

                      node_start += node->n_zeros + node->n_ones;
                      node = new_node;
                    }
                  else
                    {
                      node->n_zeros += zeros;
                      abt_reaugmented (&rt->abt, &node->abt_node);
                    }
                }
              if (ones)
                {
                  node->n_ones += ones;
                  abt_reaugmented (&rt->abt, &node->abt_node);
                }

              new_start += zeros + ones;
            }
        }
      width -= zeros + ones;
    }
  while (width > 0);
}

/* Returns true if there is a 1-bit at the given POSITION in RT,
   false otherwise. */
bool
range_tower_contains (const struct range_tower *rt_, unsigned long int position)
{
  struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);
  if (position >= rt->cache_end || position < rt->cache_start)
    {
      struct range_tower_node *node;
      unsigned long int node_start;

      node = range_tower_lookup (rt, position, &node_start);
      if (position < node_start + node->n_zeros)
        {
          rt->cache_start = node_start;
          rt->cache_end = node_start + node->n_zeros;
          rt->cache_value = false;
        }
      else
        {
          rt->cache_start = node_start + node->n_zeros;
          rt->cache_end = rt->cache_start + node->n_ones;
          rt->cache_value = true;
        }
    }
  return rt->cache_value;
}

/* Returns the smallest position of a 1-bit greater than or
   equal to START.  Returns ULONG_MAX if there is no 1-bit with
   position greater than or equal to START. */
unsigned long int
range_tower_scan (const struct range_tower *rt_, unsigned long int start)
{
  struct range_tower *rt = CONST_CAST (struct range_tower *, rt_);

  if (start < rt->cache_end && start >= rt->cache_start && rt->cache_value)
    return start;

  if (start != ULONG_MAX)
    {
      struct range_tower_node *node;
      unsigned long int node_start;

      node = range_tower_lookup (rt, start, &node_start);
      if (node->n_ones)
        {
          rt->cache_start = node_start + node->n_zeros;
          rt->cache_end = rt->cache_start + node->n_ones;
          rt->cache_value = true;
          return MAX (start, rt->cache_start);
        }
      else
        {
          rt->cache_start = node_start;
          rt->cache_end = ULONG_MAX;
          rt->cache_value = false;
        }
    }
  return ULONG_MAX;
}

/* Recalculates the subtree_width of NODE based on its LEFT and
   RIGHT children's "subtree_width"s. */
static void
reaugment_range_tower_node (struct abt_node *node_, const void *aux UNUSED)
{
  struct range_tower_node *node = range_tower_node_from_abt_node (node_);

  node->subtree_width = node->n_zeros + node->n_ones;
  if (node->abt_node.down[0] != NULL)
    {
      struct range_tower_node *left;

      left = range_tower_node_from_abt_node (node->abt_node.down[0]);
      node->subtree_width += left->subtree_width;
    }
  if (node->abt_node.down[1] != NULL)
    {
      struct range_tower_node *right;

      right = range_tower_node_from_abt_node (node->abt_node.down[1]);
      node->subtree_width += right->subtree_width;
    }
}

/* Deletes NODE from RT and frees it. */
static void
delete_node (struct range_tower *rt, struct range_tower_node *node)
{
  abt_delete (&rt->abt, &node->abt_node);
  free (node);
}

struct range_tower_node *
range_tower_lookup (const struct range_tower *rt, unsigned long int position,
                    unsigned long int *node_start)
{
  const struct range_tower_node *node;
  const struct abt_node *abt_node;

  abt_node = rt->abt.root;
  node = range_tower_node_from_abt_node (abt_node);
  *node_start = subtree_width (abt_node->down[0]);
  for (;;)
    {
      unsigned long int left_width = subtree_width (abt_node->down[0]);

      if (position < left_width)
        {
          abt_node = abt_node->down[0];
          *node_start -= left_width - subtree_width (abt_node->down[0]);
        }
      else
        {
          unsigned long int node_width = node->n_zeros + node->n_ones;

          position -= left_width;
          if (position < node_width)
            return CONST_CAST (struct range_tower_node *, node);

          position -= node_width;
          abt_node = abt_node->down[1];
          left_width = subtree_width (abt_node->down[0]);
          *node_start += node_width + left_width;
        }
      node = range_tower_node_from_abt_node (abt_node);
    }
}

/* Destroys range tower RT.
   Helper function for range_tower_create_pool. */
static void
destroy_pool (void *rt_)
{
  struct range_tower *rt = rt_;
  rt->pool = NULL;
  range_tower_destroy (rt);
}