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

网格计算

开发平台:

Java

  1. /**
  2.  * Licensed to the Apache Software Foundation (ASF) under one
  3.  * or more contributor license agreements.  See the NOTICE file
  4.  * distributed with this work for additional information
  5.  * regarding copyright ownership.  The ASF licenses this file
  6.  * to you under the Apache License, Version 2.0 (the
  7.  * "License"); you may not use this file except in compliance
  8.  * with the License.  You may obtain a copy of the License at
  9.  *
  10.  *     http://www.apache.org/licenses/LICENSE-2.0
  11.  *
  12.  * Unless required by applicable law or agreed to in writing, software
  13.  * distributed under the License is distributed on an "AS IS" BASIS,
  14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15.  * See the License for the specific language governing permissions and
  16.  * limitations under the License.
  17.  */
  18. package org.apache.hadoop.mapred.lib;
  19. import java.util.List;
  20. import org.apache.hadoop.io.WritableComparator;
  21. import org.apache.hadoop.io.WritableUtils;
  22. import org.apache.hadoop.mapred.JobConf;
  23. import org.apache.hadoop.mapred.JobConfigurable;
  24. import org.apache.hadoop.mapred.lib.KeyFieldHelper.KeyDescription;
  25. import org.apache.hadoop.io.Text;
  26. /**
  27.  * This comparator implementation provides a subset of the features provided
  28.  * by the Unix/GNU Sort. In particular, the supported features are:
  29.  * -n, (Sort numerically)
  30.  * -r, (Reverse the result of comparison)
  31.  * -k pos1[,pos2], where pos is of the form f[.c][opts], where f is the number
  32.  *  of the field to use, and c is the number of the first character from the
  33.  *  beginning of the field. Fields and character posns are numbered starting
  34.  *  with 1; a character position of zero in pos2 indicates the field's last
  35.  *  character. If '.c' is omitted from pos1, it defaults to 1 (the beginning
  36.  *  of the field); if omitted from pos2, it defaults to 0 (the end of the
  37.  *  field). opts are ordering options (any of 'nr' as described above). 
  38.  * We assume that the fields in the key are separated by 
  39.  * map.output.key.field.separator.
  40.  */
  41. public class KeyFieldBasedComparator<K, V> extends WritableComparator 
  42. implements JobConfigurable {
  43.   private KeyFieldHelper keyFieldHelper = new KeyFieldHelper();
  44.   private static final byte NEGATIVE = (byte)'-';
  45.   private static final byte ZERO = (byte)'0';
  46.   private static final byte DECIMAL = (byte)'.';
  47.   
  48.   public void configure(JobConf job) {
  49.     String option = job.getKeyFieldComparatorOption();
  50.     String keyFieldSeparator = job.get("map.output.key.field.separator","t");
  51.     keyFieldHelper.setKeyFieldSeparator(keyFieldSeparator);
  52.     keyFieldHelper.parseOption(option);
  53.   }
  54.   
  55.   public KeyFieldBasedComparator() {
  56.     super(Text.class);
  57.   }
  58.     
  59.   public int compare(byte[] b1, int s1, int l1,
  60.       byte[] b2, int s2, int l2) {
  61.     int n1 = WritableUtils.decodeVIntSize(b1[s1]);
  62.     int n2 = WritableUtils.decodeVIntSize(b2[s2]);
  63.     List <KeyDescription> allKeySpecs = keyFieldHelper.keySpecs();
  64.     if (allKeySpecs.size() == 0) {
  65.       return compareBytes(b1, s1+n1, l1-n1, b2, s2+n2, l2-n2);
  66.     }
  67.     int []lengthIndicesFirst = keyFieldHelper.getWordLengths(b1, s1+n1, s1+l1);
  68.     int []lengthIndicesSecond = keyFieldHelper.getWordLengths(b2, s2+n2, s2+l2);
  69.     for (KeyDescription keySpec : allKeySpecs) {
  70.       int startCharFirst = keyFieldHelper.getStartOffset(b1, s1+n1, s1+l1, lengthIndicesFirst,
  71.           keySpec);
  72.       int endCharFirst = keyFieldHelper.getEndOffset(b1, s1+n1, s1+l1, lengthIndicesFirst,
  73.           keySpec);
  74.       int startCharSecond = keyFieldHelper.getStartOffset(b2, s2+n2, s2+l2, lengthIndicesSecond,
  75.           keySpec);
  76.       int endCharSecond = keyFieldHelper.getEndOffset(b2, s2+n2, s2+l2, lengthIndicesSecond,
  77.           keySpec);
  78.       int result;
  79.       if ((result = compareByteSequence(b1, startCharFirst, endCharFirst, b2, 
  80.           startCharSecond, endCharSecond, keySpec)) != 0) {
  81.         return result;
  82.       }
  83.     }
  84.     return 0;
  85.   }
  86.   
  87.   private int compareByteSequence(byte[] first, int start1, int end1, 
  88.       byte[] second, int start2, int end2, KeyDescription key) {
  89.     if (start1 == -1) {
  90.       if (key.reverse) {
  91.         return 1;
  92.       }
  93.       return -1;
  94.     }
  95.     if (start2 == -1) {
  96.       if (key.reverse) {
  97.         return -1; 
  98.       }
  99.       return 1;
  100.     }
  101.     int compareResult = 0;
  102.     if (!key.numeric) {
  103.       compareResult = compareBytes(first, start1, end1, second, start2, end2);
  104.     }
  105.     if (key.numeric) {
  106.       compareResult = numericalCompare (first, start1, end1, second, start2, end2);
  107.     }
  108.     if (key.reverse) {
  109.       return -compareResult;
  110.     }
  111.     return compareResult;
  112.   }
  113.   
  114.   private int numericalCompare (byte[] a, int start1, int end1, 
  115.       byte[] b, int start2, int end2) {
  116.     int i = start1;
  117.     int j = start2;
  118.     int mul = 1;
  119.     byte first_a = a[i];
  120.     byte first_b = b[j];
  121.     if (first_a == NEGATIVE) {
  122.       if (first_b != NEGATIVE) {
  123.         //check for cases like -0.0 and 0.0 (they should be declared equal)
  124.         return oneNegativeCompare(a,start1+1,end1,b,start2,end2);
  125.       }
  126.       i++;
  127.     }
  128.     if (first_b == NEGATIVE) {
  129.       if (first_a != NEGATIVE) {
  130.         //check for cases like 0.0 and -0.0 (they should be declared equal)
  131.         return -oneNegativeCompare(b,start2+1,end2,a,start1,end1);
  132.       }
  133.       j++;
  134.     }
  135.     if (first_b == NEGATIVE && first_a == NEGATIVE) {
  136.       mul = -1;
  137.     }
  138.     //skip over ZEROs
  139.     while (i <= end1) {
  140.       if (a[i] != ZERO) {
  141.         break;
  142.       }
  143.       i++;
  144.     }
  145.     while (j <= end2) {
  146.       if (b[j] != ZERO) {
  147.         break;
  148.       }
  149.       j++;
  150.     }
  151.     
  152.     //skip over equal characters and stopping at the first nondigit char
  153.     //The nondigit character could be '.'
  154.     while (i <= end1 && j <= end2) {
  155.       if (!isdigit(a[i]) || a[i] != b[j]) {
  156.         break;
  157.       }
  158.       i++; j++;
  159.     }
  160.     if (i <= end1) {
  161.       first_a = a[i];
  162.     }
  163.     if (j <= end2) {
  164.       first_b = b[j];
  165.     }
  166.     //store the result of the difference. This could be final result if the
  167.     //number of digits in the mantissa is the same in both the numbers 
  168.     int firstResult = first_a - first_b;
  169.     
  170.     //check whether we hit a decimal in the earlier scan
  171.     if ((first_a == DECIMAL && (!isdigit(first_b) || j > end2)) ||
  172.             (first_b == DECIMAL && (!isdigit(first_a) || i > end1))) {
  173.       return ((mul < 0) ? -decimalCompare(a,i,end1,b,j,end2) : 
  174.         decimalCompare(a,i,end1,b,j,end2));
  175.     }
  176.     //check the number of digits in the mantissa of the numbers
  177.     int numRemainDigits_a = 0;
  178.     int numRemainDigits_b = 0;
  179.     while (i <= end1) {
  180.       //if we encounter a non-digit treat the corresponding number as being 
  181.       //smaller      
  182.       if (isdigit(a[i++])) {
  183.         numRemainDigits_a++;
  184.       } else break;
  185.     }
  186.     while (j <= end2) {
  187.       //if we encounter a non-digit treat the corresponding number as being 
  188.       //smaller
  189.       if (isdigit(b[j++])) {
  190.         numRemainDigits_b++;
  191.       } else break;
  192.     }
  193.     int ret = numRemainDigits_a - numRemainDigits_b;
  194.     if (ret == 0) { 
  195.       return ((mul < 0) ? -firstResult : firstResult);
  196.     } else {
  197.       return ((mul < 0) ? -ret : ret);
  198.     }
  199.   }
  200.   private boolean isdigit(byte b) {
  201.     if ('0' <= b && b <= '9') {
  202.       return true;
  203.     }
  204.     return false;
  205.   }
  206.   private int decimalCompare(byte[] a, int i, int end1, 
  207.                              byte[] b, int j, int end2) {
  208.     if (i > end1) {
  209.       //if a[] has nothing remaining
  210.       return -decimalCompare1(b, ++j, end2);
  211.     }
  212.     if (j > end2) {
  213.       //if b[] has nothing remaining
  214.       return decimalCompare1(a, ++i, end1);
  215.     }
  216.     if (a[i] == DECIMAL && b[j] == DECIMAL) {
  217.       while (i <= end1 && j <= end2) {
  218.         if (a[i] != b[j]) {
  219.           if (isdigit(a[i]) && isdigit(b[j])) {
  220.             return a[i] - b[j];
  221.           }
  222.           if (isdigit(a[i])) {
  223.             return 1;
  224.           }
  225.           if (isdigit(b[j])) {
  226.             return -1;
  227.           }
  228.           return 0;
  229.         }
  230.         i++; j++;
  231.       }
  232.       if (i > end1 && j > end2) {
  233.         return 0;
  234.       }
  235.         
  236.       if (i > end1) {
  237.         //check whether there is a non-ZERO digit after potentially
  238.         //a number of ZEROs (e.g., a=.4444, b=.444400004)
  239.         return -decimalCompare1(b, j, end2);
  240.       }
  241.       if (j > end2) {
  242.         //check whether there is a non-ZERO digit after potentially
  243.         //a number of ZEROs (e.g., b=.4444, a=.444400004)
  244.         return decimalCompare1(a, i, end1);
  245.       }
  246.     }
  247.     else if (a[i] == DECIMAL) {
  248.       return decimalCompare1(a, ++i, end1);
  249.     }
  250.     else if (b[j] == DECIMAL) {
  251.       return -decimalCompare1(b, ++j, end2);
  252.     }
  253.     return 0;
  254.   }
  255.   
  256.   private int decimalCompare1(byte[] a, int i, int end) {
  257.     while (i <= end) {
  258.       if (a[i] == ZERO) {
  259.         i++;
  260.         continue;
  261.       }
  262.       if (isdigit(a[i])) {
  263.         return 1;
  264.       } else {
  265.         return 0;
  266.       }
  267.     }
  268.     return 0;
  269.   }
  270.   
  271.   private int oneNegativeCompare(byte[] a, int start1, int end1, 
  272.       byte[] b, int start2, int end2) {
  273.     //here a[] is negative and b[] is positive
  274.     //We have to ascertain whether the number contains any digits.
  275.     //If it does, then it is a smaller number for sure. If not,
  276.     //then we need to scan b[] to find out whether b[] has a digit
  277.     //If b[] does contain a digit, then b[] is certainly
  278.     //greater. If not, that is, both a[] and b[] don't contain
  279.     //digits then they should be considered equal.
  280.     if (!isZero(a, start1, end1)) {
  281.       return -1;
  282.     }
  283.     //reached here - this means that a[] is a ZERO
  284.     if (!isZero(b, start2, end2)) {
  285.       return -1;
  286.     }
  287.     //reached here - both numbers are basically ZEROs and hence
  288.     //they should compare equal
  289.     return 0;
  290.   }
  291.   
  292.   private boolean isZero(byte a[], int start, int end) {
  293.     //check for zeros in the significand part as well as the decimal part
  294.     //note that we treat the non-digit characters as ZERO
  295.     int i = start;
  296.     //we check the significand for being a ZERO
  297.     while (i <= end) {
  298.       if (a[i] != ZERO) {
  299.         if (a[i] != DECIMAL && isdigit(a[i])) {
  300.           return false;
  301.         }
  302.         break;
  303.       }
  304.       i++;
  305.     }
  306.     if (i != (end+1) && a[i++] == DECIMAL) {
  307.       //we check the decimal part for being a ZERO
  308.       while (i <= end) {
  309.         if (a[i] != ZERO) {
  310.           if (isdigit(a[i])) {
  311.             return false;
  312.           }
  313.           break;
  314.         }
  315.         i++;
  316.       }
  317.     }
  318.     return true;
  319.   }
  320. }