13 Replies - 718 Views - Last Post: 10 May 2020 - 07:42 AM Rate Topic: -----

#1 Splashsky   User is offline

  • D.I.C Addict
  • member icon

Reputation: 9
  • View blog
  • Posts: 562
  • Joined: 25-August 13

Issue with Iterating over ArrayList

Posted 08 May 2020 - 07:46 AM

I hate Java. I'm having a problem iterating over an ArrayList - the goal of this function is to take all the zeroes in a given Integer Arraylist and move them to the end while preserving the order of all other integers. My solution was to iterate over the array, count the number of zeroes and remove them as I iterate, then add the zeroes back before returning the ArrayList.

The problem I'm running into is that given the ArrayList [0, 0, 4, 0, 0, 0], my function returns [0, 4, 0, 0, 0, 0], where I expect 4 to be the first value in the list.

Here's the function;
public static ArrayList<Integer> zerosBack(ArrayList<Integer> arr)
{
    int zeroes = 0;
    
    for(int i = 0; i < arr.size(); i++) {
        if(arr.get(i) == 0) {
            arr.remove(i);
            zeroes = zeroes + 1;
        }
    }
    
    if(zeroes > 0) {
        for(int i = 0; i < zeroes; i++) {
            arr.add(0);
        }
    }
    
    return arr;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Issue with Iterating over ArrayList

#2 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 15686
  • View blog
  • Posts: 62,833
  • Joined: 12-June 08

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:07 AM

Ya may want to go the less tricksy route and break it up to two for loops. One to classify/count, the other to add in zeros.

Ex:
	ArrayList<Integer> foo = new ArrayList<Integer>();
    	ArrayList<Integer> bar = new ArrayList<Integer>();
    	int zeroCount = 0;
    	
    	foo.add(0);
    	foo.add(0);
    	foo.add(4);
    	foo.add(0);
    	foo.add(0);
    	foo.add(0);
    	
    	//1.  count the zeros, or add to the second arraylist.
    	for(int i =0; i < foo.size(); i++)
    	{
    		if (foo.get(i) == 0)
    			zeroCount +=1;
    		else
    			bar.add(foo.get(i));
    	}
    	
    	//2.  add in any zeros counted.
    	for(int i = 0; i < zeroCount;i++)
    	{
    		bar.add(0);
    	}
    	
    	//3. print out for profit.
       	for(int i =0; i < foo.size(); i++)
    	{
       		System.out.print(foo.get(i));
    	}
       	System.out.println("\n-----------");
       	for(int i =0; i < bar.size(); i++)
    	{
       		System.out.print(bar.get(i));
    	}


0 0 4 0 0 0 
-----------
4 0 0 0 0 0 

Was This Post Helpful? 1
  • +
  • -

#3 g00se   User is offline

  • D.I.C Lover
  • member icon

Reputation: 3687
  • View blog
  • Posts: 16,914
  • Joined: 20-September 08

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:17 AM

Why mutate a List you're iterating? Better to create a new one and return that
If you're determined to use the same List, then iterate it backwards

This post has been edited by g00se: 08 May 2020 - 08:19 AM
Reason for edit:: Clarification

Was This Post Helpful? 1
  • +
  • -

#4 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 819
  • View blog
  • Posts: 6,305
  • Joined: 25-December 13

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:30 AM

Are you sure the code is doing what you expect? The output may be misleading.
When I changed this line to add -1 vs 0:
            arr.add(-1);


The output was:
in [0, 0, 4, 0, 0, 0]
out [0, 4, 0, -1, -1, -1]

See g00se's post

Quote

If you're determined to use the same List, then iterate it backwards

This post has been edited by NormR: 08 May 2020 - 08:34 AM

Was This Post Helpful? 0
  • +
  • -

#5 Splashsky   User is offline

  • D.I.C Addict
  • member icon

Reputation: 9
  • View blog
  • Posts: 562
  • Joined: 25-August 13

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:33 AM

Modi's suggestion is fantastic and worked. Thanks to you guys, too; I'm a PHP developer and even touching Java boils my blood. I'm not sure why it seemed to ignore the 0 at the start of the array, and as in NormR's example it doesn't appear to recognize 0 at all. I've noticed it acting weird when I attempt to println the index as well, so maybe it's a Java thing I don't understand.

Anywho, thanks guys. :)
Was This Post Helpful? 0
  • +
  • -

#6 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 819
  • View blog
  • Posts: 6,305
  • Joined: 25-December 13

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:38 AM

In the for loop, the value of arr.size() changes at each remove. i continues to increment and passes it, stopping the loop.
Was This Post Helpful? 3
  • +
  • -

#7 Splashsky   User is offline

  • D.I.C Addict
  • member icon

Reputation: 9
  • View blog
  • Posts: 562
  • Joined: 25-August 13

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:39 AM

Ah, that's right, isn't it? I hadn't even thought of that. Makes sense as to why I shouldn't mutate the list I'm working on, then. I made such a blunder QQ
Was This Post Helpful? 0
  • +
  • -

#8 andrewsw   User is online

  • a lovely bit of linq
  • member icon

Reputation: 6891
  • View blog
  • Posts: 28,511
  • Joined: 12-December 12

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:41 AM

Yes, removing while iterating forwards is the issue with your original code, you are skipping items.

It would be in interesting challenge to do this as a pseudo bubble-sort process. Let the zeroes bubble to the end.
Was This Post Helpful? 1
  • +
  • -

#9 NormR   User is offline

  • D.I.C Lover
  • member icon

Reputation: 819
  • View blog
  • Posts: 6,305
  • Joined: 25-December 13

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:41 AM

Start from the end as g00se suggested may be a solution.
Was This Post Helpful? 0
  • +
  • -

#10 Splashsky   User is offline

  • D.I.C Addict
  • member icon

Reputation: 9
  • View blog
  • Posts: 562
  • Joined: 25-August 13

Re: Issue with Iterating over ArrayList

Posted 08 May 2020 - 08:43 AM

Since iterating backwards doesn't make a lot of intuitive sense to myself, I'll use a second list, as modi did. It's more obvious imo
Was This Post Helpful? 0
  • +
  • -

#11 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2409
  • View blog
  • Posts: 5,047
  • Joined: 11-December 07

Re: Issue with Iterating over ArrayList

Posted 09 May 2020 - 04:41 PM

I've been having some fun with this. It looks like you have a solution so I'll post what I've been doing.

There are several solutions that I want to play with so here is an interface:

import java.util.*;

public interface MoveZeros {
	List<Integer> moveZerosToEnd(List<Integer> list);
}


And I want to make sure my attempts are correct so here are some tests:

import static org.junit.Assert.*;

import java.util.*;
import java.util.stream.*;

import org.junit.*;

public class TestMoveZeros {
	@Test
	public void move_zeros_acomplished_by_copy_to_new_list() {
		testMoveZerosAlgorithm(new CopyToNewList());
	}
	
	@Test
	public void move_zeros_acomplished_by_copy_to_same_list() {
		testMoveZerosAlgorithm(new CopyToSameList());
	}
	
	@Test
	public void move_zeros_acomplished_by_iterator_remove() {
		testMoveZerosAlgorithm(new IteratorRemove());
	}
	
	@Test
	public void move_zeros_acomplished_by_remove_method() {
		testMoveZerosAlgorithm(new RemoveMethod());
	}
	
	@Test
	public void move_zeros_acomplished_by_comparator() {
		testMoveZerosAlgorithm(new ComparatorShuffle());
	}
	
	@Test
	public void move_zeros_acomplished_by_copy_with_two_indexes() {
		testMoveZerosAlgorithm(new CopyWithTwoIndexes());
	}
	
	@Test
	public void move_zeros_acomplished_by_list_concatenation() {
		testMoveZerosAlgorithm(new ListConcatenation());
	}
	
	private void testMoveZerosAlgorithm(MoveZeros algorithm) {
		test(algorithm, convertsThis(), toThis());
		test(algorithm, convertsThis(1), toThis(1));
		test(algorithm, convertsThis(1, 3, 5), toThis(1, 3, 5));
		test(algorithm, convertsThis(0), toThis(0));
		test(algorithm, convertsThis(1, 0), toThis(1, 0));
		test(algorithm, convertsThis(1, 0), toThis(1, 0));
		test(algorithm, convertsThis(1, 3, 5, 0, 0, 0), toThis(1, 3, 5, 0, 0, 0));
		test(algorithm, convertsThis(0, 1), toThis(1, 0));
		test(algorithm, convertsThis(0, 1), toThis(1, 0));
		test(algorithm, convertsThis(0, 0, 1), toThis(1, 0, 0));
	}

	private void test(MoveZeros algorithm, List<Integer> original, List<Integer> expected) {
		List<Integer> actual = algorithm.moveZerosToEnd(original);
		String message = String.format("Expected: %s but was: %s", expected, actual);
		assertEquals(message, expected, actual);
	}
	
	private List<Integer> convertsThis(int... arr) {
		return Arrays.stream(arr).boxed().collect(Collectors.toList());
	}
	
	private List<Integer> toThis(int... arr) {
		return Arrays.stream(arr).boxed().collect(Collectors.toList());
	}
}


This one is closest to what I would do professionally. It just copies the non-zeros to a list and then appends the right number of zeros.

import java.util.*;

public class CopyToNewList implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		List<Integer> result = new ArrayList<>();
		for (Integer i : list)
			if (i != 0)
				result.add(i);
		while (result.size() < list.size())
			result.add(0);
		return result;
	}

}


This one is conceptually the same algorithm as above, even though the code looks a little different. The main difference is that the source and destination arrays are the same. I prefer not to modify the input variables if I can help it.

import java.util.*;

public class CopyToSameList implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		int size = list.size();
		for (int i = 0, j = 0; i < size; i++, j++) {
			while (j < size && list.get(j) == 0) {
				j++;
			}
			int value = (j >= size) ? 0 : list.get(j);
			list.set(i, value);
		}
		return list;
	}
}


Iterators have gone out of fashion in Java but they are still there and they have a remove method. This allows you to remove while iterating which is what you originally wanted to do:

import java.util.*;

public class IteratorRemove implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		int initialSize = list.size();
		Iterator<Integer> it = list.iterator();
		while (it.hasNext())
			if (it.next() == 0) 
				it.remove();
		while (list.size() < initialSize)
			list.add(0);
		return list;
	}
}


Lists also have a remove method. I'm afraid my code here is a little bit obscure. Can you work out why using the remove method like this would be slow for large lists?

import java.util.*;

public class RemoveMethod implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		int i = 0;
		while (list.remove((Integer)0)) i++;
		while (i-- > 0) list.add(0);
		return list;
	}
}


Lists have a sort method, that allows you to sort based on some supplied criteria. The criteria I applied here says that all numbers have equal priority, except zeros that come after. It works because the sort method is a stable sort, meaning objects with equal priority maintain their order.

import java.util.*;

public class ComparatorShuffle implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		list.sort((x, y) -> 
			  (x == 0 && y != 0) ? 1 
			: (x != 0 && y == 0) ? -1 
			: 0);
		return list;
	}
}


This one has two indexes for the output array so that it can "insert" zeros and non-zeros in the correct place in one pass.

mport java.util.*;

public class CopyWithTwoIndexes implements MoveZeros {

	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		List<Integer> result = new ArrayList<>(list);
		int a = 0;
		int b = list.size() - 1;
		for (Integer i : list)
			result.set((i == 0) ? b-- : a++, i);
		return result;
	}

}



This one partitions the original list into two lists: one for zeros and the other for all the rest. Then it uses list concatenation to join them together.

import java.util.*;

public class ListConcatenation implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		List<Integer> zeros = new ArrayList<>();
		List<Integer> allTheRest = new ArrayList<>();
		for (Integer i : list)
			(i == 0 ? zeros : allTheRest).add(i);
		allTheRest.addAll(zeros);
		return allTheRest;
	}

}


Since my code seems to be getting sillier, I decided to stop here.
Was This Post Helpful? 0
  • +
  • -

#12 g00se   User is offline

  • D.I.C Lover
  • member icon

Reputation: 3687
  • View blog
  • Posts: 16,914
  • Joined: 20-September 08

Re: Issue with Iterating over ArrayList

Posted 10 May 2020 - 02:47 AM

Timings would be nice too ;)
newList = new ArrayList<Integer>(originalListSize);

immediately springs to mind
Was This Post Helpful? 0
  • +
  • -

#13 ndc85430   User is online

  • I think you'll find it's "Dr"
  • member icon

Reputation: 1025
  • View blog
  • Posts: 3,942
  • Joined: 13-June 14

Re: Issue with Iterating over ArrayList

Posted 10 May 2020 - 05:42 AM

Couldn't it just be done neatly with a filter to keep the non-zero values and then tacking on the right number of zeroes on the end?

jshell> import java.util.ArrayList

jshell> ArrayList<Integer> values = new ArrayList<>();
values ==> []

jshell> values.add(1);
$3 ==> true

jshell> values.add(0);
$4 ==> true

jshell> values.add(3);
$5 ==> true

jshell> values.add(4);
$6 ==> true

jshell> values.add(0);
$7 ==> true

jshell> values.add(0);
$8 ==> true

jshell> values
values ==> [1, 0, 3, 4, 0, 0]

jshell> ArrayList<Integer> newValues = values.stream().filter(v -> v != 0).collect(Collectors.toCollection(ArrayList::new))
newValues ==> [1, 3, 4]

jshell> newValues.addAll(Collections.nCopies(values.size() - newValues.size(), 0))
$11 ==> true

jshell> newValues
newValues ==> [1, 3, 4, 0, 0, 0]

jshell> 


The Streams API was introduced in Java 8, so you can do lots of nice functional stuff. I'm also using JShell here, a REPL for Java that was introduced in Java 9 IIRC. There's a bit more mutation here than I'd normally write in, say, Kotlin, but I don't know the Java APIs too well, but you get the idea anyway.

This post has been edited by ndc85430: 10 May 2020 - 06:06 AM

Was This Post Helpful? 1
  • +
  • -

#14 cfoley   User is offline

  • Cabbage
  • member icon

Reputation: 2409
  • View blog
  • Posts: 5,047
  • Joined: 11-December 07

Re: Issue with Iterating over ArrayList

Posted 10 May 2020 - 07:42 AM

Nice. :) Here is a version with less mutation.

import java.util.*;
import java.util.stream.*;

public class StreamConcatenation implements MoveZeros {
	@Override
	public List<Integer> moveZerosToEnd(List<Integer> list) {
		return Stream.concat( 
				list.stream().filter(x -> x != 0),
				Stream.generate(() -> 0))
			.limit(list.size())
			.collect(Collectors.toList());
	}
}

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1