source.dussan.org Git - sonarqube.git/blob

   1 /*
   2  * SonarQube, open source software quality management tool.
   3  * Copyright (C) 2008-2014 SonarSource
   4  * mailto:contact AT sonarsource DOT com
   5  *
   6  * SonarQube is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 3 of the License, or (at your option) any later version.
  10  *
  11  * SonarQube is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  */
  20 package org.sonar.plugins.core.issue.tracking;
  21
  22 /**
  23  * Wraps a {@link Sequence} to assign hash codes to elements.
  24  */
  25 public class RollingHashSequence<S extends Sequence> implements Sequence {
  26
  27   final S base;
  28   final int[] hashes;
  29
  30   public static <S extends Sequence> RollingHashSequence<S> wrap(S base, SequenceComparator<S> cmp, int lines) {
  31     int size = base.length();
  32     int[] hashes = new int[size];
  33
  34     RollingHashCalculator hashCalulator = new RollingHashCalculator(lines * 2 + 1);
  35     for (int i = 0; i <= Math.min(size - 1, lines); i++) {
  36       hashCalulator.add(cmp.hash(base, i));
  37     }
  38     for (int i = 0; i < size; i++) {
  39       hashes[i] = hashCalulator.getHash();
  40       if (i - lines >= 0) {
  41         hashCalulator.remove(cmp.hash(base, i - lines));
  42       }
  43       if (i + lines + 1 < size) {
  44         hashCalulator.add(cmp.hash(base, i + lines + 1));
  45       } else {
  46         hashCalulator.add(0);
  47       }
  48     }
  49
  50     return new RollingHashSequence<S>(base, hashes);
  51   }
  52
  53   private RollingHashSequence(S base, int[] hashes) {
  54     this.base = base;
  55     this.hashes = hashes;
  56   }
  57
  58   @Override
  59   public int length() {
  60     return base.length();
  61   }
  62
  63   private static class RollingHashCalculator {
  64
  65     private static final int PRIME_BASE = 31;
  66
  67     private final int power;
  68     private int hash;
  69
  70     public RollingHashCalculator(int size) {
  71       int pow = 1;
  72       for (int i = 0; i < size - 1; i++) {
  73         pow = pow * PRIME_BASE;
  74       }
  75       this.power = pow;
  76     }
  77
  78     public void add(int value) {
  79       hash = hash * PRIME_BASE + value;
  80     }
  81
  82     public void remove(int value) {
  83       hash = hash - power * value;
  84     }
  85
  86     public int getHash() {
  87       return hash;
  88     }
  89
  90   }
  91
  92 }