Advertisement
Guest User

Untitled

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