АПС - Компанија - Јуни

/*АПС - КОМПАНИЈА
Во една компанија организацијата на работните позиции е дадена како пар (вработен,менаџер) кој кажува кој вработен под кој пенаџер припаѓа. Потребно е да се направи некоја статистика во компанијата и според тоа треба да се даде извештај за тоа колку вработени менаџери од компанијата, колку вработени имаат под нив. Може да се случи менаџер на некои вработени да биде надворешно лице. Еден вработен може да припаѓа на само еден менаџер.

ВЛЕЗ: Во првиот ред од влезот е даден бројот на парови кои ќе се внесува N (N<=10000), а во секој нареден ред се дадени паровите (име_вработен, име_менаџер).

ИЗЛЕЗ: Листата со имињата на вработените менаџери во компанијата и тоа колку вработени имаат под нивно раководство.

ДЕЛУМНО РЕШЕНИЕ: Задачата се смета за делумно решена доколку се поминати 7 тест примери.

ЗАБЕЛЕШКА: Задачата треба да се реши со помош на хеширање.

МОЈ КОМЕНТАР:Тука задачата е решена на два начини, со OBHT или со Map. Искоментираните линии со код се решението со Map, доколку се одлучите да ја решавате со Map, избришете ги останатите класи. Исто така доколку решавате со Map потребно е да направите мала измена во последниот ред код кај делот со substring т.е. да го смените почетниот индекс на substring-от. Еден менаџер не можи сам на себе да е менаџер па затоа доколку името на вработениот и името на менаџерот (клучот) е исто, тој запис не се додава.

*/

import java.util.*;
import java.io.*;

class SLLNode<E> {
    protected E element;
    protected SLLNode<E> succ;

    public SLLNode(E elem, SLLNode<E> succ) {
        this.element = elem;
        this.succ = succ;
    }

    @Override
    public String toString() {
        return element.toString();
    }
}

class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
    // Each MapEntryobject is a pair consisting of a key (a Comparable // object) and a value (an arbitrary object).
    K key;
    E value;
    public MapEntry(K key, E val) {
        this.key= key;this.value= val;
    }
    public int compareTo(K that) {
    // Compare this map entry to that map entry.@SuppressWarnings("unchecked")
        MapEntry<K,E> other = (MapEntry<K,E>) that;
        return this.key.compareTo(other.key);
    }
    public String toString() {
        return "<" + key + "," + value + ">";
    }
}


class CBHT<K extends Comparable<K>, E> {
    private SLLNode<MapEntry<K,E>>[] buckets;
    @SuppressWarnings("unchecked")

    public CBHT(int m) {
        // Construct an empty CBHT with m buckets.
        buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % buckets.length;
    }

    public SLLNode<MapEntry<K,E>> search(K targetKey) {
        int b = hash(targetKey);
        for (SLLNode<MapEntry<K,E>> curr= buckets[b]; curr!= null; curr= curr.succ) {
            if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
                return curr;
        }
        return null;
    }

    public void insert(K key, E val) {
        // Insert the entry <key, val> into this CBHT.
        MapEntry<K, E> newEntry= new MapEntry<K, E>(key, val);
        int b = hash(key);
        for (SLLNode<MapEntry<K,E>> curr= buckets[b]; curr!= null; curr= curr.succ) {
            if (key.equals(((MapEntry<K, E>) curr.element).key)) {
            // Make newEntryreplace the existing entry ...
            curr.element= newEntry;return;
            }
        }
        buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
    }

    public void delete(K key) {
        int b = hash(key);
        for (SLLNode<MapEntry<K,E>> pred= null, curr= buckets[b]; curr!=null; pred=curr, curr=curr.succ) {
            if (key.equals(((MapEntry<K,E>) curr.element).key)) {
                if(pred==null) {
                    buckets[b] = curr.succ;
                }
                else {
                    pred.succ=curr.succ;
                }
                return;
            }
        }
    }
    //mora da se overridne toString

    public String toString() {

        String temp = "";


        for(int i=0;i<buckets.length;i++) {

            for(SLLNode<MapEntry<K, E>> curr = buckets[i]; curr!=null; curr=curr.succ) {
                temp+=curr.element.key.toString() + " " + curr.element.value.toString()+" ";
            }
        }

        return temp;
    }
}

public class Company {

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        //Map<String, Integer> table = new HashMap<String, Integer>(n*2+1);

        CBHT<String, Integer> table = new CBHT<String,Integer>(n*2+1);

        for(int i=0;i<n;i++) {
            String line = in.readLine();
            String [] niza = line.split("\\,");

            String vraboten = niza[0];
            String manager = niza[1];


             SLLNode<MapEntry<String, Integer>> node = table.search(manager);


            if(node!=null) {

                String kluc = node.element.key;

                //System.out.println("KLUC: "+kluc);
                //System.out.println("VRABOTEN: "+vraboten);

                if(!kluc.equals(vraboten)) {
                    //System.out.println("KLUC!=VRABOTEN!");
                    int temp = node.element.value;
                    ++temp;
                    table.insert(manager, temp);
                } else {

                }

            } else {

                table.insert(manager, 1);

            }
            /*
            if(!table.containsKey(manager)) {
                table.put(manager, 1);
            } else {

                Set<String> keys = table.keySet();

                int flag=1;

                for(String key : keys) {
                    if(key.equals(vraboten)) {
                        flag=0;
                    }
                }

                if(flag==1) {
                    int temp = table.get(manager);
                    table.put(manager, temp+1);

                }

            }
        */
        }

        String out = table.toString();
        System.out.println(out.substring(0,out.length()-1));
    }

}