Implement Multiset

http://www.programming-algorithms.net/article/41868/Multiset

The easiest way to implement a multiset is to use a list a forget its ordering. But this approach is very memory inefficient, because it needs to store all instances of repeating items. A better solution uses two lists – one for data and second for storing numbers of occurrences of corresponding items. This implementation performs better, but is still not optimal, because the contains operation needs to iterate over the whole array, which takes  steps, where  is number of distinct elements stored. The optimal implementation uses for storing items ahash table structure, which guarantees  average access time for all elements.

06.public class Multiset<VALUE> {

07. 

08.private List<VALUE> values;

09.private List<Integer> occurences;

10. 

11./**

12.* Constructor

13.* @param initialCapacity initial capacity of underlying lists

14.*/

15.public Multiset(int initialCapacity) {

16.values = new ArrayList<VALUE>(initialCapacity);

17.occurences = new ArrayList<Integer>(initialCapacity);

18.}

19. 

20./**

21.* Inserts a value into the multiset

22.* @param val value

23.* @return number of occurences of the value in the set after the addition

24.*/

25.public int put(VALUE val) {

26.int index = values.indexOf(val);

27.if (index == -1) {

28.values.add(val);

29.occurences.add(1);

30.return 1;

31.} else {

32.int currCount = occurences.get(index);

33.occurences.set(index, currCount + 1);

34.return currCount + 1;

35.}

36.}

37. 

38./**

39.* Returns and deletes (decrements number of uccurences) some value from the multiset

40.* @return value, null if the multiset is empty

41.*/

42.public VALUE pick() {

43.if (values.size() == 0) {

44.return null;

45.}

46.if (occurences.get(0) == 1) {

47.VALUE v = values.remove(0);

48.occurences.remove(0);

49.return v;

50.} else {

51.VALUE v = values.get(0);

52.occurences.set(0, occurences.get(0) - 1);

53.return v;

54.}

55.}

56. 

57./**

58.* Deletes a given value from the multiset (removes one occurrence)

59.* @param val value

60.* @return number of occurences of the value in the set after the deletion

61.*/

62.public int remove(VALUE e) {

63.int index = values.indexOf(e);

64.int curr = occurences.get(index);

65.if (curr != 1) {

66.occurences.set(index, curr - 1);

67.return curr - 1;

68.} else {

69.values.remove(index);

70.occurences.remove(index);

71.return 0;

72.}

73.}

74. 

75./**

76.* Query, if the multiset contains a given value

77.* @param val value

78.* @return number of occurences of the given value in the set

79.*/

80.public int contains(VALUE e) {

81.int index = values.indexOf(e);

82.if(index == -1) return 0;

83.return occurences.get(index);

84.}

85. 

86./**

87.* Size of the multiset (including all multiplicities)

88.* @return number of stored entities (values*occurences)

89.*/

90.public int size() {

91.int count = 0;

92.for(Integer i : occurences){

93.count += i;

94.}

95.return count;

96.}

97.}

https://dzone.com/articles/google-guava-multisets

Have you ever written code like the following:

Map<MyClass,Integer> objectCounts = new HashMap<MyClass,Integer>();
 
public void incrementCount(MyClass obj) {
    Integer count = objectCounts.get(obj);
    if (count == null) {
        objectCounts.put(obj,0);
    } else {
        objectCounts.put(obj,count++);
    }
}
 
public int getCount(MyClass obj) {
    Integer count = objectCounts.get(obj);
    if (count == null) {
        return 0;
    } else {
        return count;
    }
}

Bit unwieldy? Lets see how we might use a Multiset instead: 

Multiset<MyClass> myMultiset = HashMultiset.create();
 
MyClass myObject = new MyClass();
 
myMultiset.add(myObject);
myMultiset.add(myObject);  // add it a second time.
 
System.out.println(myMultiset.count(myObject)); // 2
 
myMultiset.remove(myObject);
System.out.println(myMultiset.count(myObject)); // 1