Advertisement
Guest User

Untitled

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