Advertisement
Guest User

Untitled

a guest
Dec 9th, 2018
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.15 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. class SLLNode<E> {
  30. protected E element;
  31. protected SLLNode<E> succ;
  32.  
  33. public SLLNode(E elem, SLLNode<E> succ) {
  34. this.element = elem;
  35. this.succ = succ;
  36. }
  37.  
  38. @Override
  39. public String toString() {
  40. return element.toString();
  41. }
  42. }
  43.  
  44. class CBHT<K extends Comparable<K>, E> {
  45.  
  46. // An object of class CBHT is a closed-bucket hash table, containing
  47. // entries of class MapEntry.
  48. private SLLNode<MapEntry<K,E>>[] buckets;
  49.  
  50. @SuppressWarnings("unchecked")
  51. public CBHT(int m) {
  52. // Construct an empty CBHT with m buckets.
  53. buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  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. public SLLNode<MapEntry<K,E>> search(K targetKey) {
  62. // Find which if any node of this CBHT contains an entry whose key is
  63. // equal
  64. // to targetKey. Return a link to that node (or null if there is none).
  65. int b = hash(targetKey);
  66. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  67. if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  68. return curr;
  69. }
  70. return null;
  71. }
  72.  
  73. public void insert(K key, E val) { // Insert the entry <key, val> into this CBHT.
  74. MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  75. int b = hash(key);
  76. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  77. if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  78. // Make newEntry replace the existing entry ...
  79. curr.element = newEntry;
  80. return;
  81. }
  82. }
  83. // Insert newEntry at the front of the 1WLL in bucket b ...
  84. buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  85. }
  86.  
  87. public void delete(K key) {
  88. // Delete the entry (if any) whose key is equal to key from this CBHT.
  89. int b = hash(key);
  90. for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  91. if (key.equals(((MapEntry<K,E>) curr.element).key)) {
  92. if (pred == null)
  93. buckets[b] = curr.succ;
  94. else
  95. pred.succ = curr.succ;
  96. return;
  97. }
  98. }
  99. }
  100.  
  101. public String toString() {
  102. String temp = "";
  103. for (int i = 0; i < buckets.length; i++) {
  104. temp += i + ":";
  105. for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  106. temp += curr.element.toString() + " ";
  107. }
  108. temp += "\n";
  109. }
  110. return temp;
  111. }
  112.  
  113. }
  114.  
  115. public class RoutingHashJava {
  116. public static void main (String[] args) throws IOException {
  117.  
  118. CBHT<String,String[]> tabela;
  119. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  120. int N = Integer.parseInt(br.readLine());
  121.  
  122. tabela=new CBHT<String,String[]>(2*N);
  123.  
  124. for(int i=1;i<=N;i++){
  125. String interfejs=br.readLine();
  126. String routing_table=br.readLine();
  127.  
  128. String ruti[] = routing_table.split(",");
  129. String hostNetworks[] = new String[ruti.length];
  130. for(int j=0; j<ruti.length; j++) {
  131. hostNetworks[j] = ruti[j].substring(0, ruti[j].lastIndexOf('.'));
  132. }
  133. tabela.insert(interfejs, hostNetworks);
  134. }
  135.  
  136.  
  137. int M = Integer.parseInt(br.readLine());
  138. for (int i=1;i<=M;i++)
  139. {
  140. String ip_adresa_interfejs=br.readLine();
  141. String mreza = br.readLine();
  142. mreza=mreza.substring(0, mreza.lastIndexOf('.'));
  143.  
  144. if(tabela.search(ip_adresa_interfejs) != null) {
  145. String[] hostNetworks = tabela.search(ip_adresa_interfejs).element.value;
  146. for(int j=0; j<hostNetworks.length; j++) {
  147. if (hostNetworks[j].equals(mreza)) {
  148. System.out.println("postoi");
  149. break;
  150. }
  151. if(j == hostNetworks.length-1) System.out.println("ne postoi");
  152. }
  153. }
  154. else System.out.println("ne postoi");
  155. }
  156. }
  157. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement