src/code/xset.lisp

   1 ;;;; This software is part of the SBCL system. See the README file for
   2 ;;;; more information.
   3 ;;;;
   4 ;;;; This software is derived from the CMU CL system, which was
   5 ;;;; written at Carnegie Mellon University and released into the
   6 ;;;; public domain. The software is in the public domain and is
   7 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
   8 ;;;; files for more information.
   9
  10 ;;;; XSET
  11 ;;;;
  12 ;;;; A somewhat efficient set implementation that can store arbitrary
  13 ;;;; objects. For small sets the data is stored in a list, but when
  14 ;;;; the amount of elements grows beyond +XSET-LIST-SIZE-LIMIT+, we
  15 ;;;; switch to a hash-table instead.
  16 ;;;;
  17 ;;;; ALLOC-XSET allocates an empty XSET. ADD-TO-XSET adds an element
  18 ;;;; to an XSET: it should be used only on freshly allocated XSETs.
  19 ;;;;
  20 ;;;; XSET-EMPTY-P, XSET-INTERSECTION, XSET-SUBSET-P, and XSET-MEMBER-P
  21 ;;;; do the obvious things. MAP-XSET maps over the element, but
  22 ;;;; requires a function as the first argument -- not a function
  23 ;;;; designator.
  24 ;;;;
  25 ;;;; XSET-LIST-SIZE is true only for XSETs whose data is stored into a
  26 ;;;; list -- XSET-COUNT returns the real value.
  27
  28 (in-package "SB!KERNEL")
  29
  30 #!-sb-fluid
  31 (declaim (inline alloc-xset xset-data (setf xset-data) xset-list-size (setf xset-list-size)))
  32 (defstruct (xset (:constructor alloc-xset) (:copier nil) (:predicate nil))
  33   (list-size 0 :type index)
  34   (data nil :type (or list hash-table)))
  35
  36 (defun xset-count (xset)
  37   (let ((data (xset-data xset)))
  38     (if (listp data)
  39         (xset-list-size xset)
  40         (hash-table-count data))))
  41
  42 (defun map-xset (function xset)
  43   (declare (function function))
  44   (let ((data (xset-data xset)))
  45     (if (listp data)
  46         (dolist (elt data)
  47           (funcall function elt))
  48         (maphash (lambda (k v)
  49                    (declare (ignore v))
  50                    (funcall function k))
  51                  data)))
  52   nil)
  53
  54 (defconstant +xset-list-size-limit+ 24)
  55
  56 ;;; Checks that the element is not in the set yet.
  57 (defun add-to-xset (elt xset)
  58   (let ((data (xset-data xset))
  59         (size (xset-list-size xset)))
  60     (if (listp data)
  61         (if (< size +xset-list-size-limit+)
  62             (unless (member elt data :test #'eql)
  63               (setf (xset-list-size xset) (1+ size)
  64                     (xset-data xset) (cons elt data)))
  65             (let ((table (make-hash-table :size (* 2 size) :test #'eql)))
  66               (setf (gethash elt table) t)
  67               (dolist (x data)
  68                 (setf (gethash x table) t))
  69               (setf (xset-data xset) table)))
  70         (setf (gethash elt data) t))))
  71
  72 ;; items must be canonical - no duplicates - and few in number.
  73 (defun xset-from-list (items)
  74   (let ((n (length items)))
  75     (aver (<= n +xset-list-size-limit+))
  76     (let ((xset (alloc-xset)))
  77       (setf (xset-list-size xset) n (xset-data xset) items)
  78       xset)))
  79
  80 (defun xset-union (a b)
  81   (let ((xset (alloc-xset)))
  82     (map-xset (lambda (x)
  83                 (add-to-xset x xset))
  84               a)
  85     (map-xset (lambda (y)
  86                 (add-to-xset y xset))
  87               b)
  88     xset))
  89
  90 (defun xset-member-p (elt xset)
  91   (let ((data (xset-data xset)))
  92     (if (listp data)
  93         (member elt data :test #'eql)
  94         (gethash elt data))))
  95
  96 (defun xset-members (xset)
  97   (let ((data (xset-data xset)))
  98     (if (listp data)
  99         data
 100         (let (members)
 101           (maphash (lambda (k v)
 102                      (declare (ignore v))
 103                      (push k members))
 104                    data)
 105           members))))
 106
 107 (defun xset-intersection (a b)
 108   (let ((intersection (alloc-xset)))
 109     (multiple-value-bind (source lookup)
 110         (if (< (xset-list-size a) (xset-list-size b))
 111             (values b a)
 112             (values a b))
 113       (let ((data (xset-data lookup)))
 114         (map-xset (if (listp data)
 115                       (lambda (elt)
 116                         (when (member elt data :test #'eql)
 117                           (add-to-xset elt intersection)))
 118                       (lambda (elt)
 119                         (when (gethash elt data)
 120                           (add-to-xset elt intersection))))
 121                  source)))
 122     intersection))
 123
 124 (defun xset-subset-p (xset1 xset2)
 125   (when (<= (xset-count xset1) (xset-count xset2))
 126     (let ((data (xset-data xset2)))
 127       (map-xset
 128        (if (listp data)
 129            (lambda (elt)
 130              (unless (member elt data :test #'eql)
 131                (return-from xset-subset-p nil)))
 132            (lambda (elt)
 133              (unless (gethash elt data)
 134                (return-from xset-subset-p nil))))
 135        xset1))
 136     t))
 137
 138 #!-sb-fluid (declaim (inline xset-empty-p))
 139 (defun xset-empty-p (xset)
 140   (not (xset-data xset)))