/*
 * IntSet.java                                                 Matt Gerrans
 *                                                            February 2003
 *
 * Simple demo of a set of integers implemented as linked list.
 *
 * Copyright 2003, Matt Gerrans.
 *
 * Turning in this code as homework is a violation of ethical principals,
 * and punishable by severe penalties, even if you change the variable
 * names.
 */
 
/**
 * I've defined this IntSet interface because the Set interface described
 * in the question was clearly not java.util.Set.   And since I'm not using
 * a package (for simplicity of exposition), I don't want to muddy the waters
 * by using the name "Set" which could confuse matters for any other sample 
 * apps in the default namepaces that import "java.util.*".
 *
 * @author Matt Gerrans
 */
public interface IntSet
{
   /**
    * Inserts an integer value into the set, if it is not already there.
    *
    * @param  value The value to add.
    * @return true if the value is added to the set, false if it was
    *               already there.
    */
   boolean insert( int value );
   /**
    * Returns true if the value is in the set, false otherwise.
    *
    * @param  value The value to find.
    * @return true if the value is in the set.
    */
   boolean member( int value );
   /**
    * If the value is in the set, this removes it and returns true,
    * otherwise, it simply returns false.
    *
    * @param  value The value to remove.
    * @return true if the value was removed.
    */
   boolean remove( int value );
}
 
 
/*
 * IntSetTestSuite.java                                        Matt Gerrans
 *                                                            February 2003
 *
 * To build and use this Test Suite:
 * 1) Add the SuiteRunner jar file to the classpath.
 *    (eg. set classpath=%classpath%;D:\artima\suiterunner-1.0beta3.jar
 *     Adjusting for where you actually installed SuiteRunner, of course)
 *
 * 2) Compile this java file with jikes (preferably) or javac (if you
 *    have no other choice).
 *
 * 3) Run "java -jar suiterunner-1.0beta3.jar"
 *
 * 4) To do the testing, load the IntSetTestSuite.srj file.  If you don't
 *    have the srj file, you can just enter the settings:
 *    a) Choose "Edit Recipe..." form the File menu.   
 *    b) In the run path tab, add the directory where this file was 
 *       compiled (where the class file is).
 *    c) In the Suites tab use the "Select..." button and the 
 *       IntSetTestSuite class should appear in the list; select it
 *       and you are ready for action, Jackson.
 *    d) If you want to use this configuration again, be sure and save it.
 *
 * Copyright 2003, Matt Gerrans.
 *
 * Turning in this code as homework is a violation of ethical principals,
 * and punishable by severe penalties, even if you change the variable
 * names.
 */
 
import org.suiterunner.Suite;
import org.suiterunner.Report;
import org.suiterunner.Reporter;
import java.util.Date;
 
/**
 * Tests for IntSet and LinkedListIntSet.
 * 
 * @author Matt Gerrans
 */
public class IntSetTestSuite extends Suite
{
   private IntSet intSet;
   private long millisecondsToPause = 200;
 
   Reporter reporter; // I want to keep a reference to the reporter so
                      // I can report that the fixture was cleaned up.
   
   /**
    * This is a silly pause that is called by each
    * of the test methods (needs to be an aspect of them, eh?),
    * for the sole purpose of giving that warm and fuzzy feeling
    * of seeing the tests in action as the progress bar slowly
    * but surely fills to 100%.
    *
    * I do this for small suites, just to have a more visceral feeling
    * of the progress.   For a large suite, this would be a dumb idea.
    */
   private void pause() 
   {
      try
      {
         Thread.sleep(millisecondsToPause); 
      }
      catch(java.lang.InterruptedException ie)
      {
         // How's a program supposed to get any sleep around here?
      }
   }
 
   /**
    * Creates an intSet for each test to muck with.
    */
   public void setupFixture()
   {
      intSet = new LinkedListIntSet();
   }
   
   /**
    * "Deletes" the intSet created by setupFixture(), which is really not
    * necessary, since the reference will be reassigned for the next 
    * setup anyway.
    * Also reports an infoProvided report to the reporter, which can
    * later be viewed in the UI, or log, or what have you.
    */
   public void cleanupFixture()
   {
      intSet = null;  // Not really necessary.
      if( reporter != null )
         reporter.infoProvided( new Report(this,"Fixture","Cleaned up!") );
   }
 
   /**
    * Tests the ability to insert some items into the set.  Also tests
    * that values already in the set won't be added again.
    */
   public void testInsertion( org.suiterunner.Reporter r )
   {
      pause();
 
      if( reporter == null ) reporter = r;
 
      // Verify each unique value can be added:
      for( int i = 0; i < 1000; i++ )
         verify( intSet.insert(i), "Insert " + Integer.toString(i) );
 
      // Verify duplicate values can't be added:
      for( int i = 0; i < 1000; i++ )
         verify( !intSet.insert(i), "Should fail to insert " + Integer.toString(i));
 
      // Verify duplicate values can't be added, going backwards:
      for( int i = 999; i >= 0; i-- )
         verify( !intSet.insert(i), "Should fail to insert " + Integer.toString(i));
   }
 
   /**
    * Tests removal of items from the set.
    */
   public void testRemoval( org.suiterunner.Reporter r )
   {
      pause();
      if( reporter == null ) reporter = r;
      verify( intSet.insert(0),  "First insert." ); 
      verify( intSet.member(0),  "Check membership." );
      verify( intSet.remove(0),  "Remove." );
      verify( !intSet.member(0), "Check membership." );
      verify( !intSet.remove(0), "Remove." );
   }
 
   /**
    * Tests removing specific values, based upon where they might
    * be located in the list (which is somewhat, but not necessarily
    * based on knowledge of the set's implementation).
    */
   public void testDeletePositions( org.suiterunner.Reporter r )
   {
      pause();
      if( reporter == null ) reporter = r;
      // Verify each unique value can be added:
      for( int i = 0; i < 5; i++ )
         verify( intSet.insert(i), "Insert " + Integer.toString(i) );
 
      verify( intSet.remove(0), "Remove 0" ); // start.
      verify( intSet.remove(2), "Remove 2" );   // middle
      verify( intSet.remove(4), "Remove 4" );   // end
 
      verify( !intSet.member(0), "0 shouldn't be a member." );
      verify(  intSet.member(1), "1 should be a member."  );
      verify( !intSet.member(2), "2 shouldn't be a member."  );
      verify(  intSet.member(3), "3 should be a member."  );
      verify( !intSet.member(4), "4 shouldn't be a member."  );
 
      // remove the other two:
      verify( intSet.remove(1), "Remove 1" );   // start
      verify( intSet.remove(3), "Remove 3" );   // end
 
      for( int i = 0; i < 5; i++ )
         verify( !intSet.member(i), Integer.toString(i) + " shouldn't be a member." );
 
      // try repopulating it:
      for( int i = 0; i < 5; i++ )
         verify( intSet.insert(i), "Insert " + Integer.toString(i) );
 
      for( int i = 0; i < 5; i++ )
         verify( intSet.member(i), Integer.toString(i) + " should be a member." );
   }
 
   /**
    * Tests inserting semi-random values.
    */
   public void testRandomInsertion( org.suiterunner.Reporter r ) throws Exception
   {
      java.util.Random randy = new java.util.Random();
      
      long timeout = new Date().getTime() + 10000;  // Give up after 10 seconds.
      int i = 0;
      for( ; intSet.insert( randy.nextInt(100000) ); i++ )
         if( new Date().getTime() > timeout )
            throw new Exception( "This is taking too long!" );
 
      reporter.infoProvided( new Report( this,   
                                         "testRandomInsertion()",
                                         "Added " +Integer.toString(i)+ 
                                         " integers before getting a duplicate!") );      
   }
 
   /**
    * The entry point for the class; reallyjust prints a suggestion to the 
    * console to use the SuiteRunner UI.
    */ 
   public static void main( String []args )
   {
      System.out.println("Run me with the SuiteRunner UI!");
   }
}
 
/*
 * LinkedListIntSet.java                                       Matt Gerrans
 *                                                            February 2003
 *
 * Simple demo of a set of integers implemented as linked list.
 *
 * Copyright 2003, Matt Gerrans.
 *
 * Turning in this code as homework is a violation of ethical principals,
 * and punishable by severe penalties, even if you change the variable
 * names.
 */
 
/**
 * Set of integers implemented as a linked list.   Too bad Java doesn't have
 * generics, eh?   Be patient, they're coming...
 *
 * @author Matt Gerrans
 */
public class LinkedListIntSet implements IntSet
{
   /**
    * The Item object stores the values in the list.   This is a node
    * object for containing ints in a singly-linked list, really.
    */
   private class Item
   {
      private int value;
      private Item next;
 
      public Item( int i ) { value = i; }
 
      public int  getValue() { return value; }
      // The absence of a setter keeps the value part immutable.
   }
 
   private Item rootItem;  // The buck starts here.
 
   /**
    * Inserts an integer value in the list, if it isn't already there.
    *
    * @param  value - The value to insert.
    * @return true if the value was inserted, something else otherwise.
    */
   public boolean insert( int value )
   {
      if( !member(value) )
      {
         if(rootItem == null)
            rootItem = new Item(value);
         else
         {
            Item temp = rootItem;
            rootItem = new Item(value);
   
            rootItem.next = temp;
         }
         return true;
      }
      return false;  // Already in there.
   }
 
   /**
    * Removes an int from the list, if it is in the list.  If it isn't in 
    * the list, it will be left alone.   Are you confused?
    *
    * @param  value - The value to remove.
    * @return true only if the value <i>was</i> present and was removed.
    */
   public boolean remove( int i )
   {
      Item prev = rootItem;
 
      for( Item item = rootItem; item != null; item = item.next )
      {
         if( item.value == i )
         {
            // Found it!   ...but where in the list are we?
            if( item == rootItem )
               rootItem = rootItem.next;
            else
            {
               // If we got here, we're somewhere in the middle, or at the end
               // of the list.   Remove this item by setting the previous item
               // to point to the next one.
               prev.next = item.next;
            }
            return true;
         }
         prev = item;
      }
      return false;        // Didn't find it.
   }
 
   /**
    * Checks whether an integer value is in the list.
    *
    * @param  value - The value to check find.
    * @return true if the value was found.
    */
   public boolean member( int i )
   {
      for( Item item = rootItem; item != null; item = item.next )
         if( item.getValue() == i )
            return true;
      return false;        // Didn't find it.
   }
 
}