This is in java and it is building a Binomial Queues. The packaging division at

Question

This is in java and it is building a Binomial Queues.

The packaging division at Complex Circuits Inc. is assigned the task of packing integrated circuit chips into boxes for shipment. Boxes come in different sizes and the capacity of a box (in terms of number of chips) is an exponent of 2, i.e., boxes can hold 1, 2, 4, 8, 16….chips. Each chip has the following parameters:

weight – a positive, real number in the range of 0-1

id – positive integer in the range of 1000-9999

priority – a positive integer in the range of 1-100

Boxes carrying chips arrive on the production line at the end of each hour in lots. The maximum number of chips that can be produced in each lot is 128. The software developer for the packaging division plans to use a binomial queue to represent the data structure for the chips, boxes and lots - each lot corresponds to a binomial queue, each box corresponds to a binomial tree and each chip corresponds to a node in the binomial tree.

Write a program in Java that does the following:

Input:

input the number of lots

randomly generate a number in the range of 1-128, to denote the number of chips produced in each lot; instantiate the chip object for each chip

for each lot, insert each chip object into a binomial queue, using the priority parameter as the key. Make sure that you satisfy the heap order property while creating the binomial queue. You should randomly generate each chip's parameters within the prescribed range, when you instantiate the chip object

deleteMin(int lot): deletes the chip with the minimum key in the lot (remember to adjust nodes after the delete to restore the binomial queue structure)

levelOrder(int lot): prints the level order traversal of each binomial tree in the binomial queue corresponding to the parameter lot. Nodes within each level should be put inside square brackets while printing; each node's (chip's) parameters should be put inside curly braces. (see sample I/O below)

Finally, you need to write a user interface for the program. Sample input and output are given below:

> Enter the number of lots in this production: 3

Randomly generating number of chips in each lot...

Lot 1: 7

Lot 2: 23

Lot 3: 4

Generating the chips for each lot:

Lot 1, Chip 1: {0.2, 3425, 14}

Lot 1, Chip 2: {0.7, 1298, 7}

Lot 1, Chip 3: {0.9, 1389, 15}

Lot 1, Chip 4: {0.3, 1929, 35}

Lot 1, Chip 5: {0.5, 9526, 92}

Lot 1, Chip 6: {0.1, 1748, 5}

Lot 1, Chip 7: {0.2, 7284, 51}

Lot 2, Chip 1: {0.5, 1357, 45}

Lot 2, Chip 23: {0.7, 3313, 39}

Lot 3, Chip 1: {0.7, 3313, 39}

Lot 3, Chip 4: {0.4, 7163, 27}

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 2

> Enter the lot number: 1

> Printing level order traversal of lot 1:

Box 1: [{0.2, 7284, 51}]

Box 2: [{0.1, 1748, 5}] [{0.5, 9526, 92}]

Box 3: [{0.7, 1298, 7}] [{0.2, 3425, 14} {0.9, 1389, 15}] [{0.3, 1929, 35}]

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 1

> Enter the lot number: 1

> Deleted minimum priority chip: {0.1, 1748, 5}

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 2

> Enter the lot number: 1

> Printing level order traversal of lot 1:

Box 1:

Box 2: [{0.2, 7284, 51}] [{0.5, 9526, 92}]

Box 3: [{0.7, 1298, 7}] [{0.2, 3425, 14} {0.9, 1389, 15}] [{0.3, 1929, 35}]

> Enter a choice: 1) deleteMin(lot), 2) levelOrder (lot), 3) exit: 3

Explanation / Answer

public class BinomialQueue
{
public BinomialQueue( )
{
theTrees = new BinomialNode[ MAX_TREES ];
makeEmpty( );
}

public void merge( BinomialQueue pqr ) throws Overflow
{
if( this == pqr )
return;

if( currentSize + pqr.currentSize > capacity( ) )
throw new Overflow( );

currentSize += pqr.currentSize;

BinomialNode carry = null;
for( int i = 0, j = 1; j <= currentSize; i++, j *= 2 )
{
BinomialNode a1 = theTrees[ i ];
BinomialNode a2 = pqr.theTrees[ i ];

int whichCase = a1 == null ? 0 : 1;
whichCase += a2 == null ? 0 : 2;
whichCase += carry == null ? 0 : 4;

switch( whichCase )
{
case 0:
case 1:
break;
case 2:
theTrees[ i ] = a2;
pqr.theTrees[ i ] = null;
break;
case 4:
theTrees[ i ] = carry;
carry = null;
break;
case 3:
carry = combineTrees( a1, a2 );
theTrees[ i ] = pqr.theTrees[ i ] = null;
break;
case 5:
carry = combineTrees( a1, carry );
theTrees[ i ] = null;
break;
case 6:
carry = combineTrees( a2, carry );
pqr.theTrees[ i ] = null;
break;
case 7:
theTrees[ i ] = carry;
carry = combineTrees( a1, a2 );
pqr.theTrees[ i ] = null;
break;
}
}

for( int k = 0; k < pqr.theTrees.length; k++ )
pqr.theTrees[ k ] = null;
pqr.currentSize = 0;
}

private static BinomialNode combineTrees( BinomialNode a1,
BinomialNode a2 )
{
if( a1.element.compareTo( a2.element ) > 0 )
return combineTrees( a2, a1 );
a2.nextSibling = a1.leftChild;
a1.leftChild = a2;
return a1;
}

public void insert( Comparable x ) throws Overflow
{
BinomialQueue BinomialQueue( );
oneItem.currentSize = 1;
oneItem.theTrees[ 0 ] = new BinomialNode( x );

merge( oneItem );
}

public Comparable findMin( )
{
if( isEmpty( ) )
return null;

return theTrees[ findMinIndex( ) ].element;
}

  
private int findMinIndex( )
{
int i;
int minIndex;

for( i = 0; theTrees[ i ] == null; i++ )
;

for( minIndex = i; i < theTrees.length; i++ )
if( theTrees[ i ] != null &&
theTrees[ i ].element.compareTo( theTrees[ minIndex ].element ) < 0 )
minIndex = i;

return minIndex;
}

public Comparable deleteMin( )
{
if( isEmpty( ) )
return null;

int minIndex = findMinIndex( );
Comparable minItem = theTrees[ minIndex ].element;

BinomialNode deletedTree = theTrees[ minIndex ].leftChild;

BinomialQueue deletedQueue = new BinomialQueue( );
deletedQueue.currentSize = ( 1 << minIndex ) - 1;
for( int j = minIndex - 1; j >= 0; j-- )
{
deletedQueue.theTrees[ j ] = deletedTree;
deletedTree = deletedTree.nextSibling;
deletedQueue.theTrees[ j ].nextSibling = null;
}

theTrees[ minIndex ] = null;
currentSize -= deletedQueue.currentSize + 1;

try
{ merge( deletedQueue ); }
catch( Overflow e ) { }
return minItem;
}

public boolean isEmpty( )
{
return currentSize == 0;
}

public boolean isFull( )
{
return currentSize == capacity( );
}

  
public void makeEmpty( )
{
currentSize = 0;
for( int i = 0; i < theTrees.length; i++ )
theTrees[ i ] = null;
}

private static final int MAX_TREES = 14;

private int currentSize;
private BinomialNode [ ] theTrees;
  
private int capacity( )
{
return ( 1 << theTrees.length ) - 1;
}

public static void main( String [ ] args )
{
int numItems = 10000;
BinomialQueue l = new BinomialQueue( );
BinomialQueue l1 = new BinomialQueue( );
int i = 37;

System.out.println( "Starting check." );
try
{
for( i = 37; i != 0; i = ( i + 37 ) % numItems )
if( i % 2 == 0 )
l1.insert( new MyInteger( i ) );
else
l.insert( new MyInteger( i ) );

l.merge( l1 );
for( i = 1; i < numItems; i++ )
if( ((MyInteger)( l.deleteMin( ) )).intValue( ) != i )
System.out.println( "Oops! " + i );
}
catch( Overflow e ) { System.out.println( "Unexpected overflow" ); }
System.out.println( "Check done." );
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.