package org.apache.lucene.util.automaton.fst;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.io.IOException;

// Used to dedup states (lookup already-frozen states)
final class NodeHash<T> {

  private int[] table;
  private int count;
  private int mask;
  private final FST<T> fst;
  private final FST.Arc<T> scratchArc = new FST.Arc<T>();

  public static int conf;

  public NodeHash(FST<T> fst) {
    table = new int[16];
    mask = 15;
    this.fst = fst;
  }

  private boolean nodesEqual(Builder.UnCompiledNode<T> node, int address) throws IOException {
    fst.readFirstArc(address, scratchArc);
    if (scratchArc.bytesPerArc != 0 && node.numArcs != scratchArc.numArcs) {
      return false;
    }
    for(int arcUpto=0;arcUpto<node.numArcs;arcUpto++) {
      final Builder.Arc arc = node.arcs[arcUpto];
      if (arc.label != scratchArc.label ||
          !arc.output.equals(scratchArc.output) ||
          ((Builder.CompiledNode) arc.target).address != scratchArc.target ||
          !arc.nextFinalOutput.equals(scratchArc.nextFinalOutput) ||
          arc.isFinal != scratchArc.isFinal()) {
        return false;
      }

      if (scratchArc.isLast()) {
        if (arcUpto == node.numArcs-1) {
          return true;
        } else {
          return false;
        }
      }
      fst.readNextArc(scratchArc);
    }

    return false;
  }

  // hash code for an unfrozen node.  This must be identical
  // to the un-frozen case (below)!!
  private int hash(Builder.UnCompiledNode<T> node) {
    final int PRIME = 31;
    //System.out.println("hash unfrozen");
    int h = 0;
    // TODO: maybe if number of arcs is high we can safely subsample?
    for(int arcIdx=0;arcIdx<node.numArcs;arcIdx++) {
      final Builder.Arc<T> arc = node.arcs[arcIdx];
      //System.out.println("  label=" + arc.label + " target=" + ((Builder.CompiledNode) arc.target).address + " h=" + h + " output=" + fst.outputs.outputToString(arc.output) + " isFinal?=" + arc.isFinal);
      h = PRIME * h + arc.label;
      h = PRIME * h + ((Builder.CompiledNode) arc.target).address;
      h = PRIME * h + arc.output.hashCode();
      h = PRIME * h + arc.nextFinalOutput.hashCode();
      if (arc.isFinal) {
        h += 17;
      }
    }
    //System.out.println("  ret " + (h&Integer.MAX_VALUE));
    return h & Integer.MAX_VALUE;
  }

  // hash code for a frozen node
  private int hash(int node) throws IOException {
    final int PRIME = 31;
    //System.out.println("hash frozen");
    int h = 0;
    fst.readFirstArc(node, scratchArc);
    while(true) {
      //System.out.println("  label=" + scratchArc.label + " target=" + scratchArc.target + " h=" + h + " output=" + fst.outputs.outputToString(scratchArc.output) + " next?=" + scratchArc.flag(4) + " final?=" + scratchArc.isFinal());
      h = PRIME * h + scratchArc.label;
      h = PRIME * h + scratchArc.target;
      h = PRIME * h + scratchArc.output.hashCode();
      h = PRIME * h + scratchArc.nextFinalOutput.hashCode();
      if (scratchArc.isFinal()) {
        h += 17;
      }
      if (scratchArc.isLast()) {
        break;
      }
      fst.readNextArc(scratchArc);
    }
    //System.out.println("  ret " + (h&Integer.MAX_VALUE));
    return h & Integer.MAX_VALUE;
  }

  public int add(Builder.UnCompiledNode<T> node) throws IOException {
    // System.out.println("hash: add count=" + count + " vs " + table.length);
    final int h = hash(node);
    int h2 = h;
    int c = 1;
    while(true) {
      final int pos = h2 & mask;
      final int v = table[pos];
      if (v == 0) {
        // freeze & add
        final int address = fst.addNode(node);
        //System.out.println("  now freeze addr=" + address);
        assert hash(address) == h : "frozenHash=" + hash(address) + " vs h=" + h;
        count++;
        table[pos] = address;
        if (table.length < 2*count) {
          rehash();
        }
        return address;
      } else if (nodesEqual(node, v)) {
        // same node is already here
        return v;
      }

      // quadratic probe
      h2 = h+(c + c*c)/2;
      c++;
      conf++;
    }
  }

  // called only by rehash
  private void addNew(int address) throws IOException {
    final int h = hash(address);
    int h2 = h;
    int c = 1;
    while(true) {
      final int pos = h2 & mask;
      if (table[pos] == 0) {
        table[pos] = address;
        break;
      }

      // quadratic probe
      h2 = h + (c + c*c)/2;
      c++;
      conf++;
    }
  }

  private void rehash() throws IOException {
    final int[] oldTable = table;
    table = new int[2*table.length];
    mask = table.length-1;
    for(int idx=0;idx<oldTable.length;idx++) {
      final int address = oldTable[idx];
      if (address != 0) {
        addNew(address);
      }
    }
  }
}

@@ -1110,35 +1110,8 @@
 );%0A%0A
-  public static int conf;%0A%0A
   pu
@@ -4147,38 +4147,46 @@
 (node);%0A    int 
-h2
+pos
  = h
+ & mask
 ;%0A    int c = 1;
@@ -4175,33 +4175,33 @@
 sk;%0A    int c = 
-1
+0
 ;%0A    while(true
@@ -4208,41 +4208,8 @@
 ) %7B%0A
-      final int pos = h2 & mask;%0A
     
@@ -4749,51 +4749,34 @@
     
-h2 = h+(c + c*c)/2;%0A      c++;%0A      conf++
+pos = (pos + (++c)) & mask
 ;%0A  
@@ -4867,35 +4867,31 @@
 ption %7B%0A    
-final 
 int 
-h
+pos
  = hash(addr
@@ -4898,24 +4898,15 @@
 ess)
-;%0A    int h2 = h
+ & mask
 ;%0A  
@@ -4915,17 +4915,17 @@
 int c = 
-1
+0
 ;%0A    wh
@@ -4940,41 +4940,8 @@
 ) %7B%0A
-      final int pos = h2 & mask;%0A
     
@@ -5054,53 +5054,34 @@
     
-h2 = h + (c + c*c)/2;%0A      c++;%0A      conf++
+pos = (pos + (++c)) & mask
 ;%0A  

use more efficient quadratic hash impl; remove dead code