From 04ef14be963b955d3b33bb85149759b75a32c34e Mon Sep 17 00:00:00 2001
From: Ben Pfaff <blp@cs.stanford.edu>
Date: Sun, 25 Apr 2010 23:11:31 -0700
Subject: [PATCH] New stringi_set functions.

---
 src/libpspp/stringi-set.c        | 53 ++++++++++++++++++++++++++++++--
 src/libpspp/stringi-set.h        |  3 ++
 tests/libpspp/stringi-set-test.c | 19 +++++++++++-
 3 files changed, 72 insertions(+), 3 deletions(-)

diff --git a/src/libpspp/stringi-set.c b/src/libpspp/stringi-set.c
index 36745742..a7ae6994 100644
--- a/src/libpspp/stringi-set.c
+++ b/src/libpspp/stringi-set.c
@@ -19,12 +19,13 @@
 
 #include <config.h>
 
-#include <libpspp/stringi-set.h>
+#include "libpspp/stringi-set.h"
 
 #include <stdlib.h>
 #include <string.h>
 
-#include <libpspp/hash-functions.h>
+#include "libpspp/cast.h"
+#include "libpspp/hash-functions.h"
 
 #include "gl/xalloc.h"
 
@@ -226,6 +227,54 @@ stringi_set_subtract (struct stringi_set *a, const struct stringi_set *b)
         stringi_set_delete__ (a, node->string, node->hmap_node.hash);
     }
 }
+
+/* Allocates and returns an array that points to each of the strings in SET.
+   The caller must not free or modify any of the strings.  Removing a string
+   from SET invalidates the corresponding element of the returned array.  The
+   caller it is responsible for freeing the returned array itself (with
+   free()).
+
+   The returned array is in the same order as observed by stringi_set_first()
+   and stringi_set_next(), that is, no particular order. */
+char **
+stringi_set_get_array (const struct stringi_set *set)
+{
+  const struct stringi_set_node *node;
+  const char *s;
+  char **array;
+  size_t i;
+
+  array = xnmalloc (stringi_set_count (set), sizeof *array);
+
+  i = 0;
+  STRINGI_SET_FOR_EACH (s, node, set)
+    array[i++] = CONST_CAST (char *, s);
+
+  return array;
+}
+
+static int
+compare_strings (const void *a_, const void *b_)
+{
+  const char *const *a = a_;
+  const char *const *b = b_;
+  return strcasecmp (*a, *b);
+}
+
+/* Allocates and returns an array that points to each of the strings in SET.
+   The caller must not free or modify any of the strings.  Removing a string
+   from SET invalidates the corresponding element of the returned array.  The
+   caller it is responsible for freeing the returned array itself (with
+   free()).
+
+   The returned array is ordered according to strcasecmp(). */
+char **
+stringi_set_get_sorted_array (const struct stringi_set *set)
+{
+  char **array = stringi_set_get_array (set);
+  qsort (array, stringi_set_count (set), sizeof *array, compare_strings);
+  return array;
+}
 
 /* Internal functions. */
 
diff --git a/src/libpspp/stringi-set.h b/src/libpspp/stringi-set.h
index caccca86..f438d048 100644
--- a/src/libpspp/stringi-set.h
+++ b/src/libpspp/stringi-set.h
@@ -77,6 +77,9 @@ void stringi_set_union_and_intersection (struct stringi_set *,
 void stringi_set_intersect (struct stringi_set *, const struct stringi_set *);
 void stringi_set_subtract (struct stringi_set *, const struct stringi_set *);
 
+char **stringi_set_get_array (const struct stringi_set *);
+char **stringi_set_get_sorted_array (const struct stringi_set *);
+
 static inline const struct stringi_set_node *stringi_set_first (
   const struct stringi_set *);
 static inline const struct stringi_set_node *stringi_set_next (
diff --git a/tests/libpspp/stringi-set-test.c b/tests/libpspp/stringi-set-test.c
index 16a4e180..25f52c82 100644
--- a/tests/libpspp/stringi-set-test.c
+++ b/tests/libpspp/stringi-set-test.c
@@ -283,13 +283,18 @@ check_stringi_set (struct stringi_set *set, const int data[], size_t cnt)
   check (stringi_set_find_node (set, "") == NULL);
 
   if (cnt == 0)
-    check (stringi_set_first (set) == NULL);
+    {
+      check (stringi_set_first (set) == NULL);
+      free (stringi_set_get_array (set));
+    }
   else
     {
       const struct stringi_set_node *node;
+      char **array;
       int *data_copy;
       int left;
 
+      array = stringi_set_get_array (set);
       data_copy = xmemdup (data, cnt * sizeof *data);
       left = cnt;
       for (node = stringi_set_first (set), i = 0; i < cnt;
@@ -298,6 +303,8 @@ check_stringi_set (struct stringi_set *set, const int data[], size_t cnt)
           const char *s = stringi_set_node_get_string (node);
           size_t j;
 
+          check (s == array[i]);
+
           for (j = 0; j < left; j++)
             if (!strcasecmp (s, make_string (data_copy[j])))
               {
@@ -310,6 +317,16 @@ check_stringi_set (struct stringi_set *set, const int data[], size_t cnt)
         }
       check (node == NULL);
       free (data_copy);
+      free (array);
+
+      array = stringi_set_get_sorted_array (set);
+      for (i = 0; i < cnt; i++)
+        {
+          if (i > 0)
+            check (strcasecmp (array[i - 1], array[i]) < 0);
+          check (stringi_set_contains (set, array[i]));
+        }
+      free (array);
     }
 }
 
-- 
2.30.2