DamSi

Untitled

Nov 23rd, 2015
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.18 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Scanner;
  3.  
  4. public class RoutingHashJava {
  5.  
  6.     class SLLNode<E> {
  7.         protected E element;
  8.         protected SLLNode<E> succ;
  9.  
  10.         public SLLNode(E elem, SLLNode<E> succ) {
  11.             this.element = elem;
  12.             this.succ = succ;
  13.         }
  14.  
  15.         @Override
  16.         public String toString() {
  17.             return element.toString();
  18.         }
  19.     }
  20.  
  21.     // MAP
  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.  
  36.             return this.key.compareTo(that);
  37.         }
  38.  
  39.         public String toString() {
  40.             return "<" + key + "," + value + ">";
  41.         }
  42.     }
  43.  
  44.     // CBHT
  45.     class CBHT<K extends Comparable<K>, E> {
  46.  
  47.         // An object of class CBHT is a closed-bucket hash table, containing
  48.         // entries of class MapEntry.
  49.         private SLLNode<MapEntry<K, E>>[] buckets;
  50.  
  51.         @SuppressWarnings("unchecked")
  52.         public CBHT(int m) {
  53.             // Construct an empty CBHT with m buckets.
  54.             buckets = (SLLNode<MapEntry<K, E>>[]) new SLLNode[m];
  55.         }
  56.  
  57.         private int hash(K key) {
  58.             // Translate key to an index of the array buckets.
  59.             return Math.abs(key.hashCode()) % buckets.length;
  60.         }
  61.  
  62.         public SLLNode<MapEntry<K, E>> search(K targetKey) {
  63.             // Find which if any node of this CBHT contains an entry whose key
  64.             // is
  65.             // equal
  66.             // to targetKey. Return a link to that node (or null if there is
  67.             // none).
  68.             int b = hash(targetKey);
  69.             for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  70.                 if (targetKey.compareTo(curr.element.key) == 0)
  71.                     return curr;
  72.             }
  73.             return null;
  74.         }
  75.  
  76.         public void insert(K key, E val) { // Insert the entry <key, val> into
  77.                                             // this
  78.                                             // 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(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.  
  92.         public void delete(K key) {
  93.             // Delete the entry (if any) whose key is equal to key from this
  94.             // CBHT.
  95.             int b = hash(key);
  96.             for (SLLNode<MapEntry<K, E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  97.                 if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  98.                     if (pred == null)
  99.                         buckets[b] = curr.succ;
  100.                     else
  101.                         pred.succ = curr.succ;
  102.                     return;
  103.                 }
  104.             }
  105.         }
  106.  
  107.         public String toString() {
  108.             String temp = "";
  109.             for (int i = 0; i < buckets.length; i++) {
  110.                 temp += i + ":";
  111.                 for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  112.                     temp += curr.element.toString() + " ";
  113.                 }
  114.                 temp += "\n";
  115.             }
  116.             return temp;
  117.         }
  118.  
  119.         public boolean ima(K key, String val) {
  120.             SLLNode<MapEntry<K, E>> tmp = search(key);
  121.  
  122.             if (tmp != null) {
  123.                 IPs adresi = (IPs) tmp.element.value;
  124.                 if (adresi.postoi(val))
  125.                     return true;
  126.                 else
  127.                     return false;
  128.  
  129.             } else
  130.                 return false;
  131.  
  132.         }
  133.  
  134.     }
  135.    
  136.     class Ruter implements Comparable<Ruter> {
  137.         protected String adresa;
  138.  
  139.         Ruter(String s) {
  140.             adresa = s;
  141.         }
  142.  
  143.         @Override
  144.         public int hashCode() {
  145.             int sum = 0;
  146.             for (int i = 0; i < adresa.length(); i++)
  147.                 sum += adresa.charAt(i);
  148.             return sum;
  149.         }
  150.  
  151.         public int compareTo(Ruter r) {
  152.             if (adresa.equals(r.adresa))
  153.                 return 0;
  154.             else
  155.                 return -1;
  156.  
  157.         }
  158.     }
  159.  
  160.     class IPs {
  161.         protected ArrayList<String> lista;
  162.  
  163.         IPs() {
  164.  
  165.             lista = new ArrayList<String>();
  166.         }
  167.  
  168.         public boolean postoi(String s) {
  169.             int ind = s.lastIndexOf('.');
  170.             s = s.substring(0, ind);
  171.  
  172.             for (int i = 0; i < lista.size(); i++) {
  173.                 String nov = lista.get(i);
  174.                 int indd = nov.lastIndexOf('.');
  175.                 nov = nov.substring(0, indd);
  176.  
  177.                 if (s.equals(nov))
  178.                     return true;
  179.             }
  180.             return false;
  181.         }
  182.  
  183.         public void add(String s) {
  184.             lista.add(s);
  185.         }
  186.  
  187.     }
  188.  
  189.     /**
  190.      * @param args
  191.      */
  192.     public static void main(String[] args) {
  193.         // TODO Auto-generated method stub
  194.         RoutingHashJava x = new RoutingHashJava();
  195.         Scanner br = new Scanner(System.in);
  196.         int N = Integer.parseInt(br.nextLine());
  197.  
  198.         CBHT<Ruter, IPs> heshRuteri = x.new CBHT<Ruter, IPs>(200);
  199.  
  200.         for (int i = 0; i < N; i++) {
  201.  
  202.             Ruter r = x.new Ruter(br.nextLine());
  203.             IPs ips = x.new IPs();
  204.             String adresi = br.nextLine();
  205.  
  206.             if (adresi.indexOf(',') != -1) {
  207.  
  208.                 String pomniza[] = adresi.split(",");
  209.                 for (int j = 0; j < pomniza.length; j++) {
  210.                     ips.add(pomniza[j]);
  211.  
  212.                 }
  213.  
  214.             }
  215.  
  216.             else
  217.                 ips.add(adresi);
  218.  
  219.             heshRuteri.insert(r, ips);
  220.  
  221.         }
  222.         int M = Integer.parseInt(br.nextLine());
  223.  
  224.         for (int k = 0; k < M; k++) {
  225.             Ruter rr = x.new Ruter(br.nextLine());
  226.             String adr = br.nextLine();
  227.  
  228.             if (heshRuteri.ima(rr, adr))
  229.                 System.out.println("postoi");
  230.             else
  231.                 System.out.println("ne postoi");
  232.  
  233.         }
  234.         br.close();
  235.     }
  236.  
  237. }
Advertisement
Add Comment
Please, Sign In to add comment