Filter.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:7k
源码类别:

网格计算

开发平台:

Java

  1. /**
  2.  *
  3.  * Copyright (c) 2005, European Commission project OneLab under contract 034819
  4.  * (http://www.one-lab.org)
  5.  * 
  6.  * All rights reserved.
  7.  * Redistribution and use in source and binary forms, with or 
  8.  * without modification, are permitted provided that the following 
  9.  * conditions are met:
  10.  *  - Redistributions of source code must retain the above copyright 
  11.  *    notice, this list of conditions and the following disclaimer.
  12.  *  - Redistributions in binary form must reproduce the above copyright 
  13.  *    notice, this list of conditions and the following disclaimer in 
  14.  *    the documentation and/or other materials provided with the distribution.
  15.  *  - Neither the name of the University Catholique de Louvain - UCL
  16.  *    nor the names of its contributors may be used to endorse or 
  17.  *    promote products derived from this software without specific prior 
  18.  *    written permission.
  19.  *    
  20.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
  21.  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
  22.  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
  23.  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
  24.  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
  25.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
  26.  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
  27.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
  28.  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
  30.  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
  31.  * POSSIBILITY OF SUCH DAMAGE.
  32.  */
  33. /**
  34.  * Licensed to the Apache Software Foundation (ASF) under one
  35.  * or more contributor license agreements.  See the NOTICE file
  36.  * distributed with this work for additional information
  37.  * regarding copyright ownership.  The ASF licenses this file
  38.  * to you under the Apache License, Version 2.0 (the
  39.  * "License"); you may not use this file except in compliance
  40.  * with the License.  You may obtain a copy of the License at
  41.  *
  42.  *     http://www.apache.org/licenses/LICENSE-2.0
  43.  *
  44.  * Unless required by applicable law or agreed to in writing, software
  45.  * distributed under the License is distributed on an "AS IS" BASIS,
  46.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  47.  * See the License for the specific language governing permissions and
  48.  * limitations under the License.
  49.  */
  50. package org.apache.hadoop.util.bloom;
  51. import java.io.DataInput;
  52. import java.io.DataOutput;
  53. import java.io.IOException;
  54. import java.util.Collection;
  55. import java.util.List;
  56. import org.apache.hadoop.io.Writable;
  57. import org.apache.hadoop.util.hash.Hash;
  58. /**
  59.  * Defines the general behavior of a filter.
  60.  * <p>
  61.  * A filter is a data structure which aims at offering a lossy summary of a set <code>A</code>.  The
  62.  * key idea is to map entries of <code>A</code> (also called <i>keys</i>) into several positions 
  63.  * in a vector through the use of several hash functions.
  64.  * <p>
  65.  * Typically, a filter will be implemented as a Bloom filter (or a Bloom filter extension).
  66.  * <p>
  67.  * It must be extended in order to define the real behavior.
  68.  * 
  69.  * @see Key The general behavior of a key
  70.  * @see HashFunction A hash function
  71.  */
  72. public abstract class Filter implements Writable {
  73.   private static final int VERSION = -1; // negative to accommodate for old format 
  74.   /** The vector size of <i>this</i> filter. */
  75.   protected int vectorSize;
  76.   /** The hash function used to map a key to several positions in the vector. */
  77.   protected HashFunction hash;
  78.   /** The number of hash function to consider. */
  79.   protected int nbHash;
  80.   
  81.   /** Type of hashing function to use. */
  82.   protected int hashType;
  83.   protected Filter() {}
  84.   
  85.   /** 
  86.    * Constructor.
  87.    * @param vectorSize The vector size of <i>this</i> filter.
  88.    * @param nbHash The number of hash functions to consider.
  89.    * @param hashType type of the hashing function (see {@link Hash}).
  90.    */
  91.   protected Filter(int vectorSize, int nbHash, int hashType) {
  92.     this.vectorSize = vectorSize;
  93.     this.nbHash = nbHash;
  94.     this.hashType = hashType;
  95.     this.hash = new HashFunction(this.vectorSize, this.nbHash, this.hashType);
  96.   }
  97.   /**
  98.    * Adds a key to <i>this</i> filter.
  99.    * @param key The key to add.
  100.    */
  101.   public abstract void add(Key key);
  102.   /**
  103.    * Determines wether a specified key belongs to <i>this</i> filter.
  104.    * @param key The key to test.
  105.    * @return boolean True if the specified key belongs to <i>this</i> filter.
  106.    *       False otherwise.
  107.    */
  108.   public abstract boolean membershipTest(Key key);
  109.   /**
  110.    * Peforms a logical AND between <i>this</i> filter and a specified filter.
  111.    * <p>
  112.    * <b>Invariant</b>: The result is assigned to <i>this</i> filter.
  113.    * @param filter The filter to AND with.
  114.    */
  115.   public abstract void and(Filter filter);
  116.   /**
  117.    * Peforms a logical OR between <i>this</i> filter and a specified filter.
  118.    * <p>
  119.    * <b>Invariant</b>: The result is assigned to <i>this</i> filter.
  120.    * @param filter The filter to OR with.
  121.    */
  122.   public abstract void or(Filter filter);
  123.   /**
  124.    * Peforms a logical XOR between <i>this</i> filter and a specified filter.
  125.    * <p>
  126.    * <b>Invariant</b>: The result is assigned to <i>this</i> filter.
  127.    * @param filter The filter to XOR with.
  128.    */
  129.   public abstract void xor(Filter filter);
  130.   /**
  131.    * Performs a logical NOT on <i>this</i> filter.
  132.    * <p>
  133.    * The result is assigned to <i>this</i> filter.
  134.    */
  135.   public abstract void not();
  136.   /**
  137.    * Adds a list of keys to <i>this</i> filter.
  138.    * @param keys The list of keys.
  139.    */
  140.   public void add(List<Key> keys){
  141.     if(keys == null) {
  142.       throw new IllegalArgumentException("ArrayList<Key> may not be null");
  143.     }
  144.     for(Key key: keys) {
  145.       add(key);
  146.     }
  147.   }//end add()
  148.   /**
  149.    * Adds a collection of keys to <i>this</i> filter.
  150.    * @param keys The collection of keys.
  151.    */
  152.   public void add(Collection<Key> keys){
  153.     if(keys == null) {
  154.       throw new IllegalArgumentException("Collection<Key> may not be null");
  155.     }
  156.     for(Key key: keys) {
  157.       add(key);
  158.     }
  159.   }//end add()
  160.   /**
  161.    * Adds an array of keys to <i>this</i> filter.
  162.    * @param keys The array of keys.
  163.    */
  164.   public void add(Key[] keys){
  165.     if(keys == null) {
  166.       throw new IllegalArgumentException("Key[] may not be null");
  167.     }
  168.     for(int i = 0; i < keys.length; i++) {
  169.       add(keys[i]);
  170.     }
  171.   }//end add()
  172.   
  173.   // Writable interface
  174.   
  175.   public void write(DataOutput out) throws IOException {
  176.     out.writeInt(VERSION);
  177.     out.writeInt(this.nbHash);
  178.     out.writeByte(this.hashType);
  179.     out.writeInt(this.vectorSize);
  180.   }
  181.   public void readFields(DataInput in) throws IOException {
  182.     int ver = in.readInt();
  183.     if (ver > 0) { // old unversioned format
  184.       this.nbHash = ver;
  185.       this.hashType = Hash.JENKINS_HASH;
  186.     } else if (ver == VERSION) {
  187.       this.nbHash = in.readInt();
  188.       this.hashType = in.readByte();
  189.     } else {
  190.       throw new IOException("Unsupported version: " + ver);
  191.     }
  192.     this.vectorSize = in.readInt();
  193.     this.hash = new HashFunction(this.vectorSize, this.nbHash, this.hashType);
  194.   }
  195. }//end class