package org.apache.lucene.util.packed;

/**
 * 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 org.apache.lucene.store.*;
import org.apache.lucene.util.LuceneTestCase;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.io.IOException;

public class TestPackedInts extends LuceneTestCase {
  public void testBitsRequired() throws Exception {
    assertEquals(61, PackedInts.bitsRequired((long)Math.pow(2, 61)-1));
    assertEquals(61, PackedInts.bitsRequired(0x1FFFFFFFFFFFFFFFL));
    assertEquals(62, PackedInts.bitsRequired(0x3FFFFFFFFFFFFFFFL));
    assertEquals(63, PackedInts.bitsRequired(0x7FFFFFFFFFFFFFFFL));
  }

  public void testMaxValues() throws Exception {
    assertEquals("1 bit -> max == 1",
            1, PackedInts.maxValue(1));
    assertEquals("2 bit -> max == 3",
            3, PackedInts.maxValue(2));
    assertEquals("8 bit -> max == 255",
            255, PackedInts.maxValue(8));
    assertEquals("63 bit -> max == Long.MAX_VALUE",
            Long.MAX_VALUE, PackedInts.maxValue(63));
    assertEquals("64 bit -> max == Long.MAX_VALUE (same as for 63 bit)", 
            Long.MAX_VALUE, PackedInts.maxValue(64));
  }

  public void testPackedInts() throws IOException {
    int num = atLeast(5);
    for (int iter = 0; iter < num; iter++) {
      long ceil = 2;
      for(int nbits=1;nbits<63;nbits++) {
        final int valueCount = 100+random.nextInt(500);
        final Directory d = newDirectory();

        IndexOutput out = d.createOutput("out.bin");
        PackedInts.Writer w = PackedInts.getWriter(
                out, valueCount, nbits);

        final long[] values = new long[valueCount];
        for(int i=0;i<valueCount;i++) {
          long v = random.nextLong() % ceil;
          if (v < 0) {
            v = -v;
          }
          values[i] = v;
          w.add(values[i]);
        }
        w.finish();
        final long fp = out.getFilePointer();
        out.close();
        {// test reader
          IndexInput in = d.openInput("out.bin");
          PackedInts.Reader r = PackedInts.getReader(in);
          assertEquals(fp, in.getFilePointer());
          for(int i=0;i<valueCount;i++) {
            assertEquals("index=" + i + " ceil=" + ceil + " valueCount="
                    + valueCount + " nbits=" + nbits + " for "
                    + r.getClass().getSimpleName(), values[i], r.get(i));
          }
          in.close();
        }
        ceil *= 2;
        d.close();
      }
    }
  }
  
  public void testControlledEquality() {
    final int VALUE_COUNT = 255;
    final int BITS_PER_VALUE = 8;

    List<PackedInts.Mutable> packedInts =
            createPackedInts(VALUE_COUNT, BITS_PER_VALUE);
    for (PackedInts.Mutable packedInt: packedInts) {
      for (int i = 0 ; i < packedInt.size() ; i++) {
        packedInt.set(i, i+1);
      }
    }
    assertListEquality(packedInts);
  }

  public void testRandomEquality() {
    final int[] VALUE_COUNTS = new int[]{0, 1, 5, 8, 100, 500};
    final int MIN_BITS_PER_VALUE = 1;
    final int MAX_BITS_PER_VALUE = 64;

    for (int valueCount: VALUE_COUNTS) {
      for (int bitsPerValue = MIN_BITS_PER_VALUE ;
           bitsPerValue <= MAX_BITS_PER_VALUE ;
           bitsPerValue++) {
        assertRandomEquality(valueCount, bitsPerValue, random.nextLong());
      }
    }
  }

  private void assertRandomEquality(int valueCount, int bitsPerValue, long randomSeed) {
    List<PackedInts.Mutable> packedInts = createPackedInts(valueCount, bitsPerValue);
    for (PackedInts.Mutable packedInt: packedInts) {
      try {
        fill(packedInt, (long)(Math.pow(2, bitsPerValue)-1), randomSeed);
      } catch (Exception e) {
        e.printStackTrace(System.err);
        fail(String.format(
                "Exception while filling %s: valueCount=%d, bitsPerValue=%s",
                packedInt.getClass().getSimpleName(),
                valueCount, bitsPerValue));
      }
    }
    assertListEquality(packedInts);
  }

  private List<PackedInts.Mutable> createPackedInts(
          int valueCount, int bitsPerValue) {
    List<PackedInts.Mutable> packedInts = new ArrayList<PackedInts.Mutable>();
    if (bitsPerValue <= 8) {
      packedInts.add(new Direct8(valueCount));
    }
    if (bitsPerValue <= 16) {
      packedInts.add(new Direct16(valueCount));
    }
    if (bitsPerValue <= 31) {
      packedInts.add(new Packed32(valueCount, bitsPerValue));
    }
    if (bitsPerValue <= 32) {
      packedInts.add(new Direct32(valueCount));
    }
    if (bitsPerValue <= 63) {
      packedInts.add(new Packed64(valueCount, bitsPerValue));
    }
    packedInts.add(new Direct64(valueCount));
    return packedInts;
  }

  private void fill(PackedInts.Mutable packedInt, long maxValue, long randomSeed) {
    Random rnd2 = new Random(randomSeed);
    maxValue++;
    for (int i = 0 ; i < packedInt.size() ; i++) {
      long value = Math.abs(rnd2.nextLong() % maxValue);
      packedInt.set(i, value);
      assertEquals(String.format(
              "The set/get of the value at index %d should match for %s",
              i, packedInt.getClass().getSimpleName()),
              value, packedInt.get(i));
    }
  }

  private void assertListEquality(
          List<? extends PackedInts.Reader> packedInts) {
    assertListEquality("", packedInts);
  }

  private void assertListEquality(
            String message, List<? extends PackedInts.Reader> packedInts) {
    if (packedInts.size() == 0) {
      return;
    }
    PackedInts.Reader base = packedInts.get(0);
    int valueCount = base.size();
    for (PackedInts.Reader packedInt: packedInts) {
      assertEquals(message + ". The number of values should be the same ",
              valueCount, packedInt.size());
    }
    for (int i = 0 ; i < valueCount ; i++) {
      for (int j = 1 ; j < packedInts.size() ; j++) {
        assertEquals(String.format(
                "%s. The value at index %d should be the same for %s and %s",
                message, i, base.getClass().getSimpleName(),
                packedInts.get(j).getClass().getSimpleName()),
                base.get(i), packedInts.get(j).get(i));
      }
    }
  }

  public void testSingleValue() throws Exception {
    Directory dir = newDirectory();
    IndexOutput out = dir.createOutput("out");
    PackedInts.Writer w = PackedInts.getWriter(out, 1, 8);
    w.add(17);
    w.finish();
    final long end = out.getFilePointer();
    out.close();

    IndexInput in = dir.openInput("out");
    PackedInts.getReader(in);
    assertEquals(end, in.getFilePointer());
    in.close();

    dir.close();
  }

  public void testSecondaryBlockChange() throws IOException {
    PackedInts.Mutable mutable = new Packed64(26, 5);
    mutable.set(24, 31);
    assertEquals("The value #24 should be correct", 31, mutable.get(24));
    mutable.set(4, 16);
    assertEquals("The value #24 should remain unchanged", 31, mutable.get(24));
  }

  /*
    Check if the structures properly handle the case where
    index * bitsPerValue > Integer.MAX_VALUE
    
    NOTE: this test allocates 256 MB
   */
  public void testIntOverflow() {
    int INDEX = (int)Math.pow(2, 30)+1;
    int BITS = 2;

    Packed32 p32 = new Packed32(INDEX, BITS);
    p32.set(INDEX-1, 1);
    assertEquals("The value at position " + (INDEX-1)
        + " should be correct for Packed32", 1, p32.get(INDEX-1));
    p32 = null; // To free the 256MB used

    Packed64 p64 = new Packed64(INDEX, BITS);
    p64.set(INDEX-1, 1);
    assertEquals("The value at position " + (INDEX-1)
        + " should be correct for Packed64", 1, p64.get(INDEX-1));
  }
}
