Clases LinkedBag y ArrayBag en Java. Estructuras de Datos.

Buenas gente, os traigo un ejercicio de los primeros en Java de la asignatura Estructuras de Datos de la UMA. Ésta consiste (cito textualmente):

• La interfaz Bag y la clase  LinkedBag deben situarse dentro del paquete dataStructures.bag. Para ello, crear en el proyecto este paquete con nombre "dataStructures.bag" y colocar los ficheros dentro.

  La clase BagTester debe colocarse en el paquete por defecto y usará el paquete anterior.

  Los ficheros con extensión out son pruebas de ejecución tanto en Unix como en Dos de dos ejemplos que se encuentran en la clase BagTester. Podéis comprobar si vuestra salida por consola coincide con los ficheros que os proporcionamos.

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);
}

Ahora las respuestas:

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 + ")";
 }
}

Class LinkedBag:

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.