Multiset data structure implementation in java

Multiset  is a generalized version set structure.Similar to set, multiset only stores data values without  guarantee of any particular ordering of its contents. On the other hand, it allows storing of multiple items with the same value (ie. supports non-unique keys).

It can be implemented using list but for optimal result i.e O(1) hash table structure should be used. Otherwise it  takes steps, where is number of distinct elements stored.

Source Code (JAVA)
01. /**

02.* Multiset implemented using two lists (list of values, list of occurrences)

03.* @author Pavel Micka

04.* @param <ENTITY> type parameter of the contained value

05.*/

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.}