finiteAutomata
Class IntSet

java.lang.Object
  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)