Merge branch 'improved-sets' into 'master'

improve set iteration performance

See merge request andreyorst/fennel-cljlib!9

6 files changed, 44 insertions, 41 deletions

diff --git a/LICENSE b/LICENSE
index 787c9d2..5d98ab5 100644
--- a/LICENSE
+++ b/LICENSE
@@ -1,6 +1,6 @@
 MIT License
 
-Copyright (c) 2020 Andrey Orst
+Copyright (c) 2020-2021 Andrey Listopadov
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
diff --git a/doc/cljlib.md b/doc/cljlib.md
index f1e7f5f..a06fca5 100644
--- a/doc/cljlib.md
+++ b/doc/cljlib.md
@@ -1,4 +1,4 @@
-# Cljlib (0.4.0)
+# Cljlib (0.5.0)
 Fennel-cljlib - functions from Clojure's core.clj implemented on top
 of Fennel.
 
@@ -1162,7 +1162,7 @@ syntax. Use `hash-set` function instead.
 
 ---
 
-Copyright (C) 2020 Andrey Orst
+Copyright (C) 2020-2021 Andrey Listopadov
 
 License: [MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE)
 
diff --git a/doc/macros.md b/doc/macros.md
index 7fa717c..fdced4e 100644
--- a/doc/macros.md
+++ b/doc/macros.md
@@ -1,4 +1,4 @@
-# Macros.fnl (0.4.0)
+# Macros.fnl (0.5.0)
 Macros for Cljlib that implement various facilities from Clojure.
 
 **Table of contents**
@@ -589,7 +589,7 @@ If `test` sets `binding` to non-`nil`, evaluates `body` in implicit
 
 ---
 
-Copyright (C) 2020 Andrey Orst
+Copyright (C) 2020-2021 Andrey Listopadov
 
 License: [MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE)
 
diff --git a/init.fnl b/init.fnl
index 009c0e5..7d5a7f9 100644
--- a/init.fnl
+++ b/init.fnl
@@ -1,6 +1,6 @@
-(local core {:_VERSION "0.4.0"
+(local core {:_VERSION "0.5.0"
              :_LICENSE "[MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE)"
-             :_COPYRIGHT "Copyright (C) 2020 Andrey Orst"
+             :_COPYRIGHT "Copyright (C) 2020-2021 Andrey Listopadov"
              :_MODULE_NAME "cljlib"
              :_DESCRIPTION "Fennel-cljlib - functions from Clojure's core.clj implemented on top
 of Fennel.
@@ -1091,15 +1091,17 @@ default."
                        "{")
             set-indent (length prefix)
             indent-str (string.rep " " set-indent)
-            lines (icollect [i v (pairs Set)]
-                    (.. (if (= i 1) "" indent-str)
+            lines (icollect [v (pairs Set)]
+                    (.. indent-str
                         (view v inspector (+ indent set-indent) true)))]
-        (tset lines 1 (.. prefix (or (. lines 1) "")))
+        (tset lines 1 (.. prefix (string.gsub (or (. lines 1) "") "^%s+" "")))
         (tset lines (length lines) (.. (. lines (length lines)) "}"))
         lines)))
 
 (fn ordered-set-newindex [Set]
-  "`__newindex` metamethod for ordered-set."
+  "`__newindex` metamethod for ordered-set.
+
+Updates order of all items when some key removed from set."
   (fn [t k v]
     (if (= nil v)
         (let [k (. Set k)]
@@ -1137,28 +1139,29 @@ default."
         (lua :break)))
   (and res (= size (length s2))))
 
-(fn ordered-set-ipairs [Set]
+(fn set->iseq [Set]
+  (collect [v k (pairs Set)]
+    (values k v)))
+
+(fn ordered-set-pairs [Set]
   "Returns stateless `ipairs` iterator for ordered sets."
   (fn []
-    (fn set-next [t i]
-      (fn loop [t k]
-        (local (k v) (next t k))
-        (if v (if (= v (+ 1 i))
-                  (values v k)
-                  (loop t k))))
-      (loop t))
-    (values set-next Set 0)))
-
-(fn hash-set-ipairs [Set]
+    (var i 0)
+    (var iseq nil)
+    (fn set-next [t _]
+      (when (not iseq)
+        (set iseq (set->iseq Set)))
+      (set i (+ i 1))
+      (let [v (. iseq i)]
+        (values v v)))
+    (values set-next Set nil)))
+
+(fn hash-set-pairs [Set]
   "Returns stateful `ipairs` iterator for hashed sets."
   (fn []
-    (var i 0)
-    (fn iter [t _]
-      (var (k v) (next t))
-      (for [j 1 i]
-        (set (k v) (next t k)))
-      (if k (do (set i (+ i 1))
-                (values i k))))
+    (fn iter [t k]
+      (let [v (next t k)]
+        (values v v)))
     (values iter Set nil)))
 
 (fn into-set [Set tbl]
@@ -1252,7 +1255,7 @@ same size:
 ```"
   [& xs]
   (let [Set (setmetatable {} {:__index deep-index})
-        set-ipairs (ordered-set-ipairs Set)]
+        set-pairs (ordered-set-pairs Set)]
     (var i 1)
     (each [_ val (ipairs xs)]
       (when (not (. Set val))
@@ -1268,8 +1271,7 @@ same size:
                    :__len (set-length Set)
                    :__index #(if (. Set $2) $2 nil)
                    :__newindex (ordered-set-newindex Set)
-                   :__ipairs set-ipairs
-                   :__pairs set-ipairs
+                   :__pairs set-pairs
                    :__name "ordered set"
                    :__fennelview viewset})))
 
@@ -1290,7 +1292,7 @@ supported by the Fennel reader, so you can't create sets with this
 syntax. Use `hash-set` function instead."
   [& xs]
   (let [Set (setmetatable {} {:__index deep-index})
-        set-ipairs (hash-set-ipairs Set)]
+        set-pairs (hash-set-pairs Set)]
     (each [_ val (ipairs xs)]
       (when (not (. Set val))
         (tset Set val true)))
@@ -1304,8 +1306,7 @@ syntax. Use `hash-set` function instead."
                    :__len (set-length Set)
                    :__index #(if (. Set $2) $2 nil)
                    :__newindex (hash-set-newindex Set)
-                   :__ipairs set-ipairs
-                   :__pairs set-ipairs
+                   :__pairs set-pairs
                    :__name "hash set"
                    :__fennelview viewset})))
 
@@ -1327,4 +1328,5 @@ syntax. Use `hash-set` function instead."
 ;; LocalWords:  cljlib Clojure's clj lua PUC mapv concat Clojure fn zs
 ;; LocalWords:  defmulti multi arity eq metadata prepending variadic
 ;; LocalWords:  args tbl LocalWords memoized referentially Andrey
-;; LocalWords:  Orst codepoints
+;; LocalWords:  Orst codepoints Listopadov metamethods nums multifn
+;; LocalWords:  stateful LuaJIT
diff --git a/macros.fnl b/macros.fnl
index f0e9134..81845fe 100644
--- a/macros.fnl
+++ b/macros.fnl
@@ -55,7 +55,7 @@
     (fennel.metadata:set value k v)))
 
 
-;;;;;;;;;;;;;;;;;;;;;;;;;; Runtime function builers ;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;;;;;;;;;;;;;;;;;;;;;;;;;; Runtime function builders ;;;;;;;;;;;;;;;;;;;;;;;;;;;
 
 ;; TODO: This code should be shared with `init.fnl`
 
@@ -1205,9 +1205,9 @@ Always run some side effect action:
  : defmethod
  : def
  : defonce
- :_VERSION #"0.4.0"
+ :_VERSION #"0.5.0"
  :_LICENSE #"[MIT](https://gitlab.com/andreyorst/fennel-cljlib/-/raw/master/LICENSE)"
- :_COPYRIGHT #"Copyright (C) 2020 Andrey Orst"
+ :_COPYRIGHT #"Copyright (C) 2020-2021 Andrey Listopadov"
  :_DOC_ORDER #[:fn*
                :try
                :def :defonce :defmulti :defmethod
@@ -1221,3 +1221,4 @@ Always run some side effect action:
 ;; LocalWords:  defonce metadata metatable fac defmulti Umm defmethod
 ;; LocalWords:  multimethods multimethod multifn REPL fnl AST Lua's
 ;; LocalWords:  lua tostring str concat namespace ns Cljlib Clojure
+;; LocalWords:  TODO init Andrey Listopadov
diff --git a/tests/core.fnl b/tests/core.fnl
index ab62a4b..0220c06 100644
--- a/tests/core.fnl
+++ b/tests/core.fnl
@@ -234,8 +234,8 @@
     (assert-eq (core.kvseq {123 456}) [[123 456]])
     (assert-eq (core.kvseq {:a 1}) [[:a 1]])
     (assert-eq (core.kvseq [0 0 0 10]) [[1 0] [2 0] [3 0] [4 10]])
-    (assert-eq (core.kvseq (core.ordered-set :a :b :c)) [[1 :a] [2 :b] [3 :c]])
-    (assert-eq (core.kvseq (core.hash-set :a)) [[1 :a]])
+    (assert-eq (core.kvseq (core.ordered-set :a :b :c)) [[:a :a] [:b :b] [:c :c]])
+    (assert-eq (core.kvseq (core.hash-set :a)) [[:a :a]])
     (assert-eq (core.kvseq "abc") [[1 "a"] [2 "b"] [3 "c"]]))
 
   (testing "mapv"