/*-*- mode:c;indent-tabs-mode:nil;c-basic-offset:2;tab-width:8;coding:utf-8 -*-â
âvi: set net ft=c ts=2 sts=2 sw=2 fenc=utf-8                                :viâ
ââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ¡
â Copyright 2022 Justine Alexandra Roberts Tunney                              â
â                                                                              â
â Permission to use, copy, modify, and/or distribute this software for         â
â any purpose with or without fee is hereby granted, provided that the         â
â above copyright notice and this permission notice appear in all copies.      â
â                                                                              â
â THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL                â
â WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED                â
â WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE             â
â AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL         â
â DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR        â
â PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER               â
â TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR             â
â PERFORMANCE OF THIS SOFTWARE.                                                â
ââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââââ*/
#include "tool/plinko/lib/histo.h"
#include "tool/plinko/lib/index.h"
#include "tool/plinko/lib/plinko.h"
#include "tool/plinko/lib/tree.h"

/**
 * Performs lookup of binding.
 *
 * We perform lookups into an association list, e.g.
 *
 *       âââââ¬ââââ âââââ¬ââââ âââââ¬ââââ
 *       â ðââ ð£ââ â ðââ ð£ââ â ðââ ð£ââ
 *       âââ¬ââ´ââââ âââ¬ââ´ââââ âââ¬ââ´ââââ
 *       âââââ¬ââââ âââââ¬ââââ âââââ¬ââââ
 *     ð=â â´ â âââââ¤ â´ â âââââ¤ â´ â 0 â
 *       âââââ´ââââ âââââ´ââââ âââââ´ââââ
 *
 * For example, if ðâ is queried then we return:
 *
 *     âââââ¬ââââ
 *     â ðââ ð£ââ
 *     âââââ´ââââ
 *
 * However there's a twist: the association is allowed to turn into a
 * red-black tree. That would look like this:
 *
 *       âââââ¬ââââ âââââ¬ââââ
 *       â ðââ ð£ââ â ðââ ð£ââ
 *       âââ¬ââ´ââââ âââ¬ââ´ââââ
 *       âââââ¬ââââ âââââ¬ââââ âââââ¬ââââ
 *     ð=â â´ â âââââ¤ â´ â âââââ â¬ â ð â
 *       âââââ´ââââ âââââ´ââââ âââââ´ââââ
 *                           âââ´ââ¬ââââ
 *                           â â¬ â â¬ â
 *                           âââââ´ââââ
 *                      âââââ¬âââ´â ââ´âââ¬ââââ
 *                      â ðââ ð£ââ â L â R â
 *                      âââââ´ââââ âââââ´ââââ
 *
 * We're able to tell a tree node apart from an association list node
 * because we make the assumption that ðáµ¢ is an atom. On the other hand
 * ð£áµ¢ can be anything.
 *
 * @param k is an atom
 * @param a is an association list and/or red-black tree
 * @return entry cons cell or 0 if not found
 */
int Assoc(int k, int a) {
  int i, j, e, c, r;
  DCHECK_GE(k, 0);
  i = a;
  r = 0;
  if (k && k != 1) {
    for (c = 0; i;) {
      e = Head(i);
      i = Cdr(i);
      j = Head(e);
      ++c;
      if (j == k) {
        r = e;
        break;
      } else if (j < 0 && (j =
#if HISTO_ASSOC
                               GetTreeCount(k, e, &c)
#else
                               GetTree(k, e)
#endif
                               )) {
        r = Ent(j);
        break;
      }
    }
#if HISTO_ASSOC
    HISTO(g_assoc_histogram, c);
#endif
  }
  return r;
}
