org.jscience.mathematics.algebraic.matrices
Class BooleanVector

java.lang.Object
  extended by org.jscience.mathematics.algebraic.AbstractHypermatrix
      extended by org.jscience.mathematics.algebraic.AbstractMatrix
          extended by org.jscience.mathematics.algebraic.AbstractVector
              extended by org.jscience.mathematics.algebraic.matrices.AbstractBooleanVector
                  extended by 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.

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:

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:

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.