Java DataStructure Programs

//********************************************************************
// ArrayIterator.java Authors: Lewis/Chase
//
// Represents an iterator over the elements of an array.
//********************************************************************

package jss2;

import java.util.*;

public class ArrayIterator implements Iterator
{
  private int count; // the number of elements in the collection
  private int current; // the current position in the iteration 
  private T[] items; 

  //-----------------------------------------------------------------
  // Sets up this iterator using the specified items.
  //-----------------------------------------------------------------
  public ArrayIterator (T[] collection, int size)
  {
  items = collection;
  count = size;
  current = 0;
  }

  //-----------------------------------------------------------------
  // Returns true if this iterator has at least one more element
  // to deliver in the iteraion.
  //-----------------------------------------------------------------
  public boolean hasNext()
  {
  return (current < count);
  }

  //-----------------------------------------------------------------
  // Returns the next element in the iteration. If there are no
  // more elements in this itertion, a NoSuchElementException is
  // thrown.
  //-----------------------------------------------------------------
  public T next()
  {
  if (! hasNext())
  throw new NoSuchElementException();

  current++;

  return items[current - 1]; 
  
  }

  //-----------------------------------------------------------------
  // The remove operation is not supported in this collection.
  //-----------------------------------------------------------------
  public void remove() throws UnsupportedOperationException
  {
  throw new UnsupportedOperationException();
  }
}

------------------------------------------

//********************************************************************
// ArraySet.java Author: Lewis/Chase
//
// Represents an array implementation of a set.
//********************************************************************

package jss2;
import jss2.exceptions.*;
import java.util.*;

public class ArraySet implements SetADT
{
  private static Random rand = new Random();

  private final int DEFAULT_CAPACITY = 100;
  private final int NOT_FOUND = -1;

  private int count; // the current number of elements in the set 

  private T[] contents; 

  //-----------------------------------------------------------------
  // Creates an empty set using the default capacity.
  //-----------------------------------------------------------------
  public ArraySet()
  {
  count = 0;
  contents = (T[])(new Object[DEFAULT_CAPACITY]);
  }

  //-----------------------------------------------------------------
  // Creates an empty set using the specified capacity.
  //-----------------------------------------------------------------
  public ArraySet (int initialCapacity)
  {
  count = 0;
  contents = (T[])(new Object[initialCapacity]);
  }

  //-----------------------------------------------------------------
  // Adds the specified element to the set if it's not already
  // present. Expands the capacity of the set array if necessary.
  //-----------------------------------------------------------------
  public void add (T element)
  {
  if (!(contains(element)))
  {
  if (size() == contents.length) 
  expandCapacity();

  contents[count] = element;
  count++;
  }
  }

  //-----------------------------------------------------------------
  // Adds the contents of the parameter to this set.
  //-----------------------------------------------------------------
  public void addAll (SetADT set)
  {
  Iterator scan = set.iterator();

  while (scan.hasNext())
  add (scan.next());
  }


  //-----------------------------------------------------------------
  // Removes a random element from the set and returns it. Throws
  // an EmptySetException if the set is empty.
  //-----------------------------------------------------------------
  public T removeRandom() throws EmptySetException
  {
  if (isEmpty())
  throw new EmptySetException();

  int choice = rand.nextInt(count);

  T result = contents[choice];

  contents[choice] = contents[count-1]; // fill the gap
  contents[count-1] = null;
  count--;
 
  return result;
  }

  //-----------------------------------------------------------------
  // Removes the specified element from the set and returns it.
  // Throws an EmptySetException if the set is empty and a
  // NoSuchElementException if the target is not in the set.
  //-----------------------------------------------------------------
  public T remove (T target) throws EmptySetException,
  NoSuchElementException
  {
  int search = NOT_FOUND;

  if (isEmpty())
  throw new EmptySetException();

  for (int index=0; index < count && search == NOT_FOUND; index++)
  if (contents[index].equals(target))
  search = index;

  if (search == NOT_FOUND)
  throw new NoSuchElementException();

  T result = contents[search];

  contents[search] = contents[count-1];
  contents[count-1] = null;
  count--;
 
  return result;
  }
   
  //-----------------------------------------------------------------
  // Returns a new set that is the union of this set and the
  // parameter.
  //-----------------------------------------------------------------
  public SetADT union (SetADT set)
  {
  ArraySet both = new ArraySet();

  for (int index = 0; index < count; index++)
  both.add (contents[index]);

  Iterator scan = set.iterator();
  while (scan.hasNext())
  both.add (scan.next());

  return both;
  }

  //-----------------------------------------------------------------
  // Returns true if this set contains the specified target
  // element.
  //-----------------------------------------------------------------
  public boolean contains (T target)
  {
  int search = NOT_FOUND;

  for (int index=0; index < count && search == NOT_FOUND; index++)
  if (contents[index].equals(target))
  search = index;

  return (search != NOT_FOUND);
  }

  //-----------------------------------------------------------------
  // Returns true if this set contains exactly the same elements
  // as the parameter.
  //-----------------------------------------------------------------
  public boolean equals (SetADT set)
  {
  boolean result = false;
  ArraySet temp1 = new ArraySet();
  ArraySet temp2 = new ArraySet();
  T obj;

  if (size() == set.size())
  { 
  temp1.addAll(this);
  temp2.addAll(set);

  Iterator scan = set.iterator();

  while (scan.hasNext())
  {
  obj = scan.next();  
  if (temp1.contains(obj))
  {
  temp1.remove(obj);
  temp2.remove(obj);
  }
   
  }

  result = (temp1.isEmpty() && temp2.isEmpty());
  }

  return result;
  }

  //-----------------------------------------------------------------
  // Returns true if this set is empty and false otherwise. 
  //-----------------------------------------------------------------
  public boolean isEmpty()
  {
  return (count == 0);
  }
 
  //-----------------------------------------------------------------
  // Returns the number of elements currently in this set.
  //-----------------------------------------------------------------
  public int size()
  {
  return count;
  }

  //-----------------------------------------------------------------
  // Returns an iterator for the elements currently in this set.
  //-----------------------------------------------------------------
  public Iterator iterator()
  {
  return new ArrayIterator (contents, count);
  }

  //-----------------------------------------------------------------
  // Returns a string representation of this set. 
  //-----------------------------------------------------------------
  public String toString()
  {
  String result = "";

  for (int index=0; index < count; index++) 
  result = result + contents[index].toString() + "\n";

  return result;
  }

  //-----------------------------------------------------------------
  // Creates a new array to store the contents of the set with
  // twice the capacity of the old one.
  //-----------------------------------------------------------------
  private void expandCapacity()
  {
  T[] larger = (T[])(new Object[contents.length*2]);

  for (int index=0; index < contents.length; index++)
  larger[index] = contents[index];

  contents = larger;
  }
}

--------------------------------------------------

//********************************************************************
// ElementNotFoundException.java Authors: Lewis/Chase
//
// Represents the situation in which a target element is not
// present in a collection
//********************************************************************

package jss2.exceptions;

public class ElementNotFoundException extends RuntimeException
{
  //-----------------------------------------------------------------
  // Sets up this exception with an appropriate message.
  //-----------------------------------------------------------------
  public ElementNotFoundException (String collection)
  {
  super ("The target element is not in this " + collection);
  }
}


-----------------------------------------------------

//********************************************************************
// EmptySetException.java Authors: Lewis/Chase
//
// Represents the situation in which a set is empty.
//********************************************************************

package jss2.exceptions;

public class EmptySetException extends RuntimeException
{
  //-----------------------------------------------------------------
  // Creates the exception.
  //-----------------------------------------------------------------
  public EmptySetException()
  {
  super ("The set is empty.");
  }

  //-----------------------------------------------------------------
  // Creates the exceptio with the specified message.
  //-----------------------------------------------------------------
  public EmptySetException (String message)
  {
  super (message);
  }
}

-----------------------------------------------------

package trysets;
import jss2.*;
import java.util.*;

public class IntegerSetTester {
  public static void main(String[] args) {
  System.out.println("Lab 2: Part I written by YOURNAME");
  System.out.println("Creating set1--------------------");
  SetADT set1 = new ArraySet();

  }
}

------------------------------------------------

//********************************************************************
// SetADT.java Authors: Lewis/Chase
//
// Defines the interface to a set collection.
//********************************************************************

package jss2;

import java.util.Iterator;

public interface SetADT
{
  // Adds one element to this set, ignoring duplicates
  public void add (T element);

  // Removes and returns a random element from this set
  public T removeRandom ();

  // Removes and returns the specified element from this set
  public T remove (T element);

  // Returns the union of this set and the parameter
  public SetADT union (SetADT set);

  // Returns true if this set contains the parameter
  public boolean contains (T target);

  // Returns true if this set and the parameter contain exactly
  // the same elements
  public boolean equals (SetADT set);

  // Returns true if this set contains no elements
  public boolean isEmpty();

  // Returns the number of elements in this set
  public int size();

  // Returns an iterator for the elements in this set
  public Iterator iterator();

  // Returns a string representation of this set
  public String toString();
}

--------------------------------------------

package trysets;

import java.io.*;
import java.util.*;

/**
 *

Title:

WordReader
 *

Description:

Provides an "iterator" over the file filename
 * to return individual words, while removing leading and trailing
 * punctuation. WordReader throws an IOException if it is unable
 * to open the file corresponding to filename. However, for other
 * errors, it reports errors by returning null for the next word.
 */
public class WordReader implements Iterator {
  private static final String punctuation = ".,:)({}[]';)-=+!@`";
  private BufferedReader read;
  private String name;
  private String nextWord;
  private boolean more;
  private StringTokenizer tokens;

  public WordReader(String filename) throws IOException {
  name = filename;
  more = true;
  read = new BufferedReader(new FileReader(filename));
  tokens = null;
  updateWord();
  }

  public boolean hasNext() {
  return more;
  }

  public String next() {
  if (!more)
  throw new NoSuchElementException("No more words in " + name);
  String thisWord = nextWord;
  updateWord();
  return thisWord;
  }

  public void remove() {
  throw new UnsupportedOperationException(
  "Can not remove elements from file");
  }

  private String trimPunctuation(String word) {
  int start = 0;
  // find first non-punctuation
  int end = word.length();
  while (start < end && punctuation.indexOf(word.charAt(start)) != -1) {
  start++;
  }
  if (start >= end) { // all punctuation
  return null;
  } while (punctuation.indexOf(word.charAt(end - 1)) != -1) {
  end--;
  }
  return word.substring(start, end);
  }

  private void updateWord() {
  try {
  while (more) {
  if (tokens == null) {
  String thisLine = read.readLine();
  if (thisLine == null) {
  throw new IOException("Empty line");
  }
  tokens = new StringTokenizer(thisLine);
  }
  if (tokens.hasMoreTokens()) {
  nextWord = trimPunctuation(tokens.nextToken());
  if (nextWord != null) {
  return;
  }
  } else {
  tokens = null;
  }
  }
  } catch (Exception e) {
  more = false;
  nextWord = null;
  try {
  read.close();
  } catch (Exception e1) {}
  }
  }

}