Advertisement
Guest User

3

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