[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] master 1e60e01: * rbit/rbit.el: Add 'rbit-map' function
From: |
Stefan Monnier |
Subject: |
[elpa] master 1e60e01: * rbit/rbit.el: Add 'rbit-map' function |
Date: |
Wed, 24 Jan 2018 22:06:10 -0500 (EST) |
branch: master
commit 1e60e018fd28bd16d10304c27da8cbf8f382c1ae
Author: Stefan Monnier <address@hidden>
Commit: Stefan Monnier <address@hidden>
* rbit/rbit.el: Add 'rbit-map' function
Require ert.
(rbit--bdepth): Simplify.
(rbit-map): New function.
---
packages/rbit/rbit.el | 37 +++++++++++++++++++++++++++++--------
1 file changed, 29 insertions(+), 8 deletions(-)
diff --git a/packages/rbit/rbit.el b/packages/rbit/rbit.el
index 56945db..2d19e5d 100644
--- a/packages/rbit/rbit.el
+++ b/packages/rbit/rbit.el
@@ -1,6 +1,6 @@
;;; rbit.el --- Red-black persistent interval trees -*- lexical-binding: t;
-*-
-;; Copyright (C) 2017 Free Software Foundation, Inc.
+;; Copyright (C) 2017-2018 Free Software Foundation, Inc.
;; Author: Stefan Monnier <address@hidden>
;; Keywords: data structures, binary tree, intervals
@@ -50,7 +50,7 @@
;;; Code:
(eval-when-compile (require 'cl-lib))
-
+(require 'ert)
(cl-defstruct (rbit-tree
(:conc-name rbit--)
@@ -270,12 +270,9 @@ compute the resulting value."
(defun rbit--bdepth (tree)
"Return black depth of TREE."
(if (null tree) 0
- (let ((blackness (rbit--black tree)))
- (if (zerop blackness)
- ;; We don't really care if red nodes are balanced.
- (max (rbit--bdepth (rbit--left tree))
- (rbit--bdepth (rbit--right tree)))
- (+ blackness (rbit--bdepth (rbit--left tree)))))))
+ (+ (rbit--black tree)
+ ;; Red nodes are allowed to have a nil subtree.
+ (rbit--bdepth (or (rbit--left tree) (rbit--right tree))))))
(defun rbit-do (f tree)
"Call F on each interval in TREE.
@@ -393,6 +390,30 @@ F is called with 3 args: BEG, END, and VAL. Its return
value is ignored."
(rbit--make (rbit--black tree) (max beg tbeg) (min end tend)
(rbit--val tree) nleft nright))))))))
+(defun rbit-map (fun tree)
+ "Pass every value carried by TREE through FUN and return the resulting tree."
+ (when tree
+ (rbit--node (rbit--black tree) (rbit--beg tree) (rbit--end tree)
+ (funcall fun (rbit--val tree))
+ (rbit-map fun (rbit--left tree))
+ (rbit-map fun (rbit--right tree)))))
+
+;; (defun rbit-merge (tree1 tree2 &optional fun)
+;; "Return the \"union\" of TREE1 and TREE2.
+;; The value used for those ranges covered by both trees, is that returned by
+;; FUN called with both values.
+;; If nil, FUN is taken to just return its first argument."
+;; ;; Since `tree1' and `tree2' don't necessarily have the same depth,
+;; ;; there isn't much bdepth to preserve here!
+;; (cond
+;; ((null tree1) tree2)
+;; ((null tree2) tree1)
+;; ((<= (rbit--end tree1) (rbit--beg tree2))
+;; (let* ((l1 (rbit--left tree1))
+;; (r1 (rbit--right tree1))
+;; (l2 (rbit--left tree2))
+;; (r2 (rbit--right tree2))
+
(defun rbit-min (tree)
"Return the smallest key of TREE, if any."
(when tree (or (rbit-min (rbit--left tree)) (rbit--beg tree))))
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [elpa] master 1e60e01: * rbit/rbit.el: Add 'rbit-map' function,
Stefan Monnier <=