[elpa] externals/parser-generator 13d76ae 207/434: Passed tests for generating list permutations of length k

[ELPA Syncer]

branch: externals/parser-generator
commit 13d76aee9293e8b3acf92268e87f81fc41c0bc67
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>

    Passed tests for generating list permutations of length k
---
 parser-generator.el           | 116 ++++++++++--------------------------------
 test/parser-generator-test.el |  37 +++++++++++---
 2 files changed, 56 insertions(+), 97 deletions(-)

diff --git a/parser-generator.el b/parser-generator.el
index 9a95db5..b4111e3 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -160,98 +160,36 @@
       (error "No grammar G defined!")))
   (nth 0 G))
 
-(defun parser-generator--get-grammar-prefixes ()
-  "Return all prefixes of length look-ahead number of terminals and 
non-terminals."
-  (let ((symbols
-         (append
-          (parser-generator--get-grammar-terminals)
-          (parser-generator--get-grammar-non-terminals)))
-        (prefixes)
-        (k parser-generator--look-ahead-number)
-        (indexes (make-hash-table :test 'equal))
-        (index)
-        (prefix)
-        (stack)
-        (increment-index)
-        (include))
-    (let ((symbols-length (length symbols))
+(defun parser-generator--get-list-permutations (list k)
+  "Return all possible LIST permutations length K."
+  (let ((permutations)
+        (permutations-length 1))
+    (let ((list-length (length list))
           (i 0))
-
-      ;; Reset all indexes
       (while (< i k)
-        (puthash i 0 indexes)
-        (push 0 index)
-        (setq i (1+ i)))
-
-      ;; Build stack of all indexes that needs to be processed
-      (let ((index-remains t))
-        (while index-remains
-
-          (setq i 0)
-          (setq prefix nil)
-          (setq include t)
-          (while (< i k)
-            (setq index (gethash i indexes))
-
-            (when increment-index
-              (when (= i increment-index)
-                (if (and
-                     (= index (1- symbols-length))
-                     (= increment-index (1- k)))
-                    (progn
-
-                      ;; Iterate columns and see if any is less than
-                      ;; max index, in that case increment it and re-do
-                      ;; last column
-                      (let ((found-not-incremented)
-                            (i-2 0))
-                        (while (and
-                                (< i-2 (1- k))
-                                (not found-not-incremented))
-                          (unless (= (gethash i-2 indexes) (1- symbols-length))
-                            (puthash i-2 (1+ (gethash i-2 indexes)) indexes)
-                            (puthash i -1 indexes)
-                            (setq include nil)
-                            (setq found-not-incremented t))
-                          (setq i-2 (1+ i-2)))
-
-                        (unless found-not-incremented
-                          (setq index-remains nil))))
-                  (if (= index (1- symbols-length))
-                      (progn
-                        (setq index 0)
-                        (setq increment-index (1+ increment-index)))
-                    (setq index (1+ index)))
-                  (puthash i index indexes))))
-
-            (when index-remains
-              (push index prefix))
-            (setq i (1+ i)))
 
-          (unless increment-index
-            (setq increment-index (1- k)))
-
-          (when (and
-                 index-remains
-                 include)
-            (setq prefix (nreverse prefix))
-            (push prefix stack))
-          ))
-
-      (while stack
-        (let ((index-list (pop stack)))
-          ;; Reset variables
-          (setq i 0)
-          (setq prefix nil)
-
-          ;; Build prefix and prefix-indexes from actual state
-          (while (< i k)
-            (setq index (nth i index-list))
-            (push (nth index symbols) prefix)
-            (setq i (1+ i)))
-
-          (push prefix prefixes))))
-    (sort prefixes 'parser-generator--sort-list)))
+        (let ((times (expt list-length (- k (1+ i))))
+              (global-i 0))
+          (while (< global-i permutations-length)
+            ;; For each list..
+            (let ((list-i 0))
+              (while (< list-i list-length)
+
+                ;; Add it |list| ^ (k - i) times to list
+                (let ((times-i 0))
+                  (while (< times-i times)
+                    (if (= i 0)
+                        (push (list (nth list-i list)) permutations)
+                      (push (nth list-i list) (nth global-i permutations)))
+                    (setq global-i (1+ global-i))
+                    (setq times-i (1+ times-i))))
+                (setq list-i (1+ list-i))))
+
+            (when (= i 0)
+              (setq permutations-length (length permutations)))))
+
+        (setq i (1+ i))))
+    (sort permutations 'parser-generator--sort-list)))
 
 (defun parser-generator--get-grammar-production-number (production)
   "If PRODUCTION exist, return it's number."
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index c6647f5..ea3195dc 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -674,7 +674,7 @@
 
 (defun parser-generator-test--merge-max-terminals ()
   "Test `parser-generator--merge-max-terminals'."
-  (message "Passed tests  for (parser-generator--merge-max-terminals)")
+  (message "Starting tests  for (parser-generator--merge-max-terminals)")
 
   (should
    (equal
@@ -694,9 +694,9 @@
 
   (message "Passed tests  for (parser-generator--merge-max-terminals)"))
 
-(defun parser-generator-test--get-grammar-prefixes ()
-  "Test `parser-generator--get-grammar-prefixes'."
-  (message "Passed tests  for (parser-generator--get-grammar-prefixes)")
+(defun parser-generator-test--get-list-permutations ()
+  "Test `parser-generator--get-list-permutations'."
+  (message "Starting tests  for (parser-generator--get-list-permutations)")
 
   (parser-generator-set-look-ahead-number 1)
   (parser-generator-set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A 
"a") (A ("b" "a"))) S))
@@ -705,7 +705,12 @@
   (should
    (equal
     '((A) (B) (S) ("a") ("b"))
-    (parser-generator--get-grammar-prefixes)))
+    (parser-generator--get-list-permutations
+     (append
+      (parser-generator--get-grammar-terminals)
+      (parser-generator--get-grammar-non-terminals))
+     parser-generator--look-ahead-number)))
+  (message "Passed test for list permutations of length 1")
 
   (parser-generator-set-look-ahead-number 2)
   (should
@@ -715,9 +720,25 @@
       (S A) (S B) (S S) (S "a") (S "b")
       ("a" A) ("a" B) ("a" S) ("a" "a") ("a" "b")
       ("b" A) ("b" B) ("b" S) ("b" "a") ("b" "b"))
-    (parser-generator--get-grammar-prefixes)))
+    (parser-generator--get-list-permutations
+     (append
+      (parser-generator--get-grammar-terminals)
+      (parser-generator--get-grammar-non-terminals))
+     parser-generator--look-ahead-number)))
+  (message "Passed test for list permutations of length 2")
 
-  (message "Passed tests  for (parser-generator--get-grammar-prefixes)"))
+  (parser-generator-set-look-ahead-number 3)
+  (should
+   (equal
+    '((A A A) (A A B) (A A S) (A A "a") (A A "b") (A B A) (A B B) (A B S) (A B 
"a") (A B "b") (A S A) (A S B) (A S S) (A S "a") (A S "b") (A "a" A) (A "a" B) 
(A "a" S) (A "a" "a") (A "a" "b") (A "b" A) (A "b" B) (A "b" S) (A "b" "a") (A 
"b" "b") (B A A) (B A B) (B A S) (B A "a") (B A "b") (B B A) (B B B) (B B S) (B 
B "a") (B B "b") (B S A) (B S B) (B S S) (B S "a") (B S "b") (B "a" A) (B "a" 
B) (B "a" S) (B "a" "a") (B "a" "b") (B "b" A) (B "b" B) (B "b" S) (B "b" "a") 
(B "b" "b") (S A A [...]
+    (parser-generator--get-list-permutations
+     (append
+      (parser-generator--get-grammar-terminals)
+      (parser-generator--get-grammar-non-terminals))
+     parser-generator--look-ahead-number)))
+  (message "Passed test for list permutations of length 3")
+
+  (message "Passed tests for (parser-generator--get-list-permutations)"))
 
 (defun parser-generator-test ()
   "Run test."
@@ -736,7 +757,7 @@
   (parser-generator-test--get-grammar-rhs)
   (parser-generator-test--get-grammar-look-aheads)
   (parser-generator-test--merge-max-terminals)
-  (parser-generator-test--get-grammar-prefixes)
+  (parser-generator-test--get-list-permutations)
 
   ;; Algorithms
   (parser-generator-test--first)