cgit.sxemacs.org Git - sxemacs/blob - tests/automated/bloom-tests.el

   1 ;;;  bloom-tests.el -- Regression Tests for bloom filters
   2 ;; Copyright (C) 2005 Sebastian Freundt
   3 ;;
   4 ;; Author: Sebastian Freundt <hroptatyr@sxemacs.org>
   5 ;; Keywords: tests
   6 ;;
   7 ;; This file is part of SXEmacs.
   8 ;;
   9 ;; SXEmacs is free software: you can redistribute it and/or modify it
  10 ;; under the terms of the GNU General Public License as published by the
  11 ;; Free Software Foundation, either version 3 of the License, or (at your
  12 ;; option) any later version.
  13
  14 ;; SXEmacs is distributed in the hope that it will be
  15 ;; useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17 ;; General Public License for more details.
  18
  19 ;; You should have received a copy of the GNU General Public License
  20 ;; along with this program.  If not, see <http://www.gnu.org/licenses/>.
  21 ;;
  22 ;;; Synched up with: Not in FSF.
  23 ;;
  24 ;;; Commentary:
  25 ;;
  26 ;; See test-harness.el for instructions on how to run these tests.
  27
  28 (eval-when-compile
  29   (condition-case nil
  30       (require 'test-harness)
  31     (file-error
  32      (push "." load-path)
  33      (when (and (boundp 'load-file-name) (stringp load-file-name))
  34        (push (file-name-directory load-file-name) load-path))
  35      (require 'test-harness))))
  36
  37
  38 \f
  39 ;; create some bloom filters
  40 (let ((b1 (make-bloom))
  41       (b2 (make-bloom))
  42       (b3 (make-bloom 512))
  43       (b4 (make-bloom 512 26)))
  44   (eval `(Assert (eq (bloom-order ,b1)
  45                      (bloom-order ,b2))))
  46   (eval `(Assert (eq (bloom-order ,b3) 512)))
  47   (eval `(Assert (eq (bloom-order ,b4) 512)))
  48   (eval `(Assert (eq (bloom-degree ,b1)
  49                      (bloom-degree ,b2))))
  50   (eval `(Assert (eq (bloom-degree ,b4) 26)))
  51   (eval `(Assert (eq (bloom-size ,b1) 0)))
  52   (eval `(Assert (eq (bloom-size ,b2) 0)))
  53   (eval `(Assert (eq (bloom-size ,b3) 0)))
  54   (eval `(Assert (eq (bloom-size ,b4) 0)))
  55
  56   (Assert (bloomp b1))
  57   (Assert (bloomp b2))
  58   (Assert (bloomp b3))
  59   (Assert (bloomp b4))
  60
  61   ;; add some elements
  62   (bloom-add b1 12)
  63   (bloom-add b1 21)
  64   (bloom-add b1 0)
  65
  66   (eval `(Assert (bloom-owns-p ,b1 12)))
  67   (eval `(Assert (bloom-owns-p ,b1 21)))
  68   (eval `(Assert (bloom-owns-p ,b1 0)))
  69   (eval `(Assert (not (bloom-owns-p ,b1 13))))
  70   (eval `(Assert (not (bloom-owns-p ,b1 17))))
  71   (eval `(Assert (eq (bloom-size ,b1) 3)))
  72
  73   (bloom-remove b1 12)
  74   (bloom-remove b1 21)
  75
  76   (eval `(Assert (not (bloom-owns-p ,b1 12))))
  77   (eval `(Assert (not (bloom-owns-p ,b1 21))))
  78   (eval `(Assert (bloom-owns-p ,b1 0)))
  79   (eval `(Assert (eq (bloom-size ,b1) 1)))
  80
  81   (bloom-add b1 12)
  82   (bloom-add b1 21)
  83
  84   (bloom-add b2 2)
  85   (bloom-add b2 16)
  86   (bloom-add b2 0)
  87
  88   (eval `(Assert (not (bloom-owns-p ,b2 12))))
  89   (eval `(Assert (not (bloom-owns-p ,b2 21))))
  90   (eval `(Assert (bloom-owns-p ,b2 2)))
  91   (eval `(Assert (bloom-owns-p ,b2 16)))
  92   (eval `(Assert (bloom-owns-p ,b2 0)))
  93
  94   (setq b3 (bloom-union b1 b2))
  95
  96   (eval `(Assert (bloom-owns-p ,b3 12)))
  97   (eval `(Assert (bloom-owns-p ,b3 21)))
  98   (eval `(Assert (bloom-owns-p ,b3 2)))
  99   (eval `(Assert (bloom-owns-p ,b3 16)))
 100   (eval `(Assert (bloom-owns-p ,b3 0)))
 101
 102   (eval `(Assert (>= (bloom-size ,b3) 5)))
 103   (eval `(Assert (not (bloom-owns-p ,b3 17))))
 104
 105 ;;; moved to man/lispref/lists.texi -hroptatyr
 106 ;;   ;; when we add 8-times-degree-times more elements than the order
 107 ;;   ;; of the bloom we expect it to turn into a universe
 108 ;;
 109 ;;   (dotimes (i (* 8 (bloom-degree b4) (bloom-order b4)))
 110 ;;     (bloom-add b4 i))
 111 ;;
 112 ;;   (eval `(Assert (bloom-owns-p ,b4 'a-symbol-i-never-added)))
 113 ;;   (eval `(Assert (bloom-owns-p ,b4 "a-string-i-never-added")))
 114 ;;   (eval `(Assert (bloom-owns-p ,b4 [a vector i never added])))
 115   )
 116
 117
 118 ;; dealing with universes
 119 (let ((b1 (make-bloom-universe))
 120       (b2 (make-bloom-universe))
 121       (b3 (make-bloom-universe 512))
 122       (b4 (make-bloom-universe 512 26)))
 123   (eval `(Assert (eq (bloom-order ,b1)
 124                      (bloom-order ,b2))))
 125   (eval `(Assert (eq (bloom-order ,b3) 512)))
 126   (eval `(Assert (eq (bloom-order ,b4) 512)))
 127   (eval `(Assert (eq (bloom-degree ,b1)
 128                      (bloom-degree ,b2))))
 129   (eval `(Assert (eq (bloom-degree ,b4) 26)))
 130   (eval `(Assert (eq (bloom-size ,b1)
 131                      (bloom-size ,b2))))
 132   (eval `(Assert (eq (bloom-size ,b3)
 133                      (bloom-size ,b4))))
 134
 135   (eval `(Assert (bloom-owns-p ,b1 21)))
 136   (eval `(Assert (bloom-owns-p ,b1 'a-symbol)))
 137   (eval `(Assert (bloom-owns-p ,b1 "a string")))
 138   (eval `(Assert (bloom-owns-p ,b1 [a vector])))
 139
 140   ;; we can delete many elements from the universe, they are still in the bloom
 141   (bloom-remove b1 21)
 142   (eval `(Assert (bloom-owns-p ,b1 21)))
 143
 144   (bloom-remove b1 'a-symbol)
 145   (eval `(Assert (bloom-owns-p ,b1 'a-symbol)))
 146
 147   (bloom-remove b1 "a string")
 148   (eval `(Assert (bloom-owns-p ,b1 "a string")))
 149
 150   (bloom-remove b1 [a vector])
 151   (eval `(Assert (bloom-owns-p ,b1 [a vector]))))
 152
 153
 154 ;;; bloom-tests.el ends here