You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mahout.apache.org by sr...@apache.org on 2009/11/25 04:36:02 UTC
svn commit: r883973 [4/14] - in
/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix: ./
bitvector/ buffer/ function/ list/ list/adapter/ map/
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Swapper.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Swapper.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Swapper.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Swapper.java Wed Nov 25 03:35:59 2009
@@ -13,8 +13,6 @@
*
* @see org.apache.mahout.matrix.GenericSorting
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 03-Jul-99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Timer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Timer.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Timer.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/Timer.java Wed Nov 25 03:35:59 2009
@@ -18,39 +18,39 @@
*/
@Deprecated
public class Timer extends PersistentObject {
- private long baseTime;
- private long elapsedTime;
+ private long baseTime;
+ private long elapsedTime;
- private static final long UNIT = 1000;
+ private static final long UNIT = 1000;
/**
* Constructs a new timer, initially not started. Use start() to start the timer.
*/
public Timer() {
- this.reset();
+ this.reset();
}
/**
* Prints the elapsed time on System.out
* @return <tt>this</tt> (for convenience only).
*/
public Timer display() {
- System.out.println(this);
- return this;
+ System.out.println(this);
+ return this;
}
/**
* Same as <tt>seconds()</tt>.
*/
public float elapsedTime() {
- return seconds();
+ return seconds();
}
/**
* Returns the elapsed time in milli seconds; does not stop the timer, if started.
*/
public long millis() {
- long elapsed = elapsedTime;
- if (baseTime!=0) { // we are started
- elapsed += System.currentTimeMillis() - baseTime;
- }
- return elapsed;
+ long elapsed = elapsedTime;
+ if (baseTime!=0) { // we are started
+ elapsed += System.currentTimeMillis() - baseTime;
+ }
+ return elapsed;
}
/**
* <tt>T = this - other</tt>; Constructs and returns a new timer which is the difference of the receiver and the other timer.
@@ -59,15 +59,15 @@
* @return a new timer.
*/
public Timer minus(Timer other) {
- Timer copy = new Timer();
- copy.elapsedTime = millis() - other.millis();
- return copy;
+ Timer copy = new Timer();
+ copy.elapsedTime = millis() - other.millis();
+ return copy;
}
/**
* Returns the elapsed time in minutes; does not stop the timer, if started.
*/
public float minutes() {
- return seconds() / 60;
+ return seconds() / 60;
}
/**
* <tt>T = this + other</tt>; Constructs and returns a new timer which is the sum of the receiver and the other timer.
@@ -76,91 +76,91 @@
* @return a new timer.
*/
public Timer plus(Timer other) {
- Timer copy = new Timer();
- copy.elapsedTime = millis() + other.millis();
- return copy;
+ Timer copy = new Timer();
+ copy.elapsedTime = millis() + other.millis();
+ return copy;
}
/**
* Resets the timer.
* @return <tt>this</tt> (for convenience only).
*/
public Timer reset() {
- elapsedTime = 0;
- baseTime=0;
- return this;
+ elapsedTime = 0;
+ baseTime=0;
+ return this;
}
/**
* Returns the elapsed time in seconds; does not stop the timer, if started.
*/
public float seconds() {
- return ((float) millis()) / UNIT;
+ return ((float) millis()) / UNIT;
}
/**
* Starts the timer.
* @return <tt>this</tt> (for convenience only).
*/
public Timer start() {
- baseTime = System.currentTimeMillis();
- return this;
+ baseTime = System.currentTimeMillis();
+ return this;
}
/**
* Stops the timer. You can start it again later, if necessary.
* @return <tt>this</tt> (for convenience only).
*/
public Timer stop() {
- if (baseTime!=0) {
- elapsedTime = elapsedTime + (System.currentTimeMillis() - baseTime);
- }
- baseTime = 0;
- return this;
+ if (baseTime!=0) {
+ elapsedTime = elapsedTime + (System.currentTimeMillis() - baseTime);
+ }
+ baseTime = 0;
+ return this;
}
/**
* Shows how to use a timer in convenient ways.
*/
public static void test(int size) {
- //benchmark this piece
- Timer t = new Timer().start();
- int j=0;
- for (int i=0; i<size; i++) {
- j++;
- }
- t.stop();
- t.display();
- System.out.println("I finished the test using "+t);
-
-
-
- //do something we do not want to benchmark
- j=0;
- for (int i=0; i<size; i++) {
- j++;
- }
-
-
-
- //benchmark another piece and add to last benchmark
- t.start();
- j=0;
- for (int i=0; i<size; i++) {
- j++;
- }
- t.stop().display();
-
-
-
- //benchmark yet another piece independently
- t.reset(); //set timer to zero
- t.start();
- j=0;
- for (int i=0; i<size; i++) {
- j++;
- }
- t.stop().display();
+ //benchmark this piece
+ Timer t = new Timer().start();
+ int j=0;
+ for (int i=0; i<size; i++) {
+ j++;
+ }
+ t.stop();
+ t.display();
+ System.out.println("I finished the test using "+t);
+
+
+
+ //do something we do not want to benchmark
+ j=0;
+ for (int i=0; i<size; i++) {
+ j++;
+ }
+
+
+
+ //benchmark another piece and add to last benchmark
+ t.start();
+ j=0;
+ for (int i=0; i<size; i++) {
+ j++;
+ }
+ t.stop().display();
+
+
+
+ //benchmark yet another piece independently
+ t.reset(); //set timer to zero
+ t.start();
+ j=0;
+ for (int i=0; i<size; i++) {
+ j++;
+ }
+ t.stop().display();
}
/**
* Returns a String representation of the receiver.
*/
public String toString() {
- return "Time=" + Float.toString(this.elapsedTime()) + " secs";
+ return "Time=" + Float.toString(this.elapsedTime()) + " secs";
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitMatrix.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitMatrix.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitMatrix.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitMatrix.java Wed Nov 25 03:35:59 2009
@@ -30,8 +30,6 @@
* <p>
* <b>Note</b> that this implementation is not synchronized.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
* @see BitVector
* @see QuickBitVector
* @see java.util.BitSet
@@ -42,17 +40,17 @@
*/
@Deprecated
public class BitMatrix extends PersistentObject {
- protected int columns;
- protected int rows;
+ protected int columns;
+ protected int rows;
- /*
- * The bits of this matrix.
- * bits are stored in row major, i.e.
- * bitIndex==row*columns + column
- * columnOf(bitIndex)==bitIndex%columns
- * rowOf(bitIndex)==bitIndex/columns
- */
- protected long bits[];
+ /*
+ * The bits of this matrix.
+ * bits are stored in row major, i.e.
+ * bitIndex==row*columns + column
+ * columnOf(bitIndex)==bitIndex%columns
+ * rowOf(bitIndex)==bitIndex/columns
+ */
+ protected long bits[];
/**
* Constructs a bit matrix with a given number of columns and rows. All bits are initially <tt>false</tt>.
* @param columns the number of columns the matrix shall have.
@@ -60,7 +58,7 @@
* @throws IllegalArgumentException if <tt>columns < 0 || rows < 0</tt>.
*/
public BitMatrix(int columns, int rows) {
- elements(QuickBitVector.makeBitVector(columns*rows,1),columns,rows);
+ elements(QuickBitVector.makeBitVector(columns*rows,1),columns,rows);
}
/**
* Performs a logical <b>AND</b> of the receiver with another bit matrix.
@@ -73,8 +71,8 @@
* @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
*/
public void and(BitMatrix other) {
- checkDimensionCompatibility(other);
- toBitVector().and(other.toBitVector());
+ checkDimensionCompatibility(other);
+ toBitVector().and(other.toBitVector());
}
/**
* Clears all of the bits in receiver whose corresponding
@@ -85,27 +83,27 @@
* @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
*/
public void andNot(BitMatrix other) {
- checkDimensionCompatibility(other);
- toBitVector().andNot(other.toBitVector());
+ checkDimensionCompatibility(other);
+ toBitVector().andNot(other.toBitVector());
}
/**
* Returns the number of bits currently in the <tt>true</tt> state.
* Optimized for speed. Particularly quick if the receiver is either sparse or dense.
*/
public int cardinality() {
- return toBitVector().cardinality();
+ return toBitVector().cardinality();
}
/**
* Sanity check for operations requiring matrices with the same number of columns and rows.
*/
protected void checkDimensionCompatibility(BitMatrix other) {
- if (columns != other.columns() || rows != other.rows()) throw new IllegalArgumentException("Incompatible dimensions: (columns,rows)=("+columns+","+rows+"), (other.columns,other.rows)=("+other.columns()+","+other.rows()+")");
+ if (columns != other.columns() || rows != other.rows()) throw new IllegalArgumentException("Incompatible dimensions: (columns,rows)=("+columns+","+rows+"), (other.columns,other.rows)=("+other.columns()+","+other.rows()+")");
}
/**
* Clears all bits of the receiver.
*/
public void clear() {
- toBitVector().clear();
+ toBitVector().clear();
}
/**
* Cloning this <code>BitMatrix</code> produces a new <code>BitMatrix</code>
@@ -117,21 +115,21 @@
* @return a clone of this bit matrix.
*/
public Object clone() {
- BitMatrix clone = (BitMatrix) super.clone();
- if (this.bits != null) clone.bits = (long[]) this.bits.clone();
- return clone;
+ BitMatrix clone = (BitMatrix) super.clone();
+ if (this.bits != null) clone.bits = (long[]) this.bits.clone();
+ return clone;
}
/**
* Returns the number of columns of the receiver.
*/
public int columns() {
- return columns;
+ return columns;
}
/**
* Checks whether the receiver contains the given box.
*/
protected void containsBox(int column, int row, int width, int height) {
- if (column<0 || column+width>columns || row<0 || row+height>rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row+" ,width:"+width+", height:"+height);
+ if (column<0 || column+width>columns || row<0 || row+height>rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row+" ,width:"+width+", height:"+height);
}
/**
* Returns a shallow clone of the receiver; calls <code>clone()</code> and casts the result.
@@ -139,10 +137,10 @@
* @return a shallow clone of the receiver.
*/
public BitMatrix copy() {
- return (BitMatrix) clone();
+ return (BitMatrix) clone();
}
protected long[] elements() {
- return bits;
+ return bits;
}
/**
* You normally need not use this method. Use this method only if performance is critical.
@@ -152,10 +150,10 @@
* @throws IllegalArgumentException if <tt>columns < 0 || rows < 0 || columns*rows > bits.length*64</tt>
*/
protected void elements(long[] bits, int columns, int rows) {
- if (columns<0 || columns<0 || columns*rows>bits.length*QuickBitVector.BITS_PER_UNIT) throw new IllegalArgumentException();
- this.bits = bits;
- this.columns = columns;
- this.rows = rows;
+ if (columns<0 || columns<0 || columns*rows>bits.length*QuickBitVector.BITS_PER_UNIT) throw new IllegalArgumentException();
+ this.bits = bits;
+ this.columns = columns;
+ this.rows = rows;
}
/**
* Compares this object against the specified object.
@@ -168,15 +166,15 @@
* <code>false</code> otherwise.
*/
public boolean equals(Object obj) {
- if (obj == null || !(obj instanceof BitMatrix))
- return false;
- if (this == obj)
- return true;
+ if (obj == null || !(obj instanceof BitMatrix))
+ return false;
+ if (this == obj)
+ return true;
- BitMatrix other = (BitMatrix) obj;
- if (columns != other.columns() || rows != other.rows()) return false;
+ BitMatrix other = (BitMatrix) obj;
+ if (columns != other.columns() || rows != other.rows()) return false;
- return toBitVector().equals(other.toBitVector());
+ return toBitVector().equals(other.toBitVector());
}
/**
* Applies a procedure to each coordinate that holds a bit in the given state.
@@ -193,95 +191,95 @@
* @return <tt>false</tt> if the procedure stopped before all elements where iterated over, <tt>true</tt> otherwise.
*/
public boolean forEachCoordinateInState(boolean state, final org.apache.mahout.matrix.function.IntIntProcedure procedure) {
- /*
- this is equivalent to the low level version below, apart from that it iterates in the reverse oder and is slower.
- if (size()==0) return true;
- BitVector vector = toBitVector();
- return vector.forEachIndexFromToInState(0,size()-1,state,
- new org.apache.mahout.matrix.function.IntFunction() {
- public boolean apply(int index) {
- return function.apply(index%columns, index/columns);
- }
- }
- );
- */
-
- //low level implementation for speed.
- if (size()==0) return true;
- BitVector vector = new BitVector(bits,size());
-
- long[] theBits=bits;
-
- int column=columns-1;
- int row=rows-1;
-
- // for each coordinate of bits of partial unit
- long val = theBits[bits.length-1];
- for (int j=vector.numberOfBitsInPartialUnit(); --j >= 0; ) {
- long mask = val & (1L << j);
- if ((state && (mask!=0L)) || ((!state) && (mask==0L))) {
- if (!procedure.apply(column,row)) return false;
- }
- if (--column < 0) {
- column=columns-1;
- --row;
- }
- }
-
-
- // for each coordinate of bits of full units
- final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
- long comparator;
- if (state) comparator = 0L;
- else comparator = ~0L; // all 64 bits set
-
- for(int i=vector.numberOfFullUnits(); --i >= 0;) {
- val = theBits[i];
- if (val != comparator) {
- // at least one element within current unit matches.
- // iterate over all bits within current unit.
- if (state) {
- for (int j=bitsPerUnit; --j >= 0; ) {
- if (((val & (1L << j))) != 0L) {
- if (!procedure.apply(column,row)) return false;
- }
- if (--column < 0) {
- column=columns-1;
- --row;
- }
- }
- }
- else { // unrolled comparison for speed.
- for (int j=bitsPerUnit; --j >= 0; ) {
- if (((val & (1L << j))) == 0L) {
- if (!procedure.apply(column,row)) return false;
- }
- if (--column < 0) {
- column=columns-1;
- --row;
- }
- }
- }
-
- }
- else { // no element within current unit matches --> skip unit
- column -= bitsPerUnit;
- if (column < 0) {
- // avoid implementation with *, /, %
- column += bitsPerUnit;
- for (int j=bitsPerUnit; --j >= 0; ) {
- if (--column < 0) {
- column=columns-1;
- --row;
- }
- }
- }
- }
-
- }
+ /*
+ this is equivalent to the low level version below, apart from that it iterates in the reverse oder and is slower.
+ if (size()==0) return true;
+ BitVector vector = toBitVector();
+ return vector.forEachIndexFromToInState(0,size()-1,state,
+ new org.apache.mahout.matrix.function.IntFunction() {
+ public boolean apply(int index) {
+ return function.apply(index%columns, index/columns);
+ }
+ }
+ );
+ */
+
+ //low level implementation for speed.
+ if (size()==0) return true;
+ BitVector vector = new BitVector(bits,size());
+
+ long[] theBits=bits;
+
+ int column=columns-1;
+ int row=rows-1;
+
+ // for each coordinate of bits of partial unit
+ long val = theBits[bits.length-1];
+ for (int j=vector.numberOfBitsInPartialUnit(); --j >= 0; ) {
+ long mask = val & (1L << j);
+ if ((state && (mask!=0L)) || ((!state) && (mask==0L))) {
+ if (!procedure.apply(column,row)) return false;
+ }
+ if (--column < 0) {
+ column=columns-1;
+ --row;
+ }
+ }
+
+
+ // for each coordinate of bits of full units
+ final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
+ long comparator;
+ if (state) comparator = 0L;
+ else comparator = ~0L; // all 64 bits set
+
+ for(int i=vector.numberOfFullUnits(); --i >= 0;) {
+ val = theBits[i];
+ if (val != comparator) {
+ // at least one element within current unit matches.
+ // iterate over all bits within current unit.
+ if (state) {
+ for (int j=bitsPerUnit; --j >= 0; ) {
+ if (((val & (1L << j))) != 0L) {
+ if (!procedure.apply(column,row)) return false;
+ }
+ if (--column < 0) {
+ column=columns-1;
+ --row;
+ }
+ }
+ }
+ else { // unrolled comparison for speed.
+ for (int j=bitsPerUnit; --j >= 0; ) {
+ if (((val & (1L << j))) == 0L) {
+ if (!procedure.apply(column,row)) return false;
+ }
+ if (--column < 0) {
+ column=columns-1;
+ --row;
+ }
+ }
+ }
+
+ }
+ else { // no element within current unit matches --> skip unit
+ column -= bitsPerUnit;
+ if (column < 0) {
+ // avoid implementation with *, /, %
+ column += bitsPerUnit;
+ for (int j=bitsPerUnit; --j >= 0; ) {
+ if (--column < 0) {
+ column=columns-1;
+ --row;
+ }
+ }
+ }
+ }
+
+ }
- return true;
-
+ return true;
+
}
/**
* Returns from the receiver the value of the bit at the specified coordinate.
@@ -290,11 +288,11 @@
* @param column the index of the column-coordinate.
* @param row the index of the row-coordinate.
* @return the value of the bit at the specified coordinate.
- * @throws IndexOutOfBoundsException if <tt>column<0 || column>=columns() || row<0 || row>=rows()</tt>
+ * @throws IndexOutOfBoundsException if <tt>column<0 || column>=columns() || row<0 || row>=rows()</tt>
*/
public boolean get(int column, int row) {
- if (column<0 || column>=columns || row<0 || row>=rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row);
- return QuickBitVector.get(bits, row*columns + column);
+ if (column<0 || column>=columns || row<0 || row>=rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row);
+ return QuickBitVector.get(bits, row*columns + column);
}
/**
* Returns from the receiver the value of the bit at the specified coordinate; <b>WARNING:</b> Does not check preconditions.
@@ -309,19 +307,19 @@
* @return the value of the bit at the specified coordinate.
*/
public boolean getQuick(int column, int row) {
- return QuickBitVector.get(bits, row*columns + column);
+ return QuickBitVector.get(bits, row*columns + column);
}
/**
* Returns a hash code value for the receiver.
*/
public int hashCode() {
- return toBitVector().hashCode();
+ return toBitVector().hashCode();
}
/**
* Performs a logical <b>NOT</b> on the bits of the receiver.
*/
public void not() {
- toBitVector().not();
+ toBitVector().not();
}
/**
* Performs a logical <b>OR</b> of the receiver with another bit matrix.
@@ -334,8 +332,8 @@
* @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
*/
public void or(BitMatrix other) {
- checkDimensionCompatibility(other);
- toBitVector().or(other.toBitVector());
+ checkDimensionCompatibility(other);
+ toBitVector().or(other.toBitVector());
}
/**
* Constructs and returns a new matrix with <tt>width</tt> columns and <tt>height</tt> rows which is a copy of the contents of the given box.
@@ -344,15 +342,15 @@
* @param row the index of the row-coordinate.
* @param width the width of the box.
* @param height the height of the box.
- * @throws IndexOutOfBoundsException if <tt>column<0 || column+width>columns() || row<0 || row+height>rows()</tt>
+ * @throws IndexOutOfBoundsException if <tt>column<0 || column+width>columns() || row<0 || row+height>rows()</tt>
*/
public BitMatrix part(int column, int row, int width, int height) {
- if (column<0 || column+width>columns || row<0 || row+height>rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row+" ,width:"+width+", height:"+height);
- if (width<=0 || height<=0) return new BitMatrix(0,0);
+ if (column<0 || column+width>columns || row<0 || row+height>rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row+" ,width:"+width+", height:"+height);
+ if (width<=0 || height<=0) return new BitMatrix(0,0);
- BitMatrix subMatrix = new BitMatrix(width,height);
- subMatrix.replaceBoxWith(0,0,width,height,this,column,row);
- return subMatrix;
+ BitMatrix subMatrix = new BitMatrix(width,height);
+ subMatrix.replaceBoxWith(0,0,width,height,this,column,row);
+ return subMatrix;
}
/**
* Sets the bit at the specified coordinate to the state specified by <tt>value</tt>.
@@ -360,11 +358,11 @@
* @param column the index of the column-coordinate.
* @param row the index of the row-coordinate.
* @param value the value of the bit to be copied into the specified coordinate.
- * @throws IndexOutOfBoundsException if <tt>column<0 || column>=columns() || row<0 || row>=rows()</tt>
+ * @throws IndexOutOfBoundsException if <tt>column<0 || column>=columns() || row<0 || row>=rows()</tt>
*/
public void put(int column, int row, boolean value) {
- if (column<0 || column>=columns || row<0 || row>=rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row);
- QuickBitVector.put(bits, row*columns + column, value);
+ if (column<0 || column>=columns || row<0 || row>=rows) throw new IndexOutOfBoundsException("column:"+column+", row:"+row);
+ QuickBitVector.put(bits, row*columns + column, value);
}
/**
* Sets the bit at the specified coordinate to the state specified by <tt>value</tt>; <b>WARNING:</b> Does not check preconditions.
@@ -378,7 +376,7 @@
* @param value the value of the bit to be copied into the specified coordinate.
*/
public void putQuick(int column, int row, boolean value) {
- QuickBitVector.put(bits, row*columns + column, value);
+ QuickBitVector.put(bits, row*columns + column, value);
}
/**
* Replaces a box of the receiver with the contents of another matrix's box.
@@ -394,30 +392,30 @@
* @param source the source matrix to copy from(may be identical to the receiver).
* @param sourceColumn the index of the source column-coordinate.
* @param sourceRow the index of the source row-coordinate.
- * @throws IndexOutOfBoundsException if <tt>column<0 || column+width>columns() || row<0 || row+height>rows()</tt>
- * @throws IndexOutOfBoundsException if <tt>sourceColumn<0 || sourceColumn+width>source.columns() || sourceRow<0 || sourceRow+height>source.rows()</tt>
+ * @throws IndexOutOfBoundsException if <tt>column<0 || column+width>columns() || row<0 || row+height>rows()</tt>
+ * @throws IndexOutOfBoundsException if <tt>sourceColumn<0 || sourceColumn+width>source.columns() || sourceRow<0 || sourceRow+height>source.rows()</tt>
*/
public void replaceBoxWith(int column, int row, int width, int height, BitMatrix source, int sourceColumn, int sourceRow) {
- this.containsBox(column,row,width,height);
- source.containsBox(sourceColumn,sourceRow,width,height);
- if (width<=0 || height<=0) return;
-
- if (source==this) {
- Rectangle destRect = new Rectangle(column,row,width,height);
- Rectangle sourceRect = new Rectangle(sourceColumn,sourceRow,width,height);
- if (destRect.intersects(sourceRect)) { // dangerous intersection
- source = source.copy();
- }
- }
-
- BitVector sourceVector = source.toBitVector();
- BitVector destVector = this.toBitVector();
- int sourceColumns = source.columns();
- for (; --height >=0; row++, sourceRow++) {
- int offset = row*columns + column;
- int sourceOffset = sourceRow*sourceColumns + sourceColumn;
- destVector.replaceFromToWith(offset,offset+width-1,sourceVector,sourceOffset);
- }
+ this.containsBox(column,row,width,height);
+ source.containsBox(sourceColumn,sourceRow,width,height);
+ if (width<=0 || height<=0) return;
+
+ if (source==this) {
+ Rectangle destRect = new Rectangle(column,row,width,height);
+ Rectangle sourceRect = new Rectangle(sourceColumn,sourceRow,width,height);
+ if (destRect.intersects(sourceRect)) { // dangerous intersection
+ source = source.copy();
+ }
+ }
+
+ BitVector sourceVector = source.toBitVector();
+ BitVector destVector = this.toBitVector();
+ int sourceColumns = source.columns();
+ for (; --height >=0; row++, sourceRow++) {
+ int offset = row*columns + column;
+ int sourceOffset = sourceRow*sourceColumns + sourceColumn;
+ destVector.replaceFromToWith(offset,offset+width-1,sourceVector,sourceOffset);
+ }
}
/**
* Sets the bits in the given box to the state specified by <tt>value</tt>.
@@ -428,29 +426,29 @@
* @param width the width of the box.
* @param height the height of the box.
* @param value the value of the bit to be copied into the bits of the specified box.
- * @throws IndexOutOfBoundsException if <tt>column<0 || column+width>columns() || row<0 || row+height>rows()</tt>
+ * @throws IndexOutOfBoundsException if <tt>column<0 || column+width>columns() || row<0 || row+height>rows()</tt>
*/
public void replaceBoxWith(int column, int row, int width, int height, boolean value) {
- containsBox(column,row,width,height);
- if (width<=0 || height<=0) return;
-
- BitVector destVector = this.toBitVector();
- for (; --height >= 0; row++) {
- int offset = row*columns + column;
- destVector.replaceFromToWith(offset, offset+width-1,value);
- }
+ containsBox(column,row,width,height);
+ if (width<=0 || height<=0) return;
+
+ BitVector destVector = this.toBitVector();
+ for (; --height >= 0; row++) {
+ int offset = row*columns + column;
+ destVector.replaceFromToWith(offset, offset+width-1,value);
+ }
}
/**
* Returns the number of rows of the receiver.
*/
public int rows() {
- return rows;
+ return rows;
}
/**
* Returns the size of the receiver which is <tt>columns()*rows()</tt>.
*/
public int size() {
- return columns*rows;
+ return columns*rows;
}
/**
* Converts the receiver to a bitvector.
@@ -460,13 +458,13 @@
* If this behaviour is not what you want, you should first use <tt>copy()</tt> to make sure both objects use separate internal storage.
*/
public BitVector toBitVector() {
- return new BitVector(bits,size());
+ return new BitVector(bits,size());
}
/**
* Returns a (very crude) string representation of the receiver.
*/
public String toString() {
- return toBitVector().toString();
+ return toBitVector().toString();
}
/**
* Performs a logical <b>XOR</b> of the receiver with another bit matrix.
@@ -483,7 +481,7 @@
* @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
*/
public void xor(BitMatrix other) {
- checkDimensionCompatibility(other);
- toBitVector().xor(other.toBitVector());
+ checkDimensionCompatibility(other);
+ toBitVector().xor(other.toBitVector());
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitVector.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitVector.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitVector.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/BitVector.java Wed Nov 25 03:35:59 2009
@@ -42,8 +42,6 @@
* <p>
* <b>Note</b> that this implementation is not synchronized.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.01, 11/10/99
* @see QuickBitVector
* @see BitMatrix
* @see java.util.BitSet
@@ -53,31 +51,31 @@
*/
@Deprecated
public class BitVector extends org.apache.mahout.matrix.PersistentObject {
- /*
- * Bits are packed into arrays of "units." Currently a unit is a long,
- * which consists of 64 bits, requiring 6 address bits. The choice of unit
- * is determined purely by performance concerns.
- */
-
- /**
- * The bits of this object. The ith 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).
- *
- * @serial
- */
- protected long bits[];
-
- protected int nbits; //the size
-
- // IntProcedure for method indexOfFromTo(...)
- private class IndexProcedure implements org.apache.mahout.matrix.function.IntProcedure {
- private int foundPos = -1;
- public boolean apply(int index) {
- foundPos = index;
- return false;
- }
- }
+ /*
+ * Bits are packed into arrays of "units." Currently a unit is a long,
+ * which consists of 64 bits, requiring 6 address bits. The choice of unit
+ * is determined purely by performance concerns.
+ */
+
+ /**
+ * The bits of this object. The ith 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).
+ *
+ * @serial
+ */
+ protected long bits[];
+
+ protected int nbits; //the size
+
+ // IntProcedure for method indexOfFromTo(...)
+ private class IndexProcedure implements org.apache.mahout.matrix.function.IntProcedure {
+ private int foundPos = -1;
+ public boolean apply(int index) {
+ foundPos = index;
+ return false;
+ }
+ }
/**
* You normally need not use this method. Use this method only if performance is critical.
@@ -94,7 +92,7 @@
* @throws IllegalArgumentException if <tt>size < 0 || size > bits.length*64</tt>.
*/
public BitVector (long[] bits, int size) {
- elements(bits,size);
+ elements(bits,size);
}
/**
* Constructs a bit vector that holds <tt>size</tt> bits. All bits are initially <tt>false</tt>.
@@ -103,7 +101,7 @@
* @throws IllegalArgumentException if <tt>size < 0</tt>.
*/
public BitVector(int size) {
- this(QuickBitVector.makeBitVector(size,1),size);
+ this(QuickBitVector.makeBitVector(size,1),size);
}
/**
* Performs a logical <b>AND</b> of the receiver with another bit vector (A = A & B).
@@ -116,11 +114,11 @@
* @throws IllegalArgumentException if <tt>size() > other.size()</tt>.
*/
public void and(BitVector other) {
- if (this == other) return;
- checkSize(other);
- final long[] theBits = this.bits; // cached for speed.
- final long[] otherBits = other.bits; //cached for speed.
- for(int i=theBits.length; --i >= 0;) theBits[i] &= otherBits[i];
+ if (this == other) return;
+ checkSize(other);
+ final long[] theBits = this.bits; // cached for speed.
+ final long[] otherBits = other.bits; //cached for speed.
+ for(int i=theBits.length; --i >= 0;) theBits[i] &= otherBits[i];
}
/**
* Clears all of the bits in receiver whose corresponding
@@ -131,72 +129,72 @@
* @throws IllegalArgumentException if <tt>size() > other.size()</tt>.
*/
public void andNot(BitVector other) {
- checkSize(other);
- final long[] theBits = this.bits; // cached for speed.
- final long[] otherBits = other.bits; //cached for speed.
- for(int i=theBits.length; --i >= 0;) theBits[i] &= ~otherBits[i];
+ checkSize(other);
+ final long[] theBits = this.bits; // cached for speed.
+ final long[] otherBits = other.bits; //cached for speed.
+ for(int i=theBits.length; --i >= 0;) theBits[i] &= ~otherBits[i];
}
/**
* Returns the number of bits currently in the <tt>true</tt> state.
* Optimized for speed. Particularly quick if the receiver is either sparse or dense.
*/
public int cardinality() {
- int cardinality=0;
- int fullUnits = numberOfFullUnits();
- final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
-
- // determine cardinality on full units
- final long[] theBits=bits;
- for(int i=fullUnits; --i >= 0;) {
- long val = theBits[i];
- if (val == -1L) { // all bits set?
- cardinality += bitsPerUnit;
- }
- else if (val != 0L) { // more than one bit set?
- for (int j=bitsPerUnit; --j >= 0; ) {
- if ((val & (1L << j)) != 0) cardinality++;
- }
- }
- }
-
- // determine cardinality on remaining partial unit, if any.
- for (int j=numberOfBitsInPartialUnit(); --j >= 0; ) {
- if ((theBits[fullUnits] & (1L << j)) != 0) cardinality++;
- }
+ int cardinality=0;
+ int fullUnits = numberOfFullUnits();
+ final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
+
+ // determine cardinality on full units
+ final long[] theBits=bits;
+ for(int i=fullUnits; --i >= 0;) {
+ long val = theBits[i];
+ if (val == -1L) { // all bits set?
+ cardinality += bitsPerUnit;
+ }
+ else if (val != 0L) { // more than one bit set?
+ for (int j=bitsPerUnit; --j >= 0; ) {
+ if ((val & (1L << j)) != 0) cardinality++;
+ }
+ }
+ }
+
+ // determine cardinality on remaining partial unit, if any.
+ for (int j=numberOfBitsInPartialUnit(); --j >= 0; ) {
+ if ((theBits[fullUnits] & (1L << j)) != 0) cardinality++;
+ }
- return cardinality;
+ return cardinality;
}
/**
* Checks if the given range is within the contained array's bounds.
*/
protected static void checkRangeFromTo(int from, int to, int theSize) {
- if (from<0 || from>to || to>=theSize)
- throw new IndexOutOfBoundsException("from: "+from+", to: "+to+", size="+theSize);
+ if (from<0 || from>to || to>=theSize)
+ throw new IndexOutOfBoundsException("from: "+from+", to: "+to+", size="+theSize);
}
/**
* Sanity check for operations requiring another bitvector with at least the same size.
*/
protected void checkSize(BitVector other) {
- if (nbits > other.size()) throw new IllegalArgumentException("Incompatible sizes: size="+nbits+", other.size()="+other.size());
+ if (nbits > other.size()) throw new IllegalArgumentException("Incompatible sizes: size="+nbits+", other.size()="+other.size());
}
/**
* Clears all bits of the receiver.
*/
public void clear() {
- final long[] theBits = this.bits;
- for (int i = theBits.length; --i >= 0 ;) theBits[i] = 0L;
+ final long[] theBits = this.bits;
+ for (int i = theBits.length; --i >= 0 ;) theBits[i] = 0L;
- //new LongArrayList(bits).fillFromToWith(0,size()-1,0L);
+ //new LongArrayList(bits).fillFromToWith(0,size()-1,0L);
}
/**
* Changes the bit with index <tt>bitIndex</tt> to the "clear" (<tt>false</tt>) state.
*
* @param bitIndex the index of the bit to be cleared.
- * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
+ * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
*/
public void clear(int bitIndex) {
- if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
- QuickBitVector.clear(bits, bitIndex);
+ if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
+ QuickBitVector.clear(bits, bitIndex);
}
/**
* Cloning this <code>BitVector</code> produces a new <code>BitVector</code>
@@ -208,9 +206,9 @@
* @return a deep copy of this bit vector.
*/
public Object clone() {
- BitVector clone = (BitVector) super.clone();
- if (this.bits != null) clone.bits = (long[]) this.bits.clone();
- return clone;
+ BitVector clone = (BitVector) super.clone();
+ if (this.bits != null) clone.bits = (long[]) this.bits.clone();
+ return clone;
}
/**
* Returns a deep copy of the receiver; calls <code>clone()</code> and casts the result.
@@ -218,7 +216,7 @@
* @return a deep copy of the receiver.
*/
public BitVector copy() {
- return (BitVector) clone();
+ return (BitVector) clone();
}
/**
* You normally need not use this method. Use this method only if performance is critical.
@@ -233,7 +231,7 @@
* significant bit and 63 refers to the most significant bit).
*/
public long[] elements() {
- return bits;
+ return bits;
}
/**
* You normally need not use this method. Use this method only if performance is critical.
@@ -252,9 +250,9 @@
* @throws IllegalArgumentException if <tt>size < 0 || size > bits.length*64</tt>.
*/
public void elements(long[] bits, int size) {
- if (size<0 || size>bits.length*QuickBitVector.BITS_PER_UNIT) throw new IllegalArgumentException();
- this.bits = bits;
- this.nbits = size;
+ if (size<0 || size>bits.length*QuickBitVector.BITS_PER_UNIT) throw new IllegalArgumentException();
+ this.bits = bits;
+ this.nbits = size;
}
/**
* Compares this object against the specified object.
@@ -271,27 +269,27 @@
* <code>false</code> otherwise.
*/
public boolean equals(Object obj) {
- if (obj == null || !(obj instanceof BitVector))
- return false;
- if (this == obj)
- return true;
-
- BitVector other = (BitVector) obj;
- if (size()!=other.size()) return false;
-
- int fullUnits = numberOfFullUnits();
- // perform logical comparison on full units
- for(int i=fullUnits; --i >= 0;)
- if (bits[i] != other.bits[i]) return false;
-
- // perform logical comparison on remaining bits
- int i=fullUnits*QuickBitVector.BITS_PER_UNIT;
- for (int times=numberOfBitsInPartialUnit(); --times >=0;) {
- if (get(i) != other.get(i)) return false;
- i++;
- }
+ if (obj == null || !(obj instanceof BitVector))
+ return false;
+ if (this == obj)
+ return true;
+
+ BitVector other = (BitVector) obj;
+ if (size()!=other.size()) return false;
+
+ int fullUnits = numberOfFullUnits();
+ // perform logical comparison on full units
+ for(int i=fullUnits; --i >= 0;)
+ if (bits[i] != other.bits[i]) return false;
+
+ // perform logical comparison on remaining bits
+ int i=fullUnits*QuickBitVector.BITS_PER_UNIT;
+ for (int times=numberOfBitsInPartialUnit(); --times >=0;) {
+ if (get(i) != other.get(i)) return false;
+ i++;
+ }
- return true;
+ return true;
}
/**
* Applies a procedure to each bit index within the specified range that holds a bit in the given state.
@@ -312,115 +310,115 @@
* @throws IndexOutOfBoundsException if (<tt>size()>0 && (from<0 || from>to || to>=size())</tt>).
*/
public boolean forEachIndexFromToInState(int from, int to, boolean state, org.apache.mahout.matrix.function.IntProcedure procedure) {
- /*
- // this version is equivalent to the low level version below, but about 100 times slower for large ranges.
- if (nbits==0) return true;
- checkRangeFromTo(from, to, nbits);
- final long[] theBits = this.bits; // cached for speed
- int length=to-from+1;
- for (int i=from; --length >= 0; i++) {
- if (QuickBitVector.get(theBits,i)==state) {
- if (!function.apply(i)) return false;
- }
- }
- return true;
- */
-
-
- /*
- * This low level implementation exploits the fact that for any full unit one can determine in O(1)
- * whether it contains at least one true bit,
- * and whether it contains at least one false bit.
- * Thus, 64 bits can often be skipped with one simple comparison if the vector is either sparse or dense.
- *
- * However, careful coding must be done for leading and/or trailing units which are not entirely contained in the query range.
- */
-
- if (nbits==0) return true;
- checkRangeFromTo(from, to, nbits);
- //System.out.println("\n");
- //System.out.println(this);
- //System.out.println("from="+from+", to="+to+", bit="+state);
-
- // Cache some vars for speed.
- final long[] theBits = this.bits;
- final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
-
- // Prepare
- int fromUnit = QuickBitVector.unit(from);
- int toUnit = QuickBitVector.unit(to);
- int i = from; // current bitvector index
-
- // Iterate over the leading partial unit, if any.
- int bitIndex = QuickBitVector.offset(from);
- int partialWidth;
- if (bitIndex>0) { // There exists a leading partial unit.
- partialWidth = Math.min(to-from+1, bitsPerUnit - bitIndex);
- //System.out.println("partialWidth1="+partialWidth);
- for (; --partialWidth >= 0; i++) {
- if (QuickBitVector.get(theBits,i)==state) {
- if (!procedure.apply(i)) return false;
- }
- }
- fromUnit++; // leading partial unit is done.
- }
-
- if (i>to) return true; // done
-
- // If there is a trailing partial unit, then there is one full unit less to test.
- bitIndex = QuickBitVector.offset(to);
- if (bitIndex < bitsPerUnit-1) {
- toUnit--; // trailing partial unit needs to be tested extra.
- partialWidth = bitIndex + 1;
- }
- else {
- partialWidth = 0;
- }
- //System.out.println("partialWidth2="+partialWidth);
-
- // Iterate over all full units, if any.
- // (It does not matter that iterating over partial units is a little bit slow,
- // the only thing that matters is that iterating over full units is quick.)
- long comparator;
- if (state) comparator = 0L;
- else comparator = ~0L; // all 64 bits set
-
- //System.out.println("fromUnit="+fromUnit+", toUnit="+toUnit);
- for (int unit=fromUnit; unit<=toUnit; unit++) {
- long val = theBits[unit];
- if (val != comparator) {
- // at least one element within current unit matches.
- // iterate over all bits within current unit.
- if (state) {
- for (int j=0, k=bitsPerUnit; --k >= 0; i++) {
- if ((val & (1L << j++)) != 0L) { // is bit set?
- if (!procedure.apply(i)) return false;
- }
- }
- }
- else {
- for (int j=0, k=bitsPerUnit; --k >= 0; i++) {
- if ((val & (1L << j++)) == 0L) { // is bit cleared?
- if (!procedure.apply(i)) return false;
- }
- }
- }
- }
- else {
- i += bitsPerUnit;
- }
- }
-
- //System.out.println("trail with i="+i);
-
- // Iterate over trailing partial unit, if any.
- for (; --partialWidth >= 0; i++) {
- if (QuickBitVector.get(theBits,i)==state) {
- if (!procedure.apply(i)) return false;
- }
- }
-
- return true;
+ /*
+ // this version is equivalent to the low level version below, but about 100 times slower for large ranges.
+ if (nbits==0) return true;
+ checkRangeFromTo(from, to, nbits);
+ final long[] theBits = this.bits; // cached for speed
+ int length=to-from+1;
+ for (int i=from; --length >= 0; i++) {
+ if (QuickBitVector.get(theBits,i)==state) {
+ if (!function.apply(i)) return false;
+ }
+ }
+ return true;
+ */
+
+
+ /*
+ * This low level implementation exploits the fact that for any full unit one can determine in O(1)
+ * whether it contains at least one true bit,
+ * and whether it contains at least one false bit.
+ * Thus, 64 bits can often be skipped with one simple comparison if the vector is either sparse or dense.
+ *
+ * However, careful coding must be done for leading and/or trailing units which are not entirely contained in the query range.
+ */
+
+ if (nbits==0) return true;
+ checkRangeFromTo(from, to, nbits);
+ //System.out.println("\n");
+ //System.out.println(this);
+ //System.out.println("from="+from+", to="+to+", bit="+state);
+
+ // Cache some vars for speed.
+ final long[] theBits = this.bits;
+ final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
+
+ // Prepare
+ int fromUnit = QuickBitVector.unit(from);
+ int toUnit = QuickBitVector.unit(to);
+ int i = from; // current bitvector index
+
+ // Iterate over the leading partial unit, if any.
+ int bitIndex = QuickBitVector.offset(from);
+ int partialWidth;
+ if (bitIndex>0) { // There exists a leading partial unit.
+ partialWidth = Math.min(to-from+1, bitsPerUnit - bitIndex);
+ //System.out.println("partialWidth1="+partialWidth);
+ for (; --partialWidth >= 0; i++) {
+ if (QuickBitVector.get(theBits,i)==state) {
+ if (!procedure.apply(i)) return false;
+ }
+ }
+ fromUnit++; // leading partial unit is done.
+ }
+
+ if (i>to) return true; // done
+
+ // If there is a trailing partial unit, then there is one full unit less to test.
+ bitIndex = QuickBitVector.offset(to);
+ if (bitIndex < bitsPerUnit-1) {
+ toUnit--; // trailing partial unit needs to be tested extra.
+ partialWidth = bitIndex + 1;
+ }
+ else {
+ partialWidth = 0;
+ }
+ //System.out.println("partialWidth2="+partialWidth);
+
+ // Iterate over all full units, if any.
+ // (It does not matter that iterating over partial units is a little bit slow,
+ // the only thing that matters is that iterating over full units is quick.)
+ long comparator;
+ if (state) comparator = 0L;
+ else comparator = ~0L; // all 64 bits set
+
+ //System.out.println("fromUnit="+fromUnit+", toUnit="+toUnit);
+ for (int unit=fromUnit; unit<=toUnit; unit++) {
+ long val = theBits[unit];
+ if (val != comparator) {
+ // at least one element within current unit matches.
+ // iterate over all bits within current unit.
+ if (state) {
+ for (int j=0, k=bitsPerUnit; --k >= 0; i++) {
+ if ((val & (1L << j++)) != 0L) { // is bit set?
+ if (!procedure.apply(i)) return false;
+ }
+ }
+ }
+ else {
+ for (int j=0, k=bitsPerUnit; --k >= 0; i++) {
+ if ((val & (1L << j++)) == 0L) { // is bit cleared?
+ if (!procedure.apply(i)) return false;
+ }
+ }
+ }
+ }
+ else {
+ i += bitsPerUnit;
+ }
+ }
+
+ //System.out.println("trail with i="+i);
+
+ // Iterate over trailing partial unit, if any.
+ for (; --partialWidth >= 0; i++) {
+ if (QuickBitVector.get(theBits,i)==state) {
+ if (!procedure.apply(i)) return false;
+ }
+ }
+
+ return true;
}
/**
* Returns from the bitvector the value of the bit with the specified index.
@@ -429,11 +427,11 @@
*
* @param bitIndex the bit index.
* @return the value of the bit with the specified index.
- * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
+ * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
*/
public boolean get(int bitIndex) {
- if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
- return QuickBitVector.get(bits, bitIndex);
+ if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
+ return QuickBitVector.get(bits, bitIndex);
}
/**
* Returns a long value representing bits of the receiver from index <tt>from</tt> to index <tt>to</tt>.
@@ -443,13 +441,13 @@
* @param from index of start bit (inclusive).
* @param to index of end bit (inclusive).
* @return the specified bits as long value.
- * @throws IndexOutOfBoundsException if <tt>from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64</tt>
+ * @throws IndexOutOfBoundsException if <tt>from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64</tt>
*/
public long getLongFromTo(int from, int to) {
- int width = to-from+1;
- if (width==0) return 0L;
- if (from<0 || from>=nbits || to<0 || to>=nbits || width<0 || width>QuickBitVector.BITS_PER_UNIT) throw new IndexOutOfBoundsException("from:"+from+", to:"+to);
- return QuickBitVector.getLongFromTo(bits, from, to);
+ int width = to-from+1;
+ if (width==0) return 0L;
+ if (from<0 || from>=nbits || to<0 || to>=nbits || width<0 || width>QuickBitVector.BITS_PER_UNIT) throw new IndexOutOfBoundsException("from:"+from+", to:"+to);
+ return QuickBitVector.getLongFromTo(bits, from, to);
}
/**
* Returns from the bitvector the value of the bit with the specified index; <b>WARNING:</b> Does not check preconditions.
@@ -464,7 +462,7 @@
* @return the value of the bit with the specified index.
*/
public boolean getQuick(int bitIndex) {
- return QuickBitVector.get(bits, bitIndex);
+ return QuickBitVector.get(bits, bitIndex);
}
/**
* Returns a hash code value for the receiver. The hash code
@@ -492,10 +490,10 @@
* @return a hash code value for the receiver.
*/
public int hashCode() {
- long h = 1234;
- for (int i = bits.length; --i >= 0; ) h ^= bits[i] * (i + 1);
+ long h = 1234;
+ for (int i = bits.length; --i >= 0; ) h ^= bits[i] * (i + 1);
- return (int)((h >> 32) ^ h);
+ return (int)((h >> 32) ^ h);
}
/**
* Returns the index of the first occurrence of the specified
@@ -511,29 +509,29 @@
* @exception IndexOutOfBoundsException if (<tt>size()>0 && (from<0 || from>to || to>=size())</tt>).
*/
public int indexOfFromTo(int from, int to, boolean state) {
- IndexProcedure indexProcedure = new IndexProcedure();
- forEachIndexFromToInState(from,to,state,indexProcedure);
- return indexProcedure.foundPos;
+ IndexProcedure indexProcedure = new IndexProcedure();
+ forEachIndexFromToInState(from,to,state,indexProcedure);
+ return indexProcedure.foundPos;
}
/**
* Performs a logical <b>NOT</b> on the bits of the receiver (A = ~A).
*/
public void not() {
- final long[] theBits = this.bits;
- for (int i = theBits.length; --i >= 0 ;) theBits[i] = ~theBits[i];
+ final long[] theBits = this.bits;
+ for (int i = theBits.length; --i >= 0 ;) theBits[i] = ~theBits[i];
}
/**
* Returns the number of bits used in the trailing PARTIAL unit.
* Returns zero if there is no such trailing partial unit.
*/
protected int numberOfBitsInPartialUnit() {
- return QuickBitVector.offset(nbits);
+ return QuickBitVector.offset(nbits);
}
/**
* Returns the number of units that are FULL (not PARTIAL).
*/
protected int numberOfFullUnits() {
- return QuickBitVector.unit(nbits);
+ return QuickBitVector.unit(nbits);
}
/**
* Performs a logical <b>OR</b> of the receiver with another bit vector (A = A | B).
@@ -546,11 +544,11 @@
* @throws IllegalArgumentException if <tt>size() > other.size()</tt>.
*/
public void or(BitVector other) {
- if (this == other) return;
- checkSize(other);
- final long[] theBits = this.bits; // cached for speed.
- final long[] otherBits = other.bits; //cached for speed.
- for(int i=theBits.length; --i >= 0;) theBits[i] |= otherBits[i];
+ if (this == other) return;
+ checkSize(other);
+ final long[] theBits = this.bits; // cached for speed.
+ final long[] otherBits = other.bits; //cached for speed.
+ for(int i=theBits.length; --i >= 0;) theBits[i] |= otherBits[i];
}
/**
* Constructs and returns a new bit vector which is a copy of the given range.
@@ -561,27 +559,27 @@
* @throws IndexOutOfBoundsException if <tt>size()>0 && (from<0 || from>to || to>=size()))</tt>.
*/
public BitVector partFromTo(int from, int to) {
- if (nbits==0 || to==from-1) return new BitVector(0);
- checkRangeFromTo(from, to, nbits);
+ if (nbits==0 || to==from-1) return new BitVector(0);
+ checkRangeFromTo(from, to, nbits);
- int width = to-from+1;
- BitVector part = new BitVector(width);
- part.replaceFromToWith(0,width-1,this,from);
- return part;
+ int width = to-from+1;
+ BitVector part = new BitVector(width);
+ part.replaceFromToWith(0,width-1,this,from);
+ return part;
}
/**
* Sets the bit with index <tt>bitIndex</tt> to the state specified by <tt>value</tt>.
*
* @param bitIndex the index of the bit to be changed.
* @param value the value to be stored in the bit.
- * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
+ * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
*/
-public void put(int bitIndex, boolean value) {
- if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
- if (value)
- QuickBitVector.set(bits, bitIndex);
- else
- QuickBitVector.clear(bits, bitIndex);
+public void put(int bitIndex, boolean value) {
+ if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
+ if (value)
+ QuickBitVector.set(bits, bitIndex);
+ else
+ QuickBitVector.clear(bits, bitIndex);
}
/**
* Sets bits of the receiver from index <code>from</code> to index <code>to</code> to the bits of <code>value</code>.
@@ -591,13 +589,13 @@
* @param value the value to be copied into the receiver.
* @param from index of start bit (inclusive).
* @param to index of end bit (inclusive).
- * @throws IndexOutOfBoundsException if <tt>from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64</tt>.
+ * @throws IndexOutOfBoundsException if <tt>from<0 || from>=size() || to<0 || to>=size() || to-from+1<0 || to-from+1>64</tt>.
*/
public void putLongFromTo(long value, int from, int to) {
- int width = to-from+1;
- if (width==0) return;
- if (from<0 || from>=nbits || to<0 || to>=nbits || width<0 || width>QuickBitVector.BITS_PER_UNIT) throw new IndexOutOfBoundsException("from:"+from+", to:"+to);
- QuickBitVector.putLongFromTo(bits, value, from, to);
+ int width = to-from+1;
+ if (width==0) return;
+ if (from<0 || from>=nbits || to<0 || to>=nbits || width<0 || width>QuickBitVector.BITS_PER_UNIT) throw new IndexOutOfBoundsException("from:"+from+", to:"+to);
+ QuickBitVector.putLongFromTo(bits, value, from, to);
}
/**
* Sets the bit with index <tt>bitIndex</tt> to the state specified by <tt>value</tt>; <b>WARNING:</b> Does not check preconditions.
@@ -609,11 +607,11 @@
* @param bitIndex the index of the bit to be changed.
* @param value the value to be stored in the bit.
*/
-public void putQuick(int bitIndex, boolean value) {
- if (value)
- QuickBitVector.set(bits, bitIndex);
- else
- QuickBitVector.clear(bits, bitIndex);
+public void putQuick(int bitIndex, boolean value) {
+ if (value)
+ QuickBitVector.set(bits, bitIndex);
+ else
+ QuickBitVector.clear(bits, bitIndex);
}
/**
* Replaces the bits of the receiver in the given range with the bits of another bit vector.
@@ -629,46 +627,46 @@
* @throws IndexOutOfBoundsException if <tt>size()>0 && (from<0 || from>to || to>=size() || sourceFrom<0 || sourceFrom+to-from+1>source.size()))</tt>.
*/
public void replaceFromToWith(int from, int to, BitVector source, int sourceFrom) {
- if (nbits==0 || to==from-1) return;
- checkRangeFromTo(from, to, nbits);
- int length=to-from+1;
- if (sourceFrom<0 || sourceFrom+length>source.size()) {
- throw new IndexOutOfBoundsException();
- }
-
- if (source.bits==this.bits && from<=sourceFrom && sourceFrom<=to) { // dangerous intersection
- source = source.copy();
- }
-
- final long[] theBits = this.bits; // cached for speed.
- final long[] sourceBits = source.bits; // cached for speed.
-
- /*
- This version is equivalent to the version below but 20 times slower...
- for (int i=from; --length >= 0; i++, sourceFrom++) {
- QuickBitVector.put(theBits,i,QuickBitVector.get(sourceBits,sourceFrom));
- }
- */
-
- // Low level implementation for speed.
- // This could be done even faster by implementing on even lower levels. But then the code would probably become a "don't touch" piece.
- final int width = to-from+1;
- final int blocks = QuickBitVector.unit(width); // width/64
- final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
- final int bitsPerUnitMinusOne = bitsPerUnit-1;
-
- // copy entire 64 bit blocks, if any.
- for (int i=blocks; --i >=0; ) {
- long val = QuickBitVector.getLongFromTo(sourceBits,sourceFrom,sourceFrom+bitsPerUnitMinusOne);
- QuickBitVector.putLongFromTo(theBits,val,from,from+bitsPerUnitMinusOne);
- sourceFrom += bitsPerUnit;
- from += bitsPerUnit;
- }
-
- // copy trailing bits, if any.
- int offset = QuickBitVector.offset(width); //width%64
- long val = QuickBitVector.getLongFromTo(sourceBits,sourceFrom,sourceFrom+offset-1);
- QuickBitVector.putLongFromTo(theBits,val,from,from+offset-1);
+ if (nbits==0 || to==from-1) return;
+ checkRangeFromTo(from, to, nbits);
+ int length=to-from+1;
+ if (sourceFrom<0 || sourceFrom+length>source.size()) {
+ throw new IndexOutOfBoundsException();
+ }
+
+ if (source.bits==this.bits && from<=sourceFrom && sourceFrom<=to) { // dangerous intersection
+ source = source.copy();
+ }
+
+ final long[] theBits = this.bits; // cached for speed.
+ final long[] sourceBits = source.bits; // cached for speed.
+
+ /*
+ This version is equivalent to the version below but 20 times slower...
+ for (int i=from; --length >= 0; i++, sourceFrom++) {
+ QuickBitVector.put(theBits,i,QuickBitVector.get(sourceBits,sourceFrom));
+ }
+ */
+
+ // Low level implementation for speed.
+ // This could be done even faster by implementing on even lower levels. But then the code would probably become a "don't touch" piece.
+ final int width = to-from+1;
+ final int blocks = QuickBitVector.unit(width); // width/64
+ final int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
+ final int bitsPerUnitMinusOne = bitsPerUnit-1;
+
+ // copy entire 64 bit blocks, if any.
+ for (int i=blocks; --i >=0; ) {
+ long val = QuickBitVector.getLongFromTo(sourceBits,sourceFrom,sourceFrom+bitsPerUnitMinusOne);
+ QuickBitVector.putLongFromTo(theBits,val,from,from+bitsPerUnitMinusOne);
+ sourceFrom += bitsPerUnit;
+ from += bitsPerUnit;
+ }
+
+ // copy trailing bits, if any.
+ int offset = QuickBitVector.offset(width); //width%64
+ long val = QuickBitVector.getLongFromTo(sourceBits,sourceFrom,sourceFrom+offset-1);
+ QuickBitVector.putLongFromTo(theBits,val,from,from+offset-1);
}
/**
* Sets the bits in the given range to the state specified by <tt>value</tt>.
@@ -681,61 +679,61 @@
* @throws IndexOutOfBoundsException if <tt>size()>0 && (from<0 || from>to || to>=size())</tt>.
*/
public void replaceFromToWith(int from, int to, boolean value) {
- if (nbits==0 || to==from-1) return;
- checkRangeFromTo(from, to, nbits);
- final long[] theBits = this.bits; // cached for speed
-
- int fromUnit = QuickBitVector.unit(from);
- int fromOffset = QuickBitVector.offset(from);
- int toUnit = QuickBitVector.unit(to);
- int toOffset = QuickBitVector.offset(to);
- int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
-
- long filler;
- if (value) filler = ~0L;
- else filler = 0L;
-
- int bitIndex=from;
- if (fromUnit==toUnit) { // only one unit to do
- QuickBitVector.putLongFromTo(theBits,filler,bitIndex,bitIndex+to-from);
- //slower: for (; bitIndex<=to; ) QuickBitVector.put(theBits,bitIndex++,value);
- return;
- }
-
- // treat leading partial unit, if any.
- if (fromOffset > 0) { // fix by Olivier Janssens
- QuickBitVector.putLongFromTo(theBits,filler,bitIndex,bitIndex+bitsPerUnit-fromOffset);
- bitIndex += bitsPerUnit-fromOffset+1;
- /* slower:
- for (int i=bitsPerUnit-fromOffset; --i >= 0; ) {
- QuickBitVector.put(theBits,bitIndex++,value);
- }*/
- fromUnit++;
- }
- if (toOffset<bitsPerUnit-1) toUnit--; // there is a trailing partial unit
-
- // treat full units, if any.
- for (int i=fromUnit; i<=toUnit; ) theBits[i++] = filler;
- if (fromUnit<=toUnit) bitIndex += (toUnit-fromUnit+1)*bitsPerUnit;
-
- // treat trailing partial unit, if any.
- if (toOffset<bitsPerUnit-1) {
- QuickBitVector.putLongFromTo(theBits,filler,bitIndex,to);
- /* slower:
- for (int i=toOffset+1; --i >= 0; ) {
- QuickBitVector.put(theBits,bitIndex++,value);
- }*/
- }
+ if (nbits==0 || to==from-1) return;
+ checkRangeFromTo(from, to, nbits);
+ final long[] theBits = this.bits; // cached for speed
+
+ int fromUnit = QuickBitVector.unit(from);
+ int fromOffset = QuickBitVector.offset(from);
+ int toUnit = QuickBitVector.unit(to);
+ int toOffset = QuickBitVector.offset(to);
+ int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
+
+ long filler;
+ if (value) filler = ~0L;
+ else filler = 0L;
+
+ int bitIndex=from;
+ if (fromUnit==toUnit) { // only one unit to do
+ QuickBitVector.putLongFromTo(theBits,filler,bitIndex,bitIndex+to-from);
+ //slower: for (; bitIndex<=to; ) QuickBitVector.put(theBits,bitIndex++,value);
+ return;
+ }
+
+ // treat leading partial unit, if any.
+ if (fromOffset > 0) { // fix by Olivier Janssens
+ QuickBitVector.putLongFromTo(theBits,filler,bitIndex,bitIndex+bitsPerUnit-fromOffset);
+ bitIndex += bitsPerUnit-fromOffset+1;
+ /* slower:
+ for (int i=bitsPerUnit-fromOffset; --i >= 0; ) {
+ QuickBitVector.put(theBits,bitIndex++,value);
+ }*/
+ fromUnit++;
+ }
+ if (toOffset<bitsPerUnit-1) toUnit--; // there is a trailing partial unit
+
+ // treat full units, if any.
+ for (int i=fromUnit; i<=toUnit; ) theBits[i++] = filler;
+ if (fromUnit<=toUnit) bitIndex += (toUnit-fromUnit+1)*bitsPerUnit;
+
+ // treat trailing partial unit, if any.
+ if (toOffset<bitsPerUnit-1) {
+ QuickBitVector.putLongFromTo(theBits,filler,bitIndex,to);
+ /* slower:
+ for (int i=toOffset+1; --i >= 0; ) {
+ QuickBitVector.put(theBits,bitIndex++,value);
+ }*/
+ }
}
/**
* Changes the bit with index <tt>bitIndex</tt> to the "set" (<tt>true</tt>) state.
*
* @param bitIndex the index of the bit to be set.
- * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
+ * @throws IndexOutOfBoundsException if <tt>bitIndex<0 || bitIndex>=size()</tt>
*/
public void set(int bitIndex) {
- if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
- QuickBitVector.set(bits, bitIndex);
+ if (bitIndex<0 || bitIndex>=nbits) throw new IndexOutOfBoundsException(String.valueOf(bitIndex));
+ QuickBitVector.set(bits, bitIndex);
}
/**
* Shrinks or expands the receiver so that it holds <tt>newSize</tt> bits.
@@ -747,17 +745,17 @@
* @throws IllegalArgumentException if <tt>size < 0</tt>.
*/
public void setSize(int newSize) {
- if (newSize!=size()) {
- BitVector newVector = new BitVector(newSize);
- newVector.replaceFromToWith(0,Math.min(size(),newSize)-1,this,0);
- elements(newVector.elements(),newSize);
- }
+ if (newSize!=size()) {
+ BitVector newVector = new BitVector(newSize);
+ newVector.replaceFromToWith(0,Math.min(size(),newSize)-1,this,0);
+ elements(newVector.elements(),newSize);
+ }
}
/**
* Returns the size of the receiver.
*/
public int size() {
- return nbits;
+ return nbits;
}
/**
* Returns a string representation of the receiver. For every index
@@ -770,20 +768,20 @@
* @return a string representation of this bit vector.
*/
public String toString() {
- StringBuffer buffer = new StringBuffer(nbits);
- String separator = "";
- buffer.append('{');
-
- for (int i = 0 ; i < nbits; i++) {
- if (get(i)) {
- buffer.append(separator);
- separator = ", ";
- buffer.append(i);
- }
- }
+ StringBuffer buffer = new StringBuffer(nbits);
+ String separator = "";
+ buffer.append('{');
+
+ for (int i = 0 ; i < nbits; i++) {
+ if (get(i)) {
+ buffer.append(separator);
+ separator = ", ";
+ buffer.append(i);
+ }
+ }
- buffer.append('}');
- return buffer.toString();
+ buffer.append('}');
+ return buffer.toString();
}
/**
* Performs a logical <b>XOR</b> of the receiver with another bit vector (A = A ^ B).
@@ -800,9 +798,9 @@
* @throws IllegalArgumentException if <tt>size() > other.size()</tt>.
*/
public void xor(BitVector other) {
- checkSize(other);
- final long[] theBits = this.bits; // cached for speed.
- final long[] otherBits = other.bits; //cached for speed.
- for(int i=theBits.length; --i >= 0;) theBits[i] ^= otherBits[i];
+ checkSize(other);
+ final long[] theBits = this.bits; // cached for speed.
+ final long[] otherBits = other.bits; //cached for speed.
+ for(int i=theBits.length; --i >= 0;) theBits[i] ^= otherBits[i];
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/QuickBitVector.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/QuickBitVector.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/QuickBitVector.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/bitvector/QuickBitVector.java Wed Nov 25 03:35:59 2009
@@ -15,15 +15,13 @@
* <b>WARNING: Methods of this class do not check preconditions.</b>
* Provided with invalid parameters these method may return (or set) invalid values without throwing any exception.
* <b>You should only use this class when performance is critical and you are absolutely sure that indexes are within bounds.</b>
- * <p>
+ * <p>
* A bitvector is modelled as a long array, i.e. <tt>long[] bits</tt> holds bits of a bitvector.
* 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).
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
* @see BitVector
* @see BitMatrix
* @see java.util.BitSet
@@ -33,11 +31,11 @@
*/
@Deprecated
public class QuickBitVector extends Object {
- protected final static int ADDRESS_BITS_PER_UNIT = 6; // 64=2^6
- protected final static int BITS_PER_UNIT = 64; // = 1 << ADDRESS_BITS_PER_UNIT
- protected final static int BIT_INDEX_MASK = 63; // = BITS_PER_UNIT - 1;
-
- private static final long[] pows = precomputePows(); //precompute bitmasks for speed
+ protected final static int ADDRESS_BITS_PER_UNIT = 6; // 64=2^6
+ protected final static int BITS_PER_UNIT = 64; // = 1 << ADDRESS_BITS_PER_UNIT
+ protected final static int BIT_INDEX_MASK = 63; // = BITS_PER_UNIT - 1;
+
+ private static final long[] pows = precomputePows(); //precompute bitmasks for speed
/**
* Makes this class non instantiable, but still inheritable.
*/
@@ -54,12 +52,12 @@
* @return the bit mask having all bits between <tt>from</tt> and <tt>to</tt> set to 1.
*/
public static final long bitMaskWithBitsSetFromTo(int from, int to) {
- return pows[to-from+1] << from;
+ return pows[to-from+1] << from;
- // This turned out to be slower:
- // 0xffffffffffffffffL == ~0L == -1L == all 64 bits set.
- // int width;
- // return (width=to-from+1) == 0 ? 0L : (0xffffffffffffffffL >>> (BITS_PER_UNIT-width)) << from;
+ // This turned out to be slower:
+ // 0xffffffffffffffffL == ~0L == -1L == all 64 bits set.
+ // int width;
+ // return (width=to-from+1) == 0 ? 0L : (0xffffffffffffffffL >>> (BITS_PER_UNIT-width)) << from;
}
/**
* Changes the bit with index <tt>bitIndex</tt> in the bitvector <tt>bits</tt> to the "clear" (<tt>false</tt>) state.
@@ -68,7 +66,7 @@
* @param bitIndex the index of the bit to be cleared.
*/
public static void clear(long[] bits, int bitIndex) {
- bits[bitIndex >> ADDRESS_BITS_PER_UNIT] &= ~(1L << (bitIndex & BIT_INDEX_MASK));
+ bits[bitIndex >> ADDRESS_BITS_PER_UNIT] &= ~(1L << (bitIndex & BIT_INDEX_MASK));
}
/**
* Returns from the bitvector the value of the bit with the specified index.
@@ -80,7 +78,7 @@
* @return the value of the bit with the specified index.
*/
public static boolean get(long[] bits, int bitIndex) {
- return ((bits[bitIndex >> ADDRESS_BITS_PER_UNIT] & (1L << (bitIndex & BIT_INDEX_MASK))) != 0);
+ return ((bits[bitIndex >> ADDRESS_BITS_PER_UNIT] & (1L << (bitIndex & BIT_INDEX_MASK))) != 0);
}
/**
* Returns a long value representing bits of a bitvector from index <tt>from</tt> to index <tt>to</tt>.
@@ -94,37 +92,37 @@
* @return the specified bits as long value.
*/
public static long getLongFromTo(long[] bits, int from, int to) {
- if (from>to) return 0L;
-
- final int fromIndex = from >> ADDRESS_BITS_PER_UNIT; //equivalent to from/64
- final int toIndex = to >> ADDRESS_BITS_PER_UNIT;
- final int fromOffset = from & BIT_INDEX_MASK; //equivalent to from%64
- final int toOffset = to & BIT_INDEX_MASK;
- //this is equivalent to the above, but slower:
- //final int fromIndex=from/BITS_PER_UNIT;
- //final int toIndex=to/BITS_PER_UNIT;
- //final int fromOffset=from%BITS_PER_UNIT;
- //final int toOffset=to%BITS_PER_UNIT;
+ if (from>to) return 0L;
+
+ final int fromIndex = from >> ADDRESS_BITS_PER_UNIT; //equivalent to from/64
+ final int toIndex = to >> ADDRESS_BITS_PER_UNIT;
+ final int fromOffset = from & BIT_INDEX_MASK; //equivalent to from%64
+ final int toOffset = to & BIT_INDEX_MASK;
+ //this is equivalent to the above, but slower:
+ //final int fromIndex=from/BITS_PER_UNIT;
+ //final int toIndex=to/BITS_PER_UNIT;
+ //final int fromOffset=from%BITS_PER_UNIT;
+ //final int toOffset=to%BITS_PER_UNIT;
- long mask;
- if (fromIndex==toIndex) { //range does not cross unit boundaries; value to retrieve is contained in one single long value.
- mask=bitMaskWithBitsSetFromTo(fromOffset, toOffset);
- return (bits[fromIndex] & mask) >>> fromOffset;
-
- }
+ long mask;
+ if (fromIndex==toIndex) { //range does not cross unit boundaries; value to retrieve is contained in one single long value.
+ mask=bitMaskWithBitsSetFromTo(fromOffset, toOffset);
+ return (bits[fromIndex] & mask) >>> fromOffset;
+
+ }
- //range crosses unit boundaries; value to retrieve is spread over two long values.
- //get part from first long value
- mask=bitMaskWithBitsSetFromTo(fromOffset, BIT_INDEX_MASK);
- final long x1=(bits[fromIndex] & mask) >>> fromOffset;
-
- //get part from second long value
- mask=bitMaskWithBitsSetFromTo(0, toOffset);
- final long x2=(bits[toIndex] & mask) << (BITS_PER_UNIT-fromOffset);
-
- //combine
- return x1|x2;
+ //range crosses unit boundaries; value to retrieve is spread over two long values.
+ //get part from first long value
+ mask=bitMaskWithBitsSetFromTo(fromOffset, BIT_INDEX_MASK);
+ final long x1=(bits[fromIndex] & mask) >>> fromOffset;
+
+ //get part from second long value
+ mask=bitMaskWithBitsSetFromTo(0, toOffset);
+ final long x2=(bits[toIndex] & mask) << (BITS_PER_UNIT-fromOffset);
+
+ //combine
+ return x1|x2;
}
/**
Returns the index of the least significant bit in state "true".
@@ -138,9 +136,9 @@
</pre>
*/
static public int leastSignificantBit(int value) {
- int i=-1;
- while (++i < 32 && (((1<<i) & value)) == 0);
- return i;
+ int i=-1;
+ while (++i < 32 && (((1<<i) & value)) == 0);
+ return i;
}
/**
* Constructs a low level bitvector that holds <tt>size</tt> elements, with each element taking <tt>bitsPerElement</tt> bits.
@@ -150,10 +148,10 @@
* @return a low level bitvector.
*/
public static long[] makeBitVector(int size, int bitsPerElement) {
- int nBits = size*bitsPerElement;
- int unitIndex = (nBits-1) >> ADDRESS_BITS_PER_UNIT;
- long[] bitVector = new long[unitIndex + 1];
- return bitVector;
+ int nBits = size*bitsPerElement;
+ int unitIndex = (nBits-1) >> ADDRESS_BITS_PER_UNIT;
+ long[] bitVector = new long[unitIndex + 1];
+ return bitVector;
}
/**
Returns the index of the most significant bit in state "true".
@@ -167,16 +165,16 @@
</pre>
*/
static public int mostSignificantBit(int value) {
- int i=32;
- while (--i >=0 && (((1<<i) & value)) == 0);
- return i;
+ int i=32;
+ while (--i >=0 && (((1<<i) & value)) == 0);
+ return i;
}
/**
* Returns the index within the unit that contains the given bitIndex.
*/
protected static int offset(int bitIndex) {
- return bitIndex & BIT_INDEX_MASK;
- //equivalent to bitIndex%64
+ return bitIndex & BIT_INDEX_MASK;
+ //equivalent to bitIndex%64
}
/**
* Initializes a table with numbers having 1,2,3,...,64 bits set.
@@ -185,35 +183,35 @@
* to speedup calculations in subsequent methods.
*/
private static long[] precomputePows() {
- long[] pows=new long[BITS_PER_UNIT+1];
- long value = ~0L;
- for (int i=BITS_PER_UNIT+1; --i >= 1; ) {
- pows[i]=value >>> (BITS_PER_UNIT-i);
- //System.out.println((i)+":"+pows[i]);
- }
- pows[0]=0L;
- //System.out.println((0)+":"+pows[0]);
- return pows;
+ long[] pows=new long[BITS_PER_UNIT+1];
+ long value = ~0L;
+ for (int i=BITS_PER_UNIT+1; --i >= 1; ) {
+ pows[i]=value >>> (BITS_PER_UNIT-i);
+ //System.out.println((i)+":"+pows[i]);
+ }
+ pows[0]=0L;
+ //System.out.println((0)+":"+pows[0]);
+ return pows;
- //OLD STUFF
- /*
- for (int i=BITS_PER_UNIT+1; --i >= 0; ) {
- pows[i]=value;
- value = value >>> 1;
- System.out.println((i)+":"+pows[i]);
- }
- */
-
- /*
- long[] pows=new long[BITS_PER_UNIT];
- for (int i=0; i<BITS_PER_UNIT-1; i++) {
- pows[i]=Math.round(Math.pow(2.0,i+1))-1;
- System.out.println((i)+":"+pows[i]);
- }
- pows[BITS_PER_UNIT-1] = ~0L;
- System.out.println((BITS_PER_UNIT-1)+":"+pows[BITS_PER_UNIT-1]);
- return pows;
- */
+ //OLD STUFF
+ /*
+ for (int i=BITS_PER_UNIT+1; --i >= 0; ) {
+ pows[i]=value;
+ value = value >>> 1;
+ System.out.println((i)+":"+pows[i]);
+ }
+ */
+
+ /*
+ long[] pows=new long[BITS_PER_UNIT];
+ for (int i=0; i<BITS_PER_UNIT-1; i++) {
+ pows[i]=Math.round(Math.pow(2.0,i+1))-1;
+ System.out.println((i)+":"+pows[i]);
+ }
+ pows[BITS_PER_UNIT-1] = ~0L;
+ System.out.println((BITS_PER_UNIT-1)+":"+pows[BITS_PER_UNIT-1]);
+ return pows;
+ */
}
/**
* Sets the bit with index <tt>bitIndex</tt> in the bitvector <tt>bits</tt> to the state specified by <tt>value</tt>.
@@ -222,11 +220,11 @@
* @param bitIndex the index of the bit to be changed.
* @param value the value to be stored in the bit.
*/
-public static void put(long[] bits, int bitIndex, boolean value) {
- if (value)
- set(bits, bitIndex);
- else
- clear(bits, bitIndex);
+public static void put(long[] bits, int bitIndex, boolean value) {
+ if (value)
+ set(bits, bitIndex);
+ else
+ clear(bits, bitIndex);
}
/**
* Sets bits of a bitvector from index <code>from</code> to index <code>to</code> to the bits of <code>value</code>.
@@ -241,45 +239,45 @@
* @param to index of end bit (inclusive).
*/
public static void putLongFromTo(long[] bits, long value, int from, int to) {
- if (from>to) return;
-
- final int fromIndex=from >> ADDRESS_BITS_PER_UNIT; //equivalent to from/64
- final int toIndex=to >> ADDRESS_BITS_PER_UNIT;
- final int fromOffset=from & BIT_INDEX_MASK; //equivalent to from%64
- final int toOffset=to & BIT_INDEX_MASK;
- /*
- this is equivalent to the above, but slower:
- int fromIndex=from/BITS_PER_UNIT;
- int toIndex=to/BITS_PER_UNIT;
- int fromOffset=from%BITS_PER_UNIT;
- int toOffset=to%BITS_PER_UNIT;
- */
-
- //make sure all unused bits to the left are cleared.
- long mask;
- mask=bitMaskWithBitsSetFromTo(to-from+1, BIT_INDEX_MASK);
- long cleanValue=value & (~mask);
+ if (from>to) return;
+
+ final int fromIndex=from >> ADDRESS_BITS_PER_UNIT; //equivalent to from/64
+ final int toIndex=to >> ADDRESS_BITS_PER_UNIT;
+ final int fromOffset=from & BIT_INDEX_MASK; //equivalent to from%64
+ final int toOffset=to & BIT_INDEX_MASK;
+ /*
+ this is equivalent to the above, but slower:
+ int fromIndex=from/BITS_PER_UNIT;
+ int toIndex=to/BITS_PER_UNIT;
+ int fromOffset=from%BITS_PER_UNIT;
+ int toOffset=to%BITS_PER_UNIT;
+ */
+
+ //make sure all unused bits to the left are cleared.
+ long mask;
+ mask=bitMaskWithBitsSetFromTo(to-from+1, BIT_INDEX_MASK);
+ long cleanValue=value & (~mask);
- long shiftedValue;
-
- if (fromIndex==toIndex) { //range does not cross unit boundaries; should go into one single long value.
- shiftedValue=cleanValue << fromOffset;
- mask=bitMaskWithBitsSetFromTo(fromOffset, toOffset);
- bits[fromIndex] = (bits[fromIndex] & (~mask)) | shiftedValue;
- return;
-
- }
+ long shiftedValue;
+
+ if (fromIndex==toIndex) { //range does not cross unit boundaries; should go into one single long value.
+ shiftedValue=cleanValue << fromOffset;
+ mask=bitMaskWithBitsSetFromTo(fromOffset, toOffset);
+ bits[fromIndex] = (bits[fromIndex] & (~mask)) | shiftedValue;
+ return;
+
+ }
- //range crosses unit boundaries; value should go into two long values.
- //copy into first long value.
- shiftedValue=cleanValue << fromOffset;
- mask=bitMaskWithBitsSetFromTo(fromOffset, BIT_INDEX_MASK);
- bits[fromIndex] = (bits[fromIndex] & (~mask)) | shiftedValue;
-
- //copy into second long value.
- shiftedValue=cleanValue >>> (BITS_PER_UNIT - fromOffset);
- mask=bitMaskWithBitsSetFromTo(0, toOffset);
- bits[toIndex] = (bits[toIndex] & (~mask)) | shiftedValue;
+ //range crosses unit boundaries; value should go into two long values.
+ //copy into first long value.
+ shiftedValue=cleanValue << fromOffset;
+ mask=bitMaskWithBitsSetFromTo(fromOffset, BIT_INDEX_MASK);
+ bits[fromIndex] = (bits[fromIndex] & (~mask)) | shiftedValue;
+
+ //copy into second long value.
+ shiftedValue=cleanValue >>> (BITS_PER_UNIT - fromOffset);
+ mask=bitMaskWithBitsSetFromTo(0, toOffset);
+ bits[toIndex] = (bits[toIndex] & (~mask)) | shiftedValue;
}
/**
* Changes the bit with index <tt>bitIndex</tt> in the bitvector <tt>bits</tt> to the "set" (<tt>true</tt>) state.
@@ -288,13 +286,13 @@
* @param bitIndex the index of the bit to be set.
*/
public static void set(long[] bits, int bitIndex) {
- bits[bitIndex >> ADDRESS_BITS_PER_UNIT] |= 1L << (bitIndex & BIT_INDEX_MASK);
+ bits[bitIndex >> ADDRESS_BITS_PER_UNIT] |= 1L << (bitIndex & BIT_INDEX_MASK);
}
/**
* Returns the index of the unit that contains the given bitIndex.
*/
protected static int unit(int bitIndex) {
- return bitIndex >> ADDRESS_BITS_PER_UNIT;
- //equivalent to bitIndex/64
+ return bitIndex >> ADDRESS_BITS_PER_UNIT;
+ //equivalent to bitIndex/64
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer.java Wed Nov 25 03:35:59 2009
@@ -12,32 +12,30 @@
/**
* Fixed sized (non resizable) streaming buffer connected to a target <tt>DoubleBufferConsumer</tt> to which data is automatically flushed upon buffer overflow.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
*/
@Deprecated
public class DoubleBuffer extends org.apache.mahout.matrix.PersistentObject implements DoubleBufferConsumer {
- protected DoubleBufferConsumer target;
- protected double[] elements;
+ protected DoubleBufferConsumer target;
+ protected double[] elements;
- // vars cached for speed
- protected DoubleArrayList list;
- protected int capacity;
- protected int size;
+ // vars cached for speed
+ protected DoubleArrayList list;
+ protected int capacity;
+ protected int size;
/**
* Constructs and returns a new buffer with the given target.
* @param target the target to flush to.
* @param capacity the number of points the buffer shall be capable of holding before overflowing and flushing to the target.
*/
public DoubleBuffer(DoubleBufferConsumer target, int capacity) {
- this.target = target;
- this.capacity = capacity;
- this.elements = new double[capacity];
- this.list = new DoubleArrayList(elements);
- this.size = 0;
+ this.target = target;
+ this.capacity = capacity;
+ this.elements = new double[capacity];
+ this.list = new DoubleArrayList(elements);
+ this.size = 0;
}
/**
* Adds the specified element to the receiver.
@@ -45,33 +43,33 @@
* @param element the element to add.
*/
public void add(double element) {
- if (this.size == this.capacity) flush();
- this.elements[size++] = element;
+ if (this.size == this.capacity) flush();
+ this.elements[size++] = element;
}
/**
* Adds all elements of the specified list to the receiver.
* @param list the list of which all elements shall be added.
*/
public void addAllOf(DoubleArrayList list) {
- int listSize = list.size();
- if (this.size + listSize >= this.capacity) flush();
- this.target.addAllOf(list);
+ int listSize = list.size();
+ if (this.size + listSize >= this.capacity) flush();
+ this.target.addAllOf(list);
}
/**
* Sets the receiver's size to zero.
* In other words, forgets about any internally buffered elements.
*/
public void clear() {
- this.size = 0;
+ this.size = 0;
}
/**
* Adds all internally buffered elements to the receiver's target, then resets the current buffer size to zero.
*/
public void flush() {
- if (this.size > 0) {
- list.setSize(this.size);
- this.target.addAllOf(list);
- this.size = 0;
- }
+ if (this.size > 0) {
+ list.setSize(this.size);
+ this.target.addAllOf(list);
+ this.size = 0;
+ }
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2D.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2D.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2D.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2D.java Wed Nov 25 03:35:59 2009
@@ -12,36 +12,34 @@
/**
* Fixed sized (non resizable) streaming buffer connected to a target <tt>DoubleBuffer2DConsumer</tt> to which data is automatically flushed upon buffer overflow.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.
*/
@Deprecated
public class DoubleBuffer2D extends org.apache.mahout.matrix.PersistentObject implements DoubleBuffer2DConsumer {
- protected DoubleBuffer2DConsumer target;
- protected double[] xElements;
- protected double[] yElements;
+ protected DoubleBuffer2DConsumer target;
+ protected double[] xElements;
+ protected double[] yElements;
- // vars cached for speed
- protected DoubleArrayList xList;
- protected DoubleArrayList yList;
- protected int capacity;
- protected int size;
+ // vars cached for speed
+ protected DoubleArrayList xList;
+ protected DoubleArrayList yList;
+ protected int capacity;
+ protected int size;
/**
* Constructs and returns a new buffer with the given target.
* @param target the target to flush to.
* @param capacity the number of points the buffer shall be capable of holding before overflowing and flushing to the target.
*/
public DoubleBuffer2D(DoubleBuffer2DConsumer target, int capacity) {
- this.target = target;
- this.capacity = capacity;
- this.xElements = new double[capacity];
- this.yElements = new double[capacity];
- this.xList = new DoubleArrayList(xElements);
- this.yList = new DoubleArrayList(yElements);
- this.size = 0;
+ this.target = target;
+ this.capacity = capacity;
+ this.xElements = new double[capacity];
+ this.yElements = new double[capacity];
+ this.xList = new DoubleArrayList(xElements);
+ this.yList = new DoubleArrayList(yElements);
+ this.size = 0;
}
/**
* Adds the specified point (x,y) to the receiver.
@@ -50,9 +48,9 @@
* @param y the y-coordinate of the point to add.
*/
public void add(double x, double y) {
- if (this.size == this.capacity) flush();
- this.xElements[this.size] = x;
- this.yElements[this.size++] = y;
+ if (this.size == this.capacity) flush();
+ this.xElements[this.size] = x;
+ this.yElements[this.size++] = y;
}
/**
* Adds all specified points (x,y) to the receiver.
@@ -60,26 +58,26 @@
* @param y the y-coordinates of the points to add.
*/
public void addAllOf(DoubleArrayList x, DoubleArrayList y) {
- int listSize = x.size();
- if (this.size + listSize >= this.capacity) flush();
- this.target.addAllOf(x, y);
+ int listSize = x.size();
+ if (this.size + listSize >= this.capacity) flush();
+ this.target.addAllOf(x, y);
}
/**
* Sets the receiver's size to zero.
* In other words, forgets about any internally buffered elements.
*/
public void clear() {
- this.size = 0;
+ this.size = 0;
}
/**
* Adds all internally buffered points to the receiver's target, then resets the current buffer size to zero.
*/
public void flush() {
- if (this.size > 0) {
- xList.setSize(this.size);
- yList.setSize(this.size);
- this.target.addAllOf(xList,yList);
- this.size = 0;
- }
+ if (this.size > 0) {
+ xList.setSize(this.size);
+ yList.setSize(this.size);
+ this.target.addAllOf(xList,yList);
+ this.size = 0;
+ }
}
}
Modified: lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2DConsumer.java
URL: http://svn.apache.org/viewvc/lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2DConsumer.java?rev=883973&r1=883972&r2=883973&view=diff
==============================================================================
--- lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2DConsumer.java (original)
+++ lucene/mahout/trunk/matrix/src/main/java/org/apache/mahout/matrix/buffer/DoubleBuffer2DConsumer.java Wed Nov 25 03:35:59 2009
@@ -12,8 +12,6 @@
/**
* Target of a streaming <tt>DoubleBuffer2D</tt> into which data is flushed upon buffer overflow.
*
- * @author wolfgang.hoschek@cern.ch
- * @version 1.0, 09/24/99
*/
/**
* @deprecated until unit tests are in place. Until this time, this class/interface is unsupported.