Advertisement
sindi29

Zavod za Vrabotuvanje

Jan 25th, 2017
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.78 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5.  
  6. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  7.  
  8.     // Each MapEntry object is a pair consisting of a key (a Comparable
  9.     // object) and a value (an arbitrary object).
  10.     K key;
  11.     E value;
  12.  
  13.     public MapEntry (K key, E val) {
  14.         this.key = key;
  15.         this.value = val;
  16.     }
  17.    
  18.     public int compareTo (K that) {
  19.     // Compare this map entry to that map entry.
  20.         @SuppressWarnings("unchecked")
  21.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  22.         return this.key.compareTo(other.key);
  23.     }
  24.  
  25.     public String toString () {
  26.         return "<" + key + "," + value + ">";
  27.     }
  28. }
  29. class SLLNode<E> {
  30.     protected E element;
  31.     protected SLLNode<E> succ;
  32.  
  33.     public SLLNode(E elem, SLLNode<E> succ) {
  34.         this.element = elem;
  35.         this.succ = succ;
  36.     }
  37.  
  38.     @Override
  39.     public String toString() {
  40.         return element.toString();
  41.     }
  42. }
  43.  
  44. class CBHT<K extends Comparable<K>, E> {
  45.  
  46.     // An object of class CBHT is a closed-bucket hash table, containing
  47.     // entries of class MapEntry.
  48.     public SLLNode<MapEntry<K,E>>[] buckets; //ova se stava public
  49.  
  50.     @SuppressWarnings("unchecked")
  51.     public CBHT(int m) {
  52.         // Construct an empty CBHT with m buckets.
  53.         buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  54.     }
  55.  
  56.     public int hash(K key) { //ova se stava public
  57.         // Translate key to an index of the array buckets.
  58.         return Math.abs(key.hashCode()) % buckets.length;
  59.     }
  60.  
  61.     public SLLNode<MapEntry<K,E>> search(K targetKey) {
  62.         // Find which if any node of this CBHT contains an entry whose key is
  63.         // equal
  64.         // to targetKey. Return a link to that node (or null if there is none).
  65.         int b = hash(targetKey);
  66.         for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  67.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  68.                 return curr;
  69.         }
  70.         return null;
  71.     }
  72.  
  73.     public void insert(K key, E val) {      // Insert the entry <key, val> into this CBHT.
  74.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  75.         int b = hash(key);
  76.         for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  77.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  78.                 // Make newEntry replace the existing entry ...
  79.                 curr.element = newEntry;
  80.                 return;
  81.             }
  82.         }
  83.         // Insert newEntry at the front of the 1WLL in bucket b ...
  84.         buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  85.     }
  86.  
  87.     public void delete(K key) {
  88.         // Delete the entry (if any) whose key is equal to key from this CBHT.
  89.         int b = hash(key);
  90.         for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  91.             if (key.equals(((MapEntry<K,E>) curr.element).key)) {
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement