Can you do my assignment for programming ?

profileomarazjzq582
comp2402a2.zip
Home>Computer Science homework help>Can you do my assignment for programming ?

comp2402a2/.DS_Store

__MACOSX/comp2402a2/._.DS_Store

comp2402a2/ArrayDeque.java

comp2402a2/ArrayDeque.java

package  comp2402a2 ;

import  java . util . AbstractList ;

/**
 * An implementation of the List interface that allows for fast modifications
 * at both the head and tail.
 * 
 * The implementation is as a circular array.  The List item of rank i is stored
 * at a[(j+i)%a.length].  Insertions and removals at position i take 
 * O(1+min{i, size()-i}) amortized time.
 *  @author  morin
 *
 *  @param  <T> the type of objects stored in this list
 * TODO: Implement addAll() and removeAll() efficiently
 */
public   class   ArrayDeque < T >   extends   AbstractList < T >   {
     /**
     * The class of elements stored in this queue
     */
     protected   Factory < T >  f ;
    
     /**
     * Array used to store elements
     */
     protected  T []  a ;
    
     /**
     * Index of next element to de-queue
     */
     protected   int  j ;
    
     /**
     * Number of elements in the queue
     */
     protected   int  n ;
    
     /**
     * Grow the internal array
     */
     protected   void  resize ()   {
        T []  b  =  f . newArray ( Math . max ( 2 * n , 1 ));
         for   ( int  k  =   0 ;  k  <  n ;  k ++ )  
            b [ k ]   =  a [( j + k )   %  a . length ];
        a  =  b ;
        j  =   0 ;
     }
    
     /**
     * Constructor
     */
     public   ArrayDeque ( Class < T >  t )   {
        f  =   new   Factory < T > ( t );
        a  =  f . newArray ( 1 );
        j  =   0 ;
        n  =   0 ;
     }
    
     public   int  size ()   {
         return  n ;
     }
    
     public  T get ( int  i )   {
         if   ( i  <   0   ||  i  >  n - 1 )   throw   new   IndexOutOfBoundsException ();
         return  a [( j + i ) % a . length ];
     }
    
     public  T set ( int  i ,  T x )   {
         if   ( i  <   0   ||  i  >  n - 1 )   throw   new   IndexOutOfBoundsException ();
        T y  =  a [( j + i ) % a . length ];
        a [( j + i ) % a . length ]   =  x ;
         return  y ;
     }
    
     public   void  add ( int  i ,  T x )   {
         if   ( i  <   0   ||  i  >  n )   throw   new   IndexOutOfBoundsException ();
         if   ( n + 1   >  a . length )  resize ();
         if   ( i  <  n / 2 )   {    // shift a[0],..,a[i-1] left one position
            j  =   ( j  ==   0 )   ?  a . length  -   1   :  j  -   1 ;   // (j-1) mod a.length
             for   ( int  k  =   0 ;  k  <=  i - 1 ;  k ++ )
                a [( j + k ) % a . length ]   =  a [( j + k + 1 ) % a . length ];
         }   else   {          // shift a[i],..,a[n-1] right one position
             for   ( int  k  =  n ;  k  >  i ;  k -- )
                a [( j + k ) % a . length ]   =  a [( j + k - 1 ) % a . length ];
         }
        a [( j + i ) % a . length ]   =  x ;
        n ++ ;
     }
    
     public  T remove ( int  i )   {
         if   ( i  <   0   ||  i  >  n  -   1 )   throw   new   IndexOutOfBoundsException ();
        T x  =  a [( j + i ) % a . length ];
         if   ( i  <  n / 2 )   {    // shift a[0],..,[i-1] right one position
             for   ( int  k  =  i ;  k  >   0 ;  k -- )
                a [( j + k ) % a . length ]   =  a [( j + k - 1 ) % a . length ];
            j  =   ( j  +   1 )   %  a . length ;
         }   else   {          // shift a[i+1],..,a[n-1] left one position
             for   ( int  k  =  i ;  k  <  n - 1 ;  k ++ )
                a [( j + k ) % a . length ]   =  a [( j + k + 1 ) % a . length ];
         }
        n -- ;
         if   ( 3 * n  <  a . length )  resize ();
         return  x ;
     }
    
     public   void  clear ()   {
        n  =   0 ;
        resize ();
     }
    

}

__MACOSX/comp2402a2/._ArrayDeque.java

comp2402a2/BDeque.java

comp2402a2/BDeque.java

package  comp2402a2 ;

public   class   BDeque < T >   extends   ArrayDeque < T >   {
     public   BDeque ( int  b ,   Class < T >  clz )   {
         super ( clz );
        a  =  f . newArray ( b );
     }
    
     protected   void  resize ()   {
         // do nothing - BDeques have a fixed capacity
     }
    
     public   void  pushFront ( T x )   {
        add ( 0 ,  x );
     }
    
     public  T popFront ()   {
         return  remove ( 0 );
     }
    
     public   void  pushBack ( T x )   {
        add ( n ,  x );
     }
    
     public  T popBack ()   {
         return  remove ( n - 1 );
     }
}

__MACOSX/comp2402a2/._BDeque.java

comp2402a2/BulkArrayDeque.java

comp2402a2/BulkArrayDeque.java

package  comp2402a2 ;
import  java . util . * ;

public   class   BulkArrayDeque < T >   extends   ArrayDeque < T >   {
     public   BulkArrayDeque ( Class < T >  clazz )   {
         super ( clazz );
     }
    
     /**
     * Add all the elements of c to this array deque, starting
     * at position i
     *  @param  i
     *  @param  c
     */
     public   boolean  addAll ( int  i ,   Collection <?   extends  T >  c )   {
         boolean  modified  =   false ;
        
         int  newSize  =   Math . max ( n  +  c . size (), i  +  c . size ());
        T []  b  =  f . newArray ( newSize );
        
         for   ( int  k  =   0 ;  k  <  i ;  k ++ ){
            b [ k ]   =  a [( k )   %  a . length ];
         }
        
         int  itemsLeft  =  n  -  i ;
        
         if ( n  <  i ){
            modified  =   true ;
         }
        
         Iterator <?   extends  T >  e  =  c . iterator ();
         while   ( e . hasNext ())   {
            b [ i ++ ]   =  e . next ();
            modified  =   true ;
         }
        
         if ( itemsLeft  >   0 ){
             for   ( int  k  =   0 ;  k  <  itemsLeft ;  k ++ ){
                b [ newSize  -  itemsLeft  +  k ]   =  a [( n  -  itemsLeft  +  k )   %  a . length ];
             }
         }
        
        a  =  b ;
        j  =   0 ;
        n  =  newSize ;
        
         return  modified ;
     }
    
     public   static   void  main ( String []  args )   {
         if   ( ! Tester . testPart1 ( new   BulkArrayDeque < Integer > ( Integer . class )))   {
             System . err . println ( "Test failed!" );
             System . exit ( - 1 );
         }
     }
}

__MACOSX/comp2402a2/._BulkArrayDeque.java

comp2402a2/Factory.java

comp2402a2/Factory.java

package  comp2402a2 ;

import  java . lang . reflect . Array ;

/**
 * An ugly little class for allocating objects and arrays of generic
 * type T.  This is needed to work around limitations of Java generics.
 */
public   class   Factory < T >   {
     Class < T >  t ;
    
     /**
     * Return the type associated with this factory
     *  @return
     */
     public   Class < T >  type ()   {
         return  t ;
     }
    
     /**
     * Constructor - creates a factory for creating objects and 
     * arrays of type t(=T)
     *  @param  t0
     */
     public   Factory ( Class < T >  t0 )   {
        t  =  t0 ;
     }
    
     /**
     * Allocate a new array of objects of type T.
     *  @param  n the size of the array to allocate
     *  @return  the array allocated
     */
    @ SuppressWarnings ({ "unchecked" })
     protected  T []  newArray ( int  n )   {
         return   ( T []) Array . newInstance ( t ,  n );
     }

     /**
     * 
     *  @return
     */
     public  T newInstance ()   {
        T x ;
         try   {
            x  =  t . newInstance ();
         }   catch   ( Exception  e )   {
            x  =   null ;
         }
         return  x ;
     }
}

__MACOSX/comp2402a2/._Factory.java

comp2402a2/Fourque.java

comp2402a2/Fourque.java

package  comp2402a2 ;

import  java . util . AbstractList ;

/**
 * Fourque: an implementation of the List interface 
 * that allows for fast modifications at the FOUR places 
 * in the list: front, 1/3 in, 2/3 in and the back.
 *
 * Modify the methods so that 
 *  -set/get have constant runtime
 *  -add/remove have runtime 
 *    O(1 + min{ i, size()-i, |size()/3-i|, |2size()/3-i| })
 *
 *  @author  mjh - 2016
 *  @param  <T> the type of objects stored in this list
 */
 
public   class   Fourque < T >   extends   AbstractList < T >   {

     /**
     * The class of elements stored in this queue
     */
     protected   Factory < T >  f ;
    
     /**
     * Array used to store elements
     */
     protected  T []  a ;
    

    
     /**
     * Number of elements in the list
     */
     protected   int  n ;

     /**
     * Constructor
     */
     public   Fourque ( Class < T >  t )   {
        n  =   0 ;
        f  =   new   Factory < T > ( t );
        a  =  f . newArray ( 1000 );     
     }
    
     /** 
     * public methods
     */
     public   int  size ()  
     {
         return  n ;
     }
    
     public  T get ( int  i )  
     {
         // calculate access point
         int  p  =  i ;
         if ( n  >=   4 )
         {
            p  =  i  /   ( n / 4 );
            p  =  p  *   ( n / 4 );
            p  =  p  +   ( i - p );
         }
        
         // return value
         return  a [ p ];
     }
    
    
     public  T set ( int  i ,  T x )  
     {
         // calculate access point
         int  p  =  i ;
         if ( n  >=   4 )
         {
            p  =  i  /   ( n / 4 );
            p  =  p  *   ( n / 4 );
            p  =  p  +   ( i - p );
         }
        
         // get y
        T y  =   a [ p ];
        
         // save value
        a [ p ]   =  x ;
        
         return  y ;
     }
    
     public   void  add ( int  i ,  T x )
     {
         // calculate access point
         int  p  =  i ;
         if ( n  >=   4 )
         {
            p  =  i  /   ( n / 4 );
            p  =  p  *   ( n / 4 );
            p  =  p  +   ( i - p );
         }
        
         // make room
         for ( int  j = n ; j > p ; j -- )
            a [ j ]   =  a [ j - 1 ];
        
         // insert value
        a [ p ]   =  x ;
        n ++ ;
     }
    
     public  T remove ( int  i )  
     {
        
         // calculate access point
         int  p  =  i ;
         if ( n  >=   4 )
         {
            p  =  i  /   ( n / 4 );
            p  =  p  *   ( n / 4 );
            p  =  p  +   ( i - p );
         }
        
         // get y
        T y  =   a [ p ];
        
         // squeeze
         for ( int  j = p ; j < n - 1 ; j ++ )
            a [ i ]   =  a [ i + 1 ];
        
         return  y ;
     }
    
    
     public   void  clear ()  
     {
        n  =   0 ;
     }
    
    
     public   static   void  main ( String []  args )   {
     
    
        //Uncomment and build testPart3 to help test your code 
        //if you wish.
    
        if   ( ! Tester . testPart3 ( new   Fourque < Integer > ( Integer . class )))   {
           System . err . println ( "Test failed!" );
           System . exit ( - 1 );
        }
     
     }
    
    
}

__MACOSX/comp2402a2/._Fourque.java

comp2402a2/RandomQueue.java

comp2402a2/RandomQueue.java

package  comp2402a2 ;

import  java . util . AbstractQueue ;
import  java . util . ArrayList ;
import  java . util . Iterator ;
import  java . util . List ;
import  java . util . Random ;

/**
 * An implementation of a RandomQueue.  This is like a standard queue,
 * except that when we remove an element, we get a random element.
 * 
 * TODO: This implementation requires Theta(size) time on average for
 * poll() operation.  Improve this so that it takes constant time.
 *  @author  morin
 *
 *  @param  <T> the type of elements stored in the queue
 */
public   class   RandomQueue < T >   extends   AbstractQueue < T >   {
     /**
     * The list that stores our queue elements
     */
     List < T >  l ;
    
     /**
     * A source of random numbers
     */
     Random  r ;
    
     /**
     * The index of the next element we will return
     */
     int  next ;

     public   RandomQueue ()   {
        l  =   new   ArrayList < T > ();
        r  =   new   Random ();
     }

     /**
     * Return an iterator for the elements in the queue
     * Note: this iterator does not necessarily enumerate the elements
     * in random order
     */
     public   Iterator < T >  iterator ()   {
         return  l . iterator ();
     }

     public   int  size ()   {
         return  l . size ();
     }

     public   boolean  offer ( T x )   {
        l . add ( x );
        next  =  r . nextInt ( l . size ());
         return   true ;
     }

     /**
     * Return at the next element that will be returned by poll()/remove()
     * without actually removing it
     */
     public  T peek ()   {
         if   ( l . size ()   ==   0 )
             return   null ;
         assert ( next  >=   0   &&  next  <=  l . size () - 1 );
         return  l . get ( next );
     }

     /**
     * Remove and return a random element from the queue
     */
     public  T poll ()   {
         if   ( l . size ()   ==   0 )
             return   null ;
         assert ( next  >=   0   &&  next  <=  l . size () - 1 );
         //T x = l.remove(next);
        
         // get random number
        T x  =   l . get ( next );
        
         // get last element
        T last  =  l . get ( l . size () - 1 );
        
         // put last element here
        l . set ( next ,  last );
        l . remove ( l . size () - 1 );
        
        next  =   ( l . size ()   >   0 )   ?  r . nextInt ( l . size ())   :   - 1 ;
         return  x ;
     }

     /**
     * A stupid method to help with tests
     *  @param  b
     *  @throws  AssertionError
     */
     protected   static   void  myassert ( boolean  b )   throws   AssertionError   {
         if   ( ! b )   {
             throw   new   AssertionError ();
         }
     }

     /**
     * Some test code
     *  @param  args ignored
     */
     public   static   void  main ( String []  args )   {
         if   ( ! Tester . testPart2 ( new   RandomQueue < Integer > ()))   {
             System . err . println ( "Test failed!" );
             System . exit ( - 1 );
         }
     }
}

__MACOSX/comp2402a2/._RandomQueue.java

comp2402a2/RootishArrayStack2.java

comp2402a2/RootishArrayStack2.java

package  comp2402a2 ;

import  java . util . AbstractList ;
import  java . util . ArrayList ;
import  java . util . Iterator ;
import  java . util . List ;
import  java . util . Random ;

/**
 * This class implements the List interface using a collection of arrays of
 * sizes 1, 2, 3, 4, and so on.  The main advantages of this over an 
 * implementation like ArrayList is that there is never more than O(sqrt(size())
 * space being used to store anything other than the List elements themselves.
 * Insertions and removals take O(size() - i) amortized time.
 * 
 * This provides a space-efficient implementation of an ArrayList.  
 * The total space used beyond what is required to store elements is O(sqrt(n)) 
 *  @author  morin
 *
 *  @param  <T> the type of objects stored in this list
 */
public   class   RootishArrayStack2 < T >   extends   AbstractList < T >   {
     /**
     * The type of objects stored in this list
     */
     Factory < T >  f ;
    
     /*
     * The blocks that contains the list elements
     */
     List < BDeque < T >>  blocks ;
    
     /**
     * The number of elements in the list
     */
     int  n ;

     /**
     * Implement an assertion
     */      
     protected   static   void  myassert ( boolean  b )   throws   AssertionError   {
         if   ( ! b )   {
             throw   new   AssertionError ();
         }
     }

     /**
     * Convert a list index i into a block number
     *  @param  i
     *  @return  the index of the block that contains list
     *         element i
     */
      protected   static   int  i2b ( int  i )   {
         double  db  =   ( - 3.0   +   Math . sqrt ( 9   +   8 * i ))   /   2.0 ;
         int  b  =   ( int ) Math . ceil ( db );
         return  b ;  
     }
    
     protected   void  grow ()   {
        blocks . add ( new   BDeque < T > ( blocks . size () + 1 ,  f . type ()));
     }
    
     protected   void  shrink ()   {
         int  r  =  blocks . size ();
         while   ( r  >   0   &&   ( r - 2 ) * ( r - 1 ) / 2   >=  n )   {
            blocks . remove ( blocks . size () - 1 );
            r -- ;
         }
     }
    
     public  T get ( int  i )   {
         if   ( i  <   0   ||  i  >  n  -   1 )   throw   new   IndexOutOfBoundsException ();
         int  b  =  i2b ( i );
         int  j  =  i  -  b * ( b + 1 ) / 2 ;
         return  blocks . get ( b ). get ( j );
     }

     public  T set ( int  i ,  T x )   {
         if   ( i  <   0   ||  i  >  n  -   1 )   throw   new   IndexOutOfBoundsException ();
         int  b  =  i2b ( i );
         int  j  =  i  -  b * ( b + 1 ) / 2 ;
        T y  =  blocks . get ( b ). get ( j );
        blocks . get ( b ). set ( j , x );
         return  y ;
     }
    
     /**
     * TODO: This is too slow - you need to speed it up
     */
     public   void  add ( int  i ,  T x )   {
         if   ( i  <   0   ||  i  >  n )   throw   new   IndexOutOfBoundsException ();
         int  r  =  blocks . size ();
         if   ( r * ( r + 1 ) / 2   <  n  +   1 )  grow ();
         n ++ ;
        
         //blocks.get(blocks.size()-1).add(null);
        
         //for (int j = n-1; j > i; j--)
         //  set(j, get(j-1));
         //set(i, x);
        
         // push ( pop backs )   
         for   ( int  j  =  blocks . size ()   -   1 ;  j  >  i2b ( i );  j -- )   {
            blocks . get ( j ). pushFront ( blocks . get ( j - 1 ). popBack ());
         }
        
         // add x
        blocks . get ( i2b ( i )). add ( i  -  i2b ( i ) * ( i2b ( i ) + 1 ) / 2 ,  x );
            
     }
    
     /**
     * TODO: This is too slow - you need to speed it up
     */
     public  T remove ( int  i )   {
                
         if   ( i  <   0   ||  i  >  n  -   1 )   {
             throw   new   IndexOutOfBoundsException ();
         }
        T x  =  get ( i );
         //for (int j = i; j < n - 1; j++) 
         //  set(j, get(j + 1));
         //n--;
         //int r = blocks.size();
         //if ((r-2)*(r-1)/2 >= n)   shrink();
         //return x;
        
         // remove i
        blocks . get ( i2b ( i )). remove ( i  -  i2b ( i ) * ( i2b ( i ) + 1 ) / 2 );
        
         // pushback (popfront)
         try  
         {
            
             for   ( int  j  =  i2b ( i );  j  <  blocks . size ()   -   1 ;  j ++ )     
                blocks . get ( j ). pushBack ( blocks . get ( j  +   1 ). popFront ());
            
         }

         catch   ( Exception  e )
         {
             
         }
        
         // same as above
        n -- ;
         int  r  =  blocks . size ();
         if   (( r  -   2 )   *   ( r  -   1 )   /   2   >=  n )   {
            shrink ();
         }
         return  x ;
         }
        
     public   int  size ()   {
         return  n ;
     }

     public   RootishArrayStack2 ( Class < T >  t )   {
        f  =   new   Factory < T > ( t );
        n  =   0 ;
        blocks  =   new   ArrayList < BDeque < T >> ();
     }
    
     public   void  clear ()   {
        blocks . clear ();
        n  =   0 ;
     }
    
     protected   static   < T >   boolean  listEquals ( List < T >  l1 ,   List < T >  l2 )   {
         if   ( l1 . size ()   !=  l2 . size ())   {
             return   false ;
         }
         Iterator < T >  i1  =  l1 . iterator ();
         Iterator < T >  i2  =  l2 . iterator ();
         while   ( i1 . hasNext ())   {
             if   ( !  i1 . next (). equals ( i2 . next ()))   {
                 return   false ;
             }
         }
         return   true ;
     }
    
     public   static   void  main ( String []  args )   {
         if   ( ! Tester . testPart4 ( new   RootishArrayStack2 < Integer > ( Integer . class )))   {
             System . err . println ( "Test failed!" );
             System . exit ( - 1 );
         }
     }
}

__MACOSX/comp2402a2/._RootishArrayStack2.java

comp2402a2/Stopwatch.java

comp2402a2/Stopwatch.java

package  comp2402a2 ;

public   class   Stopwatch   {
     protected   long  start ,  stop ;
    
     public   void  start ()   {
        start  =   System . nanoTime ();
     }
    
     public   void  stop ()   {
        stop  =   System . nanoTime ();
     }
    
     public   double  elapsedSeconds ()   {
         return   ( stop - start ) * 1e-9 ;
     }
}

__MACOSX/comp2402a2/._Stopwatch.java

comp2402a2/Tester.java

comp2402a2/Tester.java

package  comp2402a2 ;

import  java . util . * ;

public   class   Tester   {

    
     public   static   boolean  testPart1 ( List < Integer >  ad )   {
         // Your code goes here
         Stopwatch  time  =   new   Stopwatch ();
         boolean  pass  =   true ;
        
         List < Integer >  nums1  =   Arrays . asList ( 0 ,   1 ,   2 ,   3 ,   4 ,   5 ,   6 ,   7 ,   8 ,   9 );
         List < Integer >  nums2  =   Arrays . asList ( 10 ,   11 ,   12 ,   13 ,   14 ,   15 ,   16 ,   17 ,   18 ,   19 );
         List < Integer >  nums3  =   Arrays . asList ( 20 ,   21 ,   22 ,   23 ,   24 ,   25 ,   26 ,   27 ,   28 ,   29 );
         List < Integer >  nums4  =   Arrays . asList ( 30 ,   31 ,   32 ,   33 ,   34 ,   35 ,   36   ,   37 ,   38 ,   39 );
         List < Integer >  result  =   Arrays . asList ( 0 ,   1 ,   2 ,   3 ,   4 ,   10 ,   11 ,   12 ,   13 ,   14 ,   20 ,   21 ,   22 ,   23 ,   24 ,   30 ,   31 ,   32 ,   33 ,   34 ,   35 ,   36 ,   37 ,   38 ,   39 ,   25 ,   26 ,   27 ,   28 ,   29 ,   15 ,   16 ,   17 ,   18 ,   19 ,   5 ,   6 ,   7 ,   8 ,   9 );
        
        time . start ();
        
        ad . addAll ( 0 , nums1 );
        ad . addAll ( 5 , nums2 );
        ad . addAll ( 10 , nums3 );
        ad . addAll ( 15 , nums4 );
        
        time . stop ();
         System . out . print ( ""   +  ad );
         if ( time . elapsedSeconds ()   >   2 ){
            pass  =   false ;
         }
        
         if ( pass ){
             if ( ad . size ()   !=  result . size ()){
                pass  =   false ;
             }
         }
        
         if ( pass ){
             for   ( int  i  =   0 ;  i  <  result . size ();  i ++ )   {
                 if ( ad . get ( i )   !=  result . get ( i )){
                    pass  =   false ;
                     break ;
                 }
             }
         }
     }

     public   static   boolean  testPart2 ( Queue < Integer >  q )   {
         // Your code goes here
         return   false ;
     }
     public   static   boolean  testPart3 ( List < Integer >  ad )   {
         // Do not change this one
         return   true ;
     }

     public   static   boolean  testPart4 ( List < Integer >  ras )   {
         // Your code goes here
         return   false ;
     }

}

__MACOSX/comp2402a2/._Tester.java

__MACOSX/._comp2402a2