In JAVA Using MAP ADT Implement Unsorted Array List Implement Unsorted Linked Li
ID: 3835643 • Letter: I
Question
In JAVA
Using MAP ADT
Implement Unsorted Array List
Implement Unsorted Linked List
//---------------------------------------------------------------------------
// ArrayListMap.java by Dale/Joyce/Weems Chapter 8
//
// Implements a map using an ArrayList.
//
// A map provides (K = key, V = value) pairs, mapping the key onto the value.
// Keys are unique. Keys cannot be null.
//
// Methods throw IllegalArgumentException if passed a null key argument.
//
// Values can be null, so a null value returned by put, get, or remove does
// not necessarily mean that an entry did not exist.
//---------------------------------------------------------------------------
//package ch08.maps;
import java.util.*; // Iterator, ArrayList
public class ArrayListMap<K, V> implements MapInterface<K,V>
{
protected ArrayList<MapEntry<K, V>> map;
public ArrayListMap()
{
map = new ArrayList<MapEntry<K, V>>();
}
public ArrayListMap(int initCapacity)
{
map = new ArrayList<MapEntry<K, V>>(initCapacity);
}
public V put(K k, V v)
// If an entry in this map with key k already exists then the value
// associated with that entry is replaced by value v and the original
// value is returned; otherwise, adds the (k, v) pair to the map and
// returns null.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
MapEntry<K,V> entry = new MapEntry<K, V>(k, v);
MapEntry<K,V> temp;
Iterator<MapEntry<K,V>> search = map.iterator(); // Arraylist iterator
while (search.hasNext())
{
temp = search.next();
if (temp.getKey().equals(k))
{
search.remove();
map.add(entry);
return temp.getValue(); // k found, exits method
}
}
// No entry is associated with k.
map.add(entry);
return null;
}
public V get(K k)
// If an entry in this map with a key k exists then the value associated
// with that entry is returned; otherwise null is returned.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
for (MapEntry<K,V> temp: map) // uses ArrayList iterator
if (temp.getKey().equals(k))
return temp.getValue(); // k found, exits method
// No entry is associated with k.
return null;
}
public V remove(K k)
// If an entry in this map with key k exists then the entry is removed
// from the map and the value associated with that entry is returned;
// otherwise null is returned.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
MapEntry<K,V> temp;
Iterator<MapEntry<K,V>> search = map.iterator(); // Arraylist iterator
while (search.hasNext())
{
temp = search.next();
if (temp.getKey().equals(k))
{
search.remove();
return temp.getValue(); // k found, exits method
}
}
// No entry is associated with k.
return null;
}
public boolean contains(K k)
// Returns true if an entry in this map with key k exists;
// Returns false otherwise.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
for (MapEntry<K,V> temp: map)
if (temp.getKey().equals(k))
return true; // k found, exits method
// No entry is associated with k.
return false;
}
public boolean isEmpty()
// Returns true if this map is empty; otherwise, returns false.
{
return (map.size() == 0); // uses ArrayList size
}
public boolean isFull()
// Returns true if this map is full; otherwise, returns false.
{
return false; // An ArrayListMap is never full
}
public int size()
// Returns the number of entries in this map.
{
return map.size(); // uses ArrayList size
}
public Iterator<MapEntry<K,V>> Iterator()
// Returns the Iterator provided by ArrayList.
{
return map.iterator(); // returns ArrayList iterator
}
}
//---------------------------------------------------------------------------
// HMap.java by Dale/Joyce/Weems Chapter 8
//
// Implements a map using an array-based hash table, linear probing collision
// resolution.
//
// The remove operation is not supported. Invoking it will result in the
// unchecked UnsupportedOperationException being thrown.
//
// A map provides (K = key, V = value) pairs, mapping the key onto the value.
// Keys are unique. Keys cannot be null.
//
// Methods throw IllegalArgumentException if passed a null key argument.
//
// Values can be null, so a null value returned by put or get does
// not necessarily mean that an entry did not exist.
//@Override
//---------------------------------------------------------------------------
//package ch08.maps;
import java.util.Iterator;
import java.util.*;
public class HMap<K, V> //implements MapInterface<K,V>
{
protected MapEntry[] map;
protected final int DEFCAP = 1000; // default capacity
protected final double DEFLOAD = 0.75; // default load
protected int origCap; // original capacity
protected int currCap; // current capacity
protected double load;
protected int numPairs = 0; // number of pairs in this map
public HMap()
{
map = new MapEntry[DEFCAP];
origCap = DEFCAP;
currCap = DEFCAP;
load = DEFLOAD;
}
public HMap(int initCap, double initLoad)
{
map = new MapEntry[initCap];
origCap = initCap;
currCap = initCap;
load = initLoad;
}
private void enlarge()
// Increments the capacity of the map by an amount
// equal to the original capacity.
{
// create a snapshot iterator of the map and save current size
Iterator<MapEntry<K,V>> i = Iterator();
int count = numPairs;
// create the larger array and reset variables
map = new MapEntry[currCap + origCap];
currCap = currCap + origCap;
numPairs = 0;
// put the contents of the current map into the larger array
MapEntry entry;
for (int n = 1; n <= count; n++)
{
entry = i.next();
this.put((K)entry.getKey(), (V)entry.getValue());
}
}
public V put(K k, V v)
// If an entry in this map with key k already exists then the value
// associated with that entry is replaced by value v and the original
// value is returned; otherwise, adds the (k, v) pair to the map and
// returns null.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
MapEntry<K, V> entry = new MapEntry<K, V>(k, v);
int location = Math.abs(k.hashCode()) % currCap;
while ((map[location] != null) && !(map[location].getKey().equals(k)))
location = (location + 1) % currCap;
if (map[location] == null) // k was not in map
{
map[location] = entry;
numPairs++;
if ((float)numPairs/currCap > load)
enlarge();
return null;
}
else // k already in map
{
V temp = (V)map[location].getValue();
map[location] = entry;
return temp;
}
}
public V get(K k)
// If an entry in this map with a key k exists then the value associated
// with that entry is returned; otherwise null is returned.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
int location = Math.abs(k.hashCode()) % currCap;
while ((map[location] != null) && !(map[location].getKey().equals(k)))
location = (location + 1) % currCap;
if (map[location] == null) // k was not in map
return null;
else // k in map
return (V)map[location].getValue();
}
public V remove(K k)
// Throws UnsupportedOperationException.
{
throw new UnsupportedOperationException("HMap does not allow remove.");
}
public boolean contains(K k)
// Returns true if an entry in this map with key k exists;
// Returns false otherwise.
{
if (k == null)
throw new IllegalArgumentException("Maps do not allow null keys.");
int location = Math.abs(k.hashCode()) % currCap;
while (map[location] != null)
if (map[location].getKey().equals(k))
return true;
else
location = (location + 1) % currCap;
// if get this far then no current entry is associated with k
return false;
}
public boolean isEmpty()
// Returns true if this map is empty; otherwise, returns false.
{
return (numPairs == 0);
}
public boolean isFull()
// Returns true if this map is full; otherwise, returns false.
{
return false; // An HMap is never full
}
public int size()
// Returns the number of entries in this map.
{
return numPairs;
}
private class MapIterator implements Iterator<MapEntry<K,V>>
// Provides a snapshot Iterator over this map.
// Remove is not supported and throws UnsupportedOperationException.
{
int listSize = size();
private MapEntry[] list = new MapEntry[listSize];
private int previousPos = -1; // previous position returned from list
public MapIterator()
{
int next = -1;
for (int i = 0; i < listSize; i++)
{
next++;
while (map[next] == null)
next++;
list[i] = map[next];
}
}
public boolean hasNext()
// Returns true if iteration has more entries; otherwise returns false.
{
return (previousPos < (listSize - 1));
}
public MapEntry<K,V> next()
// Returns the next entry in the iteration.
// Throws NoSuchElementException - if the iteration has no more entries
{
if (!hasNext())
throw new IndexOutOfBoundsException("illegal invocation of next " +
" in HMap iterator. ");
previousPos++;
return list[previousPos];
}
public void remove()
// Throws UnsupportedOperationException.
// Not supported. Removal from snapshot iteration is meaningless.
{
throw new UnsupportedOperationException("Unsupported remove attempted "
+ "on HMap iterator. ");
}
}
public Iterator<MapEntry<K,V>> Iterator()
// Returns a snapshot Iterator over this map.
// Remove is not supported and throws UnsupportedOperationException.
{
return new MapIterator();
}
}
//---------------------------------------------------------------------------
// MapEntry.java by Dale/Joyce/Weems Chapter 8
//
// Provides key, value pairs for use with a Map.
// Keys are immutable.
//---------------------------------------------------------------------------
///package ch08.maps;
public class MapEntry<K, V>
{
protected K key;
protected V value;
MapEntry(K k, V v)
{
key = k; value = v;
}
public K getKey() {
return key;
}
public V getValue(){
return value;
}
public void setValue(V v){value = v;}
@Override
public String toString()
// Returns a string representing this MapEntry.
{
return "Key : " + key + " Value: " + value;
}
}
//---------------------------------------------------------------------------
// MapInterface.java by Dale/Joyce/Weems Chapter 8
//
// A map provides (K = key, V = value) pairs, mapping the key onto the value.
// Keys are unique. Keys cannot be null.
//
// Methods throw IllegalArgumentException if passed a null key argument.
//
// Values can be null, so a null value returned by put, get, or remove does
// not necessarily mean that an entry did not exist.
//---------------------------------------------------------------------------
//package ch08.maps;
import java.util.Iterator;
public interface MapInterface<K, V> extends Iterable<MapUnsort<K,V>>
{
V put(K k, V v);
// If an entry in this map with key k already exists then the value
// associated with that entry is replaced by value v and the original
// value is returned; otherwise, adds the (k, v) pair to the map and
// returns null.
V get(K k);
// If an entry in this map with a key k exists then the value associated
// with that entry is returned; otherwise null is returned.
V remove(K k);
// If an entry in this map with key k exists then the entry is removed
// from the map and the value associated with that entry is returned;
// otherwise null is returned.
//
// Optional. Throws UnsupportedOperationException if not supported.
boolean contains(K k);
// Returns true if an entry in this map with key k exists;
// Returns false otherwise.
boolean isEmpty();
// Returns true if this map is empty; otherwise, returns false.
boolean isFull();
// Returns true if this map is full; otherwise, returns false.
int size();
// Returns the number of entries in this map.
}
Explanation / Answer
Program for Unsorted Linked List Using MAP ADT :
Listelement.java:
public class ListElement<KeyType, ValueType>
{
public KeyType key;
public ValueType value;
public ListElement<KeyType,ValueType> prev;
public ListElement<KeyType,ValueType> next;
public ListElement(KeyType k, ValueType v)
{
key = k;
value = v;
prev = null;
next = null;
}
public String toString()
{
return( "(" + key + "," + value + ")" );
}
}
List.java:
public class List<KeyType, ValueType>
{
public ListElement<KeyType, ValueType> head;
public int N;
public List()
{
head = null;
N = 0;
}
public void delete(ListElement<KeyType, ValueType> ele)
{
ListElement<KeyType, ValueType> prevElement, nextElement;
if ( N == 0 )
{
return ;
}
else if ( N == 1 )
{
head = null;
}
else if ( ele.prev == null ) {
System.out.println("Deleted Element : " + ele.key);
nextElement = ele.next;
nextElement.prev = null;
head = nextElement; }
else if ( ele.next == null )
{
System.out.println("Delete: " + ele.key);
prevElement = ele.prev;
prevElement.next = null;
}
else
{
System.out.println("Delete: " + ele.key);
prevElement = ele.prev;
nextElement = ele.next;
nextElement.prev = ele.prev;
prevElement.next = ele.next;
}
N--;
}
public void insert(ListElement<KeyType, ValueType> ele)
{
if ( N == 0 )
{
ele.next = null;
ele.prev = null;
head = ele;
}
else
{
ele.next = head;
ele.prev = null;
head.prev = ele;
head = ele;
}
N++;
}
public String toString()
{
String r = "";
ListElement<KeyType, ValueType> ele;
ele = head;
r = r + "{";
while ( ele != null )
{
r = r + ele + " ";
ele = ele.next;
}
return(r);
}
}
ListMap.java:
public class ListMap<KeyType, ValueType> extends List<KeyType, ValueType>
{
public int size()
{
return(N);
}
public boolean isEmpty()
{
return(N==0);
}
public ValueType get(KeyType k)
{
ListElement<KeyType, ValueType> ele;
for ( ele = head; ele!= null; ele = ele.next )
{
if ( ele.key.equals( k ) )
return( ele.value );
}
return(null);
}
public ValueType put(KeyType k, ValueType v)
{
ListElement<KeyType, ValueType> ele;
ValueType oldval;
for ( ele = head; ele != null; ele = ele.next )
{
if (ele.key.equals( k ) )
{
oldval = ele.value;
ele.value = v;
return( oldval );
}
}
ele = new ListElement<KeyType, ValueType> (k, v);
insert(ele);
return(null);
}
public ValueType remove(KeyType k)
{
ListElement<KeyType, ValueType> ele;
ValueType oldval;
for ( ele = head; ele!= null; ele= ele.next )
{
if ( ele.key.equals( k ) )
{
oldval = ele.value;
delete(ele);
return(oldval);
}
}
return(null); }
public Collection<KeyType> keySet()
{
LinkedList<KeyType> r = new LinkedList<KeyType>();
ListElement<KeyType, ValueType> ele;
for ( ele = head; ele != null; ele = ele.next )
{
r.add( ele.key );
}
return(r);
}
public Collection<ValueType> values()
{
LinkedList<ValueType> r = new LinkedList<ValueType>();
ListElement<KeyType, ValueType> ele;
for ( ele = head; ele!= null; ele = ele.next )
{
r.add( ele.value );
}
return(r);
}
public Collection<ListElement<KeyType, ValueType>> entrySet()
{
LinkedList<ListElement<KeyType, ValueType>> r
= new LinkedList<ListElement<KeyType, ValueType>>();
ListElement<KeyType, ValueType> ele;
for ( ele = head; ele != null; ele= ele.next )
{
r.add( ele );
}
return(r);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.