Commits

Robert Smith  committed d90ea3b

Initial commit.

  • Participants

Comments (0)

Files changed (5)

+Copyright (c) 2013, Robert Smith
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+  * Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+  * Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in
+    the documentation and/or other materials provided with the
+    distribution.
+
+  * Neither Robert Smith nor the names of its contributors of the
+    software may be used to endorse or promote products derived from
+    this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+                               MAP-SET
+                               -------
+
+                           By Robert Smith
+
+Implementation of a set-like data structure with constant time
+addition, removal, and random selection.
+;;;; map-set.asd
+;;;; Copyright (c) 2013 Robert Smith
+
+(asdf:defsystem #:map-set
+  :serial t
+  :description "Set-like data structure."
+  :author "Robert Smith <quad@symbo1ics.com>"
+  :license "BSD 3-clause (See LICENSE)"
+  :components ((:file "package")
+               (:file "map-set")))

File map-set.lisp

+;;;; map-set.lisp
+;;;; Copyright (c) 2013 Robert Smith
+
+(in-package #:map-set)
+
+(defstruct (map-set (:constructor make-map-set ())
+                    (:copier nil)
+                    (:print-function (lambda (obj stream depth)
+                                       (declare (ignore depth))
+                                       (print-unreadable-object
+                                           (obj stream :type t)
+                                         (format stream
+                                                 "of ~D element~:P"
+                                                 (map-set-size obj))))))
+  (table (make-hash-table)                             :type hash-table)
+  (index (make-array 16 :adjustable t :fill-pointer 0) :type vector)
+  (size  0                                             :type unsigned-byte))
+
+(defun ms-count (ms)
+  "Return the cardinality/size of the map-set MS."
+  (map-set-size ms))
+
+(defun ms-member-p (ms item)
+  "Is ITEM a member of the map-set MS?"
+  (nth-value 1 (gethash item (map-set-table ms))))
+
+(defun ms-insert (ms item)
+  "Add the item ITEM to the map-set MS."
+  (unless (ms-member-p ms item)
+    (setf (gethash item (map-set-table ms))
+          (map-set-size ms))
+    (incf (map-set-size ms))
+    (vector-push-extend item (map-set-index ms)))
+  ms)
+
+(defun ms-delete (ms item)
+  "Remove the item ITEM from the map-set MS."
+  (when (ms-member-p ms item)
+    (let* ((idx (map-set-index ms))
+           (tbl (map-set-table ms))
+           (location (gethash item tbl)))
+      ;; Move the last element in the index to the position of the
+      ;; to-be deleted item.
+      (setf (aref idx location)
+            (aref idx (1- (map-set-size ms))))
+      
+      ;; Pop the last item off the index.
+      (vector-pop (map-set-index ms))
+      
+      ;; Decrease the element count.
+      (decf (map-set-size ms))
+      
+      ;; Remove the item from the record.
+      (remhash item tbl)
+      
+      ;; Update the position of the moved element.
+      (setf (gethash (aref idx location) tbl) location)))
+  ms)
+
+(defun ms-random (ms)
+  "Select a random element of the map-set MS."
+  (let ((size (map-set-size ms)))
+    (if (zerop size)
+        nil
+        (aref (map-set-index ms)
+              (random size)))))
+
+(defun ms-map (type f ms)
+  "Map the unary function F across the map-set MS with a result type
+TYPE."
+  (map type f (map-set-index ms)))
+
+(defun ms-for-each (f ms)
+  "Apply the function F to each item in the map-set MS."
+  (map nil f (map-set-index ms)))
+

File package.lisp

+;;;; package.lisp
+;;;; Copyright (c) 2013 Robert Smith
+
+(defpackage #:map-set
+  (:use #:cl)
+  (:export #:map-set
+           #:make-map-set
+           #:map-set-p
+           
+           #:ms-count
+           #:ms-member-p
+           #:ms-insert
+           #:ms-delete
+           #:ms-random
+           #:ms-map
+           #:ms-for-each))
+