<commit_before>package it.unimi.dsi.fastutil.objects;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

import org.junit.Test;

@SuppressWarnings("boxing")
public class ObjectArraysTest {
	
	public static Integer[] identity( final int n ) {
		final Integer[] perm = new Integer[ n ];
		for( int i = perm.length; i-- != 0; ) perm[ i ] = i;
		return perm;
	}

	@Test
	public void testMergeSort() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 }, b = a.clone(), sorted = a.clone();
		Arrays.sort( sorted );
		ObjectArrays.mergeSort( b );
		assertArrayEquals( sorted, b );
		ObjectArrays.mergeSort( b );
		assertArrayEquals( sorted, b );
		
		final Integer[] d = a.clone();
		ObjectArrays.mergeSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );

		ObjectArrays.mergeSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );
	}


	@Test
	public void testMergeSortSmallSupport() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 };
		for( int to = 1; to < a.length; to++ )
			for( int from = 0; from <= to; from++ ) {
				final Integer[] support = new Integer[ to ];
				System.arraycopy( a, 0, support, 0, to );
				ObjectArrays.mergeSort( a, from, to, support );
				if ( from < to ) for( int i = to - 1; i-- != from; ) assertTrue( a[ i ] <= a[ i + 1 ] );
			}
	}
	
	@Test
	public void testQuickSort() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 }, b = a.clone(), sorted = a.clone();
		Arrays.sort( sorted );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );

		final Integer[] d = a.clone();
		ObjectArrays.quickSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );
		ObjectArrays.quickSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );
	}
	
	@Test
	public void testParallelQuickSort() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 }, b = a.clone(), sorted = a.clone();
		Arrays.sort( sorted );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );

		final Integer[] d = a.clone();
		ObjectArrays.parallelQuickSort( d, 0, d.length );
		assertArrayEquals( sorted, d );
	}
	
	@Test
	public void testQuickSort1() {
		Integer[] t = { 2, 1, 0, 4 };
		ObjectArrays.quickSort( t );
		for( int i = t.length - 1; i-- != 0; ) assertTrue( t[ i ] <= t[ i + 1 ] );
		
		t = new Integer[] { 2, -1, 0, -4 };
		ObjectArrays.quickSort( t );
		for( int i = t.length - 1; i-- != 0; ) assertTrue( t[ i ] <= t[ i + 1 ] );
		
		t = ObjectArrays.shuffle( identity( 100 ), new Random( 0 ) );
		ObjectArrays.quickSort( t );
		for( int i = t.length - 1; i-- != 0; ) assertTrue( t[ i ] <= t[ i + 1 ] );<commit_msg>Add test case for large parallel quicksort with compare.<commit_after>package it.unimi.dsi.fastutil.objects;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

import org.junit.Test;

@SuppressWarnings("boxing")
public class ObjectArraysTest {
	
	public static Integer[] identity( final int n ) {
		final Integer[] perm = new Integer[ n ];
		for( int i = perm.length; i-- != 0; ) perm[ i ] = i;
		return perm;
	}

	@Test
	public void testMergeSort() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 }, b = a.clone(), sorted = a.clone();
		Arrays.sort( sorted );
		ObjectArrays.mergeSort( b );
		assertArrayEquals( sorted, b );
		ObjectArrays.mergeSort( b );
		assertArrayEquals( sorted, b );
		
		final Integer[] d = a.clone();
		ObjectArrays.mergeSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );

		ObjectArrays.mergeSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );
	}


	@Test
	public void testMergeSortSmallSupport() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 };
		for( int to = 1; to < a.length; to++ )
			for( int from = 0; from <= to; from++ ) {
				final Integer[] support = new Integer[ to ];
				System.arraycopy( a, 0, support, 0, to );
				ObjectArrays.mergeSort( a, from, to, support );
				if ( from < to ) for( int i = to - 1; i-- != from; ) assertTrue( a[ i ] <= a[ i + 1 ] );
			}
	}
	
	@Test
	public void testQuickSort() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 }, b = a.clone(), sorted = a.clone();
		Arrays.sort( sorted );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );

		final Integer[] d = a.clone();
		ObjectArrays.quickSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );
		ObjectArrays.quickSort( d, new Comparator<Integer>() {
			@Override
			public int compare( Integer k1, Integer k2 ) {
				return k1.compareTo( k2 );
			}
		});
		assertArrayEquals( sorted, d );
	}
	
	@Test
	public void testParallelQuickSort() {
		Integer[] a = { 2, 1, 5, 2, 1, 0, 9, 1, 4, 2, 4, 6, 8, 9, 10, 12, 1, 7 }, b = a.clone(), sorted = a.clone();
		Arrays.sort( sorted );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );
		Arrays.sort( b );
		assertArrayEquals( sorted, b );

		final Integer[] d = a.clone();
		ObjectArrays.parallelQuickSort( d, 0, d.length );
		assertArrayEquals( sorted, d );
	}
	
	@Test
	public void testLargeParallelQuickSortWithComparator() {
	  Object [] a = new Object[8192+1]; // PARALLEL_QUICKSORT_NO_FORK
	  for (int i = 0; i < a.length; i++) {
	    a[i] = new Object();
	  }
	  ObjectArrays.parallelQuickSort(a, new Comparator<Object>(){
      @Override
      public int compare(Object o1, Object o2) {
        return Integer.compare(System.identityHashCode(o1), System.identityHashCode(o2));
      }});
	}
	
    @Test
    public void testSmallParallelQuickSortWithComparator() {
      Object [] a = new Object[8];
      for (int i = 0; i < a.length; i++) {
        a[i] = new Object();
      }
      ObjectArrays.parallelQuickSort(a, new Comparator<Object>(){
      @Override
      public int compare(Object o1, Object o2) {
        return Integer.compare(System.identityHashCode(o1), System.identityHashCode(o2));
      }});
    }
    
	@Test
	public void testQuickSort1() {
		Integer[] t = { 2, 1, 0, 4 };
		ObjectArrays.quickSort( t );
		for( int i = t.length - 1; i-- != 0; ) assertTrue( t[ i ] <= t[ i + 1 ] );
		
		t = new Integer[] { 2, -1, 0, -4 };
		ObjectArrays.quickSort( t );
		for( int i = t.length - 1; i-- != 0; ) assertTrue( t[ i ] <= t[ i + 1 ] );
		
		t = ObjectArrays.shuffle( identity( 100 ), new Random( 0 ) );
		ObjectArrays.quickSort( t );
		for( int i = t.length - 1; i-- != 0; ) assertTrue( t[ i ] <= t[ i + 1 ] );
{'fraction_non_alphanumeric': 0.1647704982346018, 'fraction_numerical': 0.03504642343402641, 'mean_word_length': 3.010487676979549, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2978163', 'n_tokens_mistral': 3175, 'n_tokens_neox': 2770, 'n_words': 867}