Advertisement
sindi29

Rodendeni

Jan 24th, 2017
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 7.42 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.Collections;
  6. import java.util.List;
  7.  
  8. class SLLNode<E> {
  9.     protected E element;
  10.     protected SLLNode<E> succ;
  11.  
  12.     public SLLNode(E elem, SLLNode<E> succ) {
  13.         this.element = elem;
  14.         this.succ = succ;
  15.     }
  16.  
  17.     @Override
  18.     public String toString() {
  19.         return element.toString();
  20.     }
  21. }
  22.  
  23. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  24.  
  25.     // Each MapEntry object is a pair consisting of a key (a Comparable
  26.     // object) and a value (an arbitrary object).
  27.     K key;
  28.     E value;
  29.  
  30.     public MapEntry (K key, E val) {
  31.         this.key = key;
  32.         this.value = val;
  33.     }
  34.    
  35.     public int compareTo (K that) {
  36.     // Compare this map entry to that map entry.
  37.         @SuppressWarnings("unchecked")
  38.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  39.         return this.key.compareTo(other.key);
  40.     }
  41.  
  42.     public String toString () {
  43.         return "<" + key + "," + value + ">";
  44.     }
  45. }
  46.  
  47. class OBHT<K extends Comparable<K>,E> {
  48.  
  49.     // An object of class OBHT is an open-bucket hash table, containing entries
  50.     // of class MapEntry.
  51.     public MapEntry<K,E>[] buckets;
  52.    
  53.     // buckets[b] is null if bucket b has never been occupied.
  54.     // buckets[b] is former if bucket b is formerly-occupied
  55.     // by an entry that has since been deleted (and not yet replaced).
  56.  
  57.     static final int NONE = -1; // ... distinct from any bucket index.
  58.    
  59.     private static final MapEntry former = new MapEntry(null, null);
  60.     // This guarantees that, for any genuine entry e,
  61.     // e.key.equals(former.key) returns false.
  62.    
  63.     private int occupancy = 0;
  64.     // ... number of occupied or formerly-occupied buckets in this OBHT.
  65.    
  66.     @SuppressWarnings("unchecked")
  67.     public OBHT (int m) {
  68.     // Construct an empty OBHT with m buckets.
  69.         buckets = (MapEntry<K,E>[]) new MapEntry[m];
  70.     }
  71.  
  72.  
  73.     private int hash (K key) {
  74.     // Translate key to an index of the array buckets.
  75.         return Math.abs(key.hashCode()) % buckets.length;
  76.     }
  77.  
  78.    
  79.     public int search (K targetKey) {
  80.     // Find which if any bucket of this OBHT is occupied by an entry whose key
  81.     // is equal to targetKey. Return the index of that bucket.
  82.         int b = hash(targetKey); int n_search=0;
  83.         for (;;) {
  84.             MapEntry<K,E> oldEntry = buckets[b];
  85.             if (oldEntry == null)
  86.                 return NONE;
  87.             else if (targetKey.equals(oldEntry.key))
  88.                 return b;
  89.             else
  90.             {
  91.                 b = (b + 1) % buckets.length;
  92.                 n_search++;
  93.                 if(n_search==buckets.length)
  94.                     return NONE;
  95.  
  96.             }
  97.         }
  98.     }
  99.  
  100.  
  101.     public void insert (K key, E val) {
  102.     // Insert the entry <key, val> into this OBHT.
  103.         MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  104.         int b = hash(key); int n_search=0;
  105.         for (;;) {
  106.             MapEntry<K,E> oldEntry = buckets[b];
  107.             if (oldEntry == null) {
  108.                 if (++occupancy == buckets.length) {
  109.                     System.out.println("Hash tabelata e polna!!!");
  110.                 }
  111.                 buckets[b] = newEntry;
  112.                 return;
  113.             }
  114.             else if (oldEntry == former
  115.                     || key.equals(oldEntry.key)) {
  116.                 buckets[b] = newEntry;
  117.                 return;
  118.             }
  119.             else
  120.             {
  121.                 b = (b + 1) % buckets.length;
  122.                 n_search++;
  123.                 if(n_search==buckets.length)
  124.                     return;
  125.  
  126.             }
  127.         }
  128.     }
  129.  
  130.    
  131.     @SuppressWarnings("unchecked")
  132.     public void delete (K key) {
  133.     // Delete the entry (if any) whose key is equal to key from this OBHT.
  134.         int b = hash(key); int n_search=0;
  135.         for (;;) {
  136.             MapEntry<K,E> oldEntry = buckets[b];
  137.            
  138.             if (oldEntry == null)
  139.                 return;
  140.             else if (key.equals(oldEntry.key)) {
  141.                 buckets[b] = former;//(MapEntry<K,E>)former;
  142.                 return;
  143.             }
  144.             else{
  145.                 b = (b + 1) % buckets.length;
  146.                 n_search++;
  147.                 if(n_search==buckets.length)
  148.                     return;
  149.  
  150.             }
  151.         }
  152.     }
  153.  
  154.  
  155.     public String toString () {
  156.         String temp = "";
  157.         for (int i = 0; i < buckets.length; i++) {
  158.             temp += i + ":";
  159.             if (buckets[i] == null)
  160.                 temp += "\n";
  161.             else if (buckets[i] == former)
  162.                 temp += "former\n";
  163.             else
  164.                 temp += buckets[i] + "\n";
  165.         }
  166.         return temp;
  167.     }
  168.  
  169.  
  170.     public OBHT<K,E> clone () {
  171.         OBHT<K,E> copy = new OBHT<K,E>(buckets.length);
  172.         for (int i = 0; i < buckets.length; i++) {
  173.             MapEntry<K,E> e = buckets[i];
  174.             if (e != null && e != former)
  175.                 copy.buckets[i] = new MapEntry<K,E>(e.key, e.value);
  176.             else
  177.                 copy.buckets[i] = e;
  178.         }
  179.         return copy;
  180.     }
  181. }
  182.  
  183. class Vraboten implements Comparable<Vraboten>
  184. {
  185.     String ime;
  186.     String prezime;
  187.     int den, mesec, godina;
  188.    
  189.    
  190.     public Vraboten(String ime, String prezime, int den, int mesec, int godina) {
  191.         super();
  192.         this.ime = ime;
  193.         this.prezime = prezime;
  194.         this.den = den;
  195.         this.mesec = mesec;
  196.         this.godina = godina;
  197.     }
  198.  
  199.  
  200.     @Override
  201.     public int compareTo(Vraboten arg0) {
  202.         // TODO Auto-generated method stub
  203.         if(ime.compareTo(arg0.ime)==0)
  204.             return prezime.compareTo(arg0.prezime);
  205.            
  206.         return ime.compareTo(arg0.ime);
  207.     }
  208.     /*public int compareTo(Vraboten arg0) {
  209.         // TODO Auto-generated method stub
  210.         return arg0.godina-godina;
  211.     }*/
  212. }
  213.  
  214. public class HashRodendeni {
  215.  
  216.     public static void main(String[] args) throws IOException {
  217.         // TODO Auto-generated method stub
  218.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  219.         String s, ime, prezime, datum;
  220.         String[] pom;
  221.         String[] pomoshna;
  222.         int i, n, den, mesec, godina, h;
  223.  
  224.         s = br.readLine();
  225.         n = Integer.parseInt(s);
  226.        
  227.         OBHT<String,ArrayList<Vraboten>> tabela = new OBHT<String,ArrayList<Vraboten>>(n+1);
  228.         ArrayList<Vraboten> v;
  229.         for(i=0; i<n; i++)
  230.         {
  231.             s = br.readLine();
  232.             pom = s.split(" ");
  233.             ime = pom[0];
  234.             prezime = pom[1];
  235.             datum = pom[2];
  236.            
  237.             pomoshna = datum.split("/");
  238.             den = Integer.parseInt(pomoshna[0]);
  239.             mesec = Integer.parseInt(pomoshna[1]);
  240.             godina = Integer.parseInt(pomoshna[2]);
  241.             Vraboten k = new Vraboten(ime,prezime,den,mesec,godina);
  242.             String denMesec = pomoshna[0]+"/"+pomoshna[1];
  243.            
  244.             h = tabela.search(denMesec);
  245.             //System.out.println(denMesec);
  246.             if(h == -1)
  247.             {
  248.                 v = new ArrayList<Vraboten>();
  249.                 v.add(k);
  250.                 tabela.insert(denMesec, v);
  251.             }
  252.             else
  253.             {
  254.                 v = tabela.buckets[h].value;
  255.                 v.add(k);
  256.                 tabela.insert(denMesec, v);
  257.             }
  258.         }
  259.        
  260.         s = br.readLine();
  261.         pomoshna = s.split("/");
  262.         String denMesec = pomoshna[0]+ "/" + pomoshna[1];
  263.         int god = Integer.parseInt(pomoshna[2]);
  264.         //System.out.println(denMesec);
  265.        
  266.         h = tabela.search(denMesec);
  267.         if(h == -1)
  268.             System.out.println("Nema");
  269.         else
  270.         {
  271.             v = tabela.buckets[h].value;
  272.             //v.sort(null);
  273.             Collections.sort(v);
  274.             for(i=0; i<v.size(); i++)
  275.             {
  276.                 int f = god - v.get(i).godina;
  277.                 System.out.println(v.get(i).ime +" " + v.get(i).prezime+ " " + f);
  278.             }
  279.         }
  280.     }
  281.  
  282. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement