org.jscience.mathematics.algebraic.matrices
Class BooleanVector

java.lang.Object
  org.jscience.mathematics.algebraic.AbstractHypermatrix
      org.jscience.mathematics.algebraic.AbstractMatrix
          org.jscience.mathematics.algebraic.AbstractVector
              org.jscience.mathematics.algebraic.matrices.AbstractBooleanVector
                  org.jscience.mathematics.algebraic.matrices.BooleanVector

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, Algebra.Member, Ring.Member, AbelianGroup.Member, Hypermatrix, Matrix, Module.Member, VectorSpace.Member, Vector, Member

public class BooleanVector
extends AbstractBooleanVector
implements java.lang.Cloneable, java.io.Serializable

Fixed sized (non resizable) BooleanVector. Upon instance construction a BooleanVector is told to hold a fixed number of Booleans - it's size. The size can be any number (need not be a power of 2 or so). The Booleans of a BooleanVector are indexed by nonnegative integers. Any attempt to access a Boolean at an index<0 || index>=size() will throw an IndexOutOfBoundsException.

Individual indexed Booleans can be examined, set, or cleared. Subranges can quickly be extracted, copied and replaced. Quick iteration over subranges is provided by optimized internal iterators (forEach() methods). One BooleanVector may be used to modify the contents of another BooleanVector through logical AND, OR, XOR and other similar operations.

All operations consider the Booleans 0..size()-1 and nothing else. Operations involving two BooleanVectors (like AND, OR, XOR, etc.) will throw an IllegalArgumentException if the secondary Boolean vector has a size smaller than the receiver.

A BooleanVector is never automatically resized, but it can manually be grown or shrinked via setSize(...).

For use cases that need to store several Booleans per information entity, quick accessors are provided that interpret subranges as 64 bit long integers.

Why this class? Fist, boolean[] take one byte per stored bit. This class takes one bit per stored bit. Second, many applications find the semantics of java.util.BitSet not particularly helpful for their needs. Third, operations working on all bits of a BooleanVector are extremely quick. For example, on NT, Pentium Pro 200 Mhz, SunJDK1.2.2, java -classic, for two BooleanVectors A,B (both much larger than processor cache), the following results are obtained.

• A.and(B) i.e. A = A & B --> runs at about 35 MB/sec
• A.cardinality(), i.e. determining the selectivity, the number of bits in state "true" --> runs at about 80 MB/sec
• Similar performance for or, xor, andNot, not, copy, replace, partFromTo, indexOf, clear etc.

If you need extremely quick access to individual bits: Although getting and setting individual bits with methods get(...), set(...) and put(...)is quick, it is even quicker (but not safe) to use getQuick(...) and putQuick(...) or even QuickBooleanVector.

Note that this implementation is not synchronized.

See Also:

BooleanMatrix, BitSet, Serialized Form

Constructor Summary

	BooleanVector(AbstractBooleanVector vec) Constructs a vector by copying a vector.
	BooleanVector(boolean[] array) Constructs a vector by wrapping an array.
	BooleanVector(int size) Constructs a Boolean vector that holds size Booleans.
protected	BooleanVector(long[] bits, int size) You normally need not use this method.

Method Summary

AbelianGroup.Member	add(AbelianGroup.Member v) Returns the addition of this vector and another.
AbstractBooleanVector	add(AbstractBooleanVector v) Returns the addition (or) of this vector and another.
BooleanVector	add(BooleanVector v) Returns the addition (or) of this vector and another.
BooleanVector	and(AbstractBooleanVector other) Performs a logical AND of the receiver with another Boolean vector (A = A & B).
BooleanVector	and(BooleanVector other)
BooleanVector	andNot(AbstractBooleanVector other) Clears all of the Boolean in receiver whose corresponding bit is set in the other BooleanVector (A = A \ B).
BooleanVector	andNot(BooleanVector other) Clears all of the Boolean in receiver whose corresponding bit is set in the other BooleanVector (A = A \ B).
protected void	checkSize(BooleanVector other) Sanity check for operations requiring another BooleanVector with at least the same size.
BooleanVector	clear() Clears all Boolean of the receiver.
void	clear(int bitIndex) Changes the Boolean with index bitIndex to the "clear" (false) state.
java.lang.Object	clone() Clone vector into a new vector.
protected long[]	elements() You normally need not use this method.
boolean	equals(java.lang.Object obj) Compares this object against the specified object.
long	getLongFromTo(int from, int to) Returns a long value representing Booleans of the receiver from index from to index to.
boolean	getPrimitiveElement(int bitIndex) Returns from the BooleanVector the value of the Boolean with the specified index.
int	hashCode() Returns a hash code value for the NON EMPTY receiver.
int	indexOfFromTo(int from, int to, boolean state) Returns the index of the first occurrence of the specified state.
AbstractBooleanVector	mapElements(PrimitiveMapping f) Applies a function on all the vector components.
Ring.Member	multiply(Ring.Member r) The multiplication law.
AbelianGroup.Member	negate() Returns the negative (not) of this vector.
BooleanVector	not() Performs a logical NOT on the Boolean of the receiver (A = ~A).
protected int	numberOfBooleansInPartialUnit() Returns the number of Booleans used in the trailing PARTIAL unit.
protected int	numberOfFullUnits() Returns the number of units that are FULL (not PARTIAL).
BooleanVector	or(AbstractBooleanVector other) Performs a logical OR of the receiver with another Boolean vector (A = A | B).
BooleanVector	or(BooleanVector other)
BooleanVector	partFromTo(int from, int to) Constructs and returns a new Boolean vector which is a copy of the given range.
void	putLongFromTo(long value, int from, int to) Sets Booleans of the receiver from index from to index to to the Booleans of value.
void	replaceFromToWith(int from, int to, boolean value) Sets the Booleans in the given range to the state specified by value.
void	replaceFromToWith(int from, int to, BooleanVector source, int sourceFrom) Replaces the Booleans of the receiver in the given range with the Booleans of another Boolean vector.
AbstractBooleanVector	scalarMultiply(boolean x) Returns the multiplication (and) of this vector by a scalar.
Module.Member	scalarMultiply(Ring.Member x) Returns the multiplication (and) of this vector by a scalar.
int	scalarProduct(AbstractBooleanVector v) Returns the scalar product of this vector and another.
int	scalarProduct(BooleanVector v) Returns the scalar product of this vector and another.
void	setDimension(int newSize) Shrinks or expands the receiver so that it holds newSize Booleans.
void	setElement(int bitIndex) Changes the Boolean with index bitIndex to the "set" (true) state.
void	setElement(int bitIndex, boolean value) Sets the Boolean with index bitIndex to the state specified by value.
AbelianGroup.Member	subtract(AbelianGroup.Member v) Returns the subtraction (or not) of this vector by another.
AbstractBooleanVector	subtract(AbstractBooleanVector v) Returns the subtraction (or not) of this vector by another.
BooleanVector	subtract(BooleanVector v) Returns the subtraction (or not) of this vector by another.
java.lang.String	toString() Returns a string representation of the receiver.
int	trueBooleans() Returns the number of Booleans currently in the true state.
BooleanVector	xor(AbstractBooleanVector other) Performs a logical XOR of the receiver with another Boolean vector (A = A ^ B).
BooleanVector	xor(BooleanVector other) Performs a logical XOR of the receiver with another Boolean vector (A = A ^ B).

Methods inherited from class org.jscience.mathematics.algebraic.matrices.AbstractBooleanVector

getColumn, getElement, getRow, getSubVector, read, reverse, scalarDivide, setAllElements, setColumn, setElement, setRow, setSubVector, toComplexVector, toDoubleVector, toIntegerVector, toMatrix, toPrimitiveArray, transpose

Methods inherited from class org.jscience.mathematics.algebraic.AbstractVector

getDimension, getElement, getInvalidElementMsg, toArray, toArray

Methods inherited from class org.jscience.mathematics.algebraic.AbstractMatrix

getElement, getInvalidElementMsg, numColumns, numRows, print, print, print, print, toArray

Methods inherited from class org.jscience.mathematics.algebraic.AbstractHypermatrix

getDimensions, numDimensions, numElements, numElements, toArray

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.jscience.mathematics.algebraic.Matrix

numColumns, numRows, toArray

Methods inherited from interface org.jscience.mathematics.algebraic.Hypermatrix

getDimensions, getElement, numDimensions, numElements, numElements, toArray

Constructor Detail

BooleanVector

protected BooleanVector(long[] bits,
                        int size)

You normally need not use this method. Use this method only if performance is critical. Constructs a Boolean vector with the given backing bits and size. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.

A BooleanVector is modelled as a long array, i.e. long[] bits holds Booleans of a BooleanVector. Each long value holds 64 bits. The i-th bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).

Throws:

java.lang.IllegalArgumentException - if size < 0 || size > bits.length*64.

BooleanVector

public BooleanVector(int size)

Constructs a Boolean vector that holds size Booleans. All Booleans are initially false.

Parameters:

size - the number of Booleans the Boolean vector shall have.

Throws:

java.lang.IllegalArgumentException - if size < 0.

BooleanVector

public BooleanVector(boolean[] array)

Constructs a vector by wrapping an array.

Parameters:

array - an assigned value

BooleanVector

public BooleanVector(AbstractBooleanVector vec)

Constructs a vector by copying a vector.

Parameters:

vec - an assigned value

Method Detail

trueBooleans

public int trueBooleans()

Returns the number of Booleans currently in the true state. Optimized for speed. Particularly quick if the receiver is either sparse or dense.

checkSize

protected void checkSize(BooleanVector other)

Sanity check for operations requiring another BooleanVector with at least the same size.

elements

protected long[] elements()

You normally need not use this method. Use this method only if performance is critical. Returns the Boolean vector's backing bits. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing.

A BooleanVector is modelled as a long array, i.e. long[] bits holds bits of a BooleanVector. Each long value holds 64 bits. The i-th bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).

getPrimitiveElement

public boolean getPrimitiveElement(int bitIndex)

Returns from the BooleanVector the value of the Boolean with the specified index. The value is true if the Boolean with the index bitIndex is currently set; otherwise, returns false.

Specified by:

getPrimitiveElement in class AbstractBooleanVector

Parameters:

bitIndex - the bit index.

Returns:

the value of the bit with the specified index.

Throws:

java.lang.IndexOutOfBoundsException - if bitIndex<0 || bitIndex>=size()

getLongFromTo

public long getLongFromTo(int from,
                          int to)

Returns a long value representing Booleans of the receiver from index from to index to. Booleans are returned as a long value with the return value having bit 0 set to bit from, ..., bit to-from set to bit to. All other bits of the return value are set to 0. If to-from+1==0 then returns zero (0L).

Parameters:

from - index of start bit (inclusive).

to - index of end bit (inclusive).

Returns:

the specified bits as long value.

Throws:

java.lang.IndexOutOfBoundsException - if from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64

indexOfFromTo

public int indexOfFromTo(int from,
                         int to,
                         boolean state)

Returns the index of the first occurrence of the specified state. Returns -1 if the receiver does not contain this state. Searches between from, inclusive and to, inclusive.

Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): size=10^6, from=0, to=size-1, receiver contains matching state in the very end --> 0.002 seconds elapsed time.

Parameters:

state - state to search for.

from - the leftmost search position, inclusive.

to - the rightmost search position, inclusive.

Returns:

the index of the first occurrence of the element in the receiver; returns -1 if the element is not found.

Throws:

java.lang.IndexOutOfBoundsException - if (size()>0 && (from<0 || from>to || to>=size())).

numberOfBooleansInPartialUnit

protected int numberOfBooleansInPartialUnit()

Returns the number of Booleans used in the trailing PARTIAL unit. Returns zero if there is no such trailing partial unit.

numberOfFullUnits

protected int numberOfFullUnits()

Returns the number of units that are FULL (not PARTIAL).

partFromTo

public BooleanVector partFromTo(int from,
                                int to)

Constructs and returns a new Boolean vector which is a copy of the given range. The new BooleanVector has size()==to-from+1.

Parameters:

from - the start index within the receiver, inclusive.

to - the end index within the receiver, inclusive.

Throws:

java.lang.IndexOutOfBoundsException - if size()>0 && (from<0 || from>to || to>=size())).

setElement

public void setElement(int bitIndex,
                       boolean value)

Sets the Boolean with index bitIndex to the state specified by value.

Specified by:

setElement in class AbstractBooleanVector

Parameters:

bitIndex - the index of the Boolean to be changed.

value - the value to be stored in the Boolean.

Throws:

java.lang.IndexOutOfBoundsException - if bitIndex<0 || bitIndex>=size()

putLongFromTo

public void putLongFromTo(long value,
                          int from,
                          int to)

Sets Booleans of the receiver from index from to index to to the Booleans of value. Boolean from is set to bit 0 of value, ..., bit to is set to bit to-from of value. All other bits stay unaffected. If to-from+1==0 then does nothing.

Parameters:

value - the value to be copied into the receiver.

from - index of start bit (inclusive).

to - index of end bit (inclusive).

Throws:

java.lang.IndexOutOfBoundsException - if from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64.

replaceFromToWith

public void replaceFromToWith(int from,
                              int to,
                              BooleanVector source,
                              int sourceFrom)

Replaces the Booleans of the receiver in the given range with the Booleans of another Boolean vector. Replaces the range [from,to] with the contents of the range [sourceFrom,sourceFrom+to-from], all inclusive. If source==this and the source and destination range intersect in an ambiguous way, then replaces as if using an intermediate auxiliary copy of the receiver.

Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): replace 10^6 ill aligned Booleans --> 0.02 seconds elapsed time.

Parameters:

from - the start index within the receiver, inclusive.

to - the end index within the receiver, inclusive.

source - the source BooleanVector to copy from.

sourceFrom - the start index within source, inclusive.

Throws:

java.lang.IndexOutOfBoundsException - if size()>0 && (from<0 || from>to || to>=size() || sourceFrom<0 || sourceFrom+to-from+1>source.size())).

replaceFromToWith

public void replaceFromToWith(int from,
                              int to,
                              boolean value)

Sets the Booleans in the given range to the state specified by value.

Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): replace 10^6 ill aligned Booleans --> 0.002 seconds elapsed time.

Parameters:

from - the start index, inclusive.

to - the end index, inclusive.

value - the value to be stored in the Booleans of the range.

Throws:

java.lang.IndexOutOfBoundsException - if size()>0 && (from<0 || from>to || to>=size()).

setElement

public void setElement(int bitIndex)

Changes the Boolean with index bitIndex to the "set" (true) state.

Parameters:

bitIndex - the index of the Boolean to be set.

Throws:

java.lang.IndexOutOfBoundsException - if bitIndex<0 || bitIndex>=size()

setDimension

public void setDimension(int newSize)

Shrinks or expands the receiver so that it holds newSize Booleans. If the receiver is expanded, additional false Booleans are added to the end. If the receiver is shrinked, all Booleans between the old size and the new size are lost; their memory is subject to garbage collection. (This method introduces a new backing array of elements. WARNING: if you have more than one BooleanVector or BooleanMatrix sharing identical backing elements, be sure you know what you are doing.)

Parameters:

newSize - the number of Booleans the Boolean vector shall have.

Throws:

java.lang.IllegalArgumentException - if size < 0.

hashCode

public int hashCode()

Returns a hash code value for the NON EMPTY receiver. The hash code depends only on which Booleans have been set within the receiver. The algorithm used to compute it may be described as follows.

Suppose the Booleans in the receiver were to be stored in an array of long integers called, say, Booleans, in such a manner that Boolean k is set in the receiver (for nonnegative values of k) if and only if the expression

((k>>6) < bits.length) && ((bits[k>>6] & (1L << (bit & 0x3F))) != 0)

is true. Then the following definition of the hashCode method would be a correct implementation of the actual algorithm:

 public int hashCode() {
      long h = 1234;
      for (int i = bits.length; --i >= 0; ) {
           h ^= bits[i] * (i + 1);
      }
      return (int)((h >> 32) ^ h);
 }

Note that the hash code values change if the set of bits is altered.

Specified by:

hashCode in class AbstractBooleanVector

Returns:

a hash code value for the receiver.

equals

public boolean equals(java.lang.Object obj)

Compares this object against the specified object. The result is true if and only if the argument is not null and is a BooleanVector object that has the same size as the receiver and the same Booleans set to true as the receiver. That is, for every nonnegative int index k,

((BooleanVector)obj).get(k) == this.get(k)

must be true.

Overrides:

equals in class AbstractBooleanVector

Parameters:

obj - the object to compare with.

Returns:

true if the objects are the same; false otherwise.

toString

public java.lang.String toString()

Returns a string representation of the receiver. For every index for which the receiver contains a Boolean in the "set" (true) state, the decimal representation of that index is included in the result. Such indeces are listed in order from lowest to highest, separated by ", " (a comma and a space) and surrounded by braces.

Overrides:

toString in class AbstractBooleanVector

Returns:

a string representation of this Boolean vector.

clear

public BooleanVector clear()

Clears all Boolean of the receiver.

clear

public void clear(int bitIndex)

Changes the Boolean with index bitIndex to the "clear" (false) state.

Parameters:

bitIndex - the index of the Boolean to be cleared.

Throws:

java.lang.IndexOutOfBoundsException - if bitIndex<0 || bitIndex>=size()

and

public BooleanVector and(AbstractBooleanVector other)

Performs a logical AND of the receiver with another Boolean vector (A = A & B). The receiver is modified so that a Boolean in it has the value true if and only if it already had the value true and the corresponding Boolean in the other Boolean vector argument has the value true.

Overrides:

and in class AbstractBooleanVector

Parameters:

other - a Boolean vector.

Returns:

DOCUMENT ME!

Throws:

java.lang.IllegalArgumentException - if size() > other.size().

and

public BooleanVector and(BooleanVector other)

andNot

public BooleanVector andNot(AbstractBooleanVector other)

Clears all of the Boolean in receiver whose corresponding bit is set in the other BooleanVector (A = A \ B). In other words, determines the difference (A=A\B) between two BooleanVectors.

Parameters:

other - a BooleanVector with which to mask the receiver.

Throws:

java.lang.IllegalArgumentException - if size() > other.size().

andNot

public BooleanVector andNot(BooleanVector other)

Clears all of the Boolean in receiver whose corresponding bit is set in the other BooleanVector (A = A \ B). In other words, determines the difference (A=A\B) between two BooleanVectors.

Overrides:

andNot in class AbstractBooleanVector

Parameters:

other - a BooleanVector with which to mask the receiver.

Throws:

java.lang.IllegalArgumentException - if size() > other.size().

not

public BooleanVector not()

Performs a logical NOT on the Boolean of the receiver (A = ~A).

Overrides:

not in class AbstractBooleanVector

Returns:

DOCUMENT ME!

or

public BooleanVector or(AbstractBooleanVector other)

Performs a logical OR of the receiver with another Boolean vector (A = A | B). The receiver is modified so that a Boolean in it has the value true if and only if it either already had the value true or the corresponding Boolean in the other Boolean vector argument has the value true.

Overrides:

or in class AbstractBooleanVector

Parameters:

other - a Boolean vector.

Returns:

DOCUMENT ME!

Throws:

java.lang.IllegalArgumentException - if size() > other.size().

or

public BooleanVector or(BooleanVector other)

xor

public BooleanVector xor(AbstractBooleanVector other)

Performs a logical XOR of the receiver with another Boolean vector (A = A ^ B). The receiver is modified so that a Boolean in it has the value true if and only if one of the following statements holds:

• The Boolean initially has the value true, and the corresponding bit in the argument has the value false.
• The Boolean initially has the value false, and the corresponding Boolean in the argument has the value true.

Overrides:

xor in class AbstractBooleanVector

Parameters:

other - a Boolean vector.

Returns:

DOCUMENT ME!

Throws:

java.lang.IllegalArgumentException - if size() > other.size().

xor

public BooleanVector xor(BooleanVector other)

Performs a logical XOR of the receiver with another Boolean vector (A = A ^ B). The receiver is modified so that a Boolean in it has the value true if and only if one of the following statements holds:

• The Boolean initially has the value true, and the corresponding bit in the argument has the value false.
• The Boolean initially has the value false, and the corresponding Boolean in the argument has the value true.

Parameters:

other - a Boolean vector.

Throws:

java.lang.IllegalArgumentException - if size() > other.size().

negate

public AbelianGroup.Member negate()

Returns the negative (not) of this vector.

Specified by:

negate in interface AbelianGroup.Member

Overrides:

negate in class AbstractBooleanVector

Returns:

DOCUMENT ME!

add

public AbelianGroup.Member add(AbelianGroup.Member v)

Returns the addition of this vector and another.

Specified by:

add in interface AbelianGroup.Member

Parameters:

v - a group member

Returns:

DOCUMENT ME!

add

public AbstractBooleanVector add(AbstractBooleanVector v)

Returns the addition (or) of this vector and another.

Overrides:

add in class AbstractBooleanVector

Parameters:

v - an bit vector

Returns:

DOCUMENT ME!

Throws:

IllegalDimensionException - If the vectors are different sizes.

add

public BooleanVector add(BooleanVector v)

Returns the addition (or) of this vector and another.

Parameters:

v - an bit vector

Throws:

IllegalDimensionException - If the vectors are different sizes.

subtract

public AbelianGroup.Member subtract(AbelianGroup.Member v)

Returns the subtraction (or not) of this vector by another.

Specified by:

subtract in interface AbelianGroup.Member

Parameters:

v - a group member

Returns:

DOCUMENT ME!

subtract

public AbstractBooleanVector subtract(AbstractBooleanVector v)

Returns the subtraction (or not) of this vector by another.

Overrides:

subtract in class AbstractBooleanVector

Parameters:

v - an bit vector

Returns:

DOCUMENT ME!

Throws:

IllegalDimensionException - If the vectors are different sizes.

subtract

public BooleanVector subtract(BooleanVector v)

Returns the subtraction (or not) of this vector by another.

Parameters:

v - an bit vector

Throws:

IllegalDimensionException - If the vectors are different sizes.

multiply

public Ring.Member multiply(Ring.Member r)

Description copied from interface: Ring.Member

The multiplication law.

Specified by:

multiply in interface Ring.Member

Parameters:

r - a ring member

Returns:

DOCUMENT ME!

scalarMultiply

public Module.Member scalarMultiply(Ring.Member x)

Returns the multiplication (and) of this vector by a scalar.

Specified by:

scalarMultiply in interface Module.Member

Parameters:

x - a ring member

Returns:

DOCUMENT ME!

scalarMultiply

public AbstractBooleanVector scalarMultiply(boolean x)

Returns the multiplication (and) of this vector by a scalar.

Overrides:

scalarMultiply in class AbstractBooleanVector

Parameters:

x - an bit

Returns:

DOCUMENT ME!

scalarProduct

public int scalarProduct(AbstractBooleanVector v)

Returns the scalar product of this vector and another.

Overrides:

scalarProduct in class AbstractBooleanVector

Parameters:

v - an bit vector

Returns:

DOCUMENT ME!

Throws:

IllegalDimensionException - If the vectors are different sizes.

scalarProduct

public int scalarProduct(BooleanVector v)

Returns the scalar product of this vector and another.

Parameters:

v - an bit vector

Throws:

IllegalDimensionException - If the vectors are different sizes.

mapElements

public AbstractBooleanVector mapElements(PrimitiveMapping f)

Applies a function on all the vector components. We assume that the mapping is from int to int and that input and output values are only 0 or 1 meaning respectively false, true

Overrides:

mapElements in class AbstractBooleanVector

Parameters:

f - a user-defined function.

Returns:

a bit vector.

clone

public java.lang.Object clone()

Clone vector into a new vector.

Overrides:

clone in class java.lang.Object

Returns:

the cloned vector.