Advertisement
martinkotevski

NP - Resizable Array

Jan 24th, 2017
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 8.50 KB | None | 0 0
  1. import java.util.Scanner;
  2. import java.util.LinkedList;
  3. import java.util.Arrays;
  4.  
  5. public class ResizableArrayTest {
  6.  
  7.     public static void main(String[] args) {
  8.         Scanner jin = new Scanner(System.in);
  9.         int test = jin.nextInt();
  10.         if ( test == 0 ) { //test ResizableArray on ints
  11.             ResizableArray<Integer> a = new ResizableArray<Integer>();
  12.             System.out.println(a.count());
  13.             int first = jin.nextInt();
  14.             a.addElement(first);
  15.             System.out.println(a.count());
  16.             int last = first;
  17.             while ( jin.hasNextInt() ) {
  18.                 last = jin.nextInt();
  19.                 a.addElement(last);
  20.             }
  21.             System.out.println(a.count());
  22.             System.out.println(a.contains(first));
  23.             System.out.println(a.contains(last));
  24.             System.out.println(a.removeElement(first));
  25.             System.out.println(a.contains(first));
  26.             System.out.println(a.count());
  27.         }
  28.         if ( test == 1 ) { //test ResizableArray on strings
  29.             ResizableArray<String> a = new ResizableArray<String>();
  30.             System.out.println(a.count());
  31.             String first = jin.next();
  32.             a.addElement(first);
  33.             System.out.println(a.count());
  34.             String last = first;
  35.             for ( int i = 0 ; i < 4 ; ++i ) {
  36.                 last = jin.next();
  37.                 a.addElement(last);
  38.             }
  39.             System.out.println(a.count());
  40.             System.out.println(a.contains(first));
  41.             System.out.println(a.contains(last));
  42.             System.out.println(a.removeElement(first));
  43.             System.out.println(a.contains(first));
  44.             System.out.println(a.count());
  45.             ResizableArray<String> b = new ResizableArray<String>();
  46.             ResizableArray.copyAll(b, a);
  47.             System.out.println(b.count());
  48.             System.out.println(a.count());
  49.             System.out.println(a.contains(first));
  50.             System.out.println(a.contains(last));
  51.             System.out.println(b.contains(first));
  52.             System.out.println(b.contains(last));
  53.             ResizableArray.copyAll(b, a);
  54.             System.out.println(b.count());
  55.             System.out.println(a.count());
  56.             System.out.println(a.contains(first));
  57.             System.out.println(a.contains(last));
  58.             System.out.println(b.contains(first));
  59.             System.out.println(b.contains(last));
  60.             System.out.println(b.removeElement(first));
  61.             System.out.println(b.contains(first));
  62.             System.out.println(b.removeElement(first));
  63.             System.out.println(b.contains(first));
  64.  
  65.             System.out.println(a.removeElement(first));
  66.             ResizableArray.copyAll(b, a);
  67.             System.out.println(b.count());
  68.             System.out.println(a.count());
  69.             System.out.println(a.contains(first));
  70.             System.out.println(a.contains(last));
  71.             System.out.println(b.contains(first));
  72.             System.out.println(b.contains(last));
  73.         }
  74.         if ( test == 2 ) { //test IntegerArray
  75.             IntegerArray a = new IntegerArray();
  76.             System.out.println(a.isEmpty());
  77.             while ( jin.hasNextInt() ) {
  78.                 a.addElement(jin.nextInt());
  79.             }
  80.             jin.next();
  81.             System.out.println(a.sum());
  82.             System.out.println(a.mean());
  83.             System.out.println(a.countNonZero());
  84.             System.out.println(a.count());
  85.             IntegerArray b = a.distinct();
  86.             System.out.println(b.sum());
  87.             IntegerArray c = a.increment(5);
  88.             System.out.println(c.sum());
  89.             if ( a.sum() > 100 )
  90.                 ResizableArray.copyAll(a, a);
  91.             else
  92.                 ResizableArray.copyAll(a, b);
  93.             System.out.println(a.sum());
  94.             System.out.println(a.removeElement(jin.nextInt()));
  95.             System.out.println(a.sum());
  96.             System.out.println(a.removeElement(jin.nextInt()));
  97.             System.out.println(a.sum());
  98.             System.out.println(a.removeElement(jin.nextInt()));
  99.             System.out.println(a.sum());
  100.             System.out.println(a.contains(jin.nextInt()));
  101.             System.out.println(a.contains(jin.nextInt()));
  102.         }
  103.         if ( test == 3 ) { //test insanely large arrays
  104.             LinkedList<ResizableArray<Integer>> resizable_arrays = new LinkedList<ResizableArray<Integer>>();
  105.             for ( int w = 0 ; w < 500 ; ++w ) {
  106.                 ResizableArray<Integer> a = new ResizableArray<Integer>();
  107.                 int k =  2000;
  108.                 int t =  1000;
  109.                 for ( int i = 0 ; i < k ; ++i ) {
  110.                     a.addElement(i);
  111.                 }
  112.  
  113.                 a.removeElement(0);
  114.                 for ( int i = 0 ; i < t ; ++i ) {
  115.                     a.removeElement(k-i-1);
  116.                 }
  117.                 resizable_arrays.add(a);
  118.             }
  119.             System.out.println("You implementation finished in less then 3 seconds, well done!");
  120.         }
  121.         jin.close();
  122.     }
  123.  
  124. }
  125.  
  126. class ResizableArray<T> {
  127.     private Object[] arr;
  128.     int last;
  129.  
  130.     public ResizableArray() {
  131.         arr = new Object[50];
  132.         last = -1;
  133.     }
  134.  
  135.     public ResizableArray(Object[] elements) {
  136.         arr = Arrays.copyOf(elements, elements.length);
  137.         last = arr.length - 1;
  138.     }
  139.  
  140.     public int count() {
  141.         return last + 1;
  142.     }
  143.  
  144.     public void addElement(T element) {
  145.         if (element == null)
  146.             throw new NullPointerException();
  147.         if (isFull())
  148.             resize(arr.length * 2);
  149.         arr[++last] = element;
  150.     }
  151.  
  152.     public boolean removeElement(T element) {
  153.         if (isEmpty())
  154.             return false;
  155.         int index = -1;
  156.         for (int i = 0; i < count(); i++) {
  157.             if (arr[i].equals(element)) {
  158.                 index = i;
  159.                 break;
  160.             }
  161.         }
  162.  
  163.         if (index != -1) {
  164.             for (int i = index; i < count() - 1; i++)
  165.                 arr[i] = arr[i + 1];
  166.  
  167.             arr[last--] = null;
  168.  
  169.             int numOfElements = last + 1;
  170.             if (numOfElements <= arr.length / 4)
  171.                 resize(arr.length / 2);
  172.  
  173.             return true;
  174.         }
  175.         return false;
  176.     }
  177.  
  178.     @SuppressWarnings("unchecked")
  179.     public T elementAt(int pos) {
  180.         if (pos < 0 || pos > last)
  181.             throw new ArrayIndexOutOfBoundsException();
  182.         return (T) arr[pos];
  183.     }
  184.  
  185.     public boolean contains(T element) {
  186.         return Arrays.stream(Arrays.copyOf(arr, count())).anyMatch(el -> el.equals(element));
  187.     }
  188.  
  189.     public boolean isEmpty() {
  190.         return last == -1;
  191.     }
  192.  
  193.     public Object[] toArray() {
  194.         return Arrays.copyOf(arr, count());
  195.     }
  196.  
  197.     public static <T> void copyAll(ResizableArray<? super T> dest,
  198.                                    ResizableArray<? extends T> src) {
  199.         int size = src.count();
  200.        
  201.         for (int i = 0; i < size; i++) {
  202.             dest.addElement(src.elementAt(i));
  203.          }      
  204.     }
  205.    
  206.     private boolean isFull() {
  207.         return last == arr.length - 1;
  208.     }
  209.  
  210.     private void resize(int newSize) {
  211.         arr = Arrays.copyOf(arr, newSize);
  212.     }
  213.  
  214. }
  215.  
  216. class IntegerArray extends ResizableArray<Integer> {
  217.  
  218.     public IntegerArray() {
  219.         super();
  220.     }
  221.    
  222.     public IntegerArray(Object[] elements) {
  223.         super(elements);
  224.     }
  225.  
  226.     public double sum() {
  227.         return Arrays.stream(toArray())
  228.                 .mapToInt(el -> (Integer) el)
  229.                 .sum();
  230.     }
  231.  
  232.     public double mean() {      
  233.         // Integer[] ints = (Integer[]) toArray(); // can't do this!!! ClassCastException
  234.         Integer[] ints = Arrays.copyOf(toArray(), count(), Integer[].class);
  235.         return Arrays.stream(ints)
  236.                 .mapToInt(Integer::intValue)
  237.                 .average()
  238.                 .getAsDouble();
  239.     }
  240.  
  241.     public int countNonZero() {
  242.      
  243.         return (int) Arrays.stream(toArray())
  244.                .filter(el -> !el.equals(0))
  245.                .count();
  246.     }
  247.  
  248.     public IntegerArray distinct() {
  249.         Object[] ints = Arrays.stream(toArray())
  250.                .distinct()
  251.                .toArray();
  252.         return new IntegerArray(ints);
  253.     }
  254.  
  255.     public IntegerArray increment(int offset) {
  256.         Object[] ints = toArray();
  257.         for (int i = 0; i < ints.length; i++)
  258.             ints[i] = new Integer((Integer)ints[i] + offset);
  259.        
  260.         return new IntegerArray(ints);
  261.     }
  262. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement