Java,
Week 6

public class CircularArrayQueue<E> implements Queue<E> {
    private Object[] items;
    private int head = 0;
    private int count = 0;

    public CircularArrayQueue(int capacity) {
        items = new Object[capacity];             // one-time storage allocation
    }

    public void add(E element) {
        if (count == items.length) {
            throw new IllegalStateException("queue is full");   // bounded size
        }
        items[(head + count) % items.length] = element;
        count++;
    }

    @SuppressWarnings("unchecked")
    public E remove() {
        if (count == 0) throw new IllegalStateException("queue is empty");
        E e = (E) items[head];
        items[head] = null;
        head = (head + 1) % items.length;
        count--;
        return e;
    }

    public int size() { return count; }
}

public class Main {
    public static void main(String[] args) {
        CircularArrayQueue<Integer> q = new CircularArrayQueue<Integer>(3);
        q.add(1); q.add(2); q.add(3);        // array is full
        System.out.println(q.remove());      // head moves on
        q.add(4);                            // the tail wraps around to slot 0
        System.out.println(q.remove() + " " + q.remove() + " " + q.remove());
    }
}

1
2 3 4

public interface Queue<E> {
    void add(E element);
    E remove();
    int size();
}

public class Main {
    public static void main(String[] args) {
        Queue<String> q = new LinkedListQueue<String>();    // declared by the interface
        q.add("a");
        q.add("b");
        q.add("c");
        System.out.println(q.remove() + q.remove() + " left: " + q.size());
    }
}

ab left: 1

public class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedListQueue<Integer>();       // changed: nothing else touched
        for (int i = 1; i <= 5; i++) {
            q.add(i);
        }
        System.out.println(q.size());
    }
}

5

public class Main {
    static void fill(Queue<String> q) {                 // works for any implementation
        q.add("x");
        q.add("y");
        System.out.println(q.getClass().getSimpleName() + " has " + q.size());
    }

    public static void main(String[] args) {
        fill(new CircularArrayQueue<String>(4));
        fill(new LinkedListQueue<String>());
    }
}

CircularArrayQueue has 2
LinkedListQueue has 2

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        Collection<String> cstr = new ArrayList<String>();
        cstr.add("one");
        cstr.add("two");
        cstr.add("three");

        Iterator<String> iter = cstr.iterator();
        while (iter.hasNext()) {
            String element = iter.next();
            System.out.println(element.toUpperCase());
        }
    }
}

ONE
TWO
THREE

import java.util.ArrayList;
import java.util.Collection;

public class Main {
    public static void main(String[] args) {
        Collection<String> cstr = new ArrayList<String>();
        cstr.add("one");
        cstr.add("two");

        for (String element : cstr) {           // the compiler builds the iterator for us
            System.out.println(element);
        }
    }
}

one
two

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;

public class Main {
    public static <E> boolean contains(Collection<E> c, Object obj) {
        for (E element : c) {
            if (element.equals(obj)) {          // every E is an Object: equals() always exists
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Collection<String> list = new ArrayList<String>(List.of("a", "b", "c"));
        Collection<Integer> set = new HashSet<Integer>(List.of(10, 20, 30));
        System.out.println(contains(list, "b"));
        System.out.println(contains(set, 25));
        System.out.println(contains(set, 20));
    }
}

true
false
true

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Collection<String> cstr = new ArrayList<String>(List.of("tea", "coffee", "milk", "cola"));
        Iterator<String> iter = cstr.iterator();
        while (iter.hasNext()) {
            String element = iter.next();
            if (element.length() == 4) {        // delete the element if it has some property
                iter.remove();                  // removes the element next() just returned
            }
        }
        System.out.println(cstr);
    }
}

[tea, coffee]

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

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<String>(List.of("a", "b", "c", "d"));
        Iterator<String> iter = names.iterator();

        iter.next();        // a
        iter.remove();
        iter.next();        // b: interleave a next() before the second remove()
        iter.remove();
        System.out.println(names);
    }
}

[c, d]

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Collection<String> c = new ArrayList<String>();
        System.out.println(c.isEmpty());
        c.add("x"); c.add("y"); c.add("z");
        System.out.println(c.size() + " " + c.contains("y"));
        System.out.println(c.containsAll(List.of("x", "z")));

        c.addAll(List.of("p", "q"));                    // copy in another collection
        System.out.println(c);

        c.remove("y");                                  // Collection.remove(Object): one value
        c.removeAll(List.of("p", "q"));                 // remove every element that is in the argument
        System.out.println(c);
    }
}

true
3 true
true
[x, y, z, p, q]
[x, z]

public abstract Iterator<E> iterator();   // abstract: depends on the representation

public boolean contains(Object obj) {          // default: built on iterator()
    for (E element : this) {
        if (element.equals(obj)) return true;
    }
    return false;
}

import java.util.AbstractCollection;
import java.util.Iterator;

public class Bag<E> extends AbstractCollection<E> {
    private Object[] items = new Object[10];
    private int n = 0;

    public void put(E e) { items[n++] = e; }

    public int size() { return n; }

    public Iterator<E> iterator() {                 // the only representation-specific method besides size()
        return new Iterator<E>() {
            private int pos = 0;
            public boolean hasNext() { return pos < n; }
            @SuppressWarnings("unchecked")
            public E next() { return (E) items[pos++]; }
        };
    }
}

import java.util.List;

public class Main {
    public static void main(String[] args) {
        Bag<String> bag = new Bag<String>();
        bag.put("red");
        bag.put("green");
        bag.put("blue");

        System.out.println(bag.contains("green"));      // inherited: built on iterator()
        System.out.println(bag.containsAll(List.of("red", "blue")));
        System.out.println(bag.isEmpty());              // inherited: built on size()
        System.out.println(bag);                        // inherited toString()
        for (String s : bag) {                          // for-each works: it is Iterable
            System.out.print(s.length() + " ");
        }
        System.out.println();
    }
}

true
true
false
[red, green, blue]
3 5 4 

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("b");                    // Collection.add: append
        list.add("c");
        list.add(0, "a");                 // List.add(index, e): insert at a position
        System.out.println(list);

        System.out.println(list.get(1));  // by position
        System.out.println(list.set(1, "B"));   // set returns the old element
        String removed = list.remove(2);  // remove(int) returns the removed element
        System.out.println(removed + " " + list);
    }
}

[a, b, c]
b
b
c [a, B]

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>(List.of("a", "c", "d"));
        ListIterator<String> it = list.listIterator();

        it.next();                                  // passes "a"
        it.add("b");                                // inserted BEFORE the current position
        System.out.println(list);

        it.next();                                  // passes "c"
        System.out.println(it.hasPrevious());       // legal to go backwards?
        String back = it.previous();                // previous() returns the element, not void
        System.out.println(back);

        it.set("C");                                // replaces what previous() just returned
        System.out.println(list);
    }
}

[a, b, c, d]
true
c
[a, b, C, d]

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.RandomAccess;

public class Main {
    static int sum(List<Integer> c) {
        int total = 0;
        if (c instanceof RandomAccess) {            // a tagging interface: no methods
            for (int i = 0; i < c.size(); i++) {    // random access algorithm
                total += c.get(i);
            }
        } else {
            for (int x : c) {                       // sequential access algorithm
                total += x;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<Integer>(List.of(1, 2, 3));
        List<Integer> l = new LinkedList<Integer>(List.of(1, 2, 3));
        System.out.println((a instanceof RandomAccess) + " " + (l instanceof RandomAccess));
        System.out.println(sum(a) + " " + sum(l));
    }
}

true false
6 6

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static long viaGet(List<Integer> list) {
        long t = System.nanoTime();
        long s = 0;
        for (int i = 0; i < list.size(); ++i) s += list.get(i);     // a fresh scan to i each time
        return System.nanoTime() - t;
    }

    static long viaIterator(List<Integer> list) {
        long t = System.nanoTime();
        long s = 0;
        for (int x : list) s += x;                                  // one pass
        return System.nanoTime() - t;
    }

    public static void main(String[] args) {
        List<Integer> linked = new LinkedList<Integer>();
        List<Integer> array = new ArrayList<Integer>();
        for (int i = 0; i < 30000; i++) { linked.add(i); array.add(i); }

        long linkedGet = viaGet(linked), linkedIter = viaIterator(linked), arrayGet = viaGet(array);
        System.out.println("LinkedList: get(i) loop slower than iterator? " + (linkedGet > 20 * linkedIter));
        System.out.println("ArrayList get(i) faster than LinkedList get(i)? " + (arrayGet * 20 < linkedGet));
    }
}

LinkedList: get(i) loop slower than iterator? true
ArrayList get(i) faster than LinkedList get(i)? true

import java.util.AbstractCollection;
import java.util.AbstractList;
import java.util.AbstractSequentialList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        System.out.println(AbstractCollection.class.isAssignableFrom(AbstractList.class));
        System.out.println(AbstractList.class.isAssignableFrom(AbstractSequentialList.class));
        System.out.println(AbstractSequentialList.class.isAssignableFrom(LinkedList.class));
        System.out.println(AbstractList.class.isAssignableFrom(ArrayList.class));
        System.out.println(AbstractSequentialList.class.isAssignableFrom(ArrayList.class));
        System.out.println(Collection.class.isAssignableFrom(java.util.HashMap.class));
    }
}

true
true
true
true
false
false

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        Set<String> set = new HashSet<String>();

        System.out.println(list.add("x"));         // Collection.add returns boolean: did the collection change?
        System.out.println(list.add("x"));         // a list always accepts
        System.out.println(set.add("x"));
        System.out.println(set.add("x"));          // a set refuses a duplicate: false

        ListIterator<String> it = list.listIterator();
        it.add("y");                               // ListIterator.add returns void
        System.out.println(list);
    }
}

true
true
true
false
[y, x, x]

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> hs = new HashSet<String>();
        hs.add("banana"); hs.add("apple"); hs.add("cherry");
        System.out.println(hs.add("apple") + " " + hs.size());   // duplicate: no effect, false

        Set<String> ts = new TreeSet<String>(hs);                // same contents, sorted
        System.out.println(ts);
        System.out.println(hs.equals(ts));                       // equal contents, order ignored
        System.out.println(hs);                                  // HashSet order: unspecified
    }
}

false 3
[apple, banana, cherry]
true
[banana, apple, cherry]

public class Point {
    private final int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }
    // hashCode() NOT overridden
}

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Point> set = new HashSet<Point>();
        set.add(new Point(1, 2));
        set.add(new Point(1, 2));                      // equal to the first one
        System.out.println(set.size());
        System.out.println(set.contains(new Point(1, 2)));
    }
}

2
false

public class Point {
    private final int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() { return 31 * x + y; }       // equal points give equal hashes
}

1
true

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<Job> byPriority = new TreeSet<Job>(Comparator.comparingInt(j -> j.priority));
        byPriority.add(new Job("print", 2));
        byPriority.add(new Job("email", 1));
        byPriority.add(new Job("backup", 3));
        System.out.println(byPriority);            // visited in sorted order
    }
}

[email, print, backup]

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<Integer>();
        dq.addFirst(2);
        dq.addLast(3);
        dq.offerFirst(1);
        System.out.println(dq);
        System.out.println(dq.getFirst() + " " + dq.peekLast());
        System.out.println(dq.pollFirst() + " " + dq.pollLast() + " " + dq);

        dq.push(7);                                            // a Deque is also a stack
        dq.push(8);
        System.out.println(dq.pop() + " " + dq.pop());
    }
}

[1, 2, 3]
1 3
1 3 [2]
8 7

import java.util.Collections;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        pq.add(5); pq.add(1); pq.add(4); pq.add(2); pq.add(3);
        System.out.println(pq);                                // internal heap order, NOT sorted
        System.out.print("remove(): ");
        while (!pq.isEmpty()) System.out.print(pq.remove() + " ");   // smallest first
        System.out.println();

        PriorityQueue<Integer> max = new PriorityQueue<Integer>(Collections.reverseOrder());
        max.add(5); max.add(1); max.add(4);
        System.out.println(max.remove());                      // now the largest is "highest priority"
    }
}

[1, 2, 4, 5, 3]
remove(): 1 2 3 4 5 
5

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> ll = new LinkedList<String>();
        Queue<String> asQueue = ll;                    // a LinkedList is a Queue ...
        List<String> asList = ll;                      // ... and a List

        asQueue.offer("first");
        asQueue.offer("second");
        System.out.println(asList.get(1));
        System.out.println(asQueue.poll());
    }
}

second
first

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<String, Integer>();
        System.out.println(ages.put("Asha", 21));          // no earlier value: null
        System.out.println(ages.put("Asha", 22));          // returns the PREVIOUS value; overwrites
        ages.put("Ravi", 30);

        System.out.println(ages.get("Asha"));
        System.out.println(ages.get("Meena"));             // absent key: null
        System.out.println(ages.size());                   // one entry per key
        System.out.println(ages.containsKey("Ravi") + " " + ages.containsValue(99));
    }
}

null
21
22
null
2
true false

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<String, Integer>();
        String bat = "Asha";

        // 1. getOrDefault
        scores.put(bat, scores.getOrDefault(bat, 0) + 10);
        // 2. putIfAbsent, then update
        scores.putIfAbsent(bat, 0);
        scores.put(bat, scores.get(bat) + 5);
        // 3. merge
        scores.merge(bat, 20, Integer::sum);
        scores.merge("Ravi", 20, Integer::sum);            // missing key: initialised to 20

        System.out.println(scores);
    }
}

{Ravi=20, Asha=35}

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        String text = "to be or not to be";
        Map<String, Integer> freq = new HashMap<String, Integer>();
        for (String w : text.split(" ")) {
            freq.put(w, freq.getOrDefault(w, 0) + 1);      // initialise-or-update in one line
        }
        System.out.println(freq);
    }
}

{not=1, be=2, or=1, to=2}

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> staff = new TreeMap<String, Integer>();
        staff.put("Asha", 50000);
        staff.put("Ravi", 60000);
        staff.put("Meena", 55000);

        Set<String> keys = staff.keySet();
        for (String key : keys) {
            System.out.println("key " + key);
        }

        for (Map.Entry<String, Integer> entry : staff.entrySet()) {   // key and value, no second lookup
            String k = entry.getKey();
            Integer v = entry.getValue();
            System.out.println(k + " earns " + v);
        }

        System.out.println(staff.values());
    }
}

key Asha
key Meena
key Ravi
Asha earns 50000
Meena earns 55000
Ravi earns 60000
[50000, 55000, 60000]

import java.util.Map;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new TreeMap<String, Integer>();
        m.put("a", 1); m.put("b", 2); m.put("c", 3);

        m.keySet().remove("a");                            // a view: removing here removes from the map
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            e.setValue(e.getValue() * 10);                 // writes through to the map
        }
        System.out.println(m);

        m.values().remove(30);                             // by value
        System.out.println(m);
    }
}

{b=20, c=30}
{b=20}

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    static void fill(Map<String, Integer> m) {
        m.put("pear", 1); m.put("apple", 2); m.put("fig", 3); m.put("banana", 4);
    }

    public static void main(String[] args) {
        Map<String, Integer> hash = new HashMap<String, Integer>();
        Map<String, Integer> tree = new TreeMap<String, Integer>();
        Map<String, Integer> linked = new LinkedHashMap<String, Integer>();
        fill(hash); fill(tree); fill(linked);

        System.out.println("HashMap       " + hash.keySet());      // no promise
        System.out.println("TreeMap       " + tree.keySet());      // sorted
        System.out.println("LinkedHashMap " + linked.keySet());    // insertion order
    }
}

HashMap       [banana, apple, pear, fig]
TreeMap       [apple, banana, fig, pear]
LinkedHashMap [pear, apple, fig, banana]

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> t = new TreeMap<Integer, String>();
        t.put(30, "c"); t.put(10, "a"); t.put(20, "b");
        System.out.println(t);                             // keys in sorted order
        System.out.println(t.firstKey() + " " + t.lastKey());
        System.out.println(t.headMap(30));                 // keys strictly below 30
    }
}

{10=a, 20=b, 30=c}
10 30
{10=a, 20=b}

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new LinkedHashMap<String, Integer>(16, 0.75f, true);   // access order
        m.put("a", 1); m.put("b", 2); m.put("c", 3);
        System.out.println(m.keySet());

        m.get("a");                                        // a get moves the pair to the end
        System.out.println(m.keySet());
        m.put("b", 20);                                    // so does a put on an existing key
        System.out.println(m.keySet());                    // least recently used first
    }
}

[a, b, c]
[b, c, a]
[c, a, b]

import java.util.LinkedHashMap;
import java.util.Map;

public class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LruCache(int capacity) {
        super(16, 0.75f, true);                            // access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;                          // drop the least recently used
    }
}

public class Main {
    public static void main(String[] args) {
        LruCache<String, Integer> cache = new LruCache<String, Integer>(3);
        cache.put("a", 1); cache.put("b", 2); cache.put("c", 3);
        cache.get("a");                                    // a is now the most recently used
        cache.put("d", 4);                                 // evicts b, the least recently used
        System.out.println(cache.keySet());
    }
}

[c, a, d]

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Key, String> m = new HashMap<Key, String>();
        Key k = new Key(1);
        m.put(k, "value");
        k.id = 2;                                          // the key's hash changes after insertion
        System.out.println(m.get(k));
        System.out.println(m.get(new Key(1)));
        System.out.println(m.size());
    }
}

null
null
1