Advertisement
Guest User

Untitled

a guest
Nov 27th, 2015
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.82 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  5. // Each MapEntry object is a pair consisting of a key (a Comparable
  6. // object) and a value (an arbitrary object).
  7. K key;
  8. E value;
  9. public MapEntry (K key, E val) {
  10. this.key = key;
  11. this.value = val;
  12. }
  13.  
  14. public int compareTo (K that) {
  15. // Compare this map entry to that map entry.
  16. @SuppressWarnings("unchecked")
  17. MapEntry<K,E> other = (MapEntry<K,E>) that;
  18. return this.key.compareTo(other.key);
  19. }
  20. public String toString () {
  21. return "<" + key + "," + value + ">";
  22. }
  23. }
  24. class SLLNode<E> {
  25. protected E element;
  26. protected SLLNode<E> succ;
  27. public SLLNode(E elem, SLLNode<E> succ) {
  28. this.element = elem;
  29. this.succ = succ;
  30. }
  31. @Override
  32. public String toString() {
  33. return element.toString();
  34. }
  35. }
  36. class CBHT<K extends Comparable<K>, E> {
  37. // An object of class CBHT is a closed-bucket hash table, containing
  38. // entries of class MapEntry.
  39. private SLLNode<MapEntry<K,E>>[] buckets;
  40. @SuppressWarnings("unchecked")
  41. public CBHT(int m) {
  42. // Construct an empty CBHT with m buckets.
  43. buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  44. }
  45. private int hash(K key) {
  46. // Translate key to an index of the array buckets.
  47. return Math.abs(key.hashCode()) % buckets.length;
  48. }
  49. public SLLNode<MapEntry<K,E>> search(K targetKey) {
  50. // Find which if any node of this CBHT contains an entry whose key is
  51. // equal
  52. // to targetKey. Return a link to that node (or null if there is none).
  53. int b = hash(targetKey);
  54. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  55. if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  56. return curr;
  57. }
  58. return null;
  59. }
  60. public void insert(K key, E val) { // Insert the entry <key, val> into this CBHT.
  61. MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  62. int b = hash(key);
  63. for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  64. if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  65. // Make newEntry replace the existing entry ...
  66. curr.element = newEntry;
  67. return;
  68. }
  69. }
  70. // Insert newEntry at the front of the 1WLL in bucket b ...
  71. buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  72. }
  73. public void delete(K key) {
  74. // Delete the entry (if any) whose key is equal to key from this CBHT.
  75. int b = hash(key);
  76. for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  77. if (key.equals(((MapEntry<K,E>) curr.element).key)) {
  78. if (pred == null)
  79. buckets[b] = curr.succ;
  80. else
  81. pred.succ = curr.succ;
  82. return;
  83. }
  84. }
  85. }
  86. public String toString() {
  87. String temp = "";
  88. for (int i = 0; i < buckets.length; i++) {
  89. temp += i + ":";
  90. for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  91. temp += curr.element.toString() + " ";
  92. }
  93. temp += "\n";
  94. }
  95. return temp;
  96. }
  97. }
  98. /////////////////////////////////////////////
  99. public class RoutingHashJava {
  100.  
  101.  
  102.  
  103. public static void main (String[] args) throws IOException {
  104.  
  105. CBHT<String,String[]> tabela;
  106. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  107. int N = Integer.parseInt(br.readLine());
  108.  
  109.  
  110. tabela=new CBHT<String,String[]>(2*N); //za 0.5 load factor
  111.  
  112. for(int i=1;i<=N;i++){
  113.  
  114. String interfejs=br.readLine(); //adresa na interfejs
  115. String mrezhi=br.readLine(); //adresi na mrezhi do koi ruterot ima statici ruti
  116. String[] nizaMrezhi = mrezhi.split(",");
  117. tabela.insert(interfejs, nizaMrezhi);
  118.  
  119. }
  120.  
  121.  
  122. N = Integer.parseInt(br.readLine());
  123.  
  124.  
  125. for (int i=1;i<=N;i++) //ovoj ni e glaven for kade sto ke go izminuvame vlezot od oblik (interfejs/novred/mrezha)
  126. {
  127. String interfejs=br.readLine(); // ja citame adresata na interfejs
  128. String mreza=br.readLine(); // i ja citame adresata na mrezata
  129. String pom1 = mreza.substring(0,mreza.lastIndexOf(".")); // so ova od mrezata koja momentalno ja citame
  130. //go zimame delot do poslednata tocka
  131. //23.3.3.3 --> 23.3.3
  132. //ovoj string pom1 ke ni treba posle
  133. //koga ke ja sporeduvame ovaa mreza so nizataMrezhi
  134. //za soodvetniot interfejs
  135. //dokolku ovaa pom1 se sovpaga so nekoja mrezha
  136. //od soodvetnata nizataMrezhi ke vratime "postoi"
  137. // a ako gi izmineme site od nizataMrezhi i pom1 nema
  138. //da se sovpadne so nitu edna vrakame "ne postoi"
  139.  
  140.  
  141. SLLNode<MapEntry<String, String[]>> momentalen = tabela.search(interfejs); //barame dali vneseniot interfejs go ima vo
  142. // tabelata koja e od oblik
  143. //<interfejs,nizaMrezhi>
  144. //<interfejs,nizaMrezhi>
  145. //<interfejs,nizaMrezhi> ....
  146.  
  147.  
  148. if(momentalen == null) //ako ne go najdeme pecatime "ne postoi"
  149. {
  150.  
  151. System.out.println("ne postoi");
  152. continue; // ke se vrati vo for-ot za i+1
  153. }
  154.  
  155. else //ako go najdeme soodvetniot interfejs, prodolzuvame da rabotime so negovata nizaMrezhi
  156.  
  157. {
  158. String[] nizaMrezhi = momentalen.element.value; //nizataMrezhi za interfejsot koj momentalno go razgleduvame vo tabelata
  159.  
  160.  
  161. boolean flag = false;
  162. for(int k = 0; k<nizaMrezhi.length;k++){
  163.  
  164. String mrezha = nizaMrezhi[k];
  165. String pom2=mrezha.substring(0,mrezha.lastIndexOf(".")); // od nizataMrezhi soodvetni za interfejsot gi izminuvame site so for
  166. if(pom1.equals(pom2)) // se dodeka ne najdeme soodvetna ili dodeka ne
  167. flag=true; //gi izmineme site. Za da proveriem dali e soodvetna
  168. } //vo pom2 zacuvuvame delot od adresata na mrezata do pslednata tocka
  169. //primer: 23.3.3.3 --> 23.3.3
  170. //i toj go sporeduvame so pom1 koj ni bese adresata na vleznata mrezha
  171.  
  172. if(flag) System.out.println("postoi");
  173. else System.out.println("ne postoi");
  174.  
  175. }
  176. }
  177. }
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement