import java.util.ArrayList;
import java.util.Collections;
public class SortedArraySet<E extends Comparable<E>> implements Set<E> {
ArrayList<E> list = new ArrayList<>();
public SortedArraySet() {
}
// returns index of element or (-insertion_point - 1) if element is not found
private int find(E e) {
return Collections.binarySearch(list, e);
}
@Override
public void add(E e) {
int idx = find(e);
if (idx < 0) { // not already in list
idx = -idx - 1; // compute insertion point
list.add(idx, e);
}
}
@Override
public void remove(E e) {
int idx = find(e);
if (idx >= 0) { // is in list
list.remove(idx);
}
}
@Override
public boolean contains(E e) {
return find(e) >= 0;
}
@Override
public int size() {
return list.size();
}
}
@Override
public int compareTo(Entry o) {
Character fstdig = Integer.toString(Math.abs(n)).charAt(0);
Character fstdigo = Integer.toString(Math.abs(o.n)).charAt(0);
int comp = fstdig.compareTo(fstdigo);
if (comp != 0) return comp;
Integer len = s.length();
Integer leno = o.s.length();
return leno.compareTo(len);
}
public boolean isDescendantOf(Person p) {
if (mother != null) {
if (mother == p) {
return true;
} else {
if (mother.isDescendantOf(p)) return true;
}
}
if (father != null) {
if (father == p) {
return true;
} else {
if (father.isDescendantOf(p)) return true;
}
}
return false;
}
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayMap<K, V> implements Map<K, V> {
private class Entry {
public K k;
public V v;
public Entry(K k, V v) {
this.k = k;
this.v = v;
}
}
ArrayList<Entry> list = new ArrayList<>();
// returns index of entry if key is in map, otherwise -1
private int findKey(K key) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).k.equals(key)) return i;
}
return -1;
}
@Override
public V get(K key) {
int idx = findKey(key);
if (idx >= 0) {
return list.get(idx).v;
} else {
return null;
}
}
@Override
public void put(K key, V value) {
int idx = findKey(key);
if (idx >= 0) { // key already in map
list.set(idx, new Entry(key, value));
} else { // key not in map
list.add(new Entry(key, value));
}
}
@Override
public void remove(K key) {
int idx = findKey(key);
if (idx >= 0) {
list.remove(idx);
}
}
@Override
public int size() {
return list.size();
}
private class KeysIterator implements Iterator<K> {
Iterator<Entry> iter;
KeysIterator() {
iter = list.iterator();
}
@Override
public boolean hasNext() {
return iter.hasNext();
}
@Override
public K next() {
return iter.next().k;
}
}
@Override
public Iterator<K> keysIterator() {
return new KeysIterator();
}
}