Advertisement
Guest User

3ta

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