DamSi

Untitled

Nov 23rd, 2015
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.72 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.List;
  6.  
  7. /**
  8.  *
  9.  * @author Damjan
  10.  */
  11. public class RoutingHashJava {
  12.  
  13.     public static void main(String[] args) throws IOException {
  14.         BufferedReader data = new BufferedReader(new InputStreamReader(System.in));
  15.         CBHT<Router, IPs> routingTable = new CBHT<>(150);
  16.         int numAddresses = Integer.parseInt(data.readLine());
  17.         for (int i = 0; i < numAddresses; ++i) {
  18.             String routerAddress = data.readLine();
  19.             Router r = new Router(routerAddress);
  20.             IPs ip = new IPs();
  21.             String ips = data.readLine();
  22.             if (ips.contains(",")) {
  23.                 String[] parts = ips.split(",");
  24.                 for (int j = 0; j < parts.length; ++j) {
  25.                     ip.addAddress(parts[j]);
  26.                 }
  27.             } else {
  28.                 ip.addAddress(ips);
  29.             }
  30.             routingTable.insert(r, ip);
  31.         }
  32.         int check = Integer.parseInt(data.readLine());
  33.         for (int k = 0; k < check; ++k) {
  34.             String router = data.readLine();
  35.             Router rR = new Router(router);
  36.             String addresses = data.readLine();
  37.             boolean postoi = routingTable.contains(rR, addresses);
  38.             System.out.println(postoi ? "postoi" : "ne postoi");
  39.         }
  40.         data.close();
  41.     }
  42. }
  43.  
  44. class IPs {
  45.  
  46.     private List<String> addresses;
  47.  
  48.     public IPs() {
  49.         addresses = new ArrayList<>();
  50.     }
  51.  
  52.     public List<String> getAddresses() {
  53.         return addresses;
  54.     }
  55.  
  56.     public void addAddress(String address) {
  57.         if (!addresses.contains(address)) {
  58.             addresses.add(address);
  59.         }
  60.     }
  61.  
  62.     public boolean containsAddress(String address) {
  63.         int index = address.lastIndexOf('.');
  64.         address = address.substring(0, index);
  65.         for (int i = 0; i < addresses.size(); ++i) {
  66.             String takeIP = addresses.get(i);
  67.             int indexNew = takeIP.lastIndexOf(".");
  68.             takeIP = takeIP.substring(0, indexNew);
  69.  
  70.             return address.equals(takeIP);
  71.         }
  72.         return false;
  73.     }
  74.  
  75. }
  76.  
  77. class Router implements Comparable<Router> {
  78.  
  79.     private String address;
  80.  
  81.     public Router(String address) {
  82.         this.address = address;
  83.     }
  84.  
  85.     public String getAddress() {
  86.         return address;
  87.     }
  88.  
  89.     @Override
  90.     public boolean equals(Object obj) {
  91.         Router r = (Router) obj;
  92.         return address.equals(r.address);
  93.     }
  94.  
  95.     @Override
  96.     public int hashCode() {
  97.         int sum = 0;
  98.         for (int i = 0; i < address.length(); ++i) {
  99.             sum += address.charAt(i);
  100.         }
  101.         return sum;
  102.     }
  103.  
  104.     @Override
  105.     public int compareTo(Router o) {
  106.         if (address.equals(o.address)) {
  107.             return 1;
  108.         } else {
  109.             return 0;
  110.         }
  111.     }
  112.  
  113. }
  114.  
  115.  
  116. class CBHT<K extends Comparable<K>, E> {
  117.  
  118.     // An object of class CBHT is a closed-bucket hash table, containing
  119.     // entries of class MapEntry.
  120.     private SLLNode<MapEntry<K, E>>[] buckets;
  121.  
  122.     @SuppressWarnings("unchecked")
  123.     public CBHT(int m) {
  124.         // Construct an empty CBHT with m buckets.
  125.         buckets = (SLLNode<MapEntry<K, E>>[]) new SLLNode[m];
  126.     }
  127.  
  128.     private int hash(K key) {
  129.         // Translate key to an index of the array buckets.
  130.         return Math.abs(key.hashCode()) % buckets.length;
  131.     }
  132.    
  133.     boolean contains(K key, String val) {
  134.         SLLNode<MapEntry<K, E>> tmp = search(key);
  135.         if (tmp != null) {
  136.             IPs addresses = (IPs) tmp.element.value;
  137.             return addresses.containsAddress(val);
  138.         } else {
  139.             return false;
  140.         }
  141.     }
  142.     public SLLNode<MapEntry<K, E>> search(K targetKey) {
  143.         // Find which if any node of this CBHT contains an entry whose key is
  144.         // equal
  145.         // to targetKey. Return a link to that node (or null if there is none).
  146.         int b = hash(targetKey);
  147.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  148.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key)) {
  149.                 return curr;
  150.             }
  151.         }
  152.         return null;
  153.     }
  154.  
  155.     public void insert(K key, E val) {      // Insert the entry <key, val> into this CBHT.
  156.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  157.         int b = hash(key);
  158.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  159.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  160.                 // Make newEntry replace the existing entry ...
  161.                 curr.element = newEntry;
  162.                 return;
  163.             }
  164.         }
  165.         // Insert newEntry at the front of the 1WLL in bucket b ...
  166.         buckets[b] = new SLLNode<MapEntry<K, E>>(newEntry, buckets[b]);
  167.     }
  168.     public void delete(K key) {
  169.         // Delete the entry (if any) whose key is equal to key from this CBHT.
  170.         int b = hash(key);
  171.         for (SLLNode<MapEntry<K, E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  172.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  173.                 if (pred == null) {
  174.                     buckets[b] = curr.succ;
  175.                 } else {
  176.                     pred.succ = curr.succ;
  177.                 }
  178.                 return;
  179.             }
  180.         }
  181.     }
  182.  
  183.     public String toString() {
  184.         String temp = "";
  185.         for (int i = 0; i < buckets.length; i++) {
  186.             temp += i + ":";
  187.             for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  188.                 temp += curr.element.toString() + " ";
  189.             }
  190.             temp += "\n";
  191.         }
  192.         return temp;
  193.     }
  194.  
  195. }
  196.  class MapEntry<K extends Comparable<K>, E> implements Comparable<K> {
  197.  
  198.     // Each MapEntry object is a pair consisting of a key (a Comparable
  199.     // object) and a value (an arbitrary object).
  200.     K key;
  201.     E value;
  202.  
  203.     public MapEntry(K key, E val) {
  204.         this.key = key;
  205.         this.value = val;
  206.     }
  207.  
  208.     public int compareTo(K that) {
  209.         // Compare this map entry to that map entry.
  210.         @SuppressWarnings("unchecked")
  211.         MapEntry<K, E> other = (MapEntry<K, E>) that;
  212.         return this.key.compareTo(other.key);
  213.     }
  214.  
  215.     public String toString() {
  216.         return "<" + key + "," + value + ">";
  217.     }
  218. }
  219. class SLLNode<E> {
  220.     protected E element;
  221.     protected SLLNode<E> succ;
  222.  
  223.     public SLLNode(E elem, SLLNode<E> succ) {
  224.         this.element = elem;
  225.         this.succ = succ;
  226.     }
  227.  
  228.     @Override
  229.     public String toString() {
  230.         return element.toString();
  231.     }
  232. }
Advertisement
Add Comment
Please, Sign In to add comment