Save This Page
Home » mahout-collections-1.0-src » org.apache.mahout.math.bitvector » [javadoc | source]
    1   /*
    2   Copyright 1999 CERN - European Organization for Nuclear Research.
    3   Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
    4   is hereby granted without fee, provided that the above copyright notice appear in all copies and 
    5   that both that copyright notice and this permission notice appear in supporting documentation. 
    6   CERN makes no representations about the suitability of this software for any purpose. 
    7   It is provided "as is" without expressed or implied warranty.
    8   */
    9   package org.apache.mahout.math.bitvector;
   10   
   11   import org.apache.mahout.math.PersistentObject;
   12   
   13   import java.awt.Rectangle;
   14   /**
   15    * Fixed sized (non resizable) n*m bit matrix.
   16    * A bit matrix has a number of columns and rows, which are assigned upon instance construction - The matrix's size is then <tt>columns()*rows()</tt>.
   17    * Bits are accessed via <tt>(column,row)</tt> coordinates.
   18    * <p>
   19    * Individual bits can be examined, set, or cleared.
   20    * Rectangular parts (boxes) can quickly be extracted, copied and replaced.
   21    * Quick iteration over boxes is provided by optimized internal iterators (<tt>forEach()</tt> methods).
   22    * One <code>BitMatrix</code> may be used to modify the contents of another 
   23    * <code>BitMatrix</code> through logical AND, OR, XOR and other similar operations.
   24    * <p>
   25    * Legal coordinates range from <tt>[0,0]</tt> to <tt>[columns()-1,rows()-1]</tt>.
   26    * Any attempt to access a bit at a coordinate <tt>column&lt;0 || column&gt;=columns() || row&lt;0 || row&gt;=rows()</tt> will throw an <tt>IndexOutOfBoundsException</tt>.
   27    * Operations involving two bit matrices (like AND, OR, XOR, etc.) will throw an <tt>IllegalArgumentException</tt> if both bit matrices do not have the same number of columns and rows.
   28    * <p>
   29    * If you need extremely quick access to individual bits: Although getting and setting individual bits with methods <tt>get(...)</tt> and <tt>put(...)</tt> is quick, it is even quicker (<b>but not safe</b>) to use <tt>getQuick(...)</tt> and <tt>putQuick(...)</tt>.
   30    * <p>
   31    * <b>Note</b> that this implementation is not synchronized.
   32    *
   33    * @see     BitVector
   34    * @see     QuickBitVector
   35    * @see     java.util.BitSet
   36    * @deprecated until unit tests have been written
   37    */
   38   
   39   /** @deprecated until unit tests are in place.  Until this time, this class/interface is unsupported. */
   40   @Deprecated
   41   public class BitMatrix extends PersistentObject {
   42   
   43     private int columns;
   44     private int rows;
   45   
   46     /*
   47      * The bits of this matrix.
   48      * bits are stored in row major, i.e.
   49      * bitIndex==row*columns + column
   50      * columnOf(bitIndex)==bitIndex%columns
   51      * rowOf(bitIndex)==bitIndex/columns
   52      */
   53     private long[] bits;
   54   
   55     /**
   56      * Constructs a bit matrix with a given number of columns and rows. All bits are initially <tt>false</tt>.
   57      *
   58      * @param columns the number of columns the matrix shall have.
   59      * @param rows    the number of rows the matrix shall have.
   60      * @throws IllegalArgumentException if <tt>columns &lt; 0 || rows &lt; 0</tt>.
   61      */
   62     public BitMatrix(int columns, int rows) {
   63       elements(QuickBitVector.makeBitVector(columns * rows, 1), columns, rows);
   64     }
   65   
   66     /**
   67      * Performs a logical <b>AND</b> of the receiver with another bit matrix. The receiver is modified so that a bit in it
   68      * has the value <code>true</code> if and only if it already had the value <code>true</code> and the corresponding bit
   69      * in the other bit matrix argument has the value <code>true</code>.
   70      *
   71      * @param other a bit matrix.
   72      * @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
   73      */
   74     public void and(BitMatrix other) {
   75       checkDimensionCompatibility(other);
   76       toBitVector().and(other.toBitVector());
   77     }
   78   
   79     /**
   80      * Clears all of the bits in receiver whose corresponding bit is set in the other bit matrix. In other words,
   81      * determines the difference (A\B) between two bit matrices.
   82      *
   83      * @param other a bit matrix with which to mask the receiver.
   84      * @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
   85      */
   86     public void andNot(BitMatrix other) {
   87       checkDimensionCompatibility(other);
   88       toBitVector().andNot(other.toBitVector());
   89     }
   90   
   91     /**
   92      * Returns the number of bits currently in the <tt>true</tt> state. Optimized for speed. Particularly quick if the
   93      * receiver is either sparse or dense.
   94      */
   95     public int cardinality() {
   96       return toBitVector().cardinality();
   97     }
   98   
   99     /** Sanity check for operations requiring matrices with the same number of columns and rows. */
  100     protected void checkDimensionCompatibility(BitMatrix other) {
  101       if (columns != other.columns() || rows != other.rows()) {
  102         throw new IllegalArgumentException(
  103             "Incompatible dimensions: (columns,rows)=(" + columns + ',' + rows + "), (other.columns,other.rows)=(" +
  104                 other.columns() + ',' + other.rows() + ')');
  105       }
  106     }
  107   
  108     /** Clears all bits of the receiver. */
  109     public void clear() {
  110       toBitVector().clear();
  111     }
  112   
  113     /**
  114      * Cloning this <code>BitMatrix</code> produces a new <code>BitMatrix</code> that is equal to it. The clone of the bit
  115      * matrix is another bit matrix that has exactly the same bits set to <code>true</code> as this bit matrix and the
  116      * same number of columns and rows.
  117      *
  118      * @return a clone of this bit matrix.
  119      */
  120     @Override
  121     public Object clone() {
  122       BitMatrix clone = (BitMatrix) super.clone();
  123       if (this.bits != null) {
  124         clone.bits = this.bits.clone();
  125       }
  126       return clone;
  127     }
  128   
  129     /** Returns the number of columns of the receiver. */
  130     public int columns() {
  131       return columns;
  132     }
  133   
  134     /** Checks whether the receiver contains the given box. */
  135     protected void containsBox(int column, int row, int width, int height) {
  136       if (column < 0 || column + width > columns || row < 0 || row + height > rows) {
  137         throw new IndexOutOfBoundsException(
  138             "column:" + column + ", row:" + row + " ,width:" + width + ", height:" + height);
  139       }
  140     }
  141   
  142     /**
  143      * Returns a shallow clone of the receiver; calls <code>clone()</code> and casts the result.
  144      *
  145      * @return a shallow clone of the receiver.
  146      */
  147     public BitMatrix copy() {
  148       return (BitMatrix) clone();
  149     }
  150   
  151     protected long[] elements() {
  152       return bits;
  153     }
  154   
  155     /**
  156      * You normally need not use this method. Use this method only if performance is critical. Sets the bit matrix's
  157      * backing bits, columns and rows. <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array
  158      * is not copied</b>. So if subsequently you modify the specified array directly via the [] operator, be sure you know
  159      * what you're doing.
  160      *
  161      * @throws IllegalArgumentException if <tt>columns &lt; 0 || rows &lt; 0 || columns*rows &gt; bits.length*64</tt>
  162      */
  163     protected void elements(long[] bits, int columns, int rows) {
  164       if (columns < 0 || rows < 0 || columns * rows > bits.length * QuickBitVector.BITS_PER_UNIT) {
  165         throw new IllegalArgumentException();
  166       }
  167       this.bits = bits;
  168       this.columns = columns;
  169       this.rows = rows;
  170     }
  171   
  172     /**
  173      * Compares this object against the specified object. The result is <code>true</code> if and only if the argument is
  174      * not <code>null</code> and is a <code>BitMatrix</code> object that has the same number of columns and rows as the
  175      * receiver and that has exactly the same bits set to <code>true</code> as the receiver.
  176      *
  177      * @param obj the object to compare with.
  178      * @return <code>true</code> if the objects are the same; <code>false</code> otherwise.
  179      */
  180     public boolean equals(Object obj) {
  181       if (obj == null || !(obj instanceof BitMatrix)) {
  182         return false;
  183       }
  184       if (this == obj) {
  185         return true;
  186       }
  187   
  188       BitMatrix other = (BitMatrix) obj;
  189       if (columns != other.columns() || rows != other.rows()) {
  190         return false;
  191       }
  192   
  193       return toBitVector().equals(other.toBitVector());
  194     }
  195   
  196     /**
  197      * Applies a procedure to each coordinate that holds a bit in the given state. Iterates rowwise downwards from
  198      * [columns()-1,rows()-1] to [0,0]. Useful, for example, if you want to copy bits into an image or somewhere else.
  199      * Optimized for speed. Particularly quick if one of the following conditions holds <ul> <li><tt>state==true</tt> and
  200      * the receiver is sparse (<tt>cardinality()</tt> is small compared to <tt>size()</tt>). <li><tt>state==false</tt> and
  201      * the receiver is dense (<tt>cardinality()</tt> is large compared to <tt>size()</tt>). </ul>
  202      *
  203      * @param state     element to search for.
  204      * @param procedure a procedure object taking as first argument the current column and as second argument the current
  205      *                  row. Stops iteration if the procedure returns <tt>false</tt>, otherwise continues.
  206      * @return <tt>false</tt> if the procedure stopped before all elements where iterated over, <tt>true</tt> otherwise.
  207      */
  208     public boolean forEachCoordinateInState(boolean state, org.apache.mahout.math.function.IntIntProcedure procedure) {
  209       /*
  210       this is equivalent to the low level version below, apart from that it iterates in the reverse oder and is slower.
  211       if (size()==0) return true;
  212       BitVector vector = toBitVector();
  213       return vector.forEachIndexFromToInState(0,size()-1,state,
  214         new IntFunction() {
  215           public boolean apply(int index) {
  216             return function.apply(index%columns, index/columns);
  217           }
  218         }
  219       );
  220       */
  221   
  222       //low level implementation for speed.
  223       if (size() == 0) {
  224         return true;
  225       }
  226       BitVector vector = new BitVector(bits, size());
  227   
  228       long[] theBits = bits;
  229   
  230       int column = columns - 1;
  231       int row = rows - 1;
  232   
  233       // for each coordinate of bits of partial unit
  234       long val = theBits[bits.length - 1];
  235       for (int j = vector.numberOfBitsInPartialUnit(); --j >= 0;) {
  236         long mask = val & (1L << j);
  237         if ((state && (mask != 0L)) || ((!state) && (mask == 0L))) {
  238           if (!procedure.apply(column, row)) {
  239             return false;
  240           }
  241         }
  242         if (--column < 0) {
  243           column = columns - 1;
  244           --row;
  245         }
  246       }
  247   
  248   
  249       // for each coordinate of bits of full units
  250       long comparator;
  251       if (state) {
  252         comparator = 0L;
  253       } else {
  254         comparator = ~0L;
  255       } // all 64 bits set
  256   
  257       int bitsPerUnit = QuickBitVector.BITS_PER_UNIT;
  258       for (int i = vector.numberOfFullUnits(); --i >= 0;) {
  259         val = theBits[i];
  260         if (val != comparator) {
  261           // at least one element within current unit matches.
  262           // iterate over all bits within current unit.
  263           if (state) {
  264             for (int j = bitsPerUnit; --j >= 0;) {
  265               if (((val & (1L << j))) != 0L) {
  266                 if (!procedure.apply(column, row)) {
  267                   return false;
  268                 }
  269               }
  270               if (--column < 0) {
  271                 column = columns - 1;
  272                 --row;
  273               }
  274             }
  275           } else { // unrolled comparison for speed.
  276             for (int j = bitsPerUnit; --j >= 0;) {
  277               if (((val & (1L << j))) == 0L) {
  278                 if (!procedure.apply(column, row)) {
  279                   return false;
  280                 }
  281               }
  282               if (--column < 0) {
  283                 column = columns - 1;
  284                 --row;
  285               }
  286             }
  287           }
  288   
  289         } else { // no element within current unit matches --> skip unit
  290           column -= bitsPerUnit;
  291           if (column < 0) {
  292             // avoid implementation with *, /, %
  293             column += bitsPerUnit;
  294             for (int j = bitsPerUnit; --j >= 0;) {
  295               if (--column < 0) {
  296                 column = columns - 1;
  297                 --row;
  298               }
  299             }
  300           }
  301         }
  302   
  303       }
  304   
  305       return true;
  306   
  307     }
  308   
  309     /**
  310      * Returns from the receiver the value of the bit at the specified coordinate. The value is <tt>true</tt> if this bit
  311      * is currently set; otherwise, returns <tt>false</tt>.
  312      *
  313      * @param column the index of the column-coordinate.
  314      * @param row    the index of the row-coordinate.
  315      * @return the value of the bit at the specified coordinate.
  316      * @throws IndexOutOfBoundsException if <tt>column&lt;0 || column&gt;=columns() || row&lt;0 || row&gt;=rows()</tt>
  317      */
  318     public boolean get(int column, int row) {
  319       if (column < 0 || column >= columns || row < 0 || row >= rows) {
  320         throw new IndexOutOfBoundsException("column:" + column + ", row:" + row);
  321       }
  322       return QuickBitVector.get(bits, row * columns + column);
  323     }
  324   
  325     /**
  326      * Returns from the receiver the value of the bit at the specified coordinate; <b>WARNING:</b> Does not check
  327      * preconditions. The value is <tt>true</tt> if this bit is currently set; otherwise, returns <tt>false</tt>.
  328      *
  329      * <p>Provided with invalid parameters this method may return invalid values without throwing any exception. <b>You
  330      * should only use this method when you are absolutely sure that the coordinate is within bounds.</b> Precondition
  331      * (unchecked): <tt>column&gt;=0 && column&lt;columns() && row&gt;=0 && row&lt;rows()</tt>.
  332      *
  333      * @param column the index of the column-coordinate.
  334      * @param row    the index of the row-coordinate.
  335      * @return the value of the bit at the specified coordinate.
  336      */
  337     public boolean getQuick(int column, int row) {
  338       return QuickBitVector.get(bits, row * columns + column);
  339     }
  340   
  341     /** Returns a hash code value for the receiver. */
  342     public int hashCode() {
  343       return toBitVector().hashCode();
  344     }
  345   
  346     /** Performs a logical <b>NOT</b> on the bits of the receiver. */
  347     public void not() {
  348       toBitVector().not();
  349     }
  350   
  351     /**
  352      * Performs a logical <b>OR</b> of the receiver with another bit matrix. The receiver is modified so that a bit in it
  353      * has the value <code>true</code> if and only if it either already had the value <code>true</code> or the
  354      * corresponding bit in the other bit matrix argument has the value <code>true</code>.
  355      *
  356      * @param other a bit matrix.
  357      * @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
  358      */
  359     public void or(BitMatrix other) {
  360       checkDimensionCompatibility(other);
  361       toBitVector().or(other.toBitVector());
  362     }
  363   
  364     /**
  365      * Constructs and returns a new matrix with <tt>width</tt> columns and <tt>height</tt> rows which is a copy of the
  366      * contents of the given box. The box ranges from <tt>[column,row]</tt> to <tt>[column+width-1,row+height-1]</tt>, all
  367      * inclusive.
  368      *
  369      * @param column the index of the column-coordinate.
  370      * @param row    the index of the row-coordinate.
  371      * @param width  the width of the box.
  372      * @param height the height of the box.
  373      * @throws IndexOutOfBoundsException if <tt>column&lt;0 || column+width&gt;columns() || row&lt;0 ||
  374      *                                   row+height&gt;rows()</tt>
  375      */
  376     public BitMatrix part(int column, int row, int width, int height) {
  377       if (column < 0 || column + width > columns || row < 0 || row + height > rows) {
  378         throw new IndexOutOfBoundsException(
  379             "column:" + column + ", row:" + row + " ,width:" + width + ", height:" + height);
  380       }
  381       if (width <= 0 || height <= 0) {
  382         return new BitMatrix(0, 0);
  383       }
  384   
  385       BitMatrix subMatrix = new BitMatrix(width, height);
  386       subMatrix.replaceBoxWith(0, 0, width, height, this, column, row);
  387       return subMatrix;
  388     }
  389   
  390     /**
  391      * Sets the bit at the specified coordinate to the state specified by <tt>value</tt>.
  392      *
  393      * @param column the index of the column-coordinate.
  394      * @param row    the index of the row-coordinate.
  395      * @param value  the value of the bit to be copied into the specified coordinate.
  396      * @throws IndexOutOfBoundsException if <tt>column&lt;0 || column&gt;=columns() || row&lt;0 || row&gt;=rows()</tt>
  397      */
  398     public void put(int column, int row, boolean value) {
  399       if (column < 0 || column >= columns || row < 0 || row >= rows) {
  400         throw new IndexOutOfBoundsException("column:" + column + ", row:" + row);
  401       }
  402       QuickBitVector.put(bits, row * columns + column, value);
  403     }
  404   
  405     /**
  406      * Sets the bit at the specified coordinate to the state specified by <tt>value</tt>; <b>WARNING:</b> Does not check
  407      * preconditions.
  408      *
  409      * <p>Provided with invalid parameters this method may return invalid values without throwing any exception. <b>You
  410      * should only use this method when you are absolutely sure that the coordinate is within bounds.</b> Precondition
  411      * (unchecked): <tt>column&gt;=0 && column&lt;columns() && row&gt;=0 && row&lt;rows()</tt>.
  412      *
  413      * @param column the index of the column-coordinate.
  414      * @param row    the index of the row-coordinate.
  415      * @param value  the value of the bit to be copied into the specified coordinate.
  416      */
  417     public void putQuick(int column, int row, boolean value) {
  418       QuickBitVector.put(bits, row * columns + column, value);
  419     }
  420   
  421     /**
  422      * Replaces a box of the receiver with the contents of another matrix's box. The source box ranges from
  423      * <tt>[sourceColumn,sourceRow]</tt> to <tt>[sourceColumn+width-1,sourceRow+height-1]</tt>, all inclusive. The
  424      * destination box ranges from <tt>[column,row]</tt> to <tt>[column+width-1,row+height-1]</tt>, all inclusive. Does
  425      * nothing if <tt>width &lt;= 0 || height &lt;= 0</tt>. If <tt>source==this</tt> and the source and destination box
  426      * intersect in an ambiguous way, then replaces as if using an intermediate auxiliary copy of the receiver.
  427      *
  428      * @param column       the index of the column-coordinate.
  429      * @param row          the index of the row-coordinate.
  430      * @param width        the width of the box.
  431      * @param height       the height of the box.
  432      * @param source       the source matrix to copy from(may be identical to the receiver).
  433      * @param sourceColumn the index of the source column-coordinate.
  434      * @param sourceRow    the index of the source row-coordinate.
  435      * @throws IndexOutOfBoundsException if <tt>column&lt;0 || column+width&gt;columns() || row&lt;0 ||
  436      *                                   row+height&gt;rows()</tt>
  437      * @throws IndexOutOfBoundsException if <tt>sourceColumn&lt;0 || sourceColumn+width&gt;source.columns() ||
  438      *                                   sourceRow&lt;0 || sourceRow+height&gt;source.rows()</tt>
  439      */
  440     public void replaceBoxWith(int column, int row, int width, int height, BitMatrix source, int sourceColumn,
  441                                int sourceRow) {
  442       this.containsBox(column, row, width, height);
  443       source.containsBox(sourceColumn, sourceRow, width, height);
  444       if (width <= 0 || height <= 0) {
  445         return;
  446       }
  447   
  448       if (source == this) {
  449         Rectangle destRect = new Rectangle(column, row, width, height);
  450         Rectangle sourceRect = new Rectangle(sourceColumn, sourceRow, width, height);
  451         if (destRect.intersects(sourceRect)) { // dangerous intersection
  452           source = source.copy();
  453         }
  454       }
  455   
  456       BitVector sourceVector = source.toBitVector();
  457       BitVector destVector = this.toBitVector();
  458       int sourceColumns = source.columns();
  459       for (; --height >= 0; row++, sourceRow++) {
  460         int offset = row * columns + column;
  461         int sourceOffset = sourceRow * sourceColumns + sourceColumn;
  462         destVector.replaceFromToWith(offset, offset + width - 1, sourceVector, sourceOffset);
  463       }
  464     }
  465   
  466     /**
  467      * Sets the bits in the given box to the state specified by <tt>value</tt>. The box ranges from <tt>[column,row]</tt>
  468      * to <tt>[column+width-1,row+height-1]</tt>, all inclusive. (Does nothing if <tt>width &lt;= 0 || height &lt;=
  469      * 0</tt>).
  470      *
  471      * @param column the index of the column-coordinate.
  472      * @param row    the index of the row-coordinate.
  473      * @param width  the width of the box.
  474      * @param height the height of the box.
  475      * @param value  the value of the bit to be copied into the bits of the specified box.
  476      * @throws IndexOutOfBoundsException if <tt>column&lt;0 || column+width&gt;columns() || row&lt;0 ||
  477      *                                   row+height&gt;rows()</tt>
  478      */
  479     public void replaceBoxWith(int column, int row, int width, int height, boolean value) {
  480       containsBox(column, row, width, height);
  481       if (width <= 0 || height <= 0) {
  482         return;
  483       }
  484   
  485       BitVector destVector = this.toBitVector();
  486       for (; --height >= 0; row++) {
  487         int offset = row * columns + column;
  488         destVector.replaceFromToWith(offset, offset + width - 1, value);
  489       }
  490     }
  491   
  492     /** Returns the number of rows of the receiver. */
  493     public int rows() {
  494       return rows;
  495     }
  496   
  497     /** Returns the size of the receiver which is <tt>columns()*rows()</tt>. */
  498     public int size() {
  499       return columns * rows;
  500     }
  501   
  502     /**
  503      * Converts the receiver to a bitvector. In many cases this method only makes sense on one-dimensional matrices.
  504      * <b>WARNING:</b> The returned bitvector and the receiver share the <b>same</b> backing bits. Modifying either of
  505      * them will affect the other. If this behaviour is not what you want, you should first use <tt>copy()</tt> to make
  506      * sure both objects use separate internal storage.
  507      */
  508     public BitVector toBitVector() {
  509       return new BitVector(bits, size());
  510     }
  511   
  512     /** Returns a (very crude) string representation of the receiver. */
  513     public String toString() {
  514       return toBitVector().toString();
  515     }
  516   
  517     /**
  518      * Performs a logical <b>XOR</b> of the receiver with another bit matrix. The receiver is modified so that a bit in it
  519      * has the value <code>true</code> if and only if one of the following statements holds: <ul> <li>The bit initially
  520      * has the value <code>true</code>, and the corresponding bit in the argument has the value <code>false</code>.
  521      * <li>The bit initially has the value <code>false</code>, and the corresponding bit in the argument has the value
  522      * <code>true</code>. </ul>
  523      *
  524      * @param other a bit matrix.
  525      * @throws IllegalArgumentException if <tt>columns() != other.columns() || rows() != other.rows()</tt>.
  526      */
  527     public void xor(BitMatrix other) {
  528       checkDimensionCompatibility(other);
  529       toBitVector().xor(other.toBitVector());
  530     }
  531   }

Save This Page
Home » mahout-collections-1.0-src » org.apache.mahout.math.bitvector » [javadoc | source]