DamSi

Untitled

Nov 23rd, 2015
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.20 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. public class RoutingHashJava {
  6.  
  7.     public static void main(String[] args) throws IOException {
  8.         BufferedReader data = new BufferedReader(new InputStreamReader(System.in));
  9.         CBHT<String, String[]> routingTable = new CBHT<>(150);
  10.         int numOfRoutes = Integer.parseInt(data.readLine());
  11.         for (int i = 0; i < numOfRoutes; ++i) {
  12.             String input = data.readLine();
  13.             String iface = input;
  14.             input = data.readLine();
  15.             String[] ips = input.split(",");
  16.             routingTable.insert(iface, ips);
  17.         }
  18.         numOfRoutes = Integer.parseInt(data.readLine());
  19.         for (int i = 1; i < numOfRoutes; ++i) {
  20.             String iface = data.readLine();
  21.             String ip = data.readLine();
  22.             SLLNode<MapEntry<String, String[]>> entry = routingTable.search(iface);
  23.             if (entry == null) {
  24.                 System.out.println("ne postoi");
  25.                 continue;
  26.             } else {
  27.                 String[] ips = entry.element.value;
  28.                 boolean postoi = false;
  29.                 for (String routeip : ips) {
  30.                     String[] deloviRouteIP = routeip.split("\\.");
  31.                     String[] deloviIP = ip.split("\\.");
  32.                     for (int j = 0; j < 3; ++j) {
  33.                         if (deloviRouteIP[j].equals(deloviIP[j])) {
  34.                             postoi = true;
  35.                             break;
  36.                         }
  37.                     }
  38.                 }
  39.                 System.out.println();
  40.                 System.out.println(postoi ? "postoi" : "ne postoi");
  41.             }
  42.  
  43.         }
  44.     }
  45.  
  46. }
  47.  
  48. class CBHT<K extends Comparable<K>, E> {
  49.  
  50.     // An object of class CBHT is a closed-bucket hash table, containing
  51.     // entries of class MapEntry.
  52.     private SLLNode<MapEntry<K, E>>[] buckets;
  53.  
  54.     @SuppressWarnings("unchecked")
  55.     public CBHT(int m) {
  56.         // Construct an empty CBHT with m buckets.
  57.         buckets = (SLLNode<MapEntry<K, E>>[]) new SLLNode[m];
  58.     }
  59.  
  60.     private int hash(K key) {
  61.         // Translate key to an index of the array buckets.
  62.         return Math.abs(key.hashCode()) % buckets.length;
  63.     }
  64.  
  65.     public SLLNode<MapEntry<K, E>> search(K targetKey) {
  66.         // Find which if any node of this CBHT contains an entry whose key is
  67.         // equal
  68.         // to targetKey. Return a link to that node (or null if there is none).
  69.         int b = hash(targetKey);
  70.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  71.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key)) {
  72.                 return curr;
  73.             }
  74.         }
  75.         return null;
  76.     }
  77.  
  78.     public void insert(K key, E val) {      // Insert the entry <key, val> into this CBHT.
  79.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  80.         int b = hash(key);
  81.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  82.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  83.                 // Make newEntry replace the existing entry ...
  84.                 curr.element = newEntry;
  85.                 return;
  86.             }
  87.         }
  88.         // Insert newEntry at the front of the 1WLL in bucket b ...
  89.         buckets[b] = new SLLNode<MapEntry<K, E>>(newEntry, buckets[b]);
  90.     }
  91.     public void delete(K key) {
  92.         // Delete the entry (if any) whose key is equal to key from this CBHT.
  93.         int b = hash(key);
  94.         for (SLLNode<MapEntry<K, E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  95.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  96.                 if (pred == null) {
  97.                     buckets[b] = curr.succ;
  98.                 } else {
  99.                     pred.succ = curr.succ;
  100.                 }
  101.                 return;
  102.             }
  103.         }
  104.     }
  105.  
  106.     public String toString() {
  107.         String temp = "";
  108.         for (int i = 0; i < buckets.length; i++) {
  109.             temp += i + ":";
  110.             for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  111.                 temp += curr.element.toString() + " ";
  112.             }
  113.             temp += "\n";
  114.         }
  115.         return temp;
  116.     }
  117.  
  118. }
  119.  class MapEntry<K extends Comparable<K>, E> implements Comparable<K> {
  120.  
  121.     // Each MapEntry object is a pair consisting of a key (a Comparable
  122.     // object) and a value (an arbitrary object).
  123.     K key;
  124.     E value;
  125.  
  126.     public MapEntry(K key, E val) {
  127.         this.key = key;
  128.         this.value = val;
  129.     }
  130.  
  131.     public int compareTo(K that) {
  132.         // Compare this map entry to that map entry.
  133.         @SuppressWarnings("unchecked")
  134.         MapEntry<K, E> other = (MapEntry<K, E>) that;
  135.         return this.key.compareTo(other.key);
  136.     }
  137.  
  138.     public String toString() {
  139.         return "<" + key + "," + value + ">";
  140.     }
  141. }
  142. class SLLNode<E> {
  143.     protected E element;
  144.     protected SLLNode<E> succ;
  145.  
  146.     public SLLNode(E elem, SLLNode<E> succ) {
  147.         this.element = elem;
  148.         this.succ = succ;
  149.     }
  150.  
  151.     @Override
  152.     public String toString() {
  153.         return element.toString();
  154.     }
  155. }
Advertisement
Add Comment
Please, Sign In to add comment