soundEx algorithm

20/12/2015 by marchelaphil

Немного о фонетических алгоритмах

Фонетические алгоритмы — алгоритмы, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства. Существует достаточно много фонетических алгоритмов, например: NYSIIS, Metaphone, Double Metaphone, Caverphone и т.д. В данном отчёте я напишу об одном из фонетических алгоритмов, который называется soundEx.
soundEx — алгоритм, который был разработан Робертом Расселом и Маргарет Кинг Оделл в 10-х годах прошлого века. В основном, этот алгоритм стал известен после того, как был опубликован в книге Дональда Кнута «Искусство программирования».

soundEx

Пример:

Код	Слово
a500	ammonium
i514	implementation

Данным алгоритмом предусмотрено сопоставление индекса вида LNNN(Q123) слову. Этот код получают следуя следующему алгоритму:

Первая буква сохраняется
Все гласные звуки + буквы h, w отбрасываются
Оставшиеся буквы заменяются цифрами в диапазоне от 1 до 6 по следующим правилам:

B, P, F, V 1

C, S, K, G, J, Q, X, Z 2

D, T 3

L 4

M, N 5

R 6
Последовательность из одинаковых цифр заменяется одной такой цифрой
Полученная строка обрезается до первых 4-х символов. Если в строке меньше 4х, то в конец добавляются нули.

Пример:

javalanguage → jvlngg → j214522 → j21452 → j214

Реализация:

Реализация soundEx приводится по выше описанному алгоритму.
Для тестирования создадим HashMap, в котором по ключу-индексу soundEx будем создавать список слов, подходящих под этот ключ.

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

class Codechef {
	public static String soundEx (String a){
		int n = a.length();
		char [] sdx = a.toUpperCase().toCharArray();
		char fl = sdx[0];
		for (int i = 0 ; i < n; i++){
			switch(sdx[i]) {
				case 'B' :
				case 'P' :
				case 'F' :
				case 'V' :
					sdx[i] = '1';
					break;
				case 'C':
				case 'S':
				case 'K':
				case 'G':
				case 'J':
				case 'Q':
				case 'X':
				case 'Z':
					sdx[i] = '2';
					break;
				case 'D':
				case 'T':
					sdx[i] = '3';
					break;
				case 'L':
					sdx[i] = '4';
					break;
				case 'M':
				case 'N':
					sdx[i] = '5';
					break;
				case 'R' :
					sdx[i] = '6';
					break;
				default: 
					sdx[i] = '0';
					break;
			}
		}
		String retSdx = "" + fl;
		for (int i = 0; i < sdx.length; i++){
			if (sdx[i] != '0') {
				retSdx += sdx[i];
			}
		}
		String ans = ""+fl;
		for (int i = 1; i < retSdx.length(); i++){
			if (retSdx.charAt(i) != (retSdx.charAt(i-1))) {
				ans += retSdx.charAt(i);
			}
		}
		ans = ans + "0000";
		return ans.substring(0, 4);
	}
	public static void main (String[] args) {
		Map <String, List<String> > words = new HashMap<String, List<String> > ();
		Scanner in = new Scanner (System.in);
		String input = in.nextLine();
		input = " " + input;
		String [] t = input.split(" ");
		for (int i = 1; i < t.length; i++) {
			List<String> L = words.get(soundEx(t[i]));
	    	if (L == null)
				words.put(soundEx(t[i]), L=new ArrayList<String>());
			L.add(t[i]);
		}
		for (Object x : words.keySet()){
			System.out.print(x + ": ");
			List<String> L = words.get(x);
			for (Object y : L) System.out.print(y + " ");
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Codechef {

public static String soundEx (String a){

int n = a.length();

char [] sdx = a.toUpperCase().toCharArray();

char fl = sdx[0];

for (int i = 0 ; i < n; i++){

switch(sdx[i]) {

case 'B' :

case 'P' :

case 'F' :

case 'V' :

sdx[i] = '1';

break;

case 'C':

case 'S':

case 'K':

case 'G':

case 'J':

case 'Q':

case 'X':

case 'Z':

sdx[i] = '2';

break;

case 'D':

case 'T':

sdx[i] = '3';

break;

case 'L':

sdx[i] = '4';

break;

case 'M':

case 'N':

sdx[i] = '5';

break;

case 'R' :

sdx[i] = '6';

break;

default:

sdx[i] = '0';

break;

}

String retSdx = "" + fl;

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

if (sdx[i] != '0') {

retSdx += sdx[i];

}

String ans = ""+fl;

for (int i = 1; i < retSdx.length(); i++){

if (retSdx.charAt(i) != (retSdx.charAt(i-1))) {

ans += retSdx.charAt(i);

}

ans = ans + "0000";

return ans.substring(0, 4);

}

public static void main (String[] args) {

Map <String, List<String> > words = new HashMap<String, List<String> > ();

Scanner in = new Scanner (System.in);

String input = in.nextLine();

input = " " + input;

String [] t = input.split(" ");

for (int i = 1; i < t.length; i++) {

List<String> L = words.get(soundEx(t[i]));

if (L == null)

words.put(soundEx(t[i]), L=new ArrayList<String>());

L.add(t[i]);

}

for (Object x : words.keySet()){

System.out.print(x + ": ");

List<String> L = words.get(x);

for (Object y : L) System.out.print(y + " ");

System.out.println();

}

Ссылка на Ideone

Пример:

In: Dedlovskiy Dedlovskih Nasimov Nagimov Zazimov Azazimov Marchenko Merchenko Dedlovich Nagiev Houston Watson
Out:
N521: Nagiev
D341: Dedlovskiy Dedlovskih Dedlovich
A251: Azazimov
M562: Marchenko Merchenko
W325: Watson
Z251: Zazimov
H235: Houston
N525: Nasimov Nagimov

Контрольная работа. Timus 2002

18/12/2015 by Денис Карташов

2002. Тестовое задание

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…
Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!
Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!

И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]\left( 1 \leq n \leq 100 \right)[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до [latex]30[/latex] символов включительно. Строки могут состоять только из символов с кодами от [latex]33[/latex] до [latex]126[/latex].

Результат

Для каждой операции выведите в отдельной строке сообщение в соответствии с форматом, описанным выше. Строго соблюдайте расстановку пробелов и знаков препинания в этих сообщениях.

Ограничения

Время: 0.5 секунды
Память: 64 МБ

Код

import java.io.IOException;
import java.util.HashMap;
import java.io.OutputStreamWriter;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;

class Recode{
	String pass;
	boolean hear;
	public Recode(String pass, boolean hear){
		this.pass = pass;
		this.hear = hear;
	}
}

class Comments {
	public static String errNewAdd = "fail: user already exists\n";
	public static String errLogin = "fail: no such user\n";
	public static String errInPass = "fail: incorrect password\n";
	public static String errAlIn = "fail: already logged in\n";
	public static String errLogout = "fail: already logged out\n";
	public static String sucNewAdd = "success: new user added\n";
	public static String sucLogin = "success: user logged in\n";
	public static String sucLogout = "success: user logged out\n";
}

public class Main{
	private static HashMap DataBase = new HashMap();
	
	private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws java.lang.Exception{
		int n = nextInt();
		for (int i = 0; i < n; i++){
			try{
				Query(getRequest());
			}
			catch(Exception e){
				err(e);
			}
		}
		out.flush();
	}
	
	public static String[] getRequest() throws IOException{
		return in.readLine().split(" ");
	}
	
	public static void Query(String[] req){
		if(req[0].equals("register")){
			Registration(req[1], req[2]);
		}
		else if(req[0].equals("login")){
			Login(req[1],req[2]);
		}
		else if(req[0].equals("logout")){
			Logout(req[1]);
		}
	}
	
	public static void Registration(String user, String pass){
		if(!DataBase.containsKey(user)){
			DataBase.put(user, new Recode(pass, false));
			out.print(Comments.sucNewAdd);
		}
		else{
			out.print(Comments.errNewAdd);
		}
	}
	
	
	public static void Login(String user, String pass){
		if(DataBase.containsKey(user)){
			if(DataBase.get(user).pass.equals(pass)){
				if(!DataBase.get(user).hear){
					DataBase.put(user, new Recode(pass, true));
					out.print(Comments.sucLogin);
				} 
				else out.print(Comments.errAlIn);
			}
			else out.print(Comments.errInPass);
		}
		else out.print(Comments.errLogin);
	}
	
	public static void Logout(String user){
		if(DataBase.containsKey(user)){
			if(DataBase.get(user).hear){
				DataBase.put(user, new Recode(DataBase.get(user).pass, false));
				out.print(Comments.sucLogout);
			}
			else out.print(Comments.errLogout);
		}
		else out.print(Comments.errLogin);
	}
	
	public static int nextInt() throws IOException{
		return Integer.parseInt(in.readLine());
	}
	
	private static void err(Object a){
		out.println(a);
	}
}

100

101

102

103

104

105

106

import java.io.IOException;

import java.util.HashMap;

import java.io.OutputStreamWriter;

import java.io.InputStreamReader;

import java.io.BufferedReader;

import java.io.PrintWriter;

class Recode{

String pass;

boolean hear;

public Recode(String pass, boolean hear){

this.pass = pass;

this.hear = hear;

}

class Comments {

public static String errNewAdd = "fail: user already exists\n";

public static String errLogin = "fail: no such user\n";

public static String errInPass = "fail: incorrect password\n";

public static String errAlIn = "fail: already logged in\n";

public static String errLogout = "fail: already logged out\n";

public static String sucNewAdd = "success: new user added\n";

public static String sucLogin = "success: user logged in\n";

public static String sucLogout = "success: user logged out\n";

}

public class Main{

private static HashMap DataBase = new HashMap();

private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws java.lang.Exception{

int n = nextInt();

for (int i = 0; i < n; i++){

try{

Query(getRequest());

}

catch(Exception e){

err(e);

}

out.flush();

}

public static String[] getRequest() throws IOException{

return in.readLine().split(" ");

}

public static void Query(String[] req){

if(req[0].equals("register")){

Registration(req[1], req[2]);

}

else if(req[0].equals("login")){

}

else if(req[0].equals("logout")){

Logout(req[1]);

}

public static void Registration(String user, String pass){

if(!DataBase.containsKey(user)){

DataBase.put(user, new Recode(pass, false));

out.print(Comments.sucNewAdd);

}

else{

out.print(Comments.errNewAdd);

}

public static void Login(String user, String pass){

if(DataBase.containsKey(user)){

if(DataBase.get(user).pass.equals(pass)){

if(!DataBase.get(user).hear){

DataBase.put(user, new Recode(pass, true));

out.print(Comments.sucLogin);

}

else out.print(Comments.errAlIn);

}

else out.print(Comments.errInPass);

}

else out.print(Comments.errLogin);

}

public static void Logout(String user){

if(DataBase.containsKey(user)){

if(DataBase.get(user).hear){

DataBase.put(user, new Recode(DataBase.get(user).pass, false));

out.print(Comments.sucLogout);

}

else out.print(Comments.errLogout);

}

else out.print(Comments.errLogin);

}

public static int nextInt() throws IOException{

return Integer.parseInt(in.readLine());

}

private static void err(Object a){

out.println(a);

}

Решение

Сначала мной была создана структура в которой содержалась информация о пользователе (пароль и состояние: в сети/не в сети) и класс, в котором перечислил все комментарии, которые может выдавать программа. Далее я использовал HashMap для хранения пар вида [latex]\left\{ login => \left(password , status \right)\right\}[/latex], что позволило мне за константное время проверять указанные в задаче условия. Существование пользователя (был ли он зарегистрирован ранее) я определяю с помощью метода HashMap.containsKey(T key), что позволяет мне не заводить дополнительные структуры данных.

Описание функций

main

Главная функция программы. Считывает число запросов [latex]n[/latex], и [latex]n[/latex] раз считывает массив строк с помощью getRequest и и сразу же передает его в функцию Query, после чего программа завершает свою работу.

getRequest

Считывает строку и разбивает ее с помощью метода split по пробелу. Возвращает полученный массив.

Query

Функция — распределитель. Принимает массив строк и проверяет его первый элемент.
Если он оказался равен «register» — вызывает функцию Registration. Параметрами служат второй и третий элемент входного массива.
Если он оказался равен «login» — вызывает функцию Login. Параметрами служат второй и третий элемент входного массива.
Если он оказался равен «logout» — вызывает функцию Logout. Параметром служит второй элемент входного массива.

Request

Принимает две строки, которые определяет как логин и пароль пользователя. Проверяет несуществование пользователя. Если пользователь с таким логином не существует — добавляет запись в DataBase и печатает строку «success: new user added». Иначе — печатает соответствующую ошибку.

Login

Принимает две строки, которые определяет как логин и пароль пользователя. Проверяет существование пользователя, сверяет пароль и проверяет состояние. Если пользователь существует, пароль совпадает и статус — «не в сети» — меняем статус и печатает об успехе. Если некоторое условие не было пройдено — печатает соответствующую ошибку.

Logout

Принимает одну строку, которую определяет как логин. Проверяет существование пользователя и его статус. Если пользователь существует и статус — «в сети» — меняет статус и печатает об успехе. Иначе печатает соответствующую ошибку.

Результат проверки на acm.timus.ru

Вердикт	Время работы	Использованная Память
Accepted	0.078	548 КБ

Timus 2002

16/12/2015 by Мария Илларионова

Ссылка на засчитанное решение.

Идея решения состоит в том, чтобы использовать 2 ассоциативных массива, один из которых хранит в качестве ключа и значения логин и пароль пользователь, а второй — логин и состояние (онлайн/оффлайн).

На С++ можно обойтись и одним ассоциативным массивом, если воспользоваться такой структурой: map<string, pair<string, bool> > m.

Код программы (http://ideone.com/3Uqhuh):

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

class Ideone {
	public static void main (String[] args) {
		Map<String, String> m = new HashMap<String, String>();
		Map<String, Boolean> u = new HashMap<String, Boolean>();
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s;
		for(int i = 0; i < n; i++) {
			s = in.next();
			if (s.equals("register")) {
				String a, b;
				a = in.next();
				b = in.next();
				if (m.containsKey(a)) {
					System.out.println("fail: user already exists");
				}
				else {
					m.put(a, b);
					u.put(a, false);
					System.out.println("success: new user added");
				}
			}
			else if (s.equals("login")) {
				String a, b;
				a = in.next();
				b = in.next();
				if (!m.containsKey(a)) {
					System.out.println("fail: no such user");
				}
				else if (!b.equals(m.get(a))) {
					System.out.println("fail: incorrect password");
				}
				else {
					if (u.get(a) == false) {
						u.put(a, true);
						System.out.println("success: user logged in");
					}
					else {
						System.out.println("fail: already logged in");
					}
				}
			}
			else {
				String a;
				a = in.next();
				if (!m.containsKey(a)) {
					System.out.println("fail: no such user");
				}
				else {
					if (u.get(a) == true) {
						u.put(a, false);
						System.out.println("success: user logged out");
					}
					else {
						System.out.println("fail: already logged out");
					}
				}
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Map<String, String> m = new HashMap<String, String>();

Map<String, Boolean> u = new HashMap<String, Boolean>();

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String s;

for(int i = 0; i < n; i++) {

s = in.next();

if (s.equals("register")) {

String a, b;

a = in.next();

b = in.next();

if (m.containsKey(a)) {

System.out.println("fail: user already exists");

}

else {

m.put(a, b);

u.put(a, false);

System.out.println("success: new user added");

}

else if (s.equals("login")) {

String a, b;

a = in.next();

b = in.next();

if (!m.containsKey(a)) {

System.out.println("fail: no such user");

}

else if (!b.equals(m.get(a))) {

System.out.println("fail: incorrect password");

}

else {

if (u.get(a) == false) {

u.put(a, true);

System.out.println("success: user logged in");

}

else {

System.out.println("fail: already logged in");

}

else {

String a;

a = in.next();

if (!m.containsKey(a)) {

System.out.println("fail: no such user");

}

else {

if (u.get(a) == true) {

u.put(a, false);

System.out.println("success: user logged out");

}

else {

System.out.println("fail: already logged out");

}

BinarySearchTree

16/12/2015 by Мария Илларионова

Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами.

Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше.

Описание методов, реализованных в классе BinarySearchTree:

метод add():
- если дерево пустое, то говорим, что корень — это наш узел;
- сравниваем поступивший ключ с ключом узла:
  - если ключ меньше, то идём в левое поддерево;
  - если ключ равен, то задаём узлу новое поступившее значение;
  - если ключ больше, то идём в правое поддерево;
методы minKey() и maxKey():
- по свойству дерева, минимальный ключ располагается в самом левом поддереве, а максимальный — в самом правом;
метод delete():
- сначала находим нужный элемент по ключу (если такового нет, то выходим из метода);
- если у удаляемого узла нет правого поддерева, то мы просто замещаем узел его левым поддеревом;
- иначе находим в правом поддереве узел с минимальным ключом:
  - если у этого узла родитель — это удаляемый узел, то мы просто говорим, что правое поддерево удаляемого узла есть правое поддерево найденного, а ключ и значение удаляемого узла — это ключ и значение найденного;
  - если у этого узла другой родитель, то мы замещаем найденный узел его же правым поддеревом, а ключ и значение удаляемого узла — это ключ и значение найденного;

Код программы (http://ideone.com/Z2hbBv):

import java.util.*;
import java.lang.*;
import java.io.*;
 
class BinarySearchTree <Key extends Comparable<Key>, Value> {
	private class Node {
		Key key;
		Value value;
		Node left, right;
		public Node (Key key, Value value) {
			this.key = key;
			this.value = value;
			this.left = this.right = null;
		}
	}
	private Node root;
	
	private Node add(Node node, Key key, Value value) {
		if (node == null) node = new Node(key, value);
		else {
			int compareResult = key.compareTo(node.key);
	        if(compareResult < 0) node.left = add(node.left, key, value);
    	    else if (compareResult == 0) node.value = value; 
        	else node.right = add(node.right, key, value);
		}
        return node;
	}
	public void add(Key key, Value value) {
		root = add(root, key, value);
	}
        
	public Key MinKey(){
        Node cur = root;
        while (cur.left != null) cur = cur.left;
        return cur.key;
    }
    
	public Key MaxKey(){
        Node cur = root;
        while (cur.right != null) cur = cur.right;
        return cur.key;
    }

	public void delete(Key key) {
        Node cur = root;
        Node prev = null;
        while (true) {
            if (cur == null) return;
            int compareResult = key.compareTo(cur.key);
            if (compareResult < 0) {
                prev = cur; 
                cur = cur.left;
            }
            else if (compareResult == 0) break;
            else {
            	prev = cur;
                cur = cur.right;
            }
        }
        if (cur.right == null) {
        	if (cur == prev.left) prev.left = cur.left;
        	else prev.right = cur.left;
        }
        else {
        	Node minFromRight = cur.right;
        	prev = null;
        	while (minFromRight.left != null) {
        		prev = minFromRight;
        		minFromRight = minFromRight.left;
        	}
        	if (prev == null) cur.right = minFromRight.right;
        	else prev.left = minFromRight.right;
        	cur.key = minFromRight.key;
        	cur.value = minFromRight.value;
        }
	}
	
	public Value get(Key key) {
        Node cur = root;
        while (true) {
            if (cur == null) break;
            int compareResult = key.compareTo(cur.key);
            if (compareResult < 0) cur = cur.left;
            else if (compareResult == 0) break;
            else cur = cur.right;
        }
        return cur == null ? (Value)null : cur.value;
	}
	
	private void print(Node node, int level) {
		if (node != null) {
			print(node.right, level + 1);
			for (int i = 0; i < level; i++) {
				System.out.print("\t");
			}
			System.out.println(node.key);
			//System.out.println(node.key + " -> " + node.value); 
			print(node.left, level + 1);
		}
	}
	public void print() {
		print(root, 0);
	}
}
 
class Ideone {
	public static void main (String[] args) {
		BinarySearchTree<Integer, Integer> a = new BinarySearchTree<Integer, Integer>();
		int n = 10;
		for(int i = 0; i < n; i++) {
			a.add((int)(Math.random()*10), (int)(Math.random()*1000));
		}
		System.out.println(a.MaxKey() + " -> " + a.get(a.MaxKey()));
		System.out.println(a.MinKey() + " -> " + a.get(a.MinKey()));
		a.print();
		System.out.println("\n\n");
		Integer x = (int)(Math.random()*10);
		System.out.println(x);
		System.out.println("\n\n");
		a.delete(x);
		a.print();
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

import java.util.*;

import java.lang.*;

import java.io.*;

class BinarySearchTree <Key extends Comparable<Key>, Value> {

private class Node {

Key key;

Value value;

Node left, right;

public Node (Key key, Value value) {

this.key = key;

this.value = value;

this.left = this.right = null;

}

private Node root;

private Node add(Node node, Key key, Value value) {

if (node == null) node = new Node(key, value);

else {

int compareResult = key.compareTo(node.key);

if(compareResult < 0) node.left = add(node.left, key, value);

else if (compareResult == 0) node.value = value;

else node.right = add(node.right, key, value);

}

return node;

}

public void add(Key key, Value value) {

root = add(root, key, value);

}

public Key MinKey(){

Node cur = root;

while (cur.left != null) cur = cur.left;

return cur.key;

}

public Key MaxKey(){

Node cur = root;

while (cur.right != null) cur = cur.right;

return cur.key;

}

public void delete(Key key) {

Node cur = root;

Node prev = null;

while (true) {

if (cur == null) return;

int compareResult = key.compareTo(cur.key);

if (compareResult < 0) {

prev = cur;

cur = cur.left;

}

else if (compareResult == 0) break;

else {

prev = cur;

cur = cur.right;

}

if (cur.right == null) {

if (cur == prev.left) prev.left = cur.left;

else prev.right = cur.left;

}

else {

Node minFromRight = cur.right;

prev = null;

while (minFromRight.left != null) {

prev = minFromRight;

minFromRight = minFromRight.left;

}

if (prev == null) cur.right = minFromRight.right;

else prev.left = minFromRight.right;

cur.key = minFromRight.key;

cur.value = minFromRight.value;

}

public Value get(Key key) {

Node cur = root;

while (true) {

if (cur == null) break;

int compareResult = key.compareTo(cur.key);

if (compareResult < 0) cur = cur.left;

else if (compareResult == 0) break;

else cur = cur.right;

}

return cur == null ? (Value)null : cur.value;

}

private void print(Node node, int level) {

if (node != null) {

print(node.right, level + 1);

for (int i = 0; i < level; i++) {

System.out.print("\t");

}

System.out.println(node.key);

//System.out.println(node.key + " -> " + node.value);

print(node.left, level + 1);

}

public void print() {

print(root, 0);

}

class Ideone {

public static void main (String[] args) {

BinarySearchTree<Integer, Integer> a = new BinarySearchTree<Integer, Integer>();

int n = 10;

for(int i = 0; i < n; i++) {

a.add((int)(Math.random()*10), (int)(Math.random()*1000));

}

System.out.println(a.MaxKey() + " -> " + a.get(a.MaxKey()));

System.out.println(a.MinKey() + " -> " + a.get(a.MinKey()));

a.print();

System.out.println("\n\n");

Integer x = (int)(Math.random()*10);

System.out.println(x);

System.out.println("\n\n");

a.delete(x);

a.print();

}

Обратная польская нотация

09/12/2015 by Мария Илларионова

Передо мной стояли задачи:

перевести выражение в обратную польскую нотацию;
посчитать значение выражения.

Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10().

Выражение	Обратная польская нотация	Результат
15 * -(3 — 4)	15 3 4 — u- *	15
sqrt(4) + (8 * 0.5)	4 sqrt 8 0.5 * +	6
-cube(-3)	3 u- cube u-	27
92 / 10	92 10 /	9.2
pow10(2) — 95 + 4 * 8	2 pow10 95 — 4 8 * +	37

Алгоритм перевода в обратную польскую запись:

считываем поочерёдно все лексемы, попутно убирая пробелы;
если лексема — это число или переменная, то добавляем её в результирующий список;
если лексема — это функция, то добавляем её в стэк;
если лексема — это открывающая скобка, то добавляем её в стэк;
если лексема — это закрывающая скобка, то:
- помещаем элементы из стэка в результирующую строку пока не встретим открывающую скобку, притом открывающая скобка удаляется из стэка, но в результирующую строку не добавляется;
- если на вершине стэка оказывается символ функции, то мы помещаем его из стэка в результирующую строку;
- если открывающая скока не была встречена, то скобки не согласованы.
если лексема — это оператор, то:
- если это последний символ выражения, то выражение некорректно;
- если это унарный минус, то добавляем его в стэк;
- иначе:
  - выталкиваем верхние элементы стэка в результирующую строку, пока приоритет текущего оператора меньше либо равен приоритету оператора, находящегося на верине стэка;
  - помещаем текущий оператор в стэк;
когда все данные считаны, выталкиваем все элементы стэка в результирующую строку; если в стэке оказались символы не операторов, то скобки не согласованы.

Алгоритм вычисления значения выражения в обратной польской нотации:

если в записи встретили число, то кладём его в стэк;
если в записи встретили функцию или унарный минус, то :
- вытаскиваем из стэка верхний элемент;
- применяем функцию к нему;
- кладём элемент обратно в стэк;
если в записи встретили бинарный оператор, то:
- вытаскиваем из стэка два верхних элемента;
- выполняем над ними операцию;
- кладём в стэк результат выполнения операции;
выводим последний элемент стэка.

Код программы

ideone.com

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

class ExpressionParser {
	private static String operators = "+-*/";
	private static String delimiters = "() " + operators;
	public static boolean flag = true;
	private static boolean isDelimiter(String token) {
		if (token.length() != 1) return false;
		for (int i = 0; i < delimiters.length(); i++) {
			if (token.charAt(0) == delimiters.charAt(i)) return true;
		}
		return false;
	}
	
	private static boolean isOperator(String token) {
		if (token.equals("u-")) return true;
		for (int i = 0; i < operators.length(); i++) {
			if (token.charAt(0) == operators.charAt(i)) return true;
		}
		return false;
	}
	
	private static boolean isFunction(String token) {
		if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true;
		return false;
	}
	
	private static int priority(String token) {
		if (token.equals("(")) return 1;
		if (token.equals("+") || token.equals("-")) return 2;
		if (token.equals("*") || token.equals("/")) return 3;
		return 4;
	}
	
	public static List<String> parse(String infix) {
		List<String> postfix = new ArrayList<String>();
		Deque<String> stack = new ArrayDeque<String>();
		StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);
		String prev = "";
		String curr = "";
		while (tokenizer.hasMoreTokens()) {
			curr = tokenizer.nextToken();
			if (!tokenizer.hasMoreTokens() && isOperator(curr)) {
				System.out.println("Некорректное выражение.");
				flag = false;
				return postfix;
			}
			if (curr.equals(" ")) continue;
			if (isFunction(curr)) stack.push(curr);
			else if (isDelimiter(curr)) {
				if (curr.equals("(")) stack.push(curr);
				else if (curr.equals(")")) {
					while (!stack.peek().equals("(")) {
						postfix.add(stack.pop());
						if (stack.isEmpty()) {
							System.out.println("Скобки не согласованы.");
							flag = false;
							return postfix;
						}
					}
					stack.pop();
					if (!stack.isEmpty() && isFunction(stack.peek())) {
						postfix.add(stack.pop());
					}
				}
				else {
					if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev)  && !prev.equals(")")))) {
						// унарный минус
						curr = "u-";
					}
					else {
						while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek()))) {
							postfix.add(stack.pop());
						}
						
					}
					stack.push(curr);
				}
				
			}
			
			else {
				postfix.add(curr);
			}
			prev = curr;
		}
		
		while (!stack.isEmpty()) {
			if (isOperator(stack.peek())) postfix.add(stack.pop());
			else {
				System.out.println("Скобки не согласованы.");
				flag = false;
				return postfix;
			}
		}
		return postfix;
	}
}

class Ideone {
	public static Double calc(List<String> postfix) {
		Deque<Double> stack = new ArrayDeque<Double>();
		for (String x : postfix) {
			if (x.equals("sqrt")) stack.push(Math.sqrt(stack.pop()));
			else if (x.equals("cube")) {
				Double tmp = stack.pop();
				stack.push(tmp * tmp * tmp);
			}
			else if (x.equals("pow10")) stack.push(Math.pow(10, stack.pop()));
			else if (x.equals("+")) stack.push(stack.pop() + stack.pop());
			else if (x.equals("-")) {
				Double b = stack.pop(), a = stack.pop();
				stack.push(a - b);
			}
			else if (x.equals("*")) stack.push(stack.pop() * stack.pop());
			else if (x.equals("/")) {
				Double b = stack.pop(), a = stack.pop();
				stack.push(a / b);
			}
			else if (x.equals("u-")) stack.push(-stack.pop());
			else stack.push(Double.valueOf(x));
		}
		return stack.pop();
	}
	
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		ExpressionParser n = new ExpressionParser();
		List<String> expression = n.parse(s);
		boolean flag = n.flag;
		if (flag) {
			for (String x : expression) System.out.print(x + " ");
			System.out.println();
			System.out.println(calc(expression));
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

import java.util.*;

import java.lang.*;

import java.io.*;

class ExpressionParser {

private static String operators = "+-*/";

private static String delimiters = "() " + operators;

public static boolean flag = true;

private static boolean isDelimiter(String token) {

if (token.length() != 1) return false;

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

if (token.charAt(0) == delimiters.charAt(i)) return true;

}

return false;

}

private static boolean isOperator(String token) {

if (token.equals("u-")) return true;

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

if (token.charAt(0) == operators.charAt(i)) return true;

}

return false;

}

private static boolean isFunction(String token) {

if (token.equals("sqrt") || token.equals("cube") || token.equals("pow10")) return true;

return false;

}

private static int priority(String token) {

if (token.equals("(")) return 1;

if (token.equals("+") || token.equals("-")) return 2;

if (token.equals("*") || token.equals("/")) return 3;

return 4;

}

public static List<String> parse(String infix) {

List<String> postfix = new ArrayList<String>();

Deque<String> stack = new ArrayDeque<String>();

StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);

String prev = "";

String curr = "";

while (tokenizer.hasMoreTokens()) {

curr = tokenizer.nextToken();

if (!tokenizer.hasMoreTokens() && isOperator(curr)) {

System.out.println("Некорректное выражение.");

flag = false;

return postfix;

}

if (curr.equals(" ")) continue;

if (isFunction(curr)) stack.push(curr);

else if (isDelimiter(curr)) {

if (curr.equals("(")) stack.push(curr);

else if (curr.equals(")")) {

while (!stack.peek().equals("(")) {

postfix.add(stack.pop());

if (stack.isEmpty()) {

System.out.println("Скобки не согласованы.");

flag = false;

return postfix;

}

stack.pop();

if (!stack.isEmpty() && isFunction(stack.peek())) {

postfix.add(stack.pop());

}

else {

if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev) && !prev.equals(")")))) {

// унарный минус

curr = "u-";

}

else {

while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek()))) {

postfix.add(stack.pop());

}

stack.push(curr);

}

else {

postfix.add(curr);

}

prev = curr;

}

while (!stack.isEmpty()) {

if (isOperator(stack.peek())) postfix.add(stack.pop());

else {

System.out.println("Скобки не согласованы.");

flag = false;

return postfix;

}

return postfix;

}

class Ideone {

public static Double calc(List<String> postfix) {

Deque<Double> stack = new ArrayDeque<Double>();

for (String x : postfix) {

if (x.equals("sqrt")) stack.push(Math.sqrt(stack.pop()));

else if (x.equals("cube")) {

Double tmp = stack.pop();

stack.push(tmp * tmp * tmp);

}

else if (x.equals("pow10")) stack.push(Math.pow(10, stack.pop()));

else if (x.equals("+")) stack.push(stack.pop() + stack.pop());

else if (x.equals("-")) {

Double b = stack.pop(), a = stack.pop();

stack.push(a - b);

}

else if (x.equals("*")) stack.push(stack.pop() * stack.pop());

else if (x.equals("/")) {

Double b = stack.pop(), a = stack.pop();

stack.push(a / b);

}

else if (x.equals("u-")) stack.push(-stack.pop());

else stack.push(Double.valueOf(x));

}

return stack.pop();

}

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

String s = in.nextLine();

ExpressionParser n = new ExpressionParser();

List<String> expression = n.parse(s);

boolean flag = n.flag;

if (flag) {

for (String x : expression) System.out.print(x + " ");

System.out.println();

System.out.println(calc(expression));

}

Segmented Array

05/12/2015 by Максим Швандт

Задача

Необходимо реализовать некоторую коллекцию индексированных данных некоторого типа T, выглядящую как несколько необычный массив. Вместо операции присваивания значения элементу массива в нём имеется операция присваивания одинаковых значений всем элементам для некоторого диапазона индексов. Также и операции поиска минимума и максимума должны работать для некоторого диапазона значений индексов.

При написании класса, реализующего данный интерфейс необходимо стремиться к максимальной эффективности выполнения наиболее частых операций и учитывать особенности использования отражённые в следующей таблице с заданиями:

Big array	Small \|T\|	Often				Student
Big array	Small \|T\|	get()	set()	indexOf()	min()/max()	Student
1	0	0	0	1	0	Швандт

Тест

input	output
set 2 2 H	ok
set 3 3 E	ok
set 4 5 L	ok
set 6 6 O	ok
set8 8 W	ok
set 9 9 O	ok
set 10 10 R	ok
set 11 11 L	ok
set 12 12 D	ok
set 13 13 !	ok
set 14 14 !	ok
set 15 15 !	ok
show	segment#0 { null null H E } segment#1 { L L O null } segment#2 { W O R L } segment#3 { D ! ! ! }
exit	N/A

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

Интерфейс SegmentedArray, который описывает заданную функциональность доступа к сегментированному массиву
Класс SegmentedArrayImpl, имплементирует данный интерфейс
Класс SegmentedArrayApp, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.

Интерфейс SegmentedArray

package odessa.uni.imem.maxim;

public interface SegmentedArray<Comparable>
{
   int indexOf(Comparable value, int fromIndex);
   void set(int fromIndex, int toIndex, Comparable value);
   Comparable min(int fromIndex, int toIndex);
}

package odessa.uni.imem.maxim;

public interface SegmentedArray<Comparable>

{

int indexOf(Comparable value, int fromIndex);

void set(int fromIndex, int toIndex, Comparable value);

Comparable min(int fromIndex, int toIndex);

}

Методы интерфейса:

indexOf — возвращает абсолютный индекс элемента в массиве начиная с заданного индекса.
set — присваивает последовательности элементов массива одно и тоже значение в заданном диапазоне
min — возвращает минимальный элемент в заданном диапазоне

Класс SegmentedArrayImpl

package odessa.uni.imem.maxim;

public class SegmentedArrayImpl<Item extends Comparable<Item>> implements SegmentedArray<Item>
{
   private int size;
   private int segmentSize;
   private Object[][] segments;

   public SegmentedArrayImpl(int aSegmentSize, int aSegmentCount)
   {
      segmentSize = aSegmentSize;
      size = segmentSize * aSegmentCount;

      segments = new Object[aSegmentCount][segmentSize];
   }

   public int indexOf(Item value, int fromIndex)
   {
      if (fromIndex >= size)
      {
         return -1;
      }

      int segmentIndex = findSegmentIndex(fromIndex);
      int indexInSegment = fromIndex - segmentIndex * segmentSize;

      while (segmentIndex < segments.length)
      {
         // @SuppressWarnings("unchecked")
         if (((Item) (segments[segmentIndex][indexInSegment])).compareTo(value) == 0)
         {
            return segmentIndex * indexInSegment;
         }

         indexInSegment++;

         if (indexInSegment == segmentSize)
         {
            indexInSegment = 0;
            segmentIndex++;
         }
      }

      return -1;
   }

   public void set(int fromIndex, int toIndex, Item value)
   {
      if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)
      {
         return;
      }

      int index = fromIndex;
      int segmentIndex = findSegmentIndex(fromIndex);
      int indexInSegment = fromIndex - segmentIndex * segmentSize;

      while (segmentIndex < segments.length && index <= toIndex)
      {
         // @SuppressWarnings("unchecked")
         segments[segmentIndex][indexInSegment] = value;
         index++;
         indexInSegment++;

         if (indexInSegment == segmentSize)
         {
            indexInSegment = 0;
            segmentIndex++;
         }
      }
   }

   public Item min(int fromIndex, int toIndex)
   {
      if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)
      {
         return null;
      }

      int index = fromIndex;
      int segmentIndex = findSegmentIndex(fromIndex);
      int indexInSegment = fromIndex - segmentIndex * segmentSize;
      Item minimum = null;

      while (segmentIndex < segments.length && index < toIndex)
      {
         // @SuppressWarnings("unchecked")
         Item val = (Item) segments[segmentIndex][indexInSegment];
         if (minimum == null || val.compareTo(minimum) < 0)
         {
            minimum = val;
         }

         index++;
         indexInSegment++;

         if (indexInSegment == segmentSize)
         {
            indexInSegment = 0;
            segmentIndex++;
         }
      }

      return null;
   }

   // check if the absolute index falls into given segment index
   private int compareIndexToSegment(int index, int segmentIndex)
   {
      int lowerIndex = segmentIndex * segmentSize;
      int higherIndex = (segmentIndex + 1) * segmentSize - 1;

      if (index < lowerIndex) // index falls before segment
      {
         return -1;
      }
      else if (index > higherIndex) // index falls after segment
      {
         return 1;
      }

      return 0;
   }

   // find segment that contains given absolute index using binary search
   // in array
   private int findSegmentIndex(int index)
   {
      int lo = 0; // lower segment index
      int hi = segments.length - 1; // higher segment index

      while (lo <= hi)
      {
         int mid = lo + (hi - lo) / 2; // middle segment index
         int cmp = compareIndexToSegment(index, mid);

         if (cmp < 0)
         {
            hi = mid - 1;
         }
         else if (cmp > 0)
         {
            lo = mid + 1;
         }
         else if (cmp == 0)
         {
            return mid;
         }
      }

      return lo;
   }

   public void show()
   {
      for (int i = 0; i < segments.length; i++)
      {
         System.out.printf("segment#%d { ", i);

         for (int j = 0; j < segmentSize; j++)
         {
            System.out.print((Item) segments[i][j]);
            System.out.print(" ");
         }

         System.out.printf("}\n");
      }
   }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

package odessa.uni.imem.maxim;

public class SegmentedArrayImpl<Item extends Comparable<Item>> implements SegmentedArray<Item>

{

private int size;

private int segmentSize;

private Object[][] segments;

public SegmentedArrayImpl(int aSegmentSize, int aSegmentCount)

{

segmentSize = aSegmentSize;

size = segmentSize * aSegmentCount;

segments = new Object[aSegmentCount][segmentSize];

}

public int indexOf(Item value, int fromIndex)

{

if (fromIndex >= size)

{

return -1;

}

int segmentIndex = findSegmentIndex(fromIndex);

int indexInSegment = fromIndex - segmentIndex * segmentSize;

while (segmentIndex < segments.length)

{

// @SuppressWarnings("unchecked")

if (((Item) (segments[segmentIndex][indexInSegment])).compareTo(value) == 0)

{

return segmentIndex * indexInSegment;

}

indexInSegment++;

if (indexInSegment == segmentSize)

{

indexInSegment = 0;

segmentIndex++;

}

return -1;

}

public void set(int fromIndex, int toIndex, Item value)

{

if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)

{

return;

}

int index = fromIndex;

int segmentIndex = findSegmentIndex(fromIndex);

int indexInSegment = fromIndex - segmentIndex * segmentSize;

while (segmentIndex < segments.length && index <= toIndex)

{

// @SuppressWarnings("unchecked")

segments[segmentIndex][indexInSegment] = value;

index++;

indexInSegment++;

if (indexInSegment == segmentSize)

{

indexInSegment = 0;

segmentIndex++;

}

public Item min(int fromIndex, int toIndex)

{

if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)

{

return null;

}

int index = fromIndex;

int segmentIndex = findSegmentIndex(fromIndex);

int indexInSegment = fromIndex - segmentIndex * segmentSize;

Item minimum = null;

while (segmentIndex < segments.length && index < toIndex)

{

// @SuppressWarnings("unchecked")

Item val = (Item) segments[segmentIndex][indexInSegment];

if (minimum == null || val.compareTo(minimum) < 0)

{

minimum = val;

}

index++;

indexInSegment++;

if (indexInSegment == segmentSize)

{

indexInSegment = 0;

segmentIndex++;

}

return null;

}

// check if the absolute index falls into given segment index

private int compareIndexToSegment(int index, int segmentIndex)

{

int lowerIndex = segmentIndex * segmentSize;

int higherIndex = (segmentIndex + 1) * segmentSize - 1;

if (index < lowerIndex) // index falls before segment

{

return -1;

}

else if (index > higherIndex) // index falls after segment

{

return 1;

}

return 0;

}

// find segment that contains given absolute index using binary search

// in array

private int findSegmentIndex(int index)

{

int lo = 0; // lower segment index

int hi = segments.length - 1; // higher segment index

while (lo <= hi)

{

int mid = lo + (hi - lo) / 2; // middle segment index

int cmp = compareIndexToSegment(index, mid);

if (cmp < 0)

{

hi = mid - 1;

}

else if (cmp > 0)

{

lo = mid + 1;

}

else if (cmp == 0)

{

return mid;

}

return lo;

}

public void show()

{

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

{

System.out.printf("segment#%d { ", i);

for (int j = 0; j < segmentSize; j++)

{

System.out.print((Item) segments[i][j]);

System.out.print(" ");

}

System.out.printf("}\n");

}

Данный класс реализует интерфейс SegmentedArray с учетом требования задачи, а именно:

Допускаются массивы очень большого размера
Методы indexOf и max должны работать максимально быстро

Используемый алгоритм

С учетом условий задачи был выбран алгориnм, описанный в статье Segmented Tree.

Согласно условию задачи, массив может быть очень большим, а это означает очень широкий диапазон индексов элементов. Следовательно, стоит задача максимально быстро находить начальный и конечный сегменты, которые покрывают индексы диапазона, заданные в качестве параметров методов интерфейса.

Выбранный алгоритм позволяет быстрыое нахождение нужных сегментов благодаря бинарному дереву, которым описывается набор диапазонов.

Алгоритм поиска нужного сегмента реализован с помощью методов findSegmentIndex и compareIndexToSegment.

Первый метод — это обычный двоичный поиск в массиве отсортированных элементов, которыми являются номера сегментов в порядке их следования. Данный метод заимствован из Coursera. Внутри он использует второй метод compareIndexToSegment для проверки попадания заданного абсолютного индекса в сегмент с заданным номером, т. е. он реализует нобходимый для бинарного поиска метод сравнения, где фактически абсолютный индекс сравнивается с сегментом с целью его выбора.

Методы родительского интерфейса

indexOf — находит нужный сегмент посредством findSegmentIndex и далее — индекс в сегменте, затем производит поиск в этом и последующих сегментах нужного значения
set — находит первый и последний сегменты посредством findSegmentIndex, которые покрывают входные индексы диапазона, затем выполняет запись начиная с начального сегмента и индекса в нем, и заканчивая последним сегментом и индексом в нем.
min — находит диапазон сегментов для поиска таким же образом, как и метод set и находит минимальное значения в данном диапазоне сегментов

Собственные методы

конструктор — принимает 2 аргумента — размер и количество сегментов
compareIndexToSegment — проверяет, попадает ли абсолютный индекс в данный сегмент и возвращает одно из значений: -1 — если индекс перед сегментом, 0 — если попадает в сегмент, 1 — если после сегмента
findSegmentIndex — находит сегмент, который содержит данный абсолютный индекс используя бинарный поиск в массиве
show — диагностическая печать содержимого

Класс SegmentedArrayApp

package odessa.uni.imem.maxim;

import java.util.*;

public class SegmentedArrayApp
{
   public static Vector<String> parseTextToTokens(String text)
   {
      Vector<String> tokens = new Vector<String>();
      StringTokenizer st = new StringTokenizer(text);

      while (st.hasMoreTokens())
      {
         tokens.add(st.nextToken());
      }

      return tokens;
   }

   public static Integer strToInt(String s)
   {
      Integer x = null;
      try
      {
         x = Integer.parseUnsignedInt(s);
      }
      catch (NumberFormatException e)
      {
      }

      return x;
   }

   public static void main(String[] args)
   {
      SegmentedArrayImpl<String> storage = new SegmentedArrayImpl<String>(4, 4);

      Scanner in = new Scanner(System.in);

      for (;;)
      {
         String inputLine = in.nextLine();
         if (inputLine.isEmpty())
         {
            continue;
         }

         String cmd = null;
         String arg1 = null;
         String arg2 = null;
         String arg3 = null;

         {
            Vector<String> inputTokens = parseTextToTokens(inputLine);
            if (inputTokens.size() > 0)
            {
               cmd = inputTokens.get(0);
            }
            if (inputTokens.size() > 1)
            {
               arg1 = inputTokens.get(1);
            }
            if (inputTokens.size() > 2)
            {
               arg2 = inputTokens.get(2);
            }
            if (inputTokens.size() > 3)
            {
               arg3 = inputTokens.get(3);
            }
         }

         if (cmd.equals("exit"))
         {
            break;
         }
         else if (cmd.equals("show"))
         {
            storage.show();
         }
         else if (cmd.equals("index"))
         {
            String value = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;
            Integer fromIndex = (arg2 != null) ? strToInt(arg2) : null;

            if (value == null || fromIndex == null)
            {
               System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%d>\n", cmd, arg1, arg2);
               continue;
            }

            System.out.println(storage.indexOf(value, fromIndex));
         }
         else if (cmd.equals("set"))
         {
            Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;
            Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;
            String value = (arg3 != null && !arg3.isEmpty()) ? arg3 : null;

            if (fromIndex == null || toIndex == null || value == null)
            {
               System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d> <%s>\n", cmd, arg1, arg2, arg3);
               continue;
            }

            storage.set(fromIndex, toIndex, value);
            System.out.println("Ok");
         }
         else if (cmd.equals("min"))
         {
            Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;
            Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;

            if (fromIndex == null || toIndex == null)
            {
               System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d>\n", cmd, arg1, arg2);
               continue;
            }

            System.out.println(storage.min(fromIndex, toIndex));
         }

      }

      in.close();

   }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

package odessa.uni.imem.maxim;

import java.util.*;

public class SegmentedArrayApp

{

public static Vector<String> parseTextToTokens(String text)

{

Vector<String> tokens = new Vector<String>();

StringTokenizer st = new StringTokenizer(text);

while (st.hasMoreTokens())

{

tokens.add(st.nextToken());

}

return tokens;

}

public static Integer strToInt(String s)

{

Integer x = null;

try

{

x = Integer.parseUnsignedInt(s);

}

catch (NumberFormatException e)

{

}

return x;

}

public static void main(String[] args)

{

SegmentedArrayImpl<String> storage = new SegmentedArrayImpl<String>(4, 4);

Scanner in = new Scanner(System.in);

for (;;)

{

String inputLine = in.nextLine();

if (inputLine.isEmpty())

{

continue;

}

String cmd = null;

String arg1 = null;

String arg2 = null;

String arg3 = null;

{

Vector<String> inputTokens = parseTextToTokens(inputLine);

if (inputTokens.size() > 0)

{

cmd = inputTokens.get(0);

}

if (inputTokens.size() > 1)

{

arg1 = inputTokens.get(1);

}

if (inputTokens.size() > 2)

{

arg2 = inputTokens.get(2);

}

if (inputTokens.size() > 3)

{

arg3 = inputTokens.get(3);

}

if (cmd.equals("exit"))

{

break;

}

else if (cmd.equals("show"))

{

storage.show();

}

else if (cmd.equals("index"))

{

String value = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;

Integer fromIndex = (arg2 != null) ? strToInt(arg2) : null;

if (value == null || fromIndex == null)

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%d>\n", cmd, arg1, arg2);

continue;

}

System.out.println(storage.indexOf(value, fromIndex));

}

else if (cmd.equals("set"))

{

Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;

Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;

String value = (arg3 != null && !arg3.isEmpty()) ? arg3 : null;

if (fromIndex == null || toIndex == null || value == null)

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d> <%s>\n", cmd, arg1, arg2, arg3);

continue;

}

storage.set(fromIndex, toIndex, value);

System.out.println("Ok");

}

else if (cmd.equals("min"))

{

Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;

Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;

if (fromIndex == null || toIndex == null)

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d>\n", cmd, arg1, arg2);

continue;

}

System.out.println(storage.min(fromIndex, toIndex));

}

in.close();

}

Данный класс реализует тестовое приложение для интерфейса. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста.

Методы класса

parseTextToTokens — разбирает входной текст на слова используя известный класс StringTokenizer и возвращает вектор слов
strToInt — превращает строку в число с подавлением исключения NumberFormatException
main — реализует простейший интерпритатор команд, в котором каждая команда представляет соостветствующий интерфейсный метод, состоит из цикла, где в каждом цикле посредством объекта Scanner читается полностью входная строка, которая затем разбирается на команду и ее аргументы посредством parseTextToTokens, это в дальнейшем превращается в соответствующие вызовы интерфейсных методов.

Ссылка на Ideone: https://ideone.com/BknxiN

Двоичное дерево поиска

01/12/2015 by Денис Карташов

Задача

Реализовать структуру «Двоичное дерево поиска» в соответствии с этим шаблоном.

Решение

По моему субъективному мнению, тут следует привести более ли менее детальное описание только операций вставки и удаления вершины.

Операция вставки

Пусть у нас есть вершина с ключом [latex]key[/latex] и дерево [latex]T[/latex], в которое нам нужно вставить нашу вершину. Сразу у нас есть ссылка только на корень дерева, поэтому посмотрим на значение ключа в корне дерева. Если оно вдруг совпало с нашим [latex]key[/latex], то, в этой реализации, мы заменяем поля этой вершины на новые. Если оно не совпало, то так как нам нужно найти незанятое место, куда бы мы могли вставить нашу вершину, мы проверяем: если значение нашего [latex]key[/latex] больше значения в корне — правое поддерево [latex]T[/latex], иначе — левое. Можно заметить, что ситуация изменилась только значением ключа в корне, поэтому можно применить наши прошлые действия. Так мы будем делать, пока наш выбор не остановится на пустом поддереве, то есть — пока не найдется места для нашей вершины. Теперь, когда мы нашли приют нашей вершине, мы вставляем ее на это место.

Операция удаления

Для того, чтобы удалить вершину, нам, очевидно, нужно ее сначала найти, при этом, у нас есть только ключ этой вершины. И да, мы будем не одни, с нами пойдет указатель на предыдущую вершину в дереве. Искать мы будем способом, описанным в предыдущем пункте. Если значение нашего ключа и ключа в корне совпало — мы нашли обреченную вершину, если же мы попали в пустое поддерево — можно считать, что наша работа выполнена (нет вершины — нет проблемы). Однако рассмотрим первый случай.
Пусть правое (левое) поддерево пусто. Тогда удалить вершину просто — мы заменяем адрес удаляемой вершины у предыдущей вершины (там ведь стоит указатель) на адрес левого (правого) поддерева удаляемой вершины.
Если же правое поддерево не пусто, мы уже не можем просто удалить вершину. Чтобы сохранить основное свойство дерева мы должны найти замену. В правом поддереве мы найдем вершину с наименьшим ключом и поменяем с удаляемой вершиной (если есть еще какие-то поля — их тоже заменяем). Задача свелась к первому случаю.

Код

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

class Tree <Key extends Comparable<Key>, Value> {
	
	private class Node {
		Key key;
		Value value;
		Node left, right;
		public Node (Key key, Value value) {
			this.key = key;
			this.value = value;
			this.left = this.right = null;
		}
	}
	
	private Node root;
	
	public Key getRootKey(){
		return root.key;
	}
	public Value getRootValue(){
		return root.value;
	}
	
	private Node add (Node node,Key key, Value value){
		//возвращает измененный узел (после добавления значения)
		if (node == null){
			Node newnode = new Node(key,value);
			return newnode;
		}
		int compareResult = key.compareTo(node.key);
                if(compareResult == 0) {
                    node.value = value;
                    return node;
                }
                else if(compareResult < 0)
                    node.left = add(node.left, key, value);
                else 
                    node.right = add(node.right, key, value);
        return node;
	}
        
        public Key MinKey(){
           Node cur = root;
           // спускаемся к самому левому листу, по свойству дерева - наименьший ключ там
           for(; cur.left != null; cur = cur.left){}
           return cur.key;
        }
        public Key MaxKey(){
           Node cur = root;
           // спускаемся к самому правому листу, по свойству дерева - наибольший ключ там
           for(; cur.right != null; cur = cur.right){}
           return cur.key;
        }
       
        //вспомогательная функция, которая нигде не используется.
        private Node NodeMinKey(Node node){
           Node cur = node;
           for(; cur.left != null; cur = cur.left){}
           return cur;
        }
	
	public void add(Key key, Value value) {
		root = add(root, key, value);
	}
	
        //удаление вершины
	public void delete(Key key) {
            Node cur = root;
            Node prev = null;
            //спускаемся по дереву, пока не найдем вершину или не уткнемся в null
            for(; true; ){
                if(cur == null) return;
                if(key.compareTo(cur.key) < 0){
                    prev = cur; cur = cur.left;
                }
                else if(key.compareTo(cur.key) > 0){
                    prev = cur;
                    cur = cur.right;
                }
                else break;
            }
            /*
             * Итак, у нас есть элемент, который нужно удалить (cur) и его предок (prev)
             * Теперь нас ждет разбор частных случаев:
             *      1)Если правый сын удаляемого элемента не существует, мы можем просто выкинуть этот элемент из
             *        цепи prev -> cur -> left, оставив prev -> left.
             *      2)Если же правый сын существует, так просто выкинуть вершину мы не можем. 
             *        Чтобы сохранить свойство дерева мы найдем узел с наименьшим ключом в правом поддереве cur,
             *        присоединим к найденному узлу левого сына cur и заменим cur на этот узел.
             */
             if(cur.right == null)
                    
                    if(prev == null){ 
                        root = root.left;
                    }
                    else if(cur == prev.right)
                        prev.right = cur.left;
                    else
                        prev.left = cur.left;
                
                else if(cur.left == null)
                    
                    if(prev == null){ 
                        root = root.left;
                    }
                    else if(cur == prev.right)
                            prev.right = cur.left;
                    else
                            prev.left = cur.left;

                else{
                    Node mostLeft = cur.right;
                    prev = null;
                    for(; mostLeft.left != null;){
                        prev = mostLeft;
                        mostLeft = mostLeft.left;
                    }
                    if(prev != null)
                        prev.left = mostLeft.right;
                    else
                        cur.right = mostLeft.right;
                    cur.key = mostLeft.key;
                    cur.value = mostLeft.value;
                }
                
	}
	
	public Value get(Key key) {
            Node cur = root;
            for(; true; ){
                if(cur == null) break;
                if(key.compareTo(cur.key) < 0)
                    cur = cur.left;
                else if(key.compareTo(cur.key) > 0)
                    cur = cur.right;
                else break;
            }
            return cur != null? cur.value : (Value)null;
	}
	
	private void print(Node node, int level) {
		if (node != null) {
			print(node.right, level+1);
			for (int i=0; i < level; i++) {
				System.out.print("\t");
			}
			System.out.println(node.key + " => " + node.value); 
			print(node.left, level + 1);
		}
	}
	
	public void print() {
		print(root, 0);
	}


public static void main (String[] args){
		Tree<Double, Double> a = new Tree<Double, Double>();
		int n = 10000;
		for(int i = 0; i < n; i++){
			a.add( Math.round(Math.random() * 1000.0) + 1.0*i,  Math.round(Math.random() * 1000000.0) + 1.0*i);
		}
		System.out.println(a.MaxKey() + " => " + a.get(a.MaxKey()));
		System.out.println(a.MinKey() + " => " + a.get(a.MinKey()));
                System.out.println();
                System.out.println();
                System.out.println();
                System.out.println("First print");
		a.print();
		a.delete(a.getRootKey());
                System.out.println();
                System.out.println();
                System.out.println();
                System.out.println("Second print");
		a.print();
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

import java.util.*;

import java.lang.*;

import java.io.*;

class Tree <Key extends Comparable<Key>, Value> {

private class Node {

Key key;

Value value;

Node left, right;

public Node (Key key, Value value) {

this.key = key;

this.value = value;

this.left = this.right = null;

}

private Node root;

public Key getRootKey(){

return root.key;

}

public Value getRootValue(){

return root.value;

}

private Node add (Node node,Key key, Value value){

//возвращает измененный узел (после добавления значения)

if (node == null){

Node newnode = new Node(key,value);

return newnode;

}

int compareResult = key.compareTo(node.key);

if(compareResult == 0) {

node.value = value;

return node;

}

else if(compareResult < 0)

node.left = add(node.left, key, value);

else

node.right = add(node.right, key, value);

return node;

}

public Key MinKey(){

Node cur = root;

// спускаемся к самому левому листу, по свойству дерева - наименьший ключ там

for(; cur.left != null; cur = cur.left){}

return cur.key;

}

public Key MaxKey(){

Node cur = root;

// спускаемся к самому правому листу, по свойству дерева - наибольший ключ там

for(; cur.right != null; cur = cur.right){}

return cur.key;

}

//вспомогательная функция, которая нигде не используется.

private Node NodeMinKey(Node node){

Node cur = node;

for(; cur.left != null; cur = cur.left){}

return cur;

}

public void add(Key key, Value value) {

root = add(root, key, value);

}

//удаление вершины

public void delete(Key key) {

Node cur = root;

Node prev = null;

//спускаемся по дереву, пока не найдем вершину или не уткнемся в null

for(; true; ){

if(cur == null) return;

if(key.compareTo(cur.key) < 0){

prev = cur; cur = cur.left;

}

else if(key.compareTo(cur.key) > 0){

prev = cur;

cur = cur.right;

}

else break;

}

* Итак, у нас есть элемент, который нужно удалить (cur) и его предок (prev)

* Теперь нас ждет разбор частных случаев:

* 1)Если правый сын удаляемого элемента не существует, мы можем просто выкинуть этот элемент из

* цепи prev -> cur -> left, оставив prev -> left.

* 2)Если же правый сын существует, так просто выкинуть вершину мы не можем.

* Чтобы сохранить свойство дерева мы найдем узел с наименьшим ключом в правом поддереве cur,

* присоединим к найденному узлу левого сына cur и заменим cur на этот узел.

if(cur.right == null)

if(prev == null){

root = root.left;

}

else if(cur == prev.right)

prev.right = cur.left;

else

prev.left = cur.left;

else if(cur.left == null)

if(prev == null){

root = root.left;

}

else if(cur == prev.right)

prev.right = cur.left;

else

prev.left = cur.left;

else{

Node mostLeft = cur.right;

prev = null;

for(; mostLeft.left != null;){

prev = mostLeft;

mostLeft = mostLeft.left;

}

if(prev != null)

prev.left = mostLeft.right;

else

cur.right = mostLeft.right;

cur.key = mostLeft.key;

cur.value = mostLeft.value;

}

public Value get(Key key) {

Node cur = root;

for(; true; ){

if(cur == null) break;

if(key.compareTo(cur.key) < 0)

cur = cur.left;

else if(key.compareTo(cur.key) > 0)

cur = cur.right;

else break;

}

return cur != null? cur.value : (Value)null;

}

private void print(Node node, int level) {

if (node != null) {

print(node.right, level+1);

for (int i=0; i < level; i++) {

System.out.print("\t");

}

System.out.println(node.key + " => " + node.value);

print(node.left, level + 1);

}

public void print() {

print(root, 0);

}

public static void main (String[] args){

Tree<Double, Double> a = new Tree<Double, Double>();

int n = 10000;

for(int i = 0; i < n; i++){

a.add( Math.round(Math.random() * 1000.0) + 1.0*i, Math.round(Math.random() * 1000000.0) + 1.0*i);

}

System.out.println(a.MaxKey() + " => " + a.get(a.MaxKey()));

System.out.println(a.MinKey() + " => " + a.get(a.MinKey()));

System.out.println();

System.out.println("First print");

a.print();

a.delete(a.getRootKey());

System.out.println();

System.out.println("Second print");

a.print();

}

Java Collections Framework: Map. Частотный словарь.

29/11/2015 by Максим Швандт

Задача 1:

Получив на входе корпус языка (огромный набор атрибутированных текстов на каком-нибудь языке) построить частотный словарь. Знаки препинания, скобки, кавычки и числа должны быть удалены. Слова, содержащие в себе не буквенные символы, игнорируются целиком.

Задача 2:

При автоматическом переводе необходимо из нескольких слов выбрать наиболее употребительное. Необходимо построить эффективную реализацию функции, которая для данного множества (Set) слов-ключей, определит то, которому соответствует максимальное значение.

Тест

input

output

aaa for bbb aaa for if
%EOF%

Word frequency statistics:

aaa   ,   2,   0.250000
bbb   ,   1,   0.125000
for   ,   2,   0.250000
if   ,   1,   0.125000
—————————————

Select max frequent token from: for do to while if
=> selected is: for

To be, or not to be: that is the question:
Whether ’tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And by opposing end them? To die: to sleep;
No more; and by a sleep to say we end
The heart-ache and the thousand natural shocks
That flesh is heir to, ’tis a consummation
Devoutly to be wish’d. To die, to sleep;
To sleep: perchance to dream: ay, there’s the rub;
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause: there’s the respect
That makes calamity of so long life;
For who would bear the whips and scorns of time,
The oppressor’s wrong, the proud man’s contumely,
The pangs of despised love, the law’s delay,
The insolence of office and the spurns
That patient merit of the unworthy takes,
When he himself might his quietus make
With a bare bodkin? who would fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscover’d country from whose bourn
No traveller returns, puzzles the will
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all;
And thus the native hue of resolution
Is sicklied o’er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry,
And lose the name of action. — Soft you now!
The fair Ophelia! Nymph, in thy orisons
Be all my sins remember’d.

%EOF%

Word frequency statistics:

And   ,   5,   0.007321
Be   ,   1,   0.001464
But   ,   1,   0.001464
Devoutly   ,   1,   0.001464
For   ,   2,   0.002928
Is   ,   1,   0.001464
Must   ,   1,   0.001464
No   ,   2,   0.002928
Nymph   ,   1,   0.001464
Ophelia   ,   1,   0.001464
Or   ,   1,   0.001464
Soft   ,   1,   0.001464
Than   ,   1,   0.001464
That   ,   3,   0.004392
The   ,   7,   0.010249
Thus   ,   1,   0.001464
To   ,   5,   0.007321
When   ,   2,   0.002928
Whether   ,   1,   0.001464
With   ,   2,   0.002928
a   ,   5,   0.007321
ache   ,   1,   0.001464
action   ,   1,   0.001464
after   ,   1,   0.001464
against   ,   1,   0.001464
all   ,   2,   0.002928
and   ,   7,   0.010249
arms   ,   1,   0.001464
arrows   ,   1,   0.001464
awry   ,   1,   0.001464
ay   ,   1,   0.001464
bare   ,   1,   0.001464
be   ,   3,   0.004392
bear   ,   3,   0.004392
bodkin   ,   1,   0.001464
bourn   ,   1,   0.001464
by   ,   2,   0.002928
calamity   ,   1,   0.001464
cast   ,   1,   0.001464
coil   ,   1,   0.001464
come   ,   1,   0.001464
conscience   ,   1,   0.001464
consummation   ,   1,   0.001464
contumely   ,   1,   0.001464
country   ,   1,   0.001464
cowards   ,   1,   0.001464
currents   ,   1,   0.001464
d   ,   3,   0.004392
death   ,   2,   0.002928
delay   ,   1,   0.001464
despised   ,   1,   0.001464
die   ,   2,   0.002928
does   ,   1,   0.001464
dread   ,   1,   0.001464
dream   ,   1,   0.001464
dreams   ,   1,   0.001464
end   ,   2,   0.002928
enterprises   ,   1,   0.001464
er   ,   1,   0.001464
fair   ,   1,   0.001464
fardels   ,   1,   0.001464
flesh   ,   1,   0.001464
fly   ,   1,   0.001464
fortune   ,   1,   0.001464
from   ,   1,   0.001464
give   ,   1,   0.001464
great   ,   1,   0.001464
grunt   ,   1,   0.001464
have   ,   2,   0.002928
he   ,   1,   0.001464
heart   ,   1,   0.001464
heir   ,   1,   0.001464
himself   ,   1,   0.001464
his   ,   1,   0.001464
hue   ,   1,   0.001464
ills   ,   1,   0.001464
in   ,   3,   0.004392
insolence   ,   1,   0.001464
is   ,   2,   0.002928
know   ,   1,   0.001464
law   ,   1,   0.001464
life   ,   2,   0.002928
long   ,   1,   0.001464
lose   ,   1,   0.001464
love   ,   1,   0.001464
make   ,   2,   0.002928
makes   ,   2,   0.002928
man   ,   1,   0.001464
may   ,   1,   0.001464
merit   ,   1,   0.001464
might   ,   1,   0.001464
mind   ,   1,   0.001464
moment   ,   1,   0.001464
more   ,   1,   0.001464
mortal   ,   1,   0.001464
my   ,   1,   0.001464
name   ,   1,   0.001464
native   ,   1,   0.001464
natural   ,   1,   0.001464
nobler   ,   1,   0.001464
not   ,   2,   0.002928
now   ,   1,   0.001464
o   ,   1,   0.001464
of   ,   15,   0.021962
off   ,   1,   0.001464
office   ,   1,   0.001464
opposing   ,   1,   0.001464
oppressor   ,   1,   0.001464
or   ,   1,   0.001464
orisons   ,   1,   0.001464
others   ,   1,   0.001464
outrageous   ,   1,   0.001464
pale   ,   1,   0.001464
pangs   ,   1,   0.001464
patient   ,   1,   0.001464
pause   ,   1,   0.001464
perchance   ,   1,   0.001464
pith   ,   1,   0.001464
proud   ,   1,   0.001464
puzzles   ,   1,   0.001464
question   ,   1,   0.001464
quietus   ,   1,   0.001464
rather   ,   1,   0.001464
regard   ,   1,   0.001464
remember   ,   1,   0.001464
resolution   ,   1,   0.001464
respect   ,   1,   0.001464
returns   ,   1,   0.001464
rub   ,   1,   0.001464
s   ,   5,   0.007321
say   ,   1,   0.001464
scorns   ,   1,   0.001464
sea   ,   1,   0.001464
shocks   ,   1,   0.001464
shuffled   ,   1,   0.001464
sicklied   ,   1,   0.001464
sins   ,   1,   0.001464
sleep   ,   5,   0.007321
slings   ,   1,   0.001464
so   ,   1,   0.001464
something   ,   1,   0.001464
spurns   ,   1,   0.001464
suffer   ,   1,   0.001464
sweat   ,   1,   0.001464
take   ,   1,   0.001464
takes   ,   1,   0.001464
that   ,   4,   0.005857
the   ,   15,   0.021962
their   ,   1,   0.001464
them   ,   1,   0.001464
there   ,   2,   0.002928
this   ,   2,   0.002928
those   ,   1,   0.001464
thought   ,   1,   0.001464
thousand   ,   1,   0.001464
thus   ,   1,   0.001464
thy   ,   1,   0.001464
time   ,   1,   0.001464
tis   ,   2,   0.002928
to   ,   10,   0.014641
traveller   ,   1,   0.001464
troubles   ,   1,   0.001464
turn   ,   1,   0.001464
under   ,   1,   0.001464
undiscover   ,   1,   0.001464
unworthy   ,   1,   0.001464
us   ,   3,   0.004392
we   ,   4,   0.005857
weary   ,   1,   0.001464
what   ,   1,   0.001464
whips   ,   1,   0.001464
who   ,   2,   0.002928
whose   ,   1,   0.001464
will   ,   1,   0.001464
wish   ,   1,   0.001464
with   ,   1,   0.001464
would   ,   2,   0.002928
wrong   ,   1,   0.001464
you   ,   1,   0.001464
—————————————

Select max frequent token from: else for do to while if
=> selected is: to

#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%

Word frequency statistics:

Even   ,   1,   0.032258
Odd   ,   1,   0.032258
cout   ,   2,   0.064516
else   ,   1,   0.032258
endl   ,   2,   0.064516
for   ,   1,   0.032258
i   ,   4,   0.129032
if   ,   1,   0.032258
include   ,   1,   0.032258
int   ,   2,   0.064516
iostream   ,   1,   0.032258
main   ,   1,   0.032258
namespace   ,   1,   0.032258
return   ,   1,   0.032258
std   ,   1,   0.032258
using   ,   1,   0.032258
—————————————

Select max frequent token from: else for do to while if
=> selected is: else

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

Интерфейс FrequencyVocabulary, который описывает заданную функциональность доступа к частотному словарю
Класс FrequencyVocabularyImpl, имплементирует данный интерфейс
Класс FrequencyVocabularyTest, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.

Интерфейс FrequencyVocabulary:

package odessa.uni.imem.maxim;

import java.util.Set;
import java.util.Map;
import java.util.TreeMap;

public interface FrequencyVocabulary
{
   public class Statistic
   {
      public int count;
      public double frequency;
      public Statistic()
      {
         count = 0;
         frequency = 0;
      }
   }
   
   public TreeMap<String,Statistic> getMap();
   public String selectMaxFreqToken( Set<String> tokens );
   
}

package odessa.uni.imem.maxim;

import java.util.Set;

import java.util.Map;

import java.util.TreeMap;

public interface FrequencyVocabulary

{

public class Statistic

{

public int count;

public double frequency;

public Statistic()

{

count = 0;

frequency = 0;

}

public TreeMap<String,Statistic> getMap();

public String selectMaxFreqToken( Set<String> tokens );

}

Интерфейс подразумевает, что частотный словарь представлен в виде стандартного класса TreeMap. В качестве ключа типа String выступает само слово, а в качестве значения — специальная структура Statistic, содержащая статистику по данному слову, а именно — число вхождений count и частоту frequency.

Интерфейс содержит два метода:

getMap — возвращает сам частотный словарь как TreeMap объект.
selectMaxFreqToken — выполняет условие 2-го задания, а именно — выбирает наиболее часто встречаемое слово из заданного набора, передаваемого как аргумент типа Set

Класс FrequencyVocabularyImpl:

package odessa.uni.imem.maxim;

import java.util.Set;
import java.util.Map;
import java.util.TreeMap;
import java.util.StringTokenizer;

public class FrequencyVocabularyImpl implements FrequencyVocabulary
{
   TreeMap<String, Statistic> map;

   public FrequencyVocabularyImpl(String text, String delimiters)
   {
      map = new TreeMap<String, Statistic>();
      int totalCount = 0;
      
      // first we parse text to tokens (words) and fill the map where keys are words and values - statistic for given word
      StringTokenizer st = new StringTokenizer(text, delimiters);
      while (st.hasMoreTokens())
      {
         String key = st.nextToken();
         if ( containsDigits(key) )
         {
             continue;
         }
         Statistic value = map.get(key);
         if (null != value)
         {
            value.count++;
            map.replace(key, value);
         }
         else
         {
            value = new Statistic();
            value.count = 1;
            map.put( key, value );
         }
         totalCount += value.count;
      }

      // now we can calculate and set frequency field for all the entries
      for (Map.Entry<String, Statistic> entry : map.entrySet())
      {
         if ( entry.getValue().count != 0 )
         {
            entry.getValue().frequency = ((double)entry.getValue().count) / totalCount;
         }
      }
   }

   public TreeMap<String, Statistic> getMap()
   {
      return map;
   }

   // select token with max frequency from the given set of tokens
   public String selectMaxFreqToken( Set<String> tokens )
   {
      String maxFreqToken = null;
      Statistic maxFreqStat = null;
      for( String token : tokens )
      {
         Statistic stat = map.get(token);
         if ( stat != null )
         {
            if ( maxFreqToken == null )
            {
               maxFreqToken = token;
               maxFreqStat = stat;
            }
            else
            {
               if ( stat.count > maxFreqStat.count )
               {
                  maxFreqToken = token;
                  maxFreqStat = stat;
               }
            }
         }
      }
      
      return maxFreqToken;
   }
   
   public static boolean containsDigits( String token )
   {
       if (  token.indexOf('0') >= 0 || 
               token.indexOf('1') >= 0 ||
               token.indexOf('2') >= 0 ||
               token.indexOf('3') >= 0 ||
               token.indexOf('4') >= 0 ||
               token.indexOf('5') >= 0 ||
               token.indexOf('6') >= 0 ||
               token.indexOf('7') >= 0 ||
               token.indexOf('8') >= 0 ||
               token.indexOf('9') >= 0
               )
      {
          return true;
      }
       return false;
   }
}

100

101

102

103

package odessa.uni.imem.maxim;

import java.util.Set;

import java.util.Map;

import java.util.TreeMap;

import java.util.StringTokenizer;

public class FrequencyVocabularyImpl implements FrequencyVocabulary

{

TreeMap<String, Statistic> map;

public FrequencyVocabularyImpl(String text, String delimiters)

{

map = new TreeMap<String, Statistic>();

int totalCount = 0;

// first we parse text to tokens (words) and fill the map where keys are words and values - statistic for given word

StringTokenizer st = new StringTokenizer(text, delimiters);

while (st.hasMoreTokens())

{

String key = st.nextToken();

if ( containsDigits(key) )

{

continue;

}

Statistic value = map.get(key);

if (null != value)

{

value.count++;

map.replace(key, value);

}

else

{

value = new Statistic();

value.count = 1;

map.put( key, value );

}

totalCount += value.count;

}

// now we can calculate and set frequency field for all the entries

for (Map.Entry<String, Statistic> entry : map.entrySet())

{

if ( entry.getValue().count != 0 )

{

entry.getValue().frequency = ((double)entry.getValue().count) / totalCount;

}

public TreeMap<String, Statistic> getMap()

{

return map;

}

// select token with max frequency from the given set of tokens

public String selectMaxFreqToken( Set<String> tokens )

{

String maxFreqToken = null;

Statistic maxFreqStat = null;

for( String token : tokens )

{

Statistic stat = map.get(token);

if ( stat != null )

{

if ( maxFreqToken == null )

{

maxFreqToken = token;

maxFreqStat = stat;

}

else

{

if ( stat.count > maxFreqStat.count )

{

maxFreqToken = token;

maxFreqStat = stat;

}

return maxFreqToken;

}

public static boolean containsDigits( String token )

{

if ( token.indexOf('0') >= 0 ||

token.indexOf('1') >= 0 ||

token.indexOf('2') >= 0 ||

token.indexOf('3') >= 0 ||

token.indexOf('4') >= 0 ||

token.indexOf('5') >= 0 ||

token.indexOf('6') >= 0 ||

token.indexOf('7') >= 0 ||

token.indexOf('8') >= 0 ||

token.indexOf('9') >= 0

)

{

return true;

}

return false;

}

Класс строит частотный словарь на основе входного текста. Словарь храниться в виде приватного члена типа TreeMap. Для разбора текста на слова используется известный класс StringTokenizer. Конструктор создает класс в 2 прохода. За первый проход заполняется словарь, где для каждого слова заносится статистика с подсчитанным счетчиком вхождений count и пока еще нулевым frequency, однако, вычисляется общий счетчик всех слов totalCount. За второй проход по уже известной статистике каждого слова рассчитывается его frequency как count /totalCount.

Метод containsDigits добавляет проверку для отсеивания лекскм, содержащих цифры согласно требованию 1-й задачи.

Выборка слова с максимальной частотой согласно второй задаче реализована в методе selectMaxFreqToken, где выполняется цикл по всем заданным словам и выбирается слово с максимальным count.

Класс FrequencyVocabularyTest

package odessa.uni.imem.maxim;

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.TreeMap;
import java.util.NoSuchElementException;
import java.io.IOException;

import odessa.uni.imem.maxim.FrequencyVocabulary.Statistic;

import java.util.Scanner;

public class FrequencyVocabularyTest
{

   public static void main(String[] args)
   {
      
      String text = "";
      
      Scanner in = new Scanner(System.in);
      
      for(;;)
      {
        if ( ! in.hasNextLine() ) break;
        String inputLine = in.nextLine();
        if ( inputLine == null || inputLine.equals("%EOF%") ) break;
        text = text + inputLine + "\n";
      }
      in.close();
      
      if ( text.isEmpty() )
      {
         System.out.println("*** Empty text ****");
         return;
      }
      
      //System.out.println("*** DBG:input text is: <"+text+">");
            
      FrequencyVocabulary fv = new FrequencyVocabularyImpl( text, " ?.,;:-+\n\t{}[]=()<>*&%$#@\"\'`~!" );
      
      TreeMap<String,FrequencyVocabulary.Statistic> statMap = fv.getMap();
      System.out.println("Word frequency statistics:\n");
      for (Map.Entry<String, Statistic> statEntry : statMap.entrySet())
      {
         System.out.printf("%s\t,\t%d,\t%f\n",
               statEntry.getKey(),
               statEntry.getValue().count,
               statEntry.getValue().frequency
               );
      }
      System.out.println("--------------------------------------\n");
      
      HashSet<String> tokens = new HashSet<String>();
      tokens.add("for");
      tokens.add("do");
      tokens.add("to");
      tokens.add("while");
      tokens.add("else");
      tokens.add("if");
      String caption = "Select max frequent token from: ";
      for( String s : tokens )
      {
         caption += " " + s;
      }
      System.out.println(caption);
      String s = fv.selectMaxFreqToken(tokens);
      if ( s == null ) s = "<null>";
      System.out.println("=> selected is: " + s );
      
   }

}

package odessa.uni.imem.maxim;

import java.util.Set;

import java.util.HashSet;

import java.util.Map;

import java.util.TreeMap;

import java.util.NoSuchElementException;

import java.io.IOException;

import odessa.uni.imem.maxim.FrequencyVocabulary.Statistic;

import java.util.Scanner;

public class FrequencyVocabularyTest

{

public static void main(String[] args)

{

String text = "";

Scanner in = new Scanner(System.in);

for(;;)

{

if ( ! in.hasNextLine() ) break;

String inputLine = in.nextLine();

if ( inputLine == null || inputLine.equals("%EOF%") ) break;

text = text + inputLine + "\n";

}

in.close();

if ( text.isEmpty() )

{

System.out.println("*** Empty text ****");

return;

}

//System.out.println("*** DBG:input text is: <"+text+">");

FrequencyVocabulary fv = new FrequencyVocabularyImpl( text, " ?.,;:-+\n\t{}[]=()<>*&%$#@\"\'`~!" );

TreeMap<String,FrequencyVocabulary.Statistic> statMap = fv.getMap();

System.out.println("Word frequency statistics:\n");

for (Map.Entry<String, Statistic> statEntry : statMap.entrySet())

{

System.out.printf("%s\t,\t%d,\t%f\n",

statEntry.getKey(),

statEntry.getValue().count,

statEntry.getValue().frequency

);

}

System.out.println("--------------------------------------\n");

HashSet<String> tokens = new HashSet<String>();

tokens.add("for");

tokens.add("do");

tokens.add("to");

tokens.add("while");

tokens.add("else");

tokens.add("if");

String caption = "Select max frequent token from: ";

for( String s : tokens )

{

caption += " " + s;

}

System.out.println(caption);

String s = fv.selectMaxFreqToken(tokens);

if ( s == null ) s = "<null>";

System.out.println("=> selected is: " + s );

}

В данном классе реализуется приложение, которое тестирует интерфейсные методы частотного словаря. Он состоит из следующих этапов:

Ввод исходного текста, так как текст может допускать любое количество символов новой строки, и поскольку затруднительно определить признак конца текста как конец файла, в качестве признака конца текста используется спец. лексема %EOF% , которая должна быть после последней строки текста.
Создание объекта частотного словаря на основе введенного текста, в качестве разделителей используются все известные символы, которые не явл. буквой или цифрой.
Проход по элементам словаря и печать статистики.
Тестирование метода, определяющего максимально встречающиеся слова из набора заданных

Примечание: Ввиду того, что затруднительно за один раз ввести с консоли исходный текст для 1-го задания и список слов для 2-го, набор слов для 2-го задания задается в коде непосредственно, а именно do, to, for, while и if.

Код на Ideone: https://ideone.com/jxJ4rU

BigSegmentedArray by Tolia

29/11/2015 by Осецимский Анатолий

Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим:

принимает большой массив
частые запросы get(), min();

Поскольку команда set задает значение на интервале, я решил сделать «дерево отрезков». Которое устроено как бинарное дерево относительно индекса (в задании большое количество запросов get(), следовательно будет быстрее искать элемент по индексу), имея в себе левый и правые концы интервала, а также значение на этом интервале.

Основная операция в данной структуре — set(). И она самая сложная по своей схеме. Когда приходить запрос на установление значения на интервале, надо проверить, возможно узел пуст, следовательно такого интервала еще не задавали, и тогда можно его создать. Если же узел не пуст, то надо проверить, в данном узле ли задается наш интервал, или же надо перейти к другому. Если же в данном узле надо задать интервал, то у нас вырисовывается три ситуации: когда задаваемый интервал не превосходит интервала узла, когда заданный интервал превосходить интервал узла и когда одна точка заданного интервала лежит внутри интервала узла, а другая, вне его. В первом случаем, просто разбиваем внутренний интервал на три подинтервала: левая часть внутреннего интервала, заданный интервал и правая часть внутреннего интервала. Во-втором, необходимо увеличить границы внутреннего интервала до задаваемого, и удалить все интервалы(в левом и правом узлах), которые данный новый интервал перекрыл. В третьем необходимо разбить интервал узла на подинтервал до внутренней точки задаваемого интервала, и на то, что осталось. Потом удалить все интервала, которые мы перекрыли.

Метод поиска значение по индексу осуществляется как и в бинарном дереве, пока не попадем на нужный нам интервал, или значение данного индекса еще не было установлено.

Метод нахождения минимума на подинтервала спускается по дереву, пока не попадет на нужный интервал, и потом проверяет значения на каждом из интервалов и выбирает минимальный.

Поскольку у нас дерево отсортировано по индексу, то искать индекс элемента по значению сложнее, необходимо пройти все интервалы от индекса, который нам дали в начале, пока не встретим искомое значение, или же выведем, что его нет.

Теоретическая оценка сложности методов:

get(i): O(log(count(set)));
set(x, y, val): O(log(count(set)));
indexof(val, index): O(count(set() — interval(index)));
min(x, y) : O(count(set()))

Первый Set в BigSegmentedArray отрабатывает за 436345 нс.
Get в BigSegmentedArray отрабатывает за 7700 нс.
14
Второй Set в BigSegmentedArray отрабатывает за 4991 нс.
Min в BigSegmentedArray отрабатывает за 17883 нс.
1

Первый Set в BigSegmentedArray отрабатывает за 436345 нс.

Get в BigSegmentedArray отрабатывает за 7700 нс.

Второй Set в BigSegmentedArray отрабатывает за 4991 нс.

Min в BigSegmentedArray отрабатывает за 17883 нс.

Ссылка на ideone.

/**
 * Created by green on 28.11.15.
 */

import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import java.security.Key;

/**
 * Created by green on 26.11.15.
 */

interface SegmentedArray&lt;T&gt; {
    /**
     * &lt;p&gt;Get value by element index&lt;/p&gt;
     * @param index index of element.
     * @return  Value of element with specified index.
     */
    T get(int index);

    /**
     * &lt;p&gt;Set the same value for all elements in the specified index range&lt;/p&gt;
     * @param start the beginning index, inclusive.
     * @param end the ending index, exclusive.
     * @param value value for.
     */
    void set(int start, int end, T value);

    /**
     * &lt;p&gt;Returns the index within this array of the first occurrence of the specified value,
     * starting at the specified index. If no such value of k exists, then -1 is returned.&lt;/p&gt;
     * @param value the T-based value for which to search.
     * @param fromIndex the index from which to start the search.
     * @return the index within this array of the first occurrence of the element with specified value,
     * starting at the specified index.
     */
     int indexOf(T value, int fromIndex);

    /**
     * &lt;p&gt;Find minimum value in the specified indexes range&lt;/p&gt;
     * @param start the beginning index, inclusive.
     * @param end the ending index, exclusive.
     * @return Minimum value.
     */
     T minValue(int start, int end);
}


class CT &lt;Value extends Comparable&lt;Value&gt;&gt;  implements SegmentedArray&lt;Value&gt;{

    private class Node {
        Value value;
        int l, r;
        Node left, right, father;
        public Node (Value value, Node father, int l, int r) {
            this.value = value;
            this.left = this.right = null;
            this.father = father;
            this.l = l; this.r = r;
        }
    }

    private Node root;

    private Node add (Node node,Value value, Node father, int l, int r){
        if (node == null){
            Node newnode = new Node(value,father, l , r);
            return newnode;
        }
        //int compareResultl = l.compareTo(node.l);
        //int compareResultr = r.compareTo(node.r);
        if(l &gt; node.r){
            node.right = add(node.right, value, node, l, r);
        }else if(r &lt; node.l){
            node.left = add(node.left, value, node, l, r);
        }else if(l &gt;= node.l &amp;&amp; r &lt;= node.r){
            if(l == node.l &amp;&amp; r == node.r){
                node.value = value;
                return node;
            }else if(l == node.l){
                node.right = add(node.right, node.value, node, r+1, node.r);
                node.value = value;
                node.r = r;
            }else if(r == node.r){
                node.left = add(node.left, node.value, node, node.l, l-1);
                node.value = value;
                node.l = l;
            }else{
                Node newnode = new Node(value,father, l , r);
                newnode.left = node.left;
                newnode.right = node.right;
                newnode.left = add(newnode.left, node.value, newnode, node.l, l-1);
                newnode.right = add(newnode.right, node.value, newnode, r+1, node.r);
                node = newnode;
            }
        }else if(l &lt; node.l &amp;&amp; r &gt; node.r){
            node.value = value;
            node.l = l;
            node.r = r;
            node.left = delete(node.left, l, false);
            node.right = delete(node.right, r, true);
        }else if(l &lt; node.l){
            if(r == node.r){
                node.value = value;
                node.l = l;
                node.left = delete(node.left, l, false);
            }else{
                node = add(node, node.value, father, r+1, node.r);
                node = add(node, value, father, l, r);
            }
        }else if (r &gt; node.r) {
            if (l == node.l) {
                node.value = value;
                node.r = r;
                node.right = delete(node.right, r, true);
            } else {
                node = add(node, node.value, father, node.l, l - 1);
                node = add(node, value, father, l, r);
            }
        }
        return node;
    }

    public void set(int l, int r, Value value) {
        root = add(root, value, null, l, r);
    }
    private Node delete(Node node, int d, Boolean side){
        if(node == null) return null;
        if(d &lt; node.r &amp;&amp; d &gt; node.l){
            node = add(node, node.value, node.father, node.l, d - 1);
            node = delete(node, d, side);
        }else if(d &lt; node.l){
            if(side)
                node.left = delete(node.left, d, side);
            else {
                node = node.left;
                node = delete(node, d, side);
            }
        }else if(d &gt; node.r){
            if(side) {
                node = node.right;
                node = delete(node, d, side);
            }else
                node.right = delete(node.right, d, side);
        }else if(d == node.r){
            if(side) {node = node.right;} else {node.right = null;node.r = d - 1;}
        }else if(d == node.l){
            if(side) {node.left = null;node.l = d + 1;} else {node = node.left;}
        }
        return node;
    }

    private Value get(Node node, int index){
        if(node == null) return null;
        if(index &gt; node.r)
            return get(node.right, index);
        else if (index &lt; node.l)
            return get(node.left, index);
        else
            return node.value;
    }

    public Value get(int index) {
        return get(root, index);
    }

    private Value minimum(Value x, Value y){
        if(x == null &amp;&amp; y == null) return null;
        else if(x == null) return y;
        else if(y == null) return x;
        else {
            if (x.compareTo(y) == 1) return y;
            else return x;
        }
    }

    private Value min(Node node, int start, int end){
        if(node == null) return null;
        if(end &lt; node.l){
            return min(node.left, start, end);
        }else if (start &gt; node.r){
            return min(node.right, start, end);
        }else{
            Value v1 = null, v2 = null;
            if(start &lt; node.l) v1 = min(node.left, start, end);
            if(end &gt; node.r) v2 = min(node.right, start, end);
            return minimum(v2, minimum(node.value, v1));
        }
    }

    public Value minValue(int start, int end){
        return min(root, start, end);
    }

    private Integer indexOf(Node node, Value value, int index){
        if(node == null) return null;
        if(index &lt;= node.r) {
            Integer v = null;
            if(index &lt; node.l){
                v = indexOf(node.left, value, index);
                if (v != null) return v;
            }
            if (value == node.value) return Math.max(node.l, index);
            v = indexOf(node.right, value, index);
            if (v != null) return v;
        }
        return indexOf(node.right, value, index);
    }

    public int indexOf(Value value, int index){
        return indexOf(root, value, index);
    }

    private void print(Node node, int level) {
        if (node != null) {
            print(node.right,level+1);
            for (int i=0;i&lt;level;i++) {
                System.out.print("\t");
            }
            System.out.println(node.l + "-" + node.r + "-&gt;" + node.value);
            print(node.left,level+1);
        }
    }

    public void print() {
        print(root,0);
    }

}


public class Tree_cut {
    public static void main(String[] args) {
        CT&lt;Integer&gt; tree = new CT&lt;&gt;();
        long start, end;
        start = System.nanoTime();
        tree.set(50, 4566, 14);
        //tree.set(130, 740, 29012);
        //tree.set(1000, 1084, -2);
        //tree.set(3006, 3070, 51);
        end = System.nanoTime();//tree.set(50, 4566, 14);
        System.out.println("Первый Set в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");

        start = System.nanoTime();
        Integer get = tree.get(111);
        end = System.nanoTime();
        System.out.println("Get в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");
        System.out.println(get);

        start = System.nanoTime();
        tree.set(76, 830, 1);
        end = System.nanoTime();
        System.out.println("Второй Set в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");
        tree.set(60, 92, 0);

        start = System.nanoTime();
        int minimum = tree.minValue(130, 1400);
        end = System.nanoTime();
        System.out.println("Min в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");
        System.out.println(minimum);
        tree.print();
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

/**

* Created by green on 28.11.15.

import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import java.security.Key;

/**

* Created by green on 26.11.15.

interface SegmentedArray<T> {

/**

* Get value by element index

* @param index index of element.

* @return Value of element with specified index.

T get(int index);

/**

* Set the same value for all elements in the specified index range

* @param start the beginning index, inclusive.

* @param end the ending index, exclusive.

* @param value value for.

void set(int start, int end, T value);

/**

* Returns the index within this array of the first occurrence of the specified value,

* starting at the specified index. If no such value of k exists, then -1 is returned.

* @param value the T-based value for which to search.

* @param fromIndex the index from which to start the search.

* @return the index within this array of the first occurrence of the element with specified value,

* starting at the specified index.

int indexOf(T value, int fromIndex);

/**

* Find minimum value in the specified indexes range

* @param start the beginning index, inclusive.

* @param end the ending index, exclusive.

* @return Minimum value.

T minValue(int start, int end);

}

class CT <Value extends Comparable<Value>> implements SegmentedArray<Value>{

private class Node {

Value value;

int l, r;

Node left, right, father;

public Node (Value value, Node father, int l, int r) {

this.value = value;

this.left = this.right = null;

this.father = father;

this.l = l; this.r = r;

}

private Node root;

private Node add (Node node,Value value, Node father, int l, int r){

if (node == null){

Node newnode = new Node(value,father, l , r);

return newnode;

}

//int compareResultl = l.compareTo(node.l);

//int compareResultr = r.compareTo(node.r);

if(l > node.r){

node.right = add(node.right, value, node, l, r);

}else if(r < node.l){

node.left = add(node.left, value, node, l, r);

}else if(l >= node.l && r <= node.r){

if(l == node.l && r == node.r){

node.value = value;

return node;

}else if(l == node.l){

node.right = add(node.right, node.value, node, r+1, node.r);

node.value = value;

node.r = r;

}else if(r == node.r){

node.left = add(node.left, node.value, node, node.l, l-1);

node.value = value;

node.l = l;

}else{

Node newnode = new Node(value,father, l , r);

newnode.left = node.left;

newnode.right = node.right;

newnode.left = add(newnode.left, node.value, newnode, node.l, l-1);

newnode.right = add(newnode.right, node.value, newnode, r+1, node.r);

node = newnode;

}

}else if(l < node.l && r > node.r){

node.value = value;

node.l = l;

node.r = r;

node.left = delete(node.left, l, false);

node.right = delete(node.right, r, true);

}else if(l < node.l){

if(r == node.r){

node.value = value;

node.l = l;

node.left = delete(node.left, l, false);

}else{

node = add(node, node.value, father, r+1, node.r);

node = add(node, value, father, l, r);

}

}else if (r > node.r) {

if (l == node.l) {

node.value = value;

node.r = r;

node.right = delete(node.right, r, true);

} else {

node = add(node, node.value, father, node.l, l - 1);

node = add(node, value, father, l, r);

}

return node;

}

public void set(int l, int r, Value value) {

root = add(root, value, null, l, r);

}

private Node delete(Node node, int d, Boolean side){

if(node == null) return null;

if(d < node.r && d > node.l){

node = add(node, node.value, node.father, node.l, d - 1);

node = delete(node, d, side);

}else if(d < node.l){

if(side)

node.left = delete(node.left, d, side);

else {

node = node.left;

node = delete(node, d, side);

}

}else if(d > node.r){

if(side) {

node = node.right;

node = delete(node, d, side);

}else

node.right = delete(node.right, d, side);

}else if(d == node.r){

if(side) {node = node.right;} else {node.right = null;node.r = d - 1;}

}else if(d == node.l){

if(side) {node.left = null;node.l = d + 1;} else {node = node.left;}

}

return node;

}

private Value get(Node node, int index){

if(node == null) return null;

if(index > node.r)

return get(node.right, index);

else if (index < node.l)

return get(node.left, index);

else

return node.value;

}

public Value get(int index) {

return get(root, index);

}

private Value minimum(Value x, Value y){

if(x == null && y == null) return null;

else if(x == null) return y;

else if(y == null) return x;

else {

if (x.compareTo(y) == 1) return y;

else return x;

}

private Value min(Node node, int start, int end){

if(node == null) return null;

if(end < node.l){

return min(node.left, start, end);

}else if (start > node.r){

return min(node.right, start, end);

}else{

Value v1 = null, v2 = null;

if(start < node.l) v1 = min(node.left, start, end);

if(end > node.r) v2 = min(node.right, start, end);

return minimum(v2, minimum(node.value, v1));

}

public Value minValue(int start, int end){

return min(root, start, end);

}

private Integer indexOf(Node node, Value value, int index){

if(node == null) return null;

if(index <= node.r) {

Integer v = null;

if(index < node.l){

v = indexOf(node.left, value, index);

if (v != null) return v;

}

if (value == node.value) return Math.max(node.l, index);

v = indexOf(node.right, value, index);

if (v != null) return v;

}

return indexOf(node.right, value, index);

}

public int indexOf(Value value, int index){

return indexOf(root, value, index);

}

private void print(Node node, int level) {

if (node != null) {

print(node.right,level+1);

for (int i=0;i<level;i++) {

System.out.print("\t");

}

System.out.println(node.l + "-" + node.r + "->" + node.value);

print(node.left,level+1);

}

public void print() {

print(root,0);

}

public class Tree_cut {

public static void main(String[] args) {

CT<Integer> tree = new CT<>();

long start, end;

start = System.nanoTime();

tree.set(50, 4566, 14);

//tree.set(130, 740, 29012);

//tree.set(1000, 1084, -2);

//tree.set(3006, 3070, 51);

end = System.nanoTime();//tree.set(50, 4566, 14);

System.out.println("Первый Set в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");

start = System.nanoTime();

Integer get = tree.get(111);

end = System.nanoTime();

System.out.println("Get в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");

System.out.println(get);

start = System.nanoTime();

tree.set(76, 830, 1);

end = System.nanoTime();

System.out.println("Второй Set в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");

tree.set(60, 92, 0);

start = System.nanoTime();

int minimum = tree.minValue(130, 1400);

end = System.nanoTime();

System.out.println("Min в BigSegmentedArray отрабатывает за " + (end - start) + " нс.");

System.out.println(minimum);

tree.print();

}

Binary Tree Search

28/11/2015 by Осецимский Анатолий

Код реализация Бинарного дерева на Java для задания из Word of Week. Саму идею дерева и теоретический алгоритм можно почитать в Википедии. Отличается от реализации на C++ тем, что в Java мы не обращаемся к адресам узлам явно, сравнение происходит через компаратор и сам класс при создании имеет свои особенности от C++. Для работы самого класса, в нем присутствуют приватные методы, которые работают рекурсивно, и geter’ы, позволяющие получать значение от работы приватных методов.

В тестовом выводе можно пронаблюдать(если вы запустите данный код) как выглядит дерево после добавления данных, потом как оно выглядит после удаления одного из узлов и далее убедиться в правильности дополнительных функций.

Ссылка на ideone.

import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import java.security.Key;

/**
 * Created by green on 26.11.15.
 */
class BST <Key extends Comparable<Key>, Value> {

    private class Node {
        Key key;
        Value value;
        Node left, right, father;
        public Node (Key key, Value value) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
            this.father = null;
        }
        public Node (Key key, Value value, Node father) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
            this.father = father;
        }
    }

    private Node root;

    private Node add (Node node,Key key, Value value, Node father){
        if (node == null){
            Node newnode = new Node(key,value, father);
            return newnode;
        }
        int compareResult = key.compareTo(node.key);
        if (compareResult > 0) node.right = add(node.right, key, value, node);
        else if(compareResult < 0) node.left = add(node.left, key, value, node);
        else{
            node.value = value;
        }
        return node;
    }

    public void add(Key key, Value value) {
        root = add(root, key, value, root);
    }

    private Node delete(Node node, Key key){
        if(node == null) return null;
        int compareResult = key.compareTo(node.key);
        if(compareResult > 0){
            node.right = delete(node.right, key);
        }else if(compareResult < 0){
            node.left = delete(node.left, key);
        }else{
            if(node.right == null && node.left == null){
                return node = null;
            }else if(node.right == null){
                return node = node.left;
            }else if(node.left == null){
                return node = node.right;
            }else{
                if(node.right.left == null){
                    node.right.left = node.left;
                    node.right.father = node.father;
                    return node = node.right;
                }else{
                    Node res = min(node.right);
                    node.key = res.key;
                    node.value = res.value;
                    delete(node.right, node.key);
                    return node;
                }
            }
        }
        return node;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    public Key minKey(){
        return min(root).key;
    }

    public Key maxKey(){
        return max(root).key;
    }

    private Node min(Node node){
        if(node.left == null) return node;
        return min(node.left);
    }

    private Node max(Node node){
        if(node.right == null) return node;
        return min(node.right);
    }

    private Value get(Node node, Key key){
        if(node == null) return null;
        int compareResult = key.compareTo(node.key);
        if(compareResult == 0){
            return node.value;
        }else if(compareResult > 0){
            return get(node.right, key);
        }else{
            return get(node.left, key);
        }
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private void print(Node node, int level) {
        if (node != null) {
            print(node.right,level+1);
            for (int i=0;i<level;i++) {
                System.out.print("\t");
            }
            System.out.println(node.key + "->" + node.value);
            print(node.left,level+1);
        }
    }

    public void print() {
        print(root,0);
    }

}

public class Hello_World {
    public static void main(String[] args) {
        BST<Integer, String> tree = new BST<>();
        tree.add(10, "Test1");
        tree.add(12, "Test2");
        tree.add(1, "Test3");
        tree.add(5, "Test4");
        tree.add(6, "Test5");
        tree.add(3, "Test5");
        tree.print();
        tree.delete(5);
        tree.print();
        System.out.println(tree.get(1));
        System.out.println(tree.minKey());
        System.out.println(tree.maxKey());
        System.out.println(tree.get(3));
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import java.security.Key;

/**

* Created by green on 26.11.15.

class BST <Key extends Comparable<Key>, Value> {

private class Node {

Key key;

Value value;

Node left, right, father;

public Node (Key key, Value value) {

this.key = key;

this.value = value;

this.left = this.right = null;

this.father = null;

}

public Node (Key key, Value value, Node father) {

this.key = key;

this.value = value;

this.left = this.right = null;

this.father = father;

}

private Node root;

private Node add (Node node,Key key, Value value, Node father){

if (node == null){

Node newnode = new Node(key,value, father);

return newnode;

}

int compareResult = key.compareTo(node.key);

if (compareResult > 0) node.right = add(node.right, key, value, node);

else if(compareResult < 0) node.left = add(node.left, key, value, node);

else{

node.value = value;

}

return node;

}

public void add(Key key, Value value) {

root = add(root, key, value, root);

}

private Node delete(Node node, Key key){

if(node == null) return null;

int compareResult = key.compareTo(node.key);

if(compareResult > 0){

node.right = delete(node.right, key);

}else if(compareResult < 0){

node.left = delete(node.left, key);

}else{

if(node.right == null && node.left == null){

return node = null;

}else if(node.right == null){

return node = node.left;

}else if(node.left == null){

return node = node.right;

}else{

if(node.right.left == null){

node.right.left = node.left;

node.right.father = node.father;

return node = node.right;

}else{

Node res = min(node.right);

node.key = res.key;

node.value = res.value;

delete(node.right, node.key);

return node;

}

return node;

}

public void delete(Key key) {

root = delete(root, key);

}

public Key minKey(){

return min(root).key;

}

public Key maxKey(){

return max(root).key;

}

private Node min(Node node){

if(node.left == null) return node;

return min(node.left);

}

private Node max(Node node){

if(node.right == null) return node;

return min(node.right);

}

private Value get(Node node, Key key){

if(node == null) return null;

int compareResult = key.compareTo(node.key);

if(compareResult == 0){

return node.value;

}else if(compareResult > 0){

return get(node.right, key);

}else{

return get(node.left, key);

}

public Value get(Key key) {

return get(root, key);

}

private void print(Node node, int level) {

if (node != null) {

print(node.right,level+1);

for (int i=0;i<level;i++) {

System.out.print("\t");

}

System.out.println(node.key + "->" + node.value);

print(node.left,level+1);

}

public void print() {

print(root,0);

}

public class Hello_World {

public static void main(String[] args) {

BST<Integer, String> tree = new BST<>();

tree.add(10, "Test1");

tree.add(12, "Test2");

tree.add(1, "Test3");

tree.add(5, "Test4");

tree.add(6, "Test5");

tree.add(3, "Test5");

tree.print();

tree.delete(5);

tree.print();

System.out.println(tree.get(1));

System.out.println(tree.minKey());

System.out.println(tree.maxKey());

System.out.println(tree.get(3));

}

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Category Archives: 8. Структуры данных

soundEx algorithm

Немного о фонетических алгоритмах

soundEx

Пример:

Реализация:

Пример:

Контрольная работа. Timus 2002

2002. Тестовое задание

Условие

Исходные данные

Результат

Ограничения

Код

Решение

Описание функций

main

getRequest

Query

Request

Login

Logout

Timus 2002

BinarySearchTree

Обратная польская нотация

Код программы

Segmented Array

Двоичное дерево поиска

Задача

Решение

Операция вставки

Операция удаления

Код

Java Collections Framework: Map. Частотный словарь.

Задача 1:

Задача 2:

BigSegmentedArray by Tolia

Binary Tree Search