The Wayback Machine - https://web.archive.org/web/20200802152748/https://github.com/TheAlgorithms/Java/pull/1262/files
Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add Bag #1262

Open
wants to merge 2 commits into
base: Development
from
Open

Add Bag #1262

Changes from all commits
Commits
File filter...
Filter file types
Jump to…
Jump to file
Failed to load files.

Always

Just for now

@@ -0,0 +1,111 @@
package com.dataStructures.bag;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
*
* Implementation of a Generic Bag Datastructure
* @param <Element> - generic type of elements in bag
*/
public class Bag<Element> implements Iterable<Element> {

private Node<Element> firstElement; //first element of the bag
private int size; //size of the bag

/**
* Inner static class for elements of bag
* @param <Element>
*/
private static class Node<Element> {
private Element content;
private Node<Element> nextElement;
}

/**
* Constructor
* initializes an empty bag
*/
public Bag() {
firstElement = null;
size = 0;
}

/**
* @return true if this bag is empty;
* false otherwise
*/
public boolean isEmpty() {
return firstElement == null;
}

/**
* @return the size of the bag, i.e. the number of items
*/
public int size() {
return size;
}

/**
*Add items to bag
* @param element - element to be added
*/
public void addElement(Element element) {
Node<Element> oldfirst = firstElement;
firstElement = new Node<>();
firstElement.content = element;
firstElement.nextElement = oldfirst;
size++;
}

/**
* Check whether element is in bag
* @param element
* @return true if element is in bag
* false otherwise
*/
public boolean contains(Element element) {
Iterator<Element> iterator = this.iterator();
while (iterator.hasNext()) {
if (iterator.next().equals(element)) {
return true;
}
}
return false;
}

/**
*
* @return iterator over elements in bag
*/
@Override
public Iterator<Element> iterator() {
return new ListIterator<>(firstElement);
}

/**
* private inner class iplements an iterator
*/
private class ListIterator<Element> implements Iterator<Element> {
private Node<Element> currentElement;

public ListIterator(Node<Element> firstElement) {
currentElement = firstElement;
}

@Override
public boolean hasNext() {
return currentElement != null;

}

@Override
public Element next() {
if (!hasNext())
throw new NoSuchElementException();
Element element = currentElement.content;
currentElement = currentElement.nextElement;
return element;
}
}
}
@@ -0,0 +1,49 @@
package com.dataStructures.bag;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class BagTest {

@Test
public void testIsEmpty() {
Bag<String> stringBag = new Bag<>();
Assertions.assertEquals(true, stringBag.isEmpty());
stringBag.addElement("Sample");
Assertions.assertEquals(false, stringBag.isEmpty());

Bag<Integer> integerBag = new Bag<>();
Assertions.assertEquals(true, integerBag.isEmpty());
integerBag.addElement(42);
Assertions.assertEquals(false, integerBag.isEmpty());
}

@Test
public void testAddElement() {
Bag<String> stringBag = new Bag<>();
stringBag.addElement("Sample");
Assertions.assertTrue(stringBag.contains("Sample"));

Bag<Integer> integerBag = new Bag<>();
integerBag.addElement(17);
Assertions.assertTrue(integerBag.contains(42));
}

@Test
public void testContains() {
Bag<String> stringBag = new Bag<>();
stringBag.addElement("Sample");
stringBag.addElement("element");
Assertions.assertFalse(stringBag.contains("more"));
Assertions.assertTrue(stringBag.contains("Sample"));
Assertions.assertTrue(stringBag.contains("element"));

Bag<Integer> integerBag = new Bag<>();
integerBag.addElement(42);
integerBag.addElement(47);
integerBag.addElement(11);
Assertions.assertTrue(integerBag.contains(11));
Assertions.assertTrue(integerBag.contains(42));
Assertions.assertTrue(integerBag.contains(47));
}
}
ProTip! Use n and p to navigate between commits in a pull request.
You can’t perform that action at this time.