From 9449e8429a4bc1368c322457384d69e22f8d0bb2 Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
Date: Sun, 14 Aug 2022 16:23:46 -0700
Subject: [PATCH] improve pivot table splits

---
 src/output/pivot-table.c | 69 ++++++++++++++++++++++++++++++++++++----
 1 file changed, 62 insertions(+), 7 deletions(-)

diff --git a/src/output/pivot-table.c b/src/output/pivot-table.c
index f81be9df22..93dc74c2d8 100644
--- a/src/output/pivot-table.c
+++ b/src/output/pivot-table.c
@@ -3049,12 +3049,20 @@ struct pivot_splits_var
     struct hmap values;
   };
 
+struct pivot_splits_dup
+  {
+    struct hmap_node hmap_node;
+    union value *values;
+  };
+
 struct pivot_splits
   {
     struct pivot_splits_var *vars;
     size_t n;
     char *encoding;
 
+    struct hmap dups;
+
     size_t dindexes[MAX_SPLITS];
 
     int warnings_left;
@@ -3102,6 +3110,7 @@ pivot_splits_create (struct pivot_table *pt,
     .vars = psvars,
     .n = n,
     .encoding = xstrdup (dict_get_encoding (dict)),
+    .dups = HMAP_INITIALIZER (ps->dups),
     .dindexes = { [0] = SIZE_MAX },
     .warnings_left = 5,
   };
@@ -3122,6 +3131,17 @@ pivot_splits_destroy (struct pivot_splits *ps)
                        "split values.", -ps->warnings_left),
          -ps->warnings_left);
 
+  struct pivot_splits_dup *dup, *next_dup;
+  HMAP_FOR_EACH_SAFE (dup, next_dup, struct pivot_splits_dup, hmap_node,
+                      &ps->dups)
+    {
+      for (size_t i = 0; i < ps->n; i++)
+        value_destroy (&dup->values[i], ps->vars[i].width);
+      free (dup->values);
+      free (dup);
+    }
+  hmap_destroy (&ps->dups);
+
   for (size_t i = 0; i < ps->n; i++)
     {
       struct pivot_splits_var *psvar = &ps->vars[i];
@@ -3136,6 +3156,7 @@ pivot_splits_destroy (struct pivot_splits *ps)
       hmap_destroy (&psvar->values);
     }
   free (ps->vars);
+
   free (ps->encoding);
   free (ps);
 }
@@ -3152,6 +3173,45 @@ pivot_splits_value_find (struct pivot_splits_var *psvar,
   return NULL;
 }
 
+static bool
+pivot_splits_find_dup (struct pivot_splits *ps, const struct ccase *example)
+{
+  unsigned int hash = 0;
+  for (size_t i = 0; i < ps->n; i++)
+    {
+      struct pivot_splits_var *psvar = &ps->vars[i];
+      const union value *value = case_data (example, psvar->var);
+      hash = value_hash (value, psvar->width, hash);
+    }
+  struct pivot_splits_dup *dup;
+  HMAP_FOR_EACH_WITH_HASH (dup, struct pivot_splits_dup, hmap_node, hash,
+                           &ps->dups)
+    {
+      bool equal = true;
+      for (size_t i = 0; i < ps->n && equal; i++)
+        {
+          struct pivot_splits_var *psvar = &ps->vars[i];
+          const union value *value = case_data (example, psvar->var);
+          equal = value_equal (value, &dup->values[i], psvar->width);
+        }
+      if (equal)
+        return true;
+    }
+
+  union value *values = xmalloc (ps->n * sizeof *values);
+  for (size_t i = 0; i < ps->n; i++)
+    {
+      struct pivot_splits_var *psvar = &ps->vars[i];
+      const union value *value = case_data (example, psvar->var);
+      value_clone (&values[i], value, psvar->width);
+    }
+
+  dup = xmalloc (sizeof *dup);
+  dup->values = values;
+  hmap_insert (&ps->dups, &dup->hmap_node, hash);
+  return false;
+}
+
 /* Begins adding data for a new split file group to the pivot table associated
    with PS.  EXAMPLE should be a case from the new split file group.
 
@@ -3165,7 +3225,6 @@ pivot_splits_new_split (struct pivot_splits *ps, const struct ccase *example)
   if (!ps)
     return;
 
-  size_t n_changed = 0;
   for (size_t i = 0; i < ps->n; i++)
     {
       struct pivot_splits_var *psvar = &ps->vars[i];
@@ -3182,14 +3241,10 @@ pivot_splits_new_split (struct pivot_splits *ps, const struct ccase *example)
             pivot_value_new_var_value (psvar->var, value));
         }
 
-      if (ps->dindexes[i] != psval->leaf)
-        {
-          ps->dindexes[i] = psval->leaf;
-          n_changed++;
-        }
+      ps->dindexes[i] = psval->leaf;
     }
 
-  if (!n_changed)
+  if (pivot_splits_find_dup (ps, example))
     {
       if (ps->warnings_left-- > 0)
         {
-- 
2.30.2