content: /*
   * 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.
   */
  package org.apache.arrow.algorithm.search;
  
  import static org.apache.arrow.vector.complex.BaseRepeatedValueVector.OFFSET_WIDTH;
  import static org.junit.jupiter.api.Assertions.assertEquals;
  
  import java.nio.charset.StandardCharsets;
  import org.apache.arrow.algorithm.sort.DefaultVectorComparators;
  import org.apache.arrow.algorithm.sort.VectorValueComparator;
  import org.apache.arrow.memory.BufferAllocator;
  import org.apache.arrow.memory.RootAllocator;
  import org.apache.arrow.vector.BaseVariableWidthVector;
  import org.apache.arrow.vector.BitVectorHelper;
  import org.apache.arrow.vector.IntVector;
  import org.apache.arrow.vector.VarCharVector;
  import org.apache.arrow.vector.complex.ListVector;
  import org.apache.arrow.vector.types.Types;
  import org.apache.arrow.vector.types.pojo.FieldType;
  import org.junit.jupiter.api.AfterEach;
  import org.junit.jupiter.api.BeforeEach;
  import org.junit.jupiter.api.Test;
  
  /** Test cases for {@link org.apache.arrow.algorithm.search.VectorSearcher}. */
  public class TestVectorSearcher {
  
    private final int VECTOR_LENGTH = 100;
  
    private BufferAllocator allocator;
  
    @BeforeEach
    public void prepare() {
      allocator = new RootAllocator(1024 * 1024);
    }
  
    @AfterEach
    public void shutdown() {
      allocator.close();
    }
  
    @Test
    public void testBinarySearchInt() {
      try (IntVector rawVector = new IntVector("", allocator);
          IntVector negVector = new IntVector("", allocator)) {
        rawVector.allocateNew(VECTOR_LENGTH);
        rawVector.setValueCount(VECTOR_LENGTH);
        negVector.allocateNew(1);
        negVector.setValueCount(1);
  
        // prepare data in sorted order
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          if (i == 0) {
            rawVector.setNull(i);
          } else {
            rawVector.set(i, i);
          }
        }
        negVector.set(0, -333);
  
        // do search
        VectorValueComparator<IntVector> comparator =
            DefaultVectorComparators.createDefaultComparator(rawVector);
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          int result = VectorSearcher.binarySearch(rawVector, comparator, rawVector, i);
          assertEquals(i, result);
        }
  
        // negative case
        assertEquals(-1, VectorSearcher.binarySearch(rawVector, comparator, negVector, 0));
      }
    }
  
    @Test
    public void testLinearSearchInt() {
      try (IntVector rawVector = new IntVector("", allocator);
          IntVector negVector = new IntVector("", allocator)) {
        rawVector.allocateNew(VECTOR_LENGTH);
        rawVector.setValueCount(VECTOR_LENGTH);
        negVector.allocateNew(1);
        negVector.setValueCount(1);
  
        // prepare data in sorted order
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          if (i == 0) {
            rawVector.setNull(i);
          } else {
            rawVector.set(i, i);
          }
        }
        negVector.set(0, -333);
  
        // do search
        VectorValueComparator<IntVector> comparator =
            DefaultVectorComparators.createDefaultComparator(rawVector);
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          int result = VectorSearcher.linearSearch(rawVector, comparator, rawVector, i);
          assertEquals(i, result);
        }
  
        // negative case
        assertEquals(-1, VectorSearcher.linearSearch(rawVector, comparator, negVector, 0));
      }
    }
  
    @Test
    public void testBinarySearchVarChar() {
      try (VarCharVector rawVector = new VarCharVector("", allocator);
          VarCharVector negVector = new VarCharVector("", allocator)) {
        rawVector.allocateNew(VECTOR_LENGTH * 16, VECTOR_LENGTH);
        rawVector.setValueCount(VECTOR_LENGTH);
        negVector.allocateNew(VECTOR_LENGTH, 1);
        negVector.setValueCount(1);
  
        byte[] content = new byte[2];
  
        // prepare data in sorted order
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          if (i == 0) {
            rawVector.setNull(i);
          } else {
            int q = i / 10;
            int r = i % 10;
  
            content[0] = (byte) ('a' + q);
            content[1] = (byte) r;
            rawVector.set(i, content);
          }
        }
        negVector.set(0, "abcd".getBytes(StandardCharsets.UTF_8));
  
        // do search
        VectorValueComparator<BaseVariableWidthVector> comparator =
            DefaultVectorComparators.createDefaultComparator(rawVector);
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          int result = VectorSearcher.binarySearch(rawVector, comparator, rawVector, i);
          assertEquals(i, result);
        }
  
        // negative case
        assertEquals(-1, VectorSearcher.binarySearch(rawVector, comparator, negVector, 0));
      }
    }
  
    @Test
    public void testLinearSearchVarChar() {
      try (VarCharVector rawVector = new VarCharVector("", allocator);
          VarCharVector negVector = new VarCharVector("", allocator)) {
        rawVector.allocateNew(VECTOR_LENGTH * 16, VECTOR_LENGTH);
        rawVector.setValueCount(VECTOR_LENGTH);
        negVector.allocateNew(VECTOR_LENGTH, 1);
        negVector.setValueCount(1);
  
        byte[] content = new byte[2];
  
        // prepare data in sorted order
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          if (i == 0) {
            rawVector.setNull(i);
          } else {
            int q = i / 10;
            int r = i % 10;
  
            content[0] = (byte) ('a' + q);
            content[1] = (byte) r;
            rawVector.set(i, content);
          }
        }
        negVector.set(0, "abcd".getBytes(StandardCharsets.UTF_8));
  
        // do search
        VectorValueComparator<BaseVariableWidthVector> comparator =
            DefaultVectorComparators.createDefaultComparator(rawVector);
        for (int i = 0; i < VECTOR_LENGTH; i++) {
          int result = VectorSearcher.linearSearch(rawVector, comparator, rawVector, i);
          assertEquals(i, result);
        }
  
        // negative case
        assertEquals(-1, VectorSearcher.linearSearch(rawVector, comparator, negVector, 0));
      }
    }
  
    private ListVector createListVector() {
      final int innerCount = 100;
      final int outerCount = 10;
      final int listLength = innerCount / outerCount;
  
      ListVector listVector = ListVector.empty("list vector", allocator);
  
      Types.MinorType type = Types.MinorType.INT;
      listVector.addOrGetVector(FieldType.nullable(type.getType()));
  
      listVector.allocateNew();
  
      IntVector dataVector = (IntVector) listVector.getDataVector();
  
      for (int i = 0; i < innerCount; i++) {
        dataVector.set(i, i);
      }
      dataVector.setValueCount(innerCount);
  
      for (int i = 0; i < outerCount; i++) {
        BitVectorHelper.setBit(listVector.getValidityBuffer(), i);
        listVector.getOffsetBuffer().setInt(i * OFFSET_WIDTH, i * listLength);
        listVector.getOffsetBuffer().setInt((i + 1) * OFFSET_WIDTH, (i + 1) * listLength);
      }
      listVector.setLastSet(outerCount - 1);
      listVector.setValueCount(outerCount);
  
      return listVector;
    }
  
    private ListVector createNegativeListVector() {
      final int innerCount = 100;
      final int outerCount = 10;
      final int listLength = innerCount / outerCount;
  
      ListVector listVector = ListVector.empty("list vector", allocator);
  
      Types.MinorType type = Types.MinorType.INT;
      listVector.addOrGetVector(FieldType.nullable(type.getType()));
  
      listVector.allocateNew();
  
      IntVector dataVector = (IntVector) listVector.getDataVector();
  
      for (int i = 0; i < innerCount; i++) {
        dataVector.set(i, i + 1000);
      }
      dataVector.setValueCount(innerCount);
  
      for (int i = 0; i < outerCount; i++) {
        BitVectorHelper.setBit(listVector.getValidityBuffer(), i);
        listVector.getOffsetBuffer().setInt(i * OFFSET_WIDTH, i * listLength);
        listVector.getOffsetBuffer().setInt((i + 1) * OFFSET_WIDTH, (i + 1) * listLength);
      }
      listVector.setValueCount(outerCount);
  
      return listVector;
    }
  
    @Test
    public void testBinarySearchList() {
      try (ListVector rawVector = createListVector();
          ListVector negVector = createNegativeListVector()) {
  
        // do search
        VectorValueComparator<ListVector> comparator =
            DefaultVectorComparators.createDefaultComparator(rawVector);
        for (int i = 0; i < rawVector.getValueCount(); i++) {
          int result = VectorSearcher.binarySearch(rawVector, comparator, rawVector, i);
          assertEquals(i, result);
        }
  
        // negative case
        for (int i = 0; i < rawVector.getValueCount(); i++) {
          int result = VectorSearcher.binarySearch(rawVector, comparator, negVector, i);
          assertEquals(-1, result);
        }
      }
    }
  
    @Test
    public void testLinearSearchList() {
      try (ListVector rawVector = createListVector();
          ListVector negVector = createNegativeListVector()) {
  
        // do search
        VectorValueComparator<ListVector> comparator =
            DefaultVectorComparators.createDefaultComparator(rawVector);
        for (int i = 0; i < rawVector.getValueCount(); i++) {
          int result = VectorSearcher.linearSearch(rawVector, comparator, rawVector, i);
          assertEquals(i, result);
        }
  
        // negative case
        for (int i = 0; i < rawVector.getValueCount(); i++) {
          int result = VectorSearcher.linearSearch(rawVector, comparator, negVector, i);
          assertEquals(-1, result);
        }
      }
    }
  }
  