gistfile1.c

/*
 * Copyright (C) 2015 Koz Ross <koz.ross@runbox.com>
 *
 * 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/>.
 */

#include "btt.h"
#include <assert.h>
#include <math.h>
#include <stdio.h>

static String to_bin_string(size_t*, Number);

//allocates and fills a new BTT from nums, of length len
//trusts len unconditionally - beware
//pre: nums is not null; len > 0
BTT btt_make (Number* nums, Number len) {
  assert(nums);
  assert(len);
  BTT btt = malloc(sizeof(struct BinomialTournamentTree_s));
  size_t string_size = 0;
  String bin = to_bin_string(&string_size, len);
  btt->nodes = malloc(string_size * sizeof(struct Node_s));
  btt->capacity = string_size;
  Number* num_ptr = nums;
  Number index = 0;
  for (String ptr = bin; ptr != '\0'; ptr++) {
    if (*ptr == '1') {
      Number exp = exp2(index);
      btt->nodes[index] = make_tree(num_ptr, exp);
      num_ptr += exp;
    } else {
      btt->nodes[index] = NULL;
    }
    index++;
  }
  return btt;
}

//private stuff

//converts n to a big-endian binary string
//has an out-parameter for length to avoid doing same work twice
static String to_bin_string (size_t* len, Number n) {
  char* bin = NULL;
  FILE* stream = open_memstream(&bin, len);
  Number step = 1;
  while (n != 0) {
    fprintf(stream, "%d", (int)n % 2);
    n -= step;
    step *= 2;
  }
  fclose(stream);
  return (String)bin;
}