branch: externals/phpinspect
commit 111fa2f4b5c9c383f169b3f5785011b7b109e260
Author: Hugo Thunnissen <de...@hugot.nl>
Commit: Hugo Thunnissen <de...@hugot.nl>
Fix bugs in splay tree "find" functions
---
phpinspect-splayt.el | 114 +++++++++++++++++++++++++++------------------------
test/test-splayt.el | 4 +-
2 files changed, 63 insertions(+), 55 deletions(-)
diff --git a/phpinspect-splayt.el b/phpinspect-splayt.el
index fd8433ed42..4d6ddc3c02 100644
--- a/phpinspect-splayt.el
+++ b/phpinspect-splayt.el
@@ -52,7 +52,6 @@
;; (especially parse-file.el in the benchmarks folder), your PR will be
welcomed.
;;
-
;;; Code:
(define-inline phpinspect-make-splayt-node (key value &optional left right
parent temp-store)
@@ -292,6 +291,21 @@ near the top of the tee."
(,(car place-and-splayt) (phpinspect-splayt-root-node ,(cadr
place-and-splayt)))
,@body))
+(define-inline phpinspect-splayt-node-key-less-p (node key)
+ (inline-quote (> ,key (phpinspect-splayt-node-key ,node))))
+
+(define-inline phpinspect-splayt-node-key-le-p (node key)
+ (inline-quote (>= ,key (phpinspect-splayt-node-key ,node))))
+
+(define-inline phpinspect-splayt-node-key-equal-p (node key)
+ (inline-quote (= ,key (phpinspect-splayt-node-key ,node))))
+
+(define-inline phpinspect-splayt-node-key-greater-p (node key)
+ (inline-quote (< ,key (phpinspect-splayt-node-key ,node))))
+
+(define-inline phpinspect-splayt-node-key-ge-p (node key)
+ (inline-quote (<= ,key (phpinspect-splayt-node-key ,node))))
+
(define-inline phpinspect-splayt-find-node (splayt key)
(inline-letevals (splayt key)
(inline-quote
@@ -302,7 +316,7 @@ near the top of the tee."
(progn
(phpinspect-splay ,splayt current)
(throw 'return current))
- (if (< ,key (phpinspect-splayt-node-key current))
+ (if (phpinspect-splayt-node-key-greater-p current ,key)
(setq current (phpinspect-splayt-node-left current))
(setq current (phpinspect-splayt-node-right current))))))))))
@@ -312,9 +326,9 @@ near the top of the tee."
(let ((current (phpinspect-splayt-root-node ,splayt)))
(catch 'return
(while current
- (if (or (and (> (phpinspect-splayt-node-key current) ,key)
+ (if (or (and (phpinspect-splayt-node-key-greater-p current ,key)
(not (phpinspect-splayt-node-left current)))
- (and (<= (phpinspect-splayt-node-key current) ,key)
+ (and (phpinspect-splayt-node-key-le-p current ,key)
(not (phpinspect-splayt-node-right current))))
(throw 'return current)
(if (< ,key (phpinspect-splayt-node-key current))
@@ -329,31 +343,20 @@ near the top of the tee."
(catch 'break
(while current
- (if (>= ,key (phpinspect-splayt-node-key current))
- (setf current (phpinspect-splayt-node-right current)
- smallest current)
- (throw 'break nil))))
+ (cond
+ ((phpinspect-splayt-node-key-greater-p current ,key)
+ (when (and smallest
+ (phpinspect-splayt-node-key-greater-p
+ current (phpinspect-splayt-node-key smallest)))
+ (throw 'break nil))
- (catch 'return
- (while current
- (when (= (+ ,key 1) (phpinspect-splayt-node-key current))
- (throw 'return current))
-
- (cond ((and (phpinspect-splayt-node-parent current)
- (< ,key (phpinspect-splayt-node-key
(phpinspect-splayt-node-parent current)))
- (eq (phpinspect-splayt-node-right
(phpinspect-splayt-node-parent current))
- current))
- (setf current (phpinspect-splayt-node-parent current)
- smallest current))
- ((phpinspect-splayt-node-left current)
- (setf current (phpinspect-splayt-node-left current))
- (when (< ,key (phpinspect-splayt-node-key current))
- (setf smallest current)))
- ((>= ,key (phpinspect-splayt-node-key current))
- (if (phpinspect-splayt-node-right current)
- (setf current (phpinspect-splayt-node-right current))
- (throw 'return smallest)))
- (t (throw 'return smallest)))))))))
+ (setf smallest current
+ current (phpinspect-splayt-node-left current)))
+ ((phpinspect-splayt-node-right current)
+ (setf current (phpinspect-splayt-node-right current)))
+ (t (throw 'break nil)))))
+
+ smallest))))
(define-inline phpinspect-splayt-find-largest-node-before (splayt key)
(inline-letevals (splayt key)
@@ -363,32 +366,19 @@ near the top of the tee."
(catch 'break
(while current
- (if (<= ,key (phpinspect-splayt-node-key current))
- (setf current (phpinspect-splayt-node-left current)
- largest current)
- (throw 'break nil))))
-
- (catch 'return
- (while current
- (when (= (+ ,key 1) (phpinspect-splayt-node-key current))
- (throw 'return current))
-
- (cond ((and (phpinspect-splayt-node-parent current)
- (> ,key (phpinspect-splayt-node-key
(phpinspect-splayt-node-parent current)))
- (eq (phpinspect-splayt-node-left
(phpinspect-splayt-node-parent current))
- current))
- (setf current (phpinspect-splayt-node-parent current)
- largest current))
- ((phpinspect-splayt-node-right current)
- (setf current (phpinspect-splayt-node-right current))
- (when (> ,key (phpinspect-splayt-node-key current))
- (setf largest current)))
- ((<= ,key (phpinspect-splayt-node-key current))
- (if (phpinspect-splayt-node-left current)
- (setf current (phpinspect-splayt-node-left current))
- (throw 'return largest)))
- (t (throw 'return largest)))))))))
-
+ (cond
+ ((and (phpinspect-splayt-node-key-less-p current ,key))
+ (when (and largest
+ (phpinspect-splayt-node-key-less-p
+ current (phpinspect-splayt-node-key largest)))
+ (throw 'break nil))
+ (setf largest current
+ current (phpinspect-splayt-node-right current)))
+ ((phpinspect-splayt-node-left current)
+ (setf current (phpinspect-splayt-node-left current)))
+ (t (throw 'break nil)))))
+
+ largest))))
(defsubst phpinspect-splayt-find-all-after (splayt key)
"Find all values in SPLAYT with a key higher than KEY."
@@ -406,6 +396,22 @@ near the top of the tee."
(setq first nil)))
all))
+(defsubst phpinspect-splayt-find-all-before (splayt key)
+ "Find all values in SPLAYT with a key higher than KEY."
+ (let ((first (phpinspect-splayt-find-largest-node-before splayt key))
+ all)
+ (while first
+ (push (phpinspect-splayt-node-value first) all)
+
+ (phpinspect-splayt-node-traverse (sibling (phpinspect-splayt-node-left
first))
+ (setq all (nconc all (list sibling))))
+
+ (if (and (phpinspect-splayt-node-parent first)
+ (eq first (phpinspect-splayt-node-right
(phpinspect-splayt-node-parent first))))
+ (setq first (phpinspect-splayt-node-parent first))
+ (setq first nil)))
+ all))
+
(define-inline phpinspect-splayt-find-smallest-after (splayt key)
"Find value of node with smallest key that is higher than KEY in SPLAYT."
(inline-quote
diff --git a/test/test-splayt.el b/test/test-splayt.el
index 292fe964e0..525fe1aaae 100644
--- a/test/test-splayt.el
+++ b/test/test-splayt.el
@@ -128,7 +128,9 @@
(should (string= "four" (phpinspect-splayt-find-largest-before tree 8)))
- (should (string= "eleven" (phpinspect-splayt-find-largest-before tree
12)))))
+ (should (string= "eleven" (phpinspect-splayt-find-largest-before tree 12)))
+ (should (string= "one" (phpinspect-splayt-find-largest-before tree 2)))
+ (should (string= "twelve" (phpinspect-splayt-find-largest-before tree
13)))))
(ert-deftest phpinspect-splayt-find-all-after ()
