Ein Bag wird als Multiset Datentyp bezeichnet. Der Multiset Datentyp ist keine Collection Klasse des Java SE Frameworks. Die Collection Klassen von Google hingegen beinhalten eine Multiset Klasse, die in Java-Anwendungen einsetzbar ist. Die in dem Blogbeitrag implementierte Bag-Klasse ist während einer Code Kata entstanden. Die Code Kata hat nur den Speicheralgorithmus des Bags beschrieben, ohne einen detaillierten Hinweis auf die Schnittstelle und Implementierung des Bags zu geben.
Textauszug der Kata-Beschreibung:
Eine Bag-Klasse speichert zu einem Objekt die Anzahl der Vorkommnisse. Ein Bag mit den Einträgen {"firstObj", "firstObj", "secondObj", "thirdObj"} liefert für einen getCount(„firstObj“) Aufruf den Wert zwei. Der Aufruf von uniqueEntrySet() hingegen liefert {"firstObj", "secondObj", "thirdObj"}.
Hinweis:
Ein Bag eignet sich zur Speicherplatzreduzierung, weil nicht jedes einzelne Objekt verwaltet wird. Ein ähnliches Verhalten ist von dem Flyweight Pattern bekannt. Das Flyweight Pattern ist wie der Bag ebenfalls sparsam im Umgang mit dem verfügbaren Speicherplatz.
UML-Diagramm:
Bag-Schnittstelle:
import java.util.Collection;
import java.util.Map;
public interface Bag<T> {
public boolean put(final T element);
public boolean put(final T element, final int occurrences);
public int remove(final T element);
public int remove(final T element, final int occurrences);
public int count(final T element);
public Collection<Map.Entry<T, Integer>> uniqueSet();
}
Bag-Implementierung:
import java.util.Collection;
import java.util.Collections;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class HashBag<T> implements Bag<T> {
private final Map<T, Integer> bagMap = new ConcurrentHashMap<T, Integer>();
@Override
public boolean put(final T element) {
assertElementParameterNotNull(element);
final int elementCount = count(element);
if (0 == elementCount) {
bagMap.put(element, 1);
}
else {
bagMap.put(element, elementCount + 1);
}
return true;
}
@Override
public boolean put(final T element, final int occurrences) {
assertElementParameterNotNull(element);
assertOccurrencesNotUnderOrOverflowed(occurrences);
final int elementCount = count(element);
if (0 == elementCount) {
bagMap.put(element, occurrences);
}
else {
bagMap.put(element, elementCount + occurrences);
}
return true;
}
@Override
public int remove(final T element) {
assertElementParameterNotNull(element);
assertElementAvailableInBag(element);
return bagMap.remove(element);
}
@Override
public int remove(final T element, final int occurrences) {
assertElementParameterNotNull(element);
assertElementAvailableInBag(element);
assertOccurrencesNotUnderOrOverflowed(occurrences);
assertOccurrencesNotGreaterThanElementCount(occurrences, element);
final int elementCount = count(element);
if (occurrences == elementCount) {
return remove(element);
}
return bagMap.put(element, elementCount - occurrences);
}
@Override
public Collection<Map.Entry<T, Integer>> uniqueSet() {
return Collections.unmodifiableCollection(bagMap.entrySet());
}
@Override
public int count(final T element) {
assertElementParameterNotNull(element);
final Integer elementCount = bagMap.get(element);
if (null == elementCount) {
return 0;
}
return elementCount;
}
private void assertElementParameterNotNull(final T element) {
if (null == element) {
throw new NullPointerException("Element parameter must not be null!");
}
}
private void assertElementAvailableInBag(final T element) {
final int elementCount = count(element);
if (0 == elementCount) {
final String errorMessage = String.format(
"Element (%s) not available in bag!", element);
throw new IllegalArgumentException(errorMessage);
}
}
private void assertOccurrencesNotGreaterThanElementCount(final int occurrences, final T element) {
final int elementCount = count(element);
if (occurrences > elementCount) {
final String errorMessage = String.format(
"Bag occurrences (%d) to remove greater than element count (%d) in bag!",
occurrences, elementCount);
throw new IllegalArgumentException(errorMessage);
}
}
private void assertOccurrencesNotUnderOrOverflowed(final int occurrences) {
if(occurrences < 0) {
throw new IllegalArgumentException(String.format("Underflow (occurrences (%d) < 0)!", occurrences));
}
else if(occurrences > Integer.MAX_VALUE) {
throw new IllegalArgumentException(String.format("Overflow (occurrences (%d) > max. int)! ", occurrences));
}
}
}
Bag-Testfälle:
import static org.junit.Assert.*;
import java.util.Collection;
import java.util.Map;
import org.junit.Before;
import org.junit.Test;
public class BagTest {
private Bag<String> bag;
private String firstBagElement;
private String secondBagElement;
@Before
public void setUp() {
bag = new HashBag<String>();
firstBagElement = "firstBagElement";
secondBagElement = "secondBagElement";
}
@Test
public void testPutSingleElement() {
assertEquals(true, bag.put(firstBagElement));
assertEquals(1, bag.count(firstBagElement));
}
@Test
public void testPutMultipleElements() {
assertEquals(true, bag.put(firstBagElement, 20));
assertEquals(20, bag.count(firstBagElement));
}
@Test(expected=NullPointerException.class)
public void testPutSingleNullElement() {
assertEquals(true, bag.put(null));
}
@Test(expected=NullPointerException.class)
public void testPutMultipleNullElements() {
assertEquals(true, bag.put(null, 2));
}
@Test(expected = IllegalArgumentException.class)
public void testPutMultipleElementsWithUnderflow() {
bag.put(firstBagElement, 20);
bag.put(firstBagElement, -20);
assertEquals(20, bag.count(firstBagElement));
}
@Test(expected = IllegalArgumentException.class)
public void testPutMultipleElementsWithOverflow() {
bag.put(firstBagElement, 20);
bag.put(firstBagElement, Integer.MAX_VALUE + 1);
assertEquals(20, bag.count(firstBagElement));
}
@Test
public void testPutSingleAndMultipleElements() {
bag.put(firstBagElement);
bag.put(firstBagElement, 20);
bag.put(firstBagElement);
assertEquals(22, bag.count(firstBagElement));
}
@Test
public void testPutDifferentElements() {
bag.put(firstBagElement);
bag.put(secondBagElement);
assertDifferentBagElements(bag.uniqueSet(), 2, 1, 1);
}
@Test
public void testPutMultipleDifferentElements() {
bag.put(firstBagElement, 20);
bag.put(secondBagElement, 10);
assertDifferentBagElements(bag.uniqueSet(), 2, 20, 10);
}
@Test
public void testPutMultipleAndSingleDifferentElements() {
bag.put(firstBagElement, 20);
bag.put(firstBagElement);
bag.put(secondBagElement, 10);
bag.put(secondBagElement, 10);
assertDifferentBagElements(bag.uniqueSet(), 2, 21, 20);
}
@Test
public void testRemoveSingleElement() {
bag.put(firstBagElement);
bag.put(firstBagElement);
assertEquals(2, bag.remove(firstBagElement));
assertEquals(0, bag.count(firstBagElement));
}
@Test(expected=NullPointerException.class)
public void testRemoveSingleNullElement() {
assertEquals(0, bag.remove(null));
}
@Test(expected = IllegalArgumentException.class)
public void testRemoveWhileElementIsNotAvailable() {
bag.put(firstBagElement);
bag.put(firstBagElement);
bag.remove(secondBagElement);
assertEquals(0, bag.count(secondBagElement));
}
@Test(expected = IllegalArgumentException.class)
public void testRemoveMoreOccurencesThanAvailable() {
bag.put(firstBagElement);
bag.put(firstBagElement);
bag.remove(firstBagElement,3);
assertEquals(0, bag.count(firstBagElement));
}
@Test
public void testRemoveMultipleSingleElements() {
bag.put(firstBagElement, 30);
assertEquals(30, bag.remove(firstBagElement, 30));
assertEquals(0, bag.count(firstBagElement));
}
@Test(expected=NullPointerException.class)
public void testRemoveMultipleNullElements() {
assertEquals(0, bag.remove(null, 2));
}
@Test(expected = IllegalArgumentException.class)
public void testRemoveMultipleSingleElementsWithUnderflow() {
bag.put(firstBagElement, 30);
bag.remove(firstBagElement, -1);
assertEquals(0, bag.count(firstBagElement));
}
@Test(expected = IllegalArgumentException.class)
public void testRemoveMultipleSingleElementsWithOverflow() {
bag.put(firstBagElement, 30);
bag.remove(firstBagElement, Integer.MAX_VALUE + 1);
assertEquals(0, bag.count(firstBagElement));
}
@Test
public void testRemoveDifferentSingleElements() {
bag.put(firstBagElement);
bag.put(secondBagElement);
assertEquals(1, bag.remove(firstBagElement));
assertEquals(1, bag.remove(secondBagElement));
assertDifferentBagElements(bag.uniqueSet(), 0, 1, 1);
}
@Test
public void testRemoveDifferentMultipleElements() {
bag.put(firstBagElement);
bag.put(firstBagElement);
bag.put(secondBagElement);
bag.put(secondBagElement);
assertEquals(2, bag.remove(firstBagElement,1));
assertEquals(2, bag.remove(secondBagElement,1));
assertDifferentBagElements(bag.uniqueSet(), 2, 1, 1);
}
@Test
public void testRemoveMultipleSingleElementsWithRest() {
bag.put(firstBagElement, 30);
bag.remove(firstBagElement, 10);
assertEquals(20, bag.count(firstBagElement));
}
@Test(expected = IllegalArgumentException.class)
public void testRemoveWithOverflow() {
bag.put(firstBagElement, 10);
bag.remove(firstBagElement, 20);
assertEquals(0, bag.count(firstBagElement));
}
@Test(expected=NullPointerException.class)
public void testNullElementCount() {
assertEquals(0, bag.count(null));
}
@Test
public void testUniqueElementSet() {
bag.put(firstBagElement);
bag.put(firstBagElement);
bag.put(secondBagElement);
assertDifferentBagElements(bag.uniqueSet(), 2, 2, 1);
}
private void assertDifferentBagElements(final Collection<Map.Entry<String, Integer>> ElementSet,
int ElementSetElementCount, int firstExpectedElementCount,
int secondExpectedElementCount) {
assertEquals(ElementSetElementCount, ElementSet.size());
for (Map.Entry<String, Integer> element : ElementSet) {
if (element.getKey().equals("firstBagElement")) {
assertEquals(firstExpectedElementCount, element.getValue().intValue());
}
else if (element.getKey().equals("secondBagElement")) {
assertEquals(secondExpectedElementCount, element.getValue().intValue());
}
}
}
}
Der aufmerksame Leser wird sofort erkennen, dass in den Testfällen Magic Numbers verwendet werden. Die Lesbarkeit des Quellcodes wird durch Magic Numbers verschlechtert. Ein reiner Zahlenwert hat keine semantische Aussagekraft. Änderungen an den Zahlenwerten sind überall im Quellcode nachzuziehen. Diese Änderungen sind aufwendig und fehleranfällig. Im produktiven Quellcode sind Magic Numbers deshalb nicht tolerierbar. Aufgrund der Einfachheit des Testfalls im Rahmen der Code Kata aber pragmatisch. Den Verstoß gegen das Gebot: "Schreibe die Testfälle mit der gleichen Sorgfalt wie den produktiven Quellcode" nehme ich in diesem einen Fall in Kauf.
Der Rechtshinweis des Java Blog für Clean Code Developer ist bei der Verwendung und Weiterentwicklung des Quellcodes des Blogeintrages zu beachten.
