Changeset 2172

Timestamp:

06/07/08 09:23:03 (6 months ago)

Author:

mbr

Message:

updated to version 6.4

Files:

• psad/trunk/Bit-Vector/BitVector.c (modified) (8 diffs)
• psad/trunk/Bit-Vector/BitVector.h (modified) (6 diffs)
• psad/trunk/Bit-Vector/CHANGES.txt (modified) (2 diffs)
• psad/trunk/Bit-Vector/CREDITS.txt (modified) (2 diffs)
• psad/trunk/Bit-Vector/INSTALL.txt (modified) (6 diffs)
• psad/trunk/Bit-Vector/MANIFEST (modified) (2 diffs)
• psad/trunk/Bit-Vector/Makefile.PL (modified) (2 diffs)
• psad/trunk/Bit-Vector/README.txt (modified) (15 diffs)
• psad/trunk/Bit-Vector/ToolBox.h (modified) (3 diffs)
• psad/trunk/Bit-Vector/VERSION (modified) (1 diff)
• psad/trunk/Bit-Vector/Vector.pm (modified) (2 diffs)
• psad/trunk/Bit-Vector/Vector.pod (modified) (10 diffs)
• psad/trunk/Bit-Vector/Vector.xs (modified) (2 diffs)
• psad/trunk/Bit-Vector/examples/SetObject.pl (modified) (1 diff)
• psad/trunk/Bit-Vector/examples/benchmk1.pl (added)
• psad/trunk/Bit-Vector/examples/benchmk2.pl (added)
• psad/trunk/Bit-Vector/examples/benchmk3.pl (added)
• psad/trunk/Bit-Vector/examples/primes.pl (modified) (1 diff)
• psad/trunk/Bit-Vector/examples/test.c (modified) (1 diff)
• psad/trunk/Bit-Vector/lib/Bit/Vector/Overload.pm (modified) (2 diffs)
• psad/trunk/Bit-Vector/lib/Bit/Vector/Overload.pod (modified) (2 diffs)
• psad/trunk/Bit-Vector/lib/Bit/Vector/String.pm (added)
• psad/trunk/Bit-Vector/lib/Bit/Vector/String.pod (added)
• psad/trunk/Bit-Vector/t/00____version.t (modified) (4 diffs)
• psad/trunk/Bit-Vector/t/40__auxiliary.t (added)
• psad/trunk/Bit-Vector/typemap (modified) (1 diff)

psad/trunk/Bit-Vector/BitVector.c

@@ -223 +223 @@
-
-N_int   Set_Norm             (wordptr addr);                    /* = | X |   */
+N_int   Set_Norm2            (wordptr addr);                    /* = | X |   */
+N_int   Set_Norm3            (wordptr addr);                    /* = | X |   */
-Z_long  Set_Min              (wordptr addr);                    /* = min(X)  */
-Z_long  Set_Max              (wordptr addr);                    /* = max(X)  */
@@ -265 +267 @@
-#define  ERRCODE_ZERO  "division by zero error"
-#define  ERRCODE_OOPS  "unexpected internal error - please contact author"
+
+const N_int BitVector_BYTENORM[256] =
+{
+    0x00, 0x01, 0x01, 0x02,  0x01, 0x02, 0x02, 0x03,
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04, /* 0x00 */
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05, /* 0x10 */
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05, /* 0x20 */
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06, /* 0x30 */
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05, /* 0x40 */
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06, /* 0x50 */
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06, /* 0x60 */
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07, /* 0x70 */
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05, /* 0x80 */
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06, /* 0x90 */
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06, /* 0xA0 */
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07, /* 0xB0 */
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06, /* 0xC0 */
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07, /* 0xD0 */
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07, /* 0xE0 */
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
+    0x05, 0x06, 0x06, 0x07,  0x06, 0x07, 0x07, 0x08  /* 0xF0 */
+};
-
-/*****************************************************************************/
@@ -573 +611 @@
-charptr BitVector_Version(void)
-{
-3
+4
-}
-
@@ -780 +818 @@
-        {
-            lastY = Y + sizeY - 1;
-
+
+
+
+
+
+
-            while ((sizeX > 0) and (sizeY > 0))
-            {
@@ -787 +830 @@
-                sizeY--;
-            }
-
-
-
-
-
+
-        }
-        while (sizeX-- > 0) *X++ = fill;
@@ -3472 +3511 @@
-N_int Set_Norm(wordptr addr)                                /* = | X |       */
-{
+    byteptr byte;
+    N_word  bytes;
+    N_int   n;
+
+    byte = (byteptr) addr;
+    bytes = size_(addr) << FACTOR;
+    n = 0;
+    while (bytes-- > 0)
+    {
+        n += BitVector_BYTENORM[*byte++];
+    }
+    return(n);
+}
+
+N_int Set_Norm2(wordptr addr)                               /* = | X |       */
+{
+    N_word  size = size_(addr);
+    N_word  w0,w1;
+    N_int   n,k;
+
+    n = 0;
+    while (size-- > 0)
+    {
+        k = 0;
+        w1 = NOT (w0 = *addr++);
+        while (w0 and w1)
+        {
+            w0 &= w0 - 1;
+            w1 &= w1 - 1;
+            k++;
+        }
+        if (w0 == 0) n += k;
+        else         n += BITS - k;
+    }
+    return(n);
+}
+
+N_int Set_Norm3(wordptr addr)                               /* = | X |       */
+{
-    N_word  size  = size_(addr);
-    N_int   count = 0;
@@ -3738 +3816 @@
-
-/*****************************************************************************/
-3
+4
-/*****************************************************************************/
-/*  VERSION HISTORY:                                                         */
-/*****************************************************************************/
-/*                                                                           */
+/*    Version 6.4  03.10.04  Added C++ comp. directives. Improved "Norm()".  */
-/*    Version 6.3  28.09.02  Added "Create_List()" and "GCD2()".             */
-/*    Version 6.2  15.09.02  Overhauled error handling. Fixed "GCD()".       */
@@ -3780 +3859 @@
-/*****************************************************************************/
-/*                                                                           */
-2
+4
-/*    All rights reserved.                                                   */
-/*                                                                           */

psad/trunk/Bit-Vector/BitVector.h

@@ -1 +1 @@
-#ifndef MODULE_BIT_VECTOR
-#define MODULE_BIT_VECTOR
+#ifdef __cplusplus
+extern "C"
+{
+#endif
-/*****************************************************************************/
-/*  MODULE NAME:  BitVector.h                           MODULE TYPE:  (adt)  */
@@ -223 +227 @@
-
-N_int   Set_Norm             (wordptr addr);                    /* = | X |   */
+N_int   Set_Norm2            (wordptr addr);                    /* = | X |   */
+N_int   Set_Norm3            (wordptr addr);                    /* = | X |   */
-Z_long  Set_Min              (wordptr addr);                    /* = min(X)  */
-Z_long  Set_Max              (wordptr addr);                    /* = max(X)  */
@@ -266 +272 @@
-#define  ERRCODE_OOPS  "unexpected internal error - please contact author"
-
+extern const N_int BitVector_BYTENORM[256];
+/*
+{
+    0x00, 0x01, 0x01, 0x02,  0x01, 0x02, 0x02, 0x03,
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
+    0x01, 0x02, 0x02, 0x03,  0x02, 0x03, 0x03, 0x04,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
+    0x02, 0x03, 0x03, 0x04,  0x03, 0x04, 0x04, 0x05,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
+    0x03, 0x04, 0x04, 0x05,  0x04, 0x05, 0x05, 0x06,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
+    0x04, 0x05, 0x05, 0x06,  0x05, 0x06, 0x06, 0x07,
+    0x05, 0x06, 0x06, 0x07,  0x06, 0x07, 0x07, 0x08
+};
+*/
+
-/*****************************************************************************/
-/*  MODULE IMPLEMENTATION:                                                   */
@@ -271 +315 @@
-
-/*****************************************************************************/
-3
+4
-/*****************************************************************************/
-/*  VERSION HISTORY:                                                         */
-/*****************************************************************************/
-/*                                                                           */
+/*    Version 6.4  03.10.04  Added C++ comp. directives. Improved "Norm()".  */
-/*    Version 6.3  28.09.02  Added "Create_List()" and "GCD2()".             */
-/*    Version 6.2  15.09.02  Overhauled error handling. Fixed "GCD()".       */
@@ -313 +358 @@
-/*****************************************************************************/
-/*                                                                           */
-2
+4
-/*    All rights reserved.                                                   */
-/*                                                                           */
@@ -338 +383 @@
-/*                                                                           */
-/*****************************************************************************/
+#ifdef __cplusplus
+}
-#endif
+#endif

psad/trunk/Bit-Vector/CHANGES.txt

@@ -1 +1 @@
-                    =====================================
-3
+4
-                    =====================================
-
-
-2
+4
-                             All rights reserved.
-
@@ -10 +10 @@
-Version history:
-----------------
+
+Version 6.4   03.10.2004
+
+ +  Added compiler directives for C++.
+ +  Improved the method "Norm()".
+ +  Removed "Carp::Clan" from the distribution (available separately).
+ +  Added "Bit::Vector::String" for generic string import/export functions.
+ +  Added a new test file "t/40__auxiliary.t" for "Bit::Vector::String".
+ +  Fixed a bug in method "Copy()" concerning sign (MSB) extension.
-
-Version 6.3   28.09.2002

psad/trunk/Bit-Vector/CREDITS.txt

@@ -1 +1 @@
-                    =====================================
-3
+4
-                    =====================================
-
-
-2
+4
-                             All rights reserved.
-
@@ -170 +170 @@
-with C++ compilers.
-
+Many thanks to Runip Gopisetty <Runip.Gopisetty@Procket.com> for sending
+a patch for adding functions for generic string import and export functions.
+However, I decided to realize these in Perl instead (at least for the time
+being); you can find them in the new module "Bit::Vector::String". This way
+even octal representation and enumerations are supported.
-
+Many heartfelt thanks go to Jamie Blustein <jamie@cs.dal.ca> /
+<jamie@csd.uwo.ca> / <jamie@ACM.org> for sending me the article
+"Performance Investigation of Bit-Counting Algorithms with a
+Speedup to Lookup Table", by Eyas El-Qawasmeh, Department of
+Computer Science and Information Systems, Jordan University of
+Science and Technology, cited from the Journal of Research and
+Practice in Information Technology, Vol. 32, No. 3/4, August/
+November 2000, thus prompting my reconsideration of the
+implementation of the "Norm()" method in this module.
+
+See also his web pages, especially the pages about bit vectors,
+at:
+    http://www.cs.dal.ca/~jamie/
+    http://www.csd.uwo.ca/~jamie/
+    http://www.csd.uwo.ca/%7ejamie/.Refs/code.html
+    http://www.csd.uwo.ca/%7ejamie/publications.html#BitVectors
+    http://www.csd.uwo.ca/~jamie/BitVectors/
+
+

psad/trunk/Bit-Vector/INSTALL.txt

@@ -1 +1 @@
-                    =====================================
-3
+4
-                    =====================================
-
-
-2
+4
-                             All rights reserved.
-
@@ -23 +23 @@
-Perl version 5.000 or higher, and an ANSI C compiler. (!)
-                                     ^^^^^^
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-Moreover, you usually cannot build any modules under
-
-
-
+
+
+
+
+
+
-
-Note that ActiveState provides precompiled binaries of
-this module for their Win32 port of Perl ("ActivePerl")
-
+
+
+
+
+
+
+
+
+
+
+
-
-
@@ -44 +78 @@
-    'VERSION_FROM'      => 'Vector.pm',
-to
-3
+4
-
-Then edit the file "Vector.pm" and change the line
@@ -54 +88 @@
-Also edit the file "t/00____version.t" and change the line
-
-3
+4
-
-to
@@ -98 +132 @@
-
- 1) Change directory to the directory that has been created by unpacking this
-3
+4
-
- 2) Type "perl Makefile.PL" (or whatever the name and path of your Perl 5
@@ -183 +217 @@
-    t/28__chunklist.....ok
-    t/30_overloaded.....ok
+    t/40__auxiliary.....ok
-    All tests successful.
-0,  Tests=67417, 22
-3.72 cusr +  0.57 csys = 14.29
+1,  Tests=68151, 29
+9.75 cusr +  0.73 csys = 20.48
-
-    (Note that the exact number of tests will depend on the number of bits

psad/trunk/Bit-Vector/MANIFEST

@@ -15 +15 @@
-Vector.xs
-examples/SetObject.pl
-
+
+
+
-examples/primes.pl
-examples/test.c
-lib/Bit/Vector/Overload.pm
-lib/Bit/Vector/Overload.pod
-Carp/Clan
-Carp/Clan
+Bit/Vector/String
+Bit/Vector/String
-t/00____version.t
-t/01________new.t
@@ -42 +44 @@
-t/28__chunklist.t
-t/30_overloaded.t
+t/40__auxiliary.t
-typemap

psad/trunk/Bit-Vector/Makefile.PL

@@ -3 +3 @@
-###############################################################################
-##                                                                           ##
-2
+4
-##    All rights reserved.                                                   ##
-##                                                                           ##
@@ -20 +20 @@
-    'NAME'              => 'Bit::Vector',
-    'VERSION_FROM'      => 'Vector.pm',
+    'PREREQ_PM'         => { 'Carp::Clan' => 5.3 },
-    'OBJECT'            => '$(O_FILES)',
-#   ($] >= 5.005 ?

psad/trunk/Bit-Vector/README.txt

@@ -1 +1 @@
-                    =====================================
-3
+4
-                    =====================================
-
@@ -31 +31 @@
-
-
-3
+4
---------------------------
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
-
-
@@ -52 +47 @@
-This package with all its parts is
-
-2
+4
-All rights reserved.
-
@@ -72 +67 @@
-Perl version 5.000 or higher, and an ANSI C compiler. (!)
-                                     ^^^^^^
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-Moreover, you usually cannot build any modules under
-
-
-
+
+
+
+
+
+
-
-Note that ActiveState provides precompiled binaries of
@@ -86 +105 @@
-simply by typing "ppm install Bit-Vector" in your MS-DOS
-command shell (but note the "-" instead of "::" in the
-
+ (!)
-
-If your firewall prevents "ppm" from downloading
@@ -99 +118 @@
----------------------
-
-3
+4
-been tested successfully with the following configurations:
-
@@ -109 +128 @@
-  Perl 5.7.2     -  FreeBSD 4.1.1-RELEASE
-  Perl 5.8.0     -  FreeBSD 4.1.1-RELEASE
-
-
-
-
-
+
+
-
-
@@ -152 +168 @@
-    Bit::Vector(3)
-    Bit::Vector::Overload(3)
-Carp::Clan
+Bit::Vector::String
-
-If Perl is not available on your system, you can also read the ".pod"
@@ -159 +175 @@
-    ./Vector.pod
-    ./lib/Bit/Vector/Overload.pod
-Carp/Clan
+Bit/Vector/String
-
-directly.
@@ -167 +183 @@
-----------------
-
-modul
+packag
-methods for handling them.
-
@@ -173 +189 @@
-vectors (compare with the method list below!).
-
-modul
+packag
-C applications; Perl is not necessarily required.
-
-odule is intended to serve as a base class for other applications
-r application classes, such as implementing sets or performing big
-
+ain module of this package is intended to serve as a base class for
+ther applications or application classes, such as implementing sets or
+performing big 
-
-All methods are implemented in C internally for maximum performance.
@@ -189 +205 @@
-module alone!
-
-
+
+
+
+
-
-  -  For example for implementing sets and performing set operations
@@ -198 +217 @@
-     "Sieve of Erathostenes" (for calculating prime numbers),
-
-modul
+packag
-      O(1) or O(n/b), where "b" is the number of bits in a machine word
-      on your system.)
@@ -237 +256 @@
-enumerations.
-
-modul
+packag
-also the reason why its methods are implemented in C.
-
-modul
+packag
-basic storage unit, but rather uses machine words, assuming that a machine
-word is the most efficiently handled size of all scalar types on all
@@ -250 +269 @@
-
-The greater the size of this basic storage unit, the better the complexity
-modul
+packag
-average waste of unused bits in the last word.
-

psad/trunk/Bit-Vector/ToolBox.h

@@ -2 +2 @@
-#define MODULE_TOOLBOX
-#ifdef __cplusplus
-
+
+
-#endif
-/*****************************************************************************/
@@ -116 +117 @@
-
-/*****************************************************************************/
-4
+5
-/*****************************************************************************/
-/*  VERSION HISTORY:                                                         */
-/*****************************************************************************/
-/*                                                                           */
+/*    Version 5.5   03.10.04  Added compiler directives for C++.             */
-/*    Version 5.4   08.09.02  Added conditional changes for MacOS/MacPerl.   */
-/*    Version 5.3   12.05.98  Completed history.                             */
@@ -145 +147 @@
-/*****************************************************************************/
-/*                                                                           */
-2
+4
-/*    All rights reserved.                                                   */
-/*                                                                           */

psad/trunk/Bit-Vector/VERSION

@@ -1 @@
-3
+4

psad/trunk/Bit-Vector/Vector.pm

@@ -2 +2 @@
-###############################################################################
-##                                                                           ##
-2
+4
-##    All rights reserved.                                                   ##
-##                                                                           ##
@@ -24 +24 @@
-@EXPORT_OK = qw();
-
-3
+4
-
-bootstrap Bit::Vector $VERSION;

psad/trunk/Bit-Vector/Vector.pod

@@ -9 +9 @@
-
-See L<Bit::Vector::Overload(3)>.
+
+=head2 MORE STRING IMPORT/EXPORT
+
+See L<Bit::Vector::String(3)>.
-
-=head2 CLASS METHODS
@@ -343 +347 @@
-  Norm
-      $norm = $set->Norm();
+      $norm = $set->Norm2();
+      $norm = $set->Norm3();
-
-  Min
@@ -504 +510 @@
-See L<Bit::Vector::Overload(3)>.
-
+=head2 MORE STRING IMPORT/EXPORT
+
+See L<Bit::Vector::String(3)>.
+
-=head2 CLASS METHODS
-
@@ -590 +600 @@
-all in one go.
-
-s more efficient than performing these two steps separately
-
-
-
-
-
-
-internally, and then passes the given string to the method "C<from_Hex()>"
+nternally first calls the bit vector constructor method
+
+
+
+
+
+
+of one additional method invocation
-
-An exception will be raised if the necessary memory cannot be allocated
@@ -617 +627 @@
-all in one go.
-
-s more efficient than performing these two steps separately
-
-
-
-
-
-
-internally, and then passes the given string to the method "C<from_Bin()>"
+nternally first calls the bit vector constructor method
+
+
+
+
+
+
+of one additional method invocation
-
-An exception will be raised if the necessary memory cannot be allocated
@@ -643 +653 @@
-all in one go.
-
-
-
-
+
+
+
+
+
+
+
-and second because it saves you from the associated overhead of one
-additional method invocation.
-
-The method first calls the bit vector constructor method "C<new()>"
-internally, and then passes the given string to the method "C<from_Dec()>".
-
-An exception will be raised if the necessary memory cannot be allocated
@@ -669 +680 @@
-all in one go.
-
-
-
-
+
+
+
+
+
+
+
-and second because it saves you from the associated overhead of one
-additional method invocation.
-
-The method first calls the bit vector constructor method "C<new()>"
-internally, and then passes the given string to the method "C<from_Enum()>".
-
-An exception will be raised if the necessary memory cannot be allocated
@@ -2902 +2914 @@
-set.
-
+Uses a byte lookup table for calculating the number of set bits
+per byte, and thus needs a time for evaluation (and a number of
+loops) linearly proportional to the length of the given bit vector
+(in bytes).
+
+This should be the fastest algorithm on average.
+
+=item *
+
+C<$norm = $set-E<gt>Norm2();>
+
+Returns the norm (number of bits which are set) of the given vector.
+
+This is equivalent to the number of elements contained in the given
+set.
+
+This does the same as the method "C<Norm()>" above, only with a
+different algorithm:
+
+This method counts the number of set and cleared bits at the same
+time and will stop when either of them has been exhausted, thus
+needing at most half as many loops per machine word as the total
+number of bits in a machine word - in fact it will need a number
+of loops equal to the minimum of the number of set bits and the
+number of cleared bits.
+
+This might be a faster algorithm than of the method "C<Norm()>"
+above on some systems, depending on the system's architecture
+and the compiler and optimisation used, for bit vectors with
+sparse set bits and for bit vectors with sparse cleared bits
+(i.e., predominantly set bits).
+
+=item *
+
+C<$norm = $set-E<gt>Norm3();>
+
+Returns the norm (number of bits which are set) of the given vector.
+
+This is equivalent to the number of elements contained in the given
+set.
+
+This does the same as the two methods "C<Norm()>" and "C<Norm2()>"
+above, however with a different algorithm.
+
+In fact this is the implementation of the method "C<Norm()>" used
+in previous versions of this module.
+
+The method needs a number of loops per machine word equal to the
+number of set bits in that machine word.
+
+Only for bit vectors with sparse set bits will this method be
+fast; it will depend on a system's architecture and compiler
+whether the method will be faster than any of the two methods
+above in such cases.
+
+On average however, this is probably the slowest method of the
+three.
+
-=item *
-
@@ -3054 +3124 @@
-=head1 SEE ALSO
-
-
-
-
+
+
+
+
+
+
+
+
-Graph::Kruskal(3).
-
-perl(1), perlsub(1), perlmod(1), perlref(1),
-perlobj(1), perlbot(1), perltoot(1), perlxs(1),
-perlxstut(1), perlguts(1), overload(3).
-