views:

3557

answers:

11

I have an ArrayList a collection class of java as follows.

ArrayList<String>animals = new ArrayList<String>();
animals.add("bat");
animals.add("owl");
animals.add("bat");
animals.add("bat");

As you can see the animals ArrayList consists of 3 bat elements and one owl element. I was wondering if there is any API in collection framework that returns the number of bat occurrences or is there a way to determine number of occurrences.

I found that google's collection multiset does have an api that returns total number of occurrences of an element. But that is compatible only with jdk1.5. Our product is currently in jdk 1.6. Hence cannot use it.

+2  A: 

There is no native method in Java to do that for you. However, you can use CollectionUtils#countMatches() from Apache Commons-Collections to do it for you.

Kevin
Refer to my answer below - the correct answer is to use a structure that supports the counting idea from the begining rather than counting entries from start to end each time a query is made.
mP
@mP So you just downvote everyone who has a different opinion than you? What if he can't use a Bag for some reason or is stuck with using one of the native Collections?
Kevin
Doesn't deserve a downvote, IMHO.
Adeel Ansari
-1 for being a sore loser :-) I think mP downvoted you because your solution costs time every time you want a result. A bag cost a little time only at insertion. Like databases, these sort of structures tend to be "more read than write" so it makes sense to use the low cost option.
paxdiablo
And it appears your answer also requires non-native stuff, so your comment seems a little strange.
paxdiablo
Thanks to both of you guys. I believe one of the two approaches or both of them might work. I will give it a try tomorrow.
MM
@Pax I can imagine a use case where he is not the owner/creator of the Collection but merely a user. In such a case, he wouldn't be able to use a Bag. Anyways, the appropriate answer is: Use Commons Collections :)
Kevin
Do you guys think this is wrong. It might be inefficient doesn't mean its wrong. For inefficiency don't vote, simple. Downvote means, at least to me, something totally wrong. Its bloated, I agree, but it will yield a right result.
Adeel Ansari
What do you think of this algo of Fibonacci. Its in Groovy BTW.... "def fib(x) {x <= 1 ? x : fib(x-1) + fib(x-2)}"..... Its terribly inefficient, but it will yield the right result, and if what you want is less 20 it is good to go. Doesn't deserve a negative.
Adeel Ansari
@Vinegar, the actual help text is "not helpful" rather than wrong. Having said that, I didn't downvote this one (see the smiley on my comment) because it's not "not helpful". I didn't upvote it either since I believe mP's is more helpful and I restrict myself to upvoting the one best answer IMNSHO.
paxdiablo
@Vinegar, bubble sorts are also inefficient but yield the right result. Let's see how many rep points you'd get here on SO if you answered a sort question with "bubble sort" :-). Granted, it's fine for sorting small data sets but it also won't scale.
paxdiablo
My point being, bags are a better answer to the specific question.
paxdiablo
I tend to agree, Pax. Neither I am very inclined towards this solution. I voted it +1 to make it zero. And for bubble sort example, I wouldn't expect any point in that case, neither +ve nor -ve. :)
Adeel Ansari
And if one take a look of this answer from a slightly different angle, I assume Kevin also looked it in that way. Common Collection would work as substitute of Google Collection, since the original poster mentioned this himself. But still Bags are better.
Adeel Ansari
+1  A: 

Sorry there's no simple method call that can do it. All you'd need to do though is create a map and count frequency with it.

HashMap<String,int> frequencymap = new HashMap<String,int>();
foreach(String a in animals) {
  if(frequencymap.containsKey(a)) {
    frequencymap.put(a, frequencymap.get(a)+1);
  }
  else{ frequencymap.put(a, 1); }
}
Ray Hidayat
This is really not a scalable solution - imagine MM's data set had hundreds and thousands of entries and MM wanted to know the frequences for each and every entry. This could potentially be a very costly task - especially when there are much better ways to do it.
mP
Yes, it might not be a good solution, doesn't mean its wrong.
Adeel Ansari
He just wants the number of 'bat' occurrences. Just iterate once over the original ArrayList and increment a counter whenever you see 'bat'.
@dehmann, I don't think he literally wants the number of bat occurrences in a 4-element collection, I think that was just sample data so we'd understand better :-).
paxdiablo
@VinegarJust because it works doesnt mean its the proper way to do things. We could scan all the rows in a table and manually find the bat record but we dont we create the appropriate query.
mP
@Vinegar 2/2.Programming is about doing things properly now, so we dont cause headaches or a bad experience for someone else be it a user or another coder in the future.PS: The more code your write the more chance there is something can go wrong.
mP
I agree, thats why I don't upvote those clumsy solutions. But neither I downvote those because they give the right result. Since, we can't downvote twice to a wrong answer. And IMO, we must distinguish wrong from inefficient.
Adeel Ansari
+2  A: 

What you want is a Bag - which is like a set but also counts the number of occurances. Unfortunately the java Collections framework - great as they are dont have a Bag impl. For that one must use the Apache Common Collection link text

mP
Best scalable solution and, if you can't use third-party stuff, just write your own. Bags aren't rocket science to create. +1.
paxdiablo
A: 

So do it the old fashioned way and roll your own:

Map<String, Integer> instances = new HashMap<String, Integer>();

void add(String name) {
     Integer value = instances.get(name);
     if (value == null) {
        value = new Integer(0);
        instances.put(name, value);
     }
     instances.put(name, value++);
}
Mark Renouf
With the appropriate "synchronized", if needed, to avoid race conditions. But I'd still prefer to see this in its own class.
paxdiablo
This code doesn't work. See corrected code in subsequent answer.
joel.neely
You have a typo. Need HashMap instead, as you are taking it in Map. But the mistake to put 0 instead of 1 is a bit more serious.
Adeel Ansari
No offense intended; I didn't know how to contact you directly and couldn't fit the changes in a comment. I'll delete my answer.
joel.neely
+6  A: 

I wonder, why you can't use that Google's Collection API with JDK 1.6. Does it say so? I think you can, there should not be any compatibility issues, as it is built for a lower version. The case would have been different if that were built for 1.6 and you are running 1.5.

Am I wrong somewhere?

Adeel Ansari
They have clearly mentioned that they are in the process of upgrading their api to jdk 1.6.
MM
That doesn't make old incompatible. Does it?
Adeel Ansari
It should not. But the way they were throwing disclaimers, makes me uncomfortable to use it in their 0.9 version
MM
We use it with 1.6. Where does it say it is only compatible with 1.5?
Patrick
By "upgrading to 1.6" they probably mean "upgrading to take advantage of new stuff in 1.6," not "fixing compatibility with 1.6".
Adam Jaskiewicz
A: 

Put the elements of the arraylist in the hashMap to count the frequency.

Shamik
This is exactly the same thing that tweakt says with a code sample.
mP
+1  A: 

A slightly more efficient approach might be

Map<String, AtomicInteger> instances = new HashMap<String, AtomicInteger>();

void add(String name) {
     AtomicInteger value = instances.get(name);
     if (value == null) 
        instances.put(name, new AtomicInteger(1));
     else
        value.incrementAndGet();
}
Peter Lawrey
+2  A: 

This shows, why it is important to "Refer to objects by their interfaces" as described in Effective Java book.

If you code to the implementation and use ArrayList in let's say, 50 places in your code, when you find a good "List" implementation that count the items, you will have to change all those 50 places, and probably you'll have to break your code ( if it is only used by you there is not a big deal, but if it is used by someone else uses, you'll break their code too)

By programming to the interface you can let those 50 places unchanged and replace the implementation from ArrayList to "CountItemsList" (for instance ) or some other class.

Below is a very basic sample on how this could be written. This is only a sample, a production ready List would be much more complicated.

import java.util.*;

public class CountItemsList<E> extends ArrayList<E> { 

    // This is private. It is not visible from outside.
    private Map<E,Integer> count = new HashMap<E,Integer>();

    // There are several entry points to this class
    // this is just to show one of them.
    public boolean add( E element  ) { 
        if( !count.containsKey( element ) ){
            count.put( element, 1 );
        } else { 
            count.put( element, count.get( element ) + 1 );
        }
        return super.add( element );
    }

    // This method belongs to CountItemList interface ( or class ) 
    // to used you have to cast.
    public int getCount( E element ) { 
        if( ! count.containsKey( element ) ) {
            return 0;
        }
        return count.get( element );
    }

    public static void main( String [] args ) { 
        List<String> animals = new CountItemsList<String>();
        animals.add("bat");
        animals.add("owl");
        animals.add("bat");
        animals.add("bat");

        System.out.println( (( CountItemsList<String> )animals).getCount( "bat" ));
    }
}

OO principles applied here: inheritance, polymorphism, abstraction, encapsulation.

OscarRyz
Well one should always try composition rather than inheritance. Your implementation is now stuck to ArrayList when there may be times you want a LinkedList or other. Your example should have taken another LIst in its constructor/factory and returned a wrapper.
mP
I completely agree with you. The reason I used inheritance in the sample is because it is a lot more easier to show a running example using inheritance than composition ( having to implement the List interface ). Inheritance creates the highest coupling.
OscarRyz
A: 

If you are a user of my ForEach DSL, it can be done with a Count query.

Count<String> query = Count.from(list);
for (Count<Foo> each: query) each.yield = "bat".equals(each.element);
int number = query.result();
Adrian
+1  A: 

This is an example where C# shines compared to Java. In C#, you would need only do this:

var count = (from a in animals where a.value = "bat" select a).Count();

Unfortunately, Java doesn't have anything like Linq or lambda's, so your'e stuck doing it the interative way that others suggest.

Mystere Man
+3  A: 

I'm pretty sure the static frequency-method in Collections would come in handy here:

int occurrences = Collections.frequency(animals, "bat");

That's how I'd do it anyway. I'm pretty sure this is jdk 1.6 straight up.

Lars Andren