## Wednesday, June 15, 2016

### Buttercola: O(1) Map

Buttercola: O(1) Map
Design a Map so that it supports the following operations:
2. remove(int val), O(1) time
3. contains(int val), O(1) time
4. clear(), O(1) time
5. iterate(), O(num of elements)

Analysis:
If we just use a randomized array, i.e, a hash map, add(), remove(), and contains() operations take O(1) time. The clear() takes O(size of array) time (NOT SURE), and iterate takes O(size of array) time. Note that iterate() takes O(size of array) time instead of O(num of elements) because of the implementation of a hash map is usually an array or array + list. So it needs to iterate all elements of the array no matter if it is taken or not.

If we only use a sequential accessed array, i.e, an ArrayList in Java, the add() takes O(1), but remove() and contains() takes O(num of elements) time. clear() takes O(1) ?? not sure.
iterate() takes O(num of elements) time as well.

So the idea is to combine the two data structures together.
`class` `Solution ``implements` `Iterable<Integer> {`
`  ``private` `int``[] list;`
`  ``private` `Map<Integer, Integer> map;`
`  ``private` `int` `size;`
`  ``private` `final` `int` `INIT_CAPACITY = ``4``;`
`  `
`  ``public` `Solution() {`
`    ``list = ``new` `int``[INIT_CAPACITY];`
`    ``map = ``new` `HashMap<>();`
`    ``size = ``0``;`
`  ``}`
`  `
`  ``public` `void` `add(``int` `val) {`
`    ``if` `(size == list.length) {`
`      ``resize(``2` `* list.length); `
`    ``}`
`    `
`    ``map.put(val, size);`
`    ``list[size] = val;`
`    ``size++;`
`  ``}`
`  `
`  ``public` `void` `remove(``int` `val) {`
`    ``if` `(!map.containsKey(val)) {`
`      ``throw` `new` `NoSuchElementException();`
`    ``}`
`    `
`    ``// step 1: get the index of the val to be removed`
`    ``int` `idxToRemove = map.get(val);`
`    `
`    ``// step 2: move the last element to the index to be removed`
`    ``int` `lastE = list[size - ``1``];`
`    ``list[idxToRemove] = lastE;`
`    ``//list[size - 1] = null;`
`    `
`    ``size--;`
`    ``map.remove(val);`
`    ``map.put(lastE, idxToRemove);`
`    `
`    ``// shrink the array`
`    ``if` `(size > ``0` `&& size == list.length / ``4``) {`
`      ``resize(list.length / ``2``);`
`    ``}`
`    `
`  ``}`
`  `
`  ``public` `boolean` `contains(``int` `val) {`
`    ``return` `map.containsKey(val) && `
`           ``map.get(val) < size && `
`           ``val == list[map.get(val)];`
`  ``}`

`  ``public` `void` `clear() {`
`    ``size = ``0``;`
`  ``}`
`  `
`  ``@Override`
`  ``public` `Iterator<Integer> iterator() {`
`    ``return` `new` `MyListIterator();`
`  ``}`
`  `
`  ``private` `class` `MyListIterator ``implements` `Iterator<Integer> {`
`    ``private` `int` `i = ``0``;`
`    `
`    ``@Override`
`    ``public` `boolean` `hasNext() {`
`      ``return` `i < size;`
`    ``}`
`    `
`   ``@Override`
`    ``public` `Integer next() {`
`      ``Integer result = ``0``;`
`      ``if` `(hasNext()) {`
`        ``result = (Integer) list[i];`
`        ``i++;`
`      ``}`
`      `
`      ``return` `result;`
`    ``}`
`    `
`    ``@Override`
`    ``public` `void` `remove() {`
`      ``throw` `new` `UnsupportedOperationException();`
`    ``}`
`  ``}`
`  `
`  ``private` `void` `resize(``int` `newSize) {`
`    ``int``[] newList = ``new` `int``[newSize];`
`    ``newList = Arrays.copyOf(list, size);`
`    ``list = newList;`
`  ``}`
Use two arrays, map[n] and list[n], where for the map[i], the index stores the val of the data, and its value stores the index of the data in the list array. The real value is stored in the list array as well for the convenience of iterator() in O(num of elements) time.

The basic idea of this solution is very close the method 1, just to use the map[] array to simulate a hash map. Therefore here we assume that the size of the map[] array is unlimited and the value of the data to be stored is never out of boundary.
`  ``private` `Integer[] map;`
`  ``private` `Integer[] list;`

`  ``private` `int` `size;`
`  ``private` `final` `int` `INIT_CAPACITY = ``4``;`
`  ``private` `final` `int` `MAP_CAPACITY = ``1000``;`
`  `
`  ``public` `Solution() {`
`    ``list = ``new` `Integer[INIT_CAPACITY];`
`    ``map = ``new` `Integer[MAP_CAPACITY];`
`    ``this``.size = ``0``;`
`  ``}`
`  `
`  ``public` `void` `add(``int` `val) {    `
`    ``if` `(size == list.length) {`
`      ``resize(``2` `* list.length); `
`    ``}`
`    `
`    ``map[val] = size;`
`    ``list[size] = val;`
`    ``size++;`
`  ``}`
`  `
`  ``public` `void` `remove(``int` `val) {`
`    ``if` `(!contains(val)) {`
`      ``throw` `new` `NoSuchElementException();`
`    ``}`
`    `
`    ``// step 1: get the index of the val to be removed`
`    ``int` `idxToRemove = map[val];`
`    `
`    ``// step 2: move the last element to the index to be removed`
`    ``int` `lastE = list[size - ``1``];`
`    ``list[idxToRemove] = lastE;`
`    ``list[size - ``1``] = ``null``;`
`    `
`    ``size--;`
`    `
`    ``map[lastE] = idxToRemove;`
`    ``map[val] = ``null``;`
`    `
`    `
`    `
`    ``// shrink the array`
`    ``if` `(size > ``0` `&& size == list.length / ``4``) {`
`      ``resize(list.length / ``2``);`
`    ``}`
`  ``}`
`  `
`  ``public` `boolean` `contains(``int` `val) {`
`    ``return` `map[val] != ``null` `&& `
`           ``map[val] < size && `
`           ``val == list[map[val]];`
`  ``}`

`  ``public` `void` `clear() {`
`    ``size = ``0``;`
`  ``}`
`  `
`  ``@Override`
`  ``public` `Iterator<Integer> iterator() {`
`    ``return` `new` `MyListIterator();`
`  ``}`
`  `
`  ``private` `class` `MyListIterator ``implements` `Iterator<Integer> {`
`    ``private` `int` `i = ``0``;`
`    `
`    ``@Override`
`    ``public` `boolean` `hasNext() {`
`      ``return` `i < size;`
`    ``}`
`    `
`   ``@Override`
`    ``public` `Integer next() {`
`      ``Integer result = ``0``;`
`      ``if` `(hasNext()) {`
`        ``result = list[i];`
`        ``i++;`
`      ``}`
`      `
`      ``return` `result;`
`    ``}`
`    `
`    ``@Override`
`    ``public` `void` `remove() {`
`      ``throw` `new` `UnsupportedOperationException();`
`    ``}`
`  ``}`
`  `
`  ``private` `void` `resize(``int` `newSize) {`
`    ``Integer[] newList = ``new` `Integer[newSize];`
`    ``for` `(``int` `i = ``0``; i < size; i++) {`
`      ``newList[i] = list[i];`
`    ``}`
`    ``list = newList;`
`  ``}`
`  `
`  ``public` `static` `void` `main(String[] args) {`
`    ``Solution sol = ``new` `Solution();`
`    ``sol.add(``1``);`
`    ``sol.add(``3``);`

`    ``//sol.add(5);`
`    `
`    ``//System.out.println(sol.contains(3));`
`    `
`    ``sol.clear();`
`    `
`    ``sol.add(``4``);`
`    ``sol.add(``5``);`
`    `
`    ``System.out.println(sol.contains(``3``));`
`    `
`    ``//sol.remove(3);`
`    `

`    `
`    ``Iterator<Integer> it = sol.iterator();`
`    ``while` `(it.hasNext()) {`
`      ``int` `val = it.next();`
`      ``System.out.println(val);`
`    ``}`
`    `
`  ``}`