Homework 4 Code Refactoring
1. (1 point) Read http://en.wikipedia.org/wiki/Code refactoring first. Use your own word to briefly
explain what is code refactoring?
2. (4 points) The following code has passed all test cases. First read the code and understand how the
code works. Then refactoring the code little by little. While you are refactoring the code, write down
the changes that you made. For example:
1. The comment should not use vague word. It should not use ”bubble down to its appropriate
position”. It should say ”bubble down until both its children are greater”
2. ...
3. ...
The bubbleDown method in Heap.java of Assignment 3.
/∗ ∗
∗ The e n t r y s h o u l d b e b u b b l e d down t o i t s a p p r o p r i a t e p o s i t i o n
∗ @param p
∗/
@TimeComplexity ( ”O( l g n ) ” )
p r i v a t e void bubbleDown ( P o s i t i o n <Entry<K, V>> p )
{
/ / W h i l e t h e n o d e s t i l l n e e d s t o b e b u b b l e d down , k e e p l o o p i n g t h e f o l l o w i n g .
/ / TCJ : B e c a u s e t h e maximum a m o u n t o f t i m e s t h i s l o o p c a n r u n i s d e t e r m i n e d b y t h e h e i g h t
// o f t h e t r e e , w h i c h i s e q u a l t o l g n , t h a t i s t h e t i m e c o m p l e x i t y o f t h e f u n c t i o n .
w h i l e ( t r e e . i s I n t e r n a l ( p ) &&
( t r e e . h a s L e f t ( p ) && ( t r e e . l e f t ( p ) . e l e m e n t ( ) . g e t K e y ( ) . compareTo ( p . e l e m e n t ( ) . g e t K e y ( ) ) > 0 ) | |
( t r e e . h a s R i g h t ( p ) && t r e e . r i g h t ( p ) . e l e m e n t ( ) . g e t K e y ( ) . compareTo ( p . e l e m e n t ( ) . g e t K e y ( ) ) > 0 ) ) )
{
boolean l e s s T h a n L e f t = f a l s e ;
boolean l e s s T h a n R i g h t = f a l s e ;
i f ( t r e e . h a s L e f t ( p ) && t r e e . l e f t ( p ) . e l e m e n t ( ) . g e t K e y ( ) . compareTo ( p . e l e m e n t ( ) . g e t K e y ( ) ) > 0 )
{
l e s s T h a n L e f t = true ;
}
i f ( t r e e . h a s R i g h t ( p ) && t r e e . r i g h t ( p ) . e l e m e n t ( ) . g e t K e y ( ) . compareTo ( p . e l e m e n t ( ) . g e t K e y ( ) ) > 0 )
{
l e s s T h a n R i g h t = true ;
}
i f ( l e s s T h a n L e f t && l e s s T h a n R i g h t )
{
i f ( t r e e . l e f t ( p ) . e l e m e n t ( ) . g e t K e y ( ) . compareTo ( t r e e . r i g h t ( p ) . e l e m e n t ( ) . g e t K e y ( ) ) > 0 )
{
t r e e . swapElements ( p , t r e e . l e f t ( p ) ) ;
p = tree . l e f t (p ) ;
}
else
{
t r e e . swapElements ( p , t r e e . r i g h t ( p ) ) ;
p = tree . right (p ) ;
}
}
e l s e i f ( l e s s T h a n L e f t && ! l e s s T h a n R i g h t )
{
t r e e . swapElements ( p , t r e e . l e f t ( p ) ) ;
p = tree . l e f t (p ) ;
}
e l s e i f ( ! l e s s T h a n L e f t && l e s s T h a n R i g h t )
{
t r e e . swapElements ( p , t r e e . r i g h t ( p ) ) ;
p = tree . right (p ) ;
}
}
}
(a) List of changes
1
(b) The new source code
3. (4 points) Do the same as previous question for the following code.
The insert method in OrderPQ.java of Assignment 3.
/∗ ∗ A d d s a n e n t r y t o t h e P r i o r i t y Q u e u e i n i t s p r o p e r o r d e r .
∗
∗ @param k e y The k e y t o f i n d t h e e n t r y a d d e d .
∗ @param v a l u e The v a l u e t h a t i s b e i n g s t o r e d i n t h e e n t r y .
∗ @ r e t u r n r e t u r n s t h e new e n t r y a d d e d t o t h e P r i o r i t y Q u e u e .
∗ @throws I n v a l i d K e y E x c e p t i o n
∗/
@TimeComplexity ( ”O( n ) ” )
p u b l i c Entry<K, V> i n s e r t (K key , V v a l u e ) throws I n v a l i d K e y E x c e p t i o n
{
// D e c l a r e method ’ s v a r i a b l e s .
PQEntry<K, V> r e t = new PQEntry<K, V>(key , v a l u e ) ;
boolean added = f a l s e ;
// I f t h e s i z e o f t h e Queue i s 0 , add the entry to the first index .
i f ( s i z e == 0 )
{
/ / Add t h e d a t a a n d i n c r e m e n t size .
d a t a . add ( 0 , r e t ) ;
++ s i z e ;
// R e t u r n t h e entry that was added .
return r e t ;
}
/ / TCJ : B e c a u s e we d o n o t k n o w w h e r e we a r e s u p p o s e d t o a d d t h e e n t r y , we
// need t o i t e r a t e t h r o u g h t h e e n t i r e s e q u e n c e t o f i n d i t , c a u s i n g i t t o run
// i n O( n ) t i m e .
for ( int index = 0; index < d a t a . s i z e ( ) ; ++i n d e x )
{
// D e t e r m i n e s i f t h e e n t r y h a s f o u n d i t s p r o p e r p l a c e .
i f ( d a t a . a t I n d e x ( i n d e x ) . e l e m e n t ( ) . g e t K e y ( ) . compareTo ( r e t . g e t K e y ( ) ) > 0 )
{
// i f i t has , add i t i n and b r e a k t h e l o o p .
d a t a . add ( i n d e x , r e t ) ;
index = data . s i z e ( ) ;
added = t r u e ;
}
}
// I f t h e a d d e d v a r i a b l e i s s t i l l f a l s e , t h i s means
// t h e d a t a must go i n t h e n e x t empty i n d e x .
i f ( ! added )
{
/ / Add t h e d a t a t o t h e n e x t e m p t y i n d e x .
d a t a . addLast ( r e t ) ;
}
// I n c r e m e n t size and return the new entry .
s i z e ++;
return r e t ;
}
(a) List of changes
(b) The new source code
4. (1 point) Print and sign all team member’s names below to acknowledge that you have carefully re-
viewed the code line by line with your team and refactored the code to your best. Each team needs to
have two or three team members. Each student may work in multiple teams.
