/*
 * [DeDup.java]
 *
 * Summary: Demonstrate five ways to dedup a collection.
 *
 * Copyright: (c) 2016-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.8+
 *
 * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.1 2016-08-05 add preserveOrder, more accurating timing.
 */
package com.mindprod.example;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;

import static java.lang.System.*;

/**
 * Demonstrate five ways to dedup a collection.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.1 2016-08-05 add preserveOrder, more accurating timing.
 * @since 2016-05-02
 */
public class DeDup
    {
    private static ArrayList<String> a = new ArrayList<>( 10 );

    /**
     * sort and scan the array bottom to top
     *
     * @param a
     */
    private static void bottomToTop( final ArrayList<String> a )
        {
        final int n = a.size();
        if ( n < 2 )
            {
            return;
            }
        Collections.sort( a );
        String prev = a.get( n - 1 );
        // loop down starting with second to last elt
        for ( int i = n - 2; i >= 0; i-- )
            {
            final String here = a.get( i );
            if ( here.equals( prev ) )
                {
                a.remove( i );
                }
            else
                {
                prev = here;
                }
            }
        }

    /**
     * sort and copy to a new Collection
     *
     * @param a
     */
    private static void copy( final ArrayList<String> a )
        {
        final int n = a.size();
        if ( n < 2 )
            {
            return;
            }
        Collections.sort( a );
        ArrayList<String> b = new ArrayList<>( n );
        String prev = null;
        for ( String here : a )
            {
            if ( !here.equals( prev ) )
                {
                b.add( here );
                prev = here;
                }
            }
        a.clear();
        a.addAll( b );
        }

    /**
     * display contents of the ArrayList
     */
    private static void display()
        {
        a.forEach( out::println );
        out.println( "----------------" );
        }

    /**
     * load the ArrayList up with some sample data
     */
    private static void init()
        {
        a.clear();
        a.add( "giraffe" );
        a.add( "giraffe" );
        a.add( "giraffe" );
        a.add( "lion" );
        a.add( "tiger" );
        a.add( "penguin" );
        a.add( "elephant" );
        a.add( "PENGUIN" );
        a.add( "tiger" );
        a.add( "ibex" );
        }

    /**
     * Remove duplicates if match equalIgnoreCase
     * Preserve original order.
     *
     * @param a
     */
    private static void preserveOrder( final ArrayList<String> a )
        {
        // outer loop works down
        outer:
        for ( int i = a.size() - 1; i >= 1; i-- )
            // inner partial loop works up
            {
            for ( int j = 0; j < i; j++ )
                {
                if ( a.get( j ).equalsIgnoreCase( a.get( i ) ) )
                    {
                    a.remove( i );
                    continue outer;
                    }
                }
            }
        // deduped result is left in a
        }

    /**
     * use a HashSet
     *
     * @param a
     */
    private static void withHashSet( final ArrayList<String> a )
        {
        HashSet<String> h = new HashSet<>( a.size() * 2 );
        for ( String elt : a )
            {
            h.add( elt );
            }
        a.clear();
        a.addAll( h );
        // result is unsorted
        }

    /**
     * sort and use an Iterator
     *
     * @param a
     */
    private static void withIterator( final ArrayList<String> a )
        {
        if ( a.size() < 2 )
            {
            return;
            }
        Collections.sort( a );
        String prev = null;
        // iterator range over all elements
        for ( Iterator<String> iter = a.iterator(); iter.hasNext(); )
            {
            String here = iter.next();
            if ( here.equals( prev ) )
                {
                iter.remove();
                }
            else
                {
                prev = here;
                }
            }
        }

    /**
     * sort and scan the array top to bottom , fails with IndexOutOfBoundsException
     *
     * @param a
     */
    private static void wontWork( final ArrayList<String> a )
        {
        try
            {
            final int n = a.size();
            if ( n < 2 )
                {
                return;
                }
            Collections.sort( a );
            String prev = a.get( 0 );
            // loop up starting with second  elt
            // but if removes some elts, goes too far.
            // Further, if removes elt, skips checking the next
            for ( int i = 1; i < n; i++ )
                {
                final String here = a.get( i );
                if ( here.equals( prev ) )
                    {
                    a.remove( i );
                    }
                else
                    {
                    prev = here;
                    }
                }
            }
        catch ( IndexOutOfBoundsException e )
            {
            out.println( "fail" );
            }
        }

    public static void main( String[] args )
        {
        init();
        out.println( "UNPROCESSED" );
        display();
        // f a s t e s t   m e t h o d s   a t   t h e   t o p
        long start;
        // bottom to top 21,722
        out.println( "BOTTOM TO TOP" );
        start = System.nanoTime();
        bottomToTop( a );
        out.println( System.nanoTime() - start + " ns" );
        display();
        // iterator 29,479
        out.println( "ITERATOR" );
        init();
        start = System.nanoTime();
        withIterator( a );
        out.println( System.nanoTime() - start + " ns" );
        display();
        // PreserveOrder 60,511
        out.println( "PRESERVE_ORDER" );
        init();
        start = System.nanoTime();
        preserveOrder( a );
        out.println( System.nanoTime() - start + " ns" );
        // HashSet 274,627
        out.println( "HASHSET" );
        init();
        start = System.nanoTime();
        withHashSet( a );
        out.println( System.nanoTime() - start + " ns" );
        display();
        // copy 371,755
        out.println( "COPY TO A NEW COLLECTION" );
        init();
        start = System.nanoTime();
        copy( a );
        out.println( System.nanoTime() - start + " ns" );
        display();
        // won't work
        out.println( "TOP TO BOTTOM : WON'T WORK" );
        init();
        start = System.nanoTime();
        wontWork( a );
        out.println( System.nanoTime() - start + " ns" );
        display();
        }
    }