fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. import java.util.Scanner;
  7. import java.util.StringTokenizer;
  8.  
  9.  
  10. class AVL <Key extends Comparable<Key>, Value> {
  11.     public class Node {
  12.         private int h;
  13.         private int balance;
  14.         Key key;
  15.         Value value;
  16.         private Node left, right, father;
  17.         public Node (Key key, Value value, Node father) {
  18.             this.key = key;
  19.             this.value = value;
  20.             this.left = this.right = null;
  21.             this.father = father;
  22.             this.h = 1;
  23.             this.balance = 0;
  24.         }
  25.         public Node next(){
  26.             return getHigherNode(this.key);
  27.         }
  28.         public Node previus(){
  29.             return getLowerNode(this.key);
  30.         }
  31.     }
  32.  
  33.     private Node root;
  34.  
  35.     //Возвращает ближайщий узел , больше данного ключа, если узла с таким ключом нет, то возвращает ближайщий узел, больше заданного ключа. Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null
  36.     private Node getHigherNode(Key key) {
  37.         Node p = root;
  38.         while (p != null) {
  39.             int cmp = key.compareTo(p.key);
  40.             if (cmp < 0) {
  41.                 if (p.left != null)
  42.                     p = p.left;
  43.                 else
  44.                     return p;
  45.             } else {
  46.                 if (p.right != null) {
  47.                     p = p.right;
  48.                 } else {
  49.                     Node father = p.father;
  50.                     Node ch = p;
  51.                     while (father != null && ch == father.right) {
  52.                         ch = father;
  53.                         father = father.father;
  54.                     }
  55.                     return father;
  56.                 }
  57.             }
  58.         }
  59.         return null;
  60.     }
  61.     //Возвращает ближайщий узел , меньше данного ключа, если узла с таким ключом нет, то возвращает ближайщий узел, меньше заданного ключа. Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null
  62.     private Node getLowerNode(Key key) {
  63.         Node p = root;
  64.         while (p != null) {
  65.             int cmp = key.compareTo(p.key);
  66.             if (cmp > 0) {
  67.                 if (p.right != null)
  68.                     p = p.right;
  69.                 else
  70.                     return p;
  71.             } else {
  72.                 if (p.left != null) {
  73.                     p = p.left;
  74.                 } else {
  75.                     Node father = p.father;
  76.                     Node ch = p;
  77.                     while (father != null && ch == father.left) {
  78.                         ch = father;
  79.                         father = father.father;
  80.                     }
  81.                     return father;
  82.                 }
  83.             }
  84.         }
  85.         return null;
  86.     }
  87.  
  88.     public Node getFirstNode(){
  89.         return min(root);
  90.     }
  91.  
  92.     public Node getLastNode(){
  93.         return max(root);
  94.     }
  95.  
  96.     private int height(Node x, Node y){
  97.         if(x == null && y == null) return 0;
  98.         else if(x == null) return y.h;
  99.         else if(y == null) return x.h;
  100.         else return Math.max(x.h, y.h);
  101.     }
  102.  
  103.     private int balance(Node x, Node y){
  104.         if(x == null && y == null) return 0;
  105.         else if(x == null) return - y.h;
  106.         else if(y == null) return x.h;
  107.         else return x.h - y.h;
  108.     }
  109.  
  110.     private Node add (Node node,Key key, Value value, Node father){
  111.         if (node == null){
  112.             Node newnode = new Node(key,value, father);
  113.             return newnode;
  114.         }
  115.         int compareResult = key.compareTo(node.key);
  116.         if (compareResult > 0){node.right = add(node.right, key, value, node); node.h = height(node.left, node.right) + 1;}
  117.         else if(compareResult < 0){node.left = add(node.left, key, value, node); node.h = height(node.left, node.right) + 1;}
  118.         else{
  119.             node.value = value;
  120.         }
  121.         node.balance = balance(node.left, node.right);
  122.         if(node.balance == -2){
  123.             node = leftRotation(node);
  124.         }else if(node.balance == 2){
  125.             node = rightRotation(node);
  126.         }
  127.         return node;
  128.     }
  129.  
  130.     private Node leftRotation(Node node) {
  131.         if(node.right.right == null && node.right.left != null){
  132.             node.right = rightRotation(node.right);
  133.             node = leftRotation(node);
  134.         }else if(node.right.left == null || node.right.left.h <= node.right.right.h){
  135.             Node newnode = node.right;
  136.             newnode.father = node.father;
  137.             node.right = newnode.left;
  138.             if(node.right != null)
  139.                 node.right.father = node;
  140.             node.h = height(node.left, node.right)+1;
  141.             node.father = newnode;
  142.             node.balance = balance(node.left, node.right);
  143.             newnode.left = node;
  144.             node = newnode;
  145.             node.balance = balance(node.left, node.right);
  146.             node.h = height(node.left, node.right)+1;
  147.         }else{
  148.             node.right = rightRotation(node.right);
  149.             node = leftRotation(node);
  150.         }
  151.         return node;
  152.     }
  153.     private Node rightRotation(Node node){
  154.         if(node.left.right != null && node.left.left == null){
  155.             node.left = leftRotation(node.left);
  156.             node = rightRotation(node);
  157.         }else if(node.left.right == null || node.left.right.h <= node.left.left.h){
  158.             Node newnode = node.left;
  159.             newnode.father = node.father;
  160.             node.left = newnode.right;
  161.             if(node.left != null)
  162.                 node.left.father = node;
  163.             node.h = height(node.left, node.right)+1;
  164.             node.father = newnode;
  165.             node.balance = balance(node.left, node.right);
  166.             newnode.right = node;
  167.             node = newnode;
  168.             node.balance = balance(node.left, node.right);
  169.             node.h = height(node.left, node.right)+1;
  170.         }else{
  171.             node.left = leftRotation(node.left);
  172.             node = rightRotation(node);
  173.         }
  174.         return node;
  175.     }
  176.  
  177.     public void add(Key key, Value value) {
  178.         root = add(root, key, value, null);
  179.     }
  180.  
  181.     private Node delete(Node node, Key key){
  182.         if(node == null) return null;
  183.         int compareResult = key.compareTo(node.key);
  184.         if(compareResult > 0){
  185.             node.right = delete(node.right, key);
  186.         }else if(compareResult < 0){
  187.             node.left = delete(node.left, key);
  188.         }else{
  189.             if(node.right == null && node.left == null){
  190.                 node = null;
  191.             }else if(node.right == null){
  192.                 node.left.father = node.father;
  193.                 node = node.left;
  194.             }else if(node.left == null){
  195.                 node.right.father = node.father;
  196.                 node = node.right;
  197.             }else{
  198.                 if(node.right.left == null){
  199.                     node.right.left = node.left;
  200.                     node.right.father = node.father;
  201.                     node.right.father = node.father;
  202.                     node.left.father = node.right;
  203.                     node = node.right;
  204.                 }else{
  205.                     Node res = min(node.right);
  206.                     node.key = res.key;
  207.                     node.value = res.value;
  208.                     delete(node.right, node.key);
  209.                 }
  210.             }
  211.         }
  212.         if(node != null) {
  213.             node.h = height(node.left, node.right) + 1;
  214.             node.balance = balance(node.left, node.right);
  215.             if (node.balance == -2) {
  216.                 node = leftRotation(node);
  217.             } else if (node.balance == 2) {
  218.                 node = rightRotation(node);
  219.             }
  220.         }
  221.         return node;
  222.     }
  223.  
  224.     public void delete(Key key) {
  225.         root = delete(root, key);
  226.     }
  227.  
  228.     public Key minKey(){
  229.         return min(root).key;
  230.     }
  231.  
  232.     public Key maxKey(){
  233.         return max(root).key;
  234.     }
  235.  
  236.     private Node min(Node node){
  237.         if(node.left == null) return node;
  238.         return min(node.left);
  239.     }
  240.  
  241.     private Node max(Node node){
  242.         if(node.right == null) return node;
  243.         return min(node.right);
  244.     }
  245.  
  246.     private Value get(Node node, Key key){
  247.         if(node == null) return null;
  248.         int compareResult = key.compareTo(node.key);
  249.         if(compareResult == 0){
  250.             return node.value;
  251.         }else if(compareResult > 0){
  252.             return get(node.right, key);
  253.         }else{
  254.             return get(node.left, key);
  255.         }
  256.     }
  257.  
  258.     public Value get(Key key) {
  259.         return get(root, key);
  260.     }
  261.  
  262.     private void print(Node node, int level) {
  263.         if (node != null) {
  264.             print(node.right,level+1);
  265.             for (int i=0;i<level;i++) {
  266.                 System.out.print("\t");
  267.             }
  268.             System.out.println(node.key + "->" + node.value+" h="+node.h+" balance="+node.balance);
  269.             print(node.left,level+1);
  270.         }
  271.     }
  272.  
  273.     public void print() {
  274.         print(root,0);
  275.     }
  276.  
  277. }
  278.  
  279. class Vocabular{
  280.     private AVL<String, Statistic> voc;
  281.     int gloablCount = 0;
  282.     public class Statistic{
  283.         private int Count;
  284.         private double Percent;
  285.         Statistic(){
  286.             Count = 1;
  287.             Percent = 0;
  288.         }
  289.         public int getCount(){
  290.             return Count;
  291.         }
  292.         public double getPercent(){
  293.             return Percent;
  294.         }
  295.     }
  296.     public Vocabular(String text, String delimiters){
  297.         voc = new AVL();
  298.         StringTokenizer st = new StringTokenizer(text, delimiters);
  299.         while (st.hasMoreTokens()){
  300.             String key = st.nextToken();
  301.             Statistic value = voc.get(key);
  302.             if (null != value){
  303.                 value.Count++;
  304.                 voc.add(key, value);
  305.             }else{
  306.                 value = new Statistic();
  307.                 voc.add(key, value);
  308.             }
  309.             gloablCount++;
  310.         }
  311.         for(AVL<String, Statistic>.Node e = voc.getFirstNode(); e != null; e = e.next()){
  312.             e.value.Percent = (double)e.value.Count/gloablCount;
  313.         }
  314.     }
  315.  
  316.     public AVL<String, Statistic>.Node getFirstNode(){
  317.         return voc.getFirstNode();
  318.     }
  319.  
  320.     public double getValue(String key){
  321.         Statistic v = voc.get(key);
  322.         if(v == null) return 0;
  323.         else return v.Percent;
  324.     }
  325. }
  326.  
  327.  
  328.  
  329. /* Name of the class has to be "Main" only if the class is public. */
  330. class Ideone
  331. {
  332. 	public static void main (String[] args) throws java.lang.Exception
  333. 	{
  334. 		String text = "";
  335.         Scanner in = new Scanner(System.in);
  336.         for(;;){
  337.             if(!in.hasNextLine()) break;
  338.             String inputLine = in.nextLine();
  339.             if(inputLine == null || inputLine.equals("%EOF%")) break;
  340.             text = text + inputLine + "\n";
  341.         }
  342.         in.close();
  343.         if(text.isEmpty()){
  344.             System.out.println("*** Empty text ****");
  345.             return;
  346.         }
  347.         Vocabular voc = new Vocabular(text, " ?.,;:-+\n\t{}[]=()<>*&%$#@\"\'“”`~!");
  348.         for(AVL<String, Vocabular.Statistic>.Node e = voc.getFirstNode(); e != null; e = e.next()){
  349.             System.out.println(e.key+" "+e.value.getCount()+" "+e.value.getPercent());
  350.         }
  351. 	}
  352. }
Success #stdin #stdout 0.17s 321344KB
comments (?)
stdin 
#include <iostream>
using namespace std;
int main() {

for( int i = 0; i < 10; i++ )
{
if( i % 2 == 0 )
{
cout << “Even” << endl;
}
else
{
cout << “Odd” << endl;
}
}
return 0;
}

%EOF%
stdout 
0 3 0.1111111111111111
10 1 0.037037037037037035
2 1 0.037037037037037035
Even 1 0.037037037037037035
Odd 1 0.037037037037037035
cout 2 0.07407407407407407
else 1 0.037037037037037035
endl 2 0.07407407407407407
for 1 0.037037037037037035
i 4 0.14814814814814814
if 1 0.037037037037037035
include 1 0.037037037037037035
int 2 0.07407407407407407
iostream 1 0.037037037037037035
main 1 0.037037037037037035
namespace 1 0.037037037037037035
return 1 0.037037037037037035
std 1 0.037037037037037035
using 1 0.037037037037037035
https://ideone.com/4wurcy
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!