Advertisement
Guest User

Untitled

a guest
Dec 9th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.39 KB | None | 0 0
  1. import java.util.*;
  2. public class Preveduvac {
  3.  
  4.     public static void main(String[] args) {
  5.         Scanner skener=new Scanner(System.in);
  6.         String n;
  7.         n=skener.nextLine();
  8.         OBHT <String, String> tabela= new OBHT <String,String>(Integer.parseInt(n)*2);
  9.         for(int i=0;i<Integer.parseInt(n);i++)
  10.             {
  11.             String line=skener.nextLine();
  12.             String s1[]=line.split(" ");
  13.             tabela.insert(s1[1], s1[0]);
  14.             }
  15.         while(skener.hasNext())
  16.         {
  17.             String line=skener.nextLine();
  18.             if(line.equals("KRAJ"))
  19.                 break;
  20.             if(tabela.search(line)==-1)
  21.                 System.out.println("/");
  22.             else
  23.                 System.out.println(tabela.dajmi(tabela.search(line)));
  24.         }
  25.  
  26.     }
  27.  
  28. }
  29.  
  30.  
  31.  
  32. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  33.  
  34.     // Each MapEntry object is a pair consisting of a key (a Comparable
  35.     // object) and a value (an arbitrary object).
  36.     K key;
  37.     E value;
  38.  
  39.     public MapEntry (K key, E val) {
  40.         this.key = key;
  41.         this.value = val;
  42.     }
  43.    
  44.     public int compareTo (K that) {
  45.     // Compare this map entry to that map entry.
  46.         @SuppressWarnings("unchecked")
  47.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  48.         return this.key.compareTo(other.key);
  49.     }
  50.  
  51.     public String toString () {
  52.         return "<" + key + "," + value + ">";
  53.     }
  54. }
  55.  class OBHT<K extends Comparable<K>,E> {
  56.  
  57.     // An object of class OBHT is an open-bucket hash table, containing entries
  58.     // of class MapEntry.
  59.     private MapEntry<K,E>[] buckets;
  60.    
  61.     // buckets[b] is null if bucket b has never been occupied.
  62.     // buckets[b] is former if bucket b is formerly-occupied
  63.     // by an entry that has since been deleted (and not yet replaced).
  64.  
  65.     static final int NONE = -1; // ... distinct from any bucket index.
  66.    
  67.     private static final MapEntry former = new MapEntry(null, null);
  68.     // This guarantees that, for any genuine entry e,
  69.     // e.key.equals(former.key) returns false.
  70.    
  71.     private int occupancy = 0;
  72.     // ... number of occupied or formerly-occupied buckets in this OBHT.
  73.    
  74.     @SuppressWarnings("unchecked")
  75.     public OBHT (int m) {
  76.     // Construct an empty OBHT with m buckets.
  77.         buckets = (MapEntry<K,E>[]) new MapEntry[m];
  78.     }
  79.  
  80.  
  81.     private int hash (K key) {
  82.     // Translate key to an index of the array buckets.
  83.         return Math.abs(key.hashCode()) % buckets.length;
  84.     }
  85.  
  86.    
  87.     public int search (K targetKey) {
  88.     // Find which if any bucket of this OBHT is occupied by an entry whose key
  89.     // is equal to targetKey. Return the index of that bucket.
  90.         int b = hash(targetKey); int n_search=0;
  91.         for (;;) {
  92.             MapEntry<K,E> oldEntry = buckets[b];
  93.             if (oldEntry == null)
  94.                 return NONE;
  95.             else if (targetKey.equals(oldEntry.key))
  96.                 return b;
  97.             else
  98.             {
  99.                 b = (b + 1) % buckets.length;
  100.                 n_search++;
  101.                 if(n_search==buckets.length)
  102.                     return NONE;
  103.  
  104.             }
  105.         }
  106.     }
  107.  
  108.  
  109.     public void insert (K key, E val) {
  110.     // Insert the entry <key, val> into this OBHT.
  111.         MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  112.         int b = hash(key); int n_search=0;
  113.         for (;;) {
  114.             MapEntry<K,E> oldEntry = buckets[b];
  115.             if (oldEntry == null) {
  116.                 if (++occupancy == buckets.length) {
  117.                     System.out.println("Hash tabelata e polna!!!");
  118.                 }
  119.                 buckets[b] = newEntry;
  120.                 return;
  121.             }
  122.             else if (oldEntry == former
  123.                     || key.equals(oldEntry.key)) {
  124.                 buckets[b] = newEntry;
  125.                 return;
  126.             }
  127.             else
  128.             {
  129.                 b = (b + 1) % buckets.length;
  130.                 n_search++;
  131.                 if(n_search==buckets.length)
  132.                     return;
  133.  
  134.             }
  135.         }
  136.     }
  137.  
  138.    
  139.     @SuppressWarnings("unchecked")
  140.     public void delete (K key) {
  141.     // Delete the entry (if any) whose key is equal to key from this OBHT.
  142.         int b = hash(key); int n_search=0;
  143.         for (;;) {
  144.             MapEntry<K,E> oldEntry = buckets[b];
  145.            
  146.             if (oldEntry == null)
  147.                 return;
  148.             else if (key.equals(oldEntry.key)) {
  149.                 buckets[b] = former;//(MapEntry<K,E>)former;
  150.                 return;
  151.             }
  152.             else{
  153.                 b = (b + 1) % buckets.length;
  154.                 n_search++;
  155.                 if(n_search==buckets.length)
  156.                     return;
  157.  
  158.             }
  159.         }
  160.     }
  161.  
  162.  
  163.     public String toString () {
  164.         String temp = "";
  165.         for (int i = 0; i < buckets.length; i++) {
  166.             temp += i + ":";
  167.             if (buckets[i] == null)
  168.                 temp += "\n";
  169.             else if (buckets[i] == former)
  170.                 temp += "former\n";
  171.             else
  172.                 temp += buckets[i] + "\n";
  173.         }
  174.         return temp;
  175.     }
  176.     public E dajmi(int x)
  177.     {
  178.         return buckets[x].value;
  179.     }
  180.  
  181.     public OBHT<K,E> clone () {
  182.         OBHT<K,E> copy = new OBHT<K,E>(buckets.length);
  183.         for (int i = 0; i < buckets.length; i++) {
  184.             MapEntry<K,E> e = buckets[i];
  185.             if (e != null&&e != former)
  186.                 copy.buckets[i] = new MapEntry<K,E>(e.key, e.value);
  187.             else
  188.                 copy.buckets[i] = e;
  189.         }
  190.         return copy;
  191.     }
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement