Sí, como veis nuestro profesor tampoco se esforzaba mucho en hacernos saber lo que pedía. Solía explicarlo en clase y "a buscarse la vida". Por eso mismo atrasé esta entrada para subir primero la de Haskell en la cual sí venía explicado. Aquí teneis el test, el archivo de prueba Cervantes y el Dickens.
Os doy la interfaz Bag:
package dataStructures.bag;
/**
* Interface for the Bag ADT.
*
* @param <T>
* Type of elements in bag. Note that {@code T} must be
* {@code Comparable}
*/
public interface Bag<T extends Comparable<? super T>> {
/**
* Test the bag for emptiness.
*
* @return {@code true} if bag is empty, else {@code false}.
*/
boolean isEmpty();
/**
* Inserts a new occurrence in the bag.
*
* @param item
* the element to insert.
*/
void insert(T item);
/**
* Returns the number of occurrences of {@code item} in the bag
*
* @param item
* the item to be counted
* @return number of occurrences of {@code item}
*/
int occurrences(T item);
/**
* Removes an occurrence of {@code item} from the bag
*
* @param item
* the item to remove
*/
void delete(T item);
}
Class ArrayBag:
package dataStructures.bag;
import java.util.Arrays;
public class ArrayBag<T extends Comparable<? super T>> implements Bag<T> {
private final static int INITIAL_CAPACITY = 5;
protected T[] value; // keep this array sorted
protected int[] count; // keep only positive counters
protected int nextFree;
public ArrayBag() {
this(INITIAL_CAPACITY);
}
@SuppressWarnings("unchecked")
public ArrayBag(int n) {
value = (T[]) new Comparable[n]; // everything to null
count = new int[n]; // everything to 0
nextFree = 0;
}
private void ensureCapacity() {
if (nextFree == value.length) {
value = Arrays.copyOf(value, 2 * value.length);
// TO BE FILLED OUT
count = Arrays.copyOf(count, 2*count.length);
}
}
public boolean isEmpty() {
return nextFree == 0;
}
// if "item" is stored in the array "value", returns its index
// otherwise returns the index where "item" would be inserted
// si item está almacenado en el array devuelve su índice
// si no devuelve el índice en el que item debería insertarse
private int locate(T item) {
int lower = 0;
int upper = nextFree - 1;
int mid = 0;
boolean found = false;
// binary search
while (lower <= upper && !found) {
mid = lower + ((upper - lower) / 2); // == (lower + upper) / 2;
found = value[mid].equals(item);
if (!found) {
if (value[mid].compareTo(item) > 0) {
upper = mid - 1;
} else {
lower = mid + 1;
}
}
}
if (found)
return mid; // the index where "item" is stored
else
return lower; // the index where "item" would be inserted
}
public void insert(T item) {
ensureCapacity();
int i = locate(item);//donde está o deberia estar
if (value[i] != null && value[i].equals(item)) {//está ahí
count[i]++;
// TO BE FILLED OUT
} else {
// shift elements to right
for (int j = nextFree; j > i; j--) {
value[j] = value[j - 1];
count[j] = count[j - 1];
}
value[i] = item;
count[i] = 1;
nextFree++;
}
}
public int occurrences(T item) {
int result = 0;
int i = locate(item);
if (value[i] != null && value[i].equals(item)) {
result = count[i];
}
return result;
}
public void delete(T item) {
int i = locate(item);
if (value[i] != null && value[i].equals(item)) {
if (count[i] > 1) {
count[i]--;
} else {
// shift elements to left
for (int j = i; j < nextFree-1; j++) {
value[j] = value[j+1];
count[j] = count[j+1];
}
nextFree--;
}
}
}
public String toString() {
String text = "Bag(";
for (int i = 0; i < nextFree; i++) {
text += "(" + value[i] + ", " + count[i] + ") ";
}
return text + ")";
}
}
package dataStructures.bag;
public class LinkedBag<T extends Comparable<? super T>> implements Bag<T> {
static private class Node<E> {
E elem;
int count;
Node<E> next;
Node(E x, int n, Node<E> node) {
elem = x;
count = n;
next = node;
}
}
private Node<T> first; // keep the linked list sorted by "elem"
public LinkedBag() {
first = null;
}
public boolean isEmpty() {
return first == null;
}
public void insert(T item) {
Node<T> previous = null;
Node<T> current = first;
while (current != null && current.elem.compareTo(item) < 0) {
previous = current;
current = current.next;
}
if (current != null && current.elem.equals(item)) { //hemos encontrado el elemento
//aumentamos count
current.count++;
// TO BE FILLED OUT
} else if (previous == null) { //no hay elementos
first = new Node<T>(item, 1, first);
} else {// no existe, hay que insertarlo
// TO BE FILLED OUT
Node<T> aux = new Node<T>(item, 1, current);
previous.next = aux;
}
}
public int occurrences(T item) {
Node<T> current = first;
int result = 0;
while (current != null && current.elem.compareTo(item) < 0) {
current = current.next;
}
if (current != null && current.elem.equals(item)) { // lo hemos encontrado
// TO BE FILLED OUT
result = current.count;
}
return result;
}
public void delete(T item) {
Node<T> previous = null;
Node<T> current = first;
while (current != null && current.elem.compareTo(item) < 0) {
previous = current;
current = current.next;
}
if (current != null && current.elem.equals(item)) {//lo hemos encontrado
if (current.count > 1) {// tiene mas de uno
current.count--;
} else if (previous == null) {//es el primero
first = first.next;
} else {
previous.next = current.next;
}
}
}
public String toString() {
String text = "Bag(";
for (Node<T> p = first; p != null; p = p.next) {
text += "(" + p.elem + ", " + p.count + ") ";
}
return text + ")";
}
}
Bueno amigos, eso es todo. Espero que os sirva ;) Si tenéis alguna petición o duda, comentadla ;)
Muchas gracias.
