Advertisement
Guest User

Untitled

a guest
Dec 19th, 2014
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.30 KB | None | 0 0
  1. /*
  2. * To change this template, choose Tools | Templates
  3. * and open the template in the editor.
  4. */
  5. package preveduvac;
  6.  
  7. import java.io.BufferedReader;
  8. import java.io.IOException;
  9. import java.io.InputStreamReader;
  10.  
  11. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  12.  
  13. K key;
  14. E value;
  15.  
  16. public MapEntry (K key, E val) {
  17. this.key = key;
  18. this.value = val;
  19. }
  20. public int compareTo (K that) {
  21. @SuppressWarnings("unchecked")
  22. MapEntry<K,E> other = (MapEntry<K,E>) that;
  23. return this.key.compareTo(other.key);
  24. }
  25. public String toString () {
  26. return "(" + key + "," + value + ")";
  27. }
  28. }
  29.  
  30.  
  31. class OBHT<K extends Comparable<K>,E> {
  32.  
  33. private MapEntry<K,E>[] buckets;
  34. static final int NONE = -1; // ... distinct from any bucket index.
  35. @SuppressWarnings({ "rawtypes", "unchecked" })
  36. private static final MapEntry former = new MapEntry(null, null);
  37. private int occupancy = 0;
  38.  
  39. @SuppressWarnings("unchecked")
  40. public OBHT (int m) {
  41. buckets = (MapEntry<K,E>[]) new MapEntry[m];
  42. }
  43.  
  44. private int hash (K key) {
  45. return Math.abs(key.hashCode()) % buckets.length;
  46. }
  47.  
  48. public MapEntry<K,E> getBucket(int i){
  49. return buckets[i];
  50. }
  51.  
  52. public int search (K targetKey) {
  53. int b = hash(targetKey); int n_search=0;
  54. for (;;) {
  55. MapEntry<K,E> oldEntry = buckets[b];
  56. if (oldEntry == null)
  57. return NONE;
  58. else if (targetKey.equals(oldEntry.key))
  59. return b;
  60. else{
  61. b = (b + 1) % buckets.length;
  62. n_search++;
  63. if(n_search==buckets.length)
  64. return NONE;
  65. }
  66. }
  67. }
  68.  
  69. public void insert (K key, E val) {
  70. MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  71. int b = hash(key); int n_search=0;
  72.  
  73. for (;;) {
  74. MapEntry<K,E> oldEntry = buckets[b];
  75. if (oldEntry == null) {
  76. if (++occupancy == buckets.length) {
  77. System.out.println("Hash tabelata e polna!!!");
  78. }
  79. buckets[b] = newEntry;
  80. return;
  81. } else if (oldEntry == former
  82. || key.equals(oldEntry.key)) {
  83. buckets[b] = newEntry;
  84. return;
  85. } else{
  86. b = (b + 1) % buckets.length;
  87. n_search++;
  88. if(n_search==buckets.length)
  89. return;
  90.  
  91. }
  92. }
  93. }
  94.  
  95. @SuppressWarnings("unchecked")
  96. public void delete (K key) {
  97. int b = hash(key); int n_search=0;
  98. for (;;) {
  99. MapEntry<K,E> oldEntry = buckets[b];
  100.  
  101. if (oldEntry == null)
  102. return;
  103. else if (key.equals(oldEntry.key)) {
  104. buckets[b] = former;
  105. return;
  106. } else{
  107. b = (b + 1) % buckets.length;
  108. n_search++;
  109. if(n_search==buckets.length)
  110. return;
  111.  
  112. }
  113. }
  114. }
  115.  
  116. public String toString () {
  117. String temp = "";
  118. for (int i = 0; i < buckets.length; i++) {
  119. temp += i + ":";
  120. if (buckets[i] == null)
  121. temp += "\n";
  122. else if (buckets[i] == former)
  123. temp += "former\n";
  124. else
  125. temp += buckets[i] + "\n";
  126. }
  127. return temp;
  128. }
  129. }
  130.  
  131.  
  132. class Zbor implements Comparable<Zbor>{
  133. String zbor;
  134.  
  135. public Zbor(String zbor) {
  136. this.zbor = zbor;
  137. }
  138. @Override
  139. public boolean equals(Object obj) {
  140. Zbor pom = (Zbor) obj;
  141. return this.zbor.equals(pom.zbor);
  142. }
  143. @Override
  144. public int hashCode() {
  145.  
  146. //return zbor.charAt(0)-'a';
  147. int zbir=0;
  148. for(int i=0;i<zbor.length();i++)
  149. zbir+=zbor.charAt(i)*(i+1);
  150. return zbir;
  151.  
  152.  
  153.  
  154. }
  155. @Override
  156. public String toString() {
  157. return zbor;
  158. }
  159. @Override
  160. public int compareTo(Zbor arg0) {
  161. return zbor.compareTo(arg0.zbor);
  162. }
  163. }
  164.  
  165. public class Preveduvac {
  166. public static void main (String[] args) throws IOException {
  167. OBHT<Zbor,String> tabela;
  168. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  169. int N = Integer.parseInt(br.readLine());
  170. //---Vie odluchete za goleminata na hesh tabelata----
  171. tabela = new OBHT<Zbor,String>(2*N);
  172.  
  173.  
  174. for(int i=1;i<=N;i++){
  175. String maceng = br.readLine();
  176. String[] dva = maceng.split(" ");
  177. Zbor vtor=new Zbor(dva[1]);
  178. tabela.insert(vtor,dva[0]);
  179. }
  180.  
  181. while(true)
  182. {
  183. String prevedi=br.readLine();
  184. if(prevedi.equals("KRAJ")) break;
  185. Zbor prevod=new Zbor(prevedi);
  186. int i=tabela.search(prevod);
  187.  
  188. if(i!=-1)
  189. {
  190. MapEntry<Zbor,String> zbor=tabela.getBucket(i);
  191. System.out.println(zbor.value);
  192. }
  193. else
  194. System.out.println("/");
  195. }
  196. }
  197. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement