Guest User

Untitled

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