From 0717edbd26a75442d0aa8695d140243ec0b69b5d Mon Sep 17 00:00:00 2001
From: Kaz Kylheku <kaz@kylheku.com>
Date: Wed, 17 Jul 2019 07:37:11 -0700
Subject: relate: optimize with hashes.

* lib.c (do_relate_hash, do_relate_hash_dfl): New static
functions.
(relate): If the number of keys and values is the same, and
there are more than ten, then use hashing.
If the default value is specified, and it is nil, then a hash
table can be returned directly, instead of a function.

* txr.1: Note added that relate may return a hash.
---
 lib.c | 30 +++++++++++++++++++++++++++---
 txr.1 |  5 +++++
 2 files changed, 32 insertions(+), 3 deletions(-)

diff --git a/lib.c b/lib.c
index db59cd60..08b84c74 100644
--- a/lib.c
+++ b/lib.c
@@ -10628,13 +10628,37 @@ static val do_relate_dfl(val env, val arg)
   return if3(pos, ref(rng, pos), dfl);
 }
 
+static val do_relate_hash(val hash, val arg)
+{
+  val cell = gethash_e(lit("relate"), hash, arg);
+  return if3(cell, cdr(cell), arg);
+}
+
+static val do_relate_hash_dfl(val env, val arg)
+{
+  cons_bind (hash, dfl, env);
+  val cell = gethash_e(lit("relate"), hash, arg);
+  return if3(cell, cdr(cell), dfl);
+}
 
 val relate(val domain_seq, val range_seq, val dfl_val)
 {
+  val lds = length(domain_seq);
+  val use_hash = and2(gt(lds, num_fast(10)),
+                      le(lds, length(range_seq)));
+  args_decl(args, ARGS_MIN);
+  val hash = if2(use_hash, hash_zip(domain_seq, range_seq, args));
+
   return if3(missingp(dfl_val),
-             func_f1(cons(domain_seq, range_seq), do_relate),
-             func_f1(vec(domain_seq, range_seq, dfl_val, nao),
-                     do_relate_dfl));
+             if3(use_hash,
+                 func_f1(hash, do_relate_hash),
+                 func_f1(cons(domain_seq, range_seq), do_relate)),
+             if3(use_hash,
+                 if3(null(dfl_val),
+                     hash,
+                     func_f1(cons(hash, dfl_val), do_relate_hash_dfl)),
+                 func_f1(vec(domain_seq, range_seq, dfl_val, nao),
+                         do_relate_dfl)));
 }
 
 val rcons(val from, val to)
diff --git a/txr.1 b/txr.1
index 774b84c3..7c34fb88 100644
--- a/txr.1
+++ b/txr.1
@@ -29753,6 +29753,11 @@ function may be understood in terms of the following equivalences:
                             v))
 .brev
 
+Note:
+.code relate
+may return a hash table instead of a function, if such an object
+can satisfy the semantics required by the arguments.
+
 .TP* Examples:
 
 .verb
-- 
cgit v1.2.3