/* Copyright (C) 2014 by Maxim Bublis <b@codemonkey.ru>
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "tree.h"
#include <svn_hash.h>
#include <svn_path.h>

tree_t *tree_create(apr_pool_t *pool) {
  tree_t *t = apr_pcalloc(pool, sizeof(tree_t));
  t->pool = pool;
  t->nodes = apr_hash_make(pool);
  t->value = NULL;

  return t;
}

void tree_copy(tree_t **dst, const tree_t *src, apr_pool_t *pool) {
  apr_hash_index_t *idx;
  tree_t *t = tree_create(pool);
  t->value = src->value;

  for (idx = apr_hash_first(pool, src->nodes); idx; idx = apr_hash_next(idx)) {
    const char *key = apr_hash_this_key(idx);
    const tree_t *val = apr_hash_this_val(idx);
    tree_t *subtree;

    tree_copy(&subtree, val, pool);
    svn_hash_sets(t->nodes, apr_pstrdup(t->pool, key), subtree);
  }

  *dst = t;
}

void tree_merge(tree_t **dst, const tree_t *t1, const tree_t *t2,
                apr_pool_t *pool) {
  apr_hash_index_t *idx;

  if (t1 == NULL && t2 == NULL) {
    return;
  }

  if (t1 == NULL) {
    tree_copy(dst, t2, pool);
    return;
  }

  if (t2 == NULL) {
    tree_copy(dst, t1, pool);
    return;
  }

  tree_t *t = tree_create(pool);
  t->value = t1->value != NULL ? t1->value : t2->value;

  for (idx = apr_hash_first(pool, t1->nodes); idx; idx = apr_hash_next(idx)) {
    const char *key1 = apr_hash_this_key(idx);
    const tree_t *val1 = apr_hash_this_val(idx);
    const tree_t *val2 = svn_hash_gets(t2->nodes, key1);
    tree_t *subtree;
    tree_merge(&subtree, val1, val2, pool);

    svn_hash_sets(t->nodes, apr_pstrdup(t->pool, key1), subtree);
  }

  for (idx = apr_hash_first(pool, t2->nodes); idx; idx = apr_hash_next(idx)) {
    const char *key2 = apr_hash_this_key(idx);
    const tree_t *val2 = apr_hash_this_val(idx);
    const tree_t *val1 = svn_hash_gets(t1->nodes, key2);

    if (val1 == NULL) {
      tree_t *subtree;
      tree_copy(&subtree, val2, pool);

      svn_hash_sets(t->nodes, apr_pstrdup(t->pool, key2), subtree);
    }
  }

  *dst = t;
}

void tree_diff(tree_t **dst, const tree_t *t1, const tree_t *t2,
               apr_pool_t *pool) {
  apr_hash_index_t *idx;
  tree_t *t = tree_create(pool);

  if (t1 == NULL) {
    *dst = t;
    return;
  }

  if (t2 == NULL) {
    tree_copy(dst, t1, pool);
    return;
  }

  for (idx = apr_hash_first(pool, t1->nodes); idx; idx = apr_hash_next(idx)) {
    const char *key1 = apr_hash_this_key(idx);
    const tree_t *val1 = apr_hash_this_val(idx);
    const tree_t *val2 = svn_hash_gets(t2->nodes, key1);

    tree_t *subtree;
    tree_diff(&subtree, val1, val2, pool);

    if (val2 == NULL || val2->value == NULL) {
      subtree->value = val1->value;
    }

    svn_hash_sets(t->nodes, apr_pstrdup(t->pool, key1), subtree);
  }

  *dst = t;
}

void tree_insert(tree_t *t, const char *path, const void *value,
                 apr_pool_t *pool) {
  apr_array_header_t *components = svn_path_decompose(path, pool);

  for (int i = 0; i < components->nelts; i++) {
    const char *key = APR_ARRAY_IDX(components, i, const char *);
    tree_t *subtree = svn_hash_gets(t->nodes, key);

    if (subtree == NULL) {
      subtree = tree_create(t->pool);
      svn_hash_sets(t->nodes, apr_pstrdup(t->pool, key), subtree);
    }

    t = subtree;
  }

  t->value = value;
}

const void *tree_match(const tree_t *t, const char *path, apr_pool_t *pool) {
  const void *value = t->value;
  apr_array_header_t *components = svn_path_decompose(path, pool);

  for (int i = 0; i < components->nelts; i++) {
    const char *key = APR_ARRAY_IDX(components, i, const char *);
    tree_t *subtree = svn_hash_gets(t->nodes, key);

    if (subtree == NULL) {
      break;
    }

    if (subtree->value != NULL) {
      value = subtree->value;
    }

    t = subtree;
  }

  return value;
}

const tree_t *tree_subtree(const tree_t *t, const char *path,
                           apr_pool_t *pool) {
  apr_array_header_t *components = svn_path_decompose(path, pool);

  for (int i = 0; i < components->nelts; i++) {
    const char *key = APR_ARRAY_IDX(components, i, const char *);
    t = svn_hash_gets(t->nodes, key);
    if (t == NULL) {
      break;
    }
  }

  return t;
}

apr_array_header_t *tree_values(const tree_t *t, const char *path,
                                apr_pool_t *result_pool,
                                apr_pool_t *scratch_pool) {
  apr_array_header_t *values, *queue;
  const tree_t *subtree;

  values = apr_array_make(result_pool, 0, sizeof(void *));
  queue = apr_array_make(scratch_pool, 0, sizeof(tree_t *));

  subtree = tree_subtree(t, path, scratch_pool);
  if (subtree == NULL) {
    return values;
  }

  APR_ARRAY_PUSH(queue, const tree_t *) = subtree;

  while (queue->nelts) {
    apr_hash_index_t *idx;
    const tree_t *node = *((const tree_t **)apr_array_pop(queue));

    if (node->value != NULL) {
      APR_ARRAY_PUSH(values, const void *) = node->value;
    }

    for (idx = apr_hash_first(scratch_pool, node->nodes); idx;
         idx = apr_hash_next(idx)) {
      APR_ARRAY_PUSH(queue, const tree_t *) = apr_hash_this_val(idx);
    }
  }

  return values;
}