finiteAutomata
Class IntSet

java.lang.Object
  extended by finiteAutomata.IntSet

public class IntSet
extends java.lang.Object

Finite set of integers, used to represent sets of states in finite automata. The elements of each IntSet are maintained in ascending order.

Data Fields: The set of integers is stored in a sorted Vector of Integers.

IntSet has two special methods to support conversion from NFA to DFA, based on binary arithmetic.
1. intValue() returns a uniquely-determined integer corresponding to this IntSet (assuming all elements are >= 0).
Example: intValue of [1,3,4] = 2^1 + 2^3 + 2^4 = 33.
2. setValue(int n) takes a non-negative integer n and returns a uniquely-determined Intset corresponding to n.
Example: setValue of 17 is [0,4] because 17 = 2^0 + 2^4.

Version:
Fall 2007
Author:
Barbara Wahl

Field Summary
protected  java.util.Vector data
          stores the int values as Integers
 
Constructor Summary
IntSet()
          0-parameter constructor.
IntSet(int n)
          1-parameter constructor.
IntSet(IntSet current)
          Copy constructor.
 
Method Summary
 void add(int n)
          Adds a given integer to this IntSet.
protected  void addDialog()
          Adds a user-specified integer to this IntSet.
 boolean contains(int n)
          Returns true if a given integer is in this IntSet.
 int elementAt(int i)
          Returns the int value of the ith element of this IntSet.
 boolean equals(java.lang.Object other)
          Returns true if other has exactly the same elements as this IntSet.
 int indexOf(int n)
          Returns index (position) of a given integer in this IntSet.
 int intValue()
          Returns a unique non-negative integer (bijection from finite subsets of W to W) determined by this set of non-negative integers.
protected  void intValueDialog()
          Prints the intValue of this IntSet.
 boolean isEmpty()
          Returns true if this IntSet is empty.
static void main(java.lang.String[] args)
           
 int max()
          Returns the maximum element.
protected  void menuHandler(int choice)
          Handles user's menu choice.
 int min()
          Returns the minimum element.
protected  int queryChoice()
          Reads and returns user's menu choice.
 void remove(int n)
          Removes a given integer from this IntSet.
protected  void removeDialog()
          Removes a user-specified integer from this IntSet.
protected  void runMenu()
          Repeatedly queries user for desired action & responds.
static IntSet setValue(int i)
          Calculates a unique IntSet of non-negative integers corresponding a given integer i >= 0 (bijection from W to finite subsets of W).
protected  void setValueDialog()
          Asks user for an integer >=0 and prints its setValue.
 int size()
          Returns number of elements in this IntSet.
 boolean subsetOf(IntSet other)
          Returns true if "this" is a subset of "other".
 java.lang.String toString()
          Returns a String representation of this IntSet using square brackets and commas.
 IntSet union(IntSet other)
          Adds all the elements of "other" to this IntSet, forming the union.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

data

protected java.util.Vector data
stores the int values as Integers

Constructor Detail

IntSet

public IntSet()
0-parameter constructor.

Postcondition:
constructs an empty IntSet

IntSet

public IntSet(int n)
1-parameter constructor. Creates a set with one element.

Parameters:
n - the element to be included in this IntSet
Postcondition:
constructs a new IntSet with one element, n

IntSet

public IntSet(IntSet current)
Copy constructor.

Parameters:
current - the Intset to be copied
Precondition:
current is not null
Postcondition:
constructs a new intSet via deep copy of current
Method Detail

elementAt

public int elementAt(int i)
Returns the int value of the ith element of this IntSet.

Parameters:
i - index
Returns:
int value of the ith element
Precondition:
0 <= i < data.size()

size

public int size()
Returns number of elements in this IntSet.

Returns:
data.size()

isEmpty

public boolean isEmpty()
Returns true if this IntSet is empty.

Returns:
data.isEmpty()

min

public int min()
Returns the minimum element.

Returns:
smallest element in this IntSet
Precondition:
this IntSet is not empty

max

public int max()
Returns the maximum element.

Returns:
largest element in this IntSet
Precondition:
this IntSet is not empty

toString

public java.lang.String toString()
Returns a String representation of this IntSet using square brackets and commas.

Overrides:
toString in class java.lang.Object
Returns:
data.toString()

contains

public boolean contains(int n)
Returns true if a given integer is in this IntSet.

Parameters:
n - integer to be searched for
Returns:
true iff n is in this IntSet

indexOf

public int indexOf(int n)
Returns index (position) of a given integer in this IntSet.

Parameters:
n - integer to be searched for
Returns:
index of n in data, or -1 if not found

add

public void add(int n)
Adds a given integer to this IntSet.

Parameters:
n - integer to be added
Postcondition:
n is added to this IntSet (unless it is already present), the underlying vector (data) is maintained in ascending order

remove

public void remove(int n)
Removes a given integer from this IntSet.

Parameters:
n - integer to be removed
Postcondition:
if found, n is removed from this IntSet

union

public IntSet union(IntSet other)
Adds all the elements of "other" to this IntSet, forming the union.

Parameters:
other - set to be unioned with this IntSet
Returns:
set union of "this" and "other" (no repetitions, ascending order)
Precondition:
other is not null
Postcondition:
this IntSet is changed (unless other is a subset of this)

subsetOf

public boolean subsetOf(IntSet other)
Returns true if "this" is a subset of "other".

Parameters:
other - the potential superset
Returns:
true iff every element of this IntSet is also in other
Precondition:
other is not null

equals

public boolean equals(java.lang.Object other)
Returns true if other has exactly the same elements as this IntSet.

Overrides:
equals in class java.lang.Object
Parameters:
other - the IntSet with which this will be compared
Returns:
true iff containment holds each way
Precondition:
other is a non-null IntSet

intValue

public int intValue()
Returns a unique non-negative integer (bijection from finite subsets of W to W) determined by this set of non-negative integers.

Returns:
sum of 2^i where i varies over the elements of this IntSet
Precondition:
this IntSet is non-null and has no negative values

setValue

public static IntSet setValue(int i)
Calculates a unique IntSet of non-negative integers corresponding a given integer i >= 0 (bijection from W to finite subsets of W).

Parameters:
i - the integer to be converted to an IntSet
Returns:
IntSet determined by expressing i in binary notation; if the bit in the 2^j place is non-zero then j is placed in the IntSet

runMenu

protected void runMenu()
Repeatedly queries user for desired action & responds.

Postcondition:
displays menu options and responds, repeatedly, until user chooses to exit

queryChoice

protected int queryChoice()
Reads and returns user's menu choice.

Returns:
integer choice code (1 thru 5)

menuHandler

protected void menuHandler(int choice)
Handles user's menu choice.

Parameters:
choice - choice code to be acted on
Precondition:
1 < choice < 6
Postcondition:
runs dialog to add an element, remove an element, find an IntValue, or find a setValue, according to choice code

addDialog

protected void addDialog()
Adds a user-specified integer to this IntSet.

Postcondition:
if the integer is not already present, it is added

removeDialog

protected void removeDialog()
Removes a user-specified integer from this IntSet.

Postcondition:
if the integer was present, it is removed

intValueDialog

protected void intValueDialog()
Prints the intValue of this IntSet.


setValueDialog

protected void setValueDialog()
Asks user for an integer >=0 and prints its setValue.


main

public static void main(java.lang.String[] args)