Skip to content

Instantly share code, notes, and snippets.

@sasaki-shigeo
Last active October 14, 2021 17:06
Show Gist options
  • Save sasaki-shigeo/57a6969314da9bd2dcda7ff10177b631 to your computer and use it in GitHub Desktop.
Save sasaki-shigeo/57a6969314da9bd2dcda7ff10177b631 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.Map;
import java.util.Set;
import java.util.Iterator;
import java.util.AbstractMap;
import java.util.AbstractSet;
public class LinearSearchTable<K, V> extends AbstractMap<K, V> {
class Entry extends SimpleEntry<K, V> {
K key;
V value;
public Entry(K key, V value) {
super(key, value);
this.key = key;
this.value = value;
}
}
protected ArrayList<Map.Entry<K,V>> table_;
public LinearSearchTable() {
table_ = new ArrayList<>();
}
public LinearSearchTable(int n) {
table_ = new ArrayList<>(n);
}
public Set<Map.Entry<K, V>> entrySet() {
return new AbstractSet<Map.Entry<K, V>>() {
public int size() {
return table_.size();
}
public Iterator<Map.Entry<K, V>> iterator() {
return table_.iterator();
}
};
}
@Override
public void clear() {
table_.clear();
}
protected int lin_search(Object key) {
if (key == null)
return -1;
for (int ix = 0; ix < table_.size(); ix++) {
if (key.equals(table_.get(ix).getKey()))
return ix;
}
return -1;
}
protected int index(Object key) {
return lin_search(key);
}
@Override
public V get(Object key) {
int ix = index(key);
if (ix >= 0)
return table_.get(ix).getValue();
else
return null;
}
@Override
public V put(K key, V value) {
int ix = index(key);
if (ix >= 0) {
Map.Entry<K, V> ent = table_.get(ix);
V before = ent.getValue();
ent.setValue(value);
return before;
}
else {
table_.add(new Entry(key, value));
return null;
}
}
// Test code will be here
public static void main(String[] args) {
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment