Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.text.ParseException;
- import java.text.SimpleDateFormat;
- import java.util.*;
- public class Program {
- public static void main(String[] args) {
- BTree<Integer, Integer> tree = new BTree<>(3);
- int n = 10976, i = 0;
- for ( i = 0; i < n; i++) {
- int k = i % 17 + (i+78)%3;
- try {
- tree.add(k, i);
- }
- catch (Exception e)
- {
- System.out.println(i + " " +k);;
- }
- }
- /* for (int i = 0; i < n; i++) {
- if(i % 213 == 0)
- for (int j = i; j < n; j++) {
- if (j % 25 == 0) {
- List<Integer> list = tree.lookupRange(i, j);
- for (int k = i; k <= j; k++) {
- if (!list.contains(k))
- System.out.println("Program has failed in range [" + i + "," + j + "]\n");
- }
- }
- }
- }*/
- }
- void SolveRangeQueries ()
- { BTree<Date, Integer> tree = new BTree<>(48);
- Integer number;
- SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
- //tree.add(new Date(2000-12-01), 1);
- try (Scanner in = new Scanner(System.in)) {
- number = Integer.parseInt(in.next());
- for (int i = 0; i < number; i++) {
- String firstWord;
- String command;
- Date date;
- Date dateFrom;
- Date dateTo;
- Integer amount;
- firstWord = in.next();
- if (firstWord.equals("REPORT")) {
- command = in.next();
- dateFrom = dateFormat.parse(in.next());
- command = in.next();
- dateTo = dateFormat.parse(in.next());
- List<Integer> list = tree.lookupRange(dateFrom, dateTo);
- if (list == null)
- System.out.println(0);
- else if (list.size() == 0)
- System.out.println(0);
- else {
- Integer answer = 0;
- for (int k = 0; k < list.size(); k++) {
- answer += list.get(k);
- }
- System.out.println(answer);
- }
- } else {
- date = dateFormat.parse(firstWord);
- command = in.next();
- amount = Integer.parseInt(in.next());
- if (command.equals("DEPOSIT"))
- tree.add(date, amount);
- else if (command.equals("WITHDRAW"))
- tree.add(date, -amount);
- }
- }
- } catch (ParseException e) {
- e.printStackTrace();
- }
- }
- }
- class MyDate implements Comparable<MyDate> {
- public int year;
- public int month;
- public int day;
- public MyDate(int y, int m, int d) {
- this.year = y;
- this.month = m;
- this.day = d;
- }
- @Override
- public int compareTo(MyDate o) {
- if (this.year == o.year)
- {
- if (this.month == o.month)
- {
- if (this.day == o.day)
- return 0;
- else
- return this.day - o.day;
- }
- else
- return this.month - o.month;
- }
- else
- return this.year - o.year;
- }
- }
- interface RangeMap<K, V> {
- int size();
- boolean isEmpty();
- void add(K key, V value); // insert new item into the map
- boolean contains(K key); // check if a key is present
- V lookup(K key); // lookup a value by the key
- List<V> lookupRange(K from, K to); // lookup values for a range of keys
- // optional: remove an item from a map (+1% extra credit)
- Object remove(K key);
- }
- class BTree<K extends Comparable<K>, V extends Number> implements RangeMap<K, V> {
- private BNode<K, V> root = null;
- public final int B;
- private int size = 0;
- static class BNode<K extends Comparable<K>, V extends Number> {
- private final BTree<K, V> tree;
- private final int B;
- private BNode<K, V> parent;
- private final List<Pair<K, V>> nodes;
- private final List<BNode<K, V>> children;
- public BNode(BNode<K, V> parent, BTree<K, V> tree) {
- this.tree = tree;
- this.B = tree.B;
- this.parent = parent;
- this.nodes = new ArrayList<>(B);
- this.children = new ArrayList<>(B + 1);
- }
- public void addKey(K newKey, V newValue) {
- if (children.size() == 0) {
- add(newKey, newValue);
- } else {
- //Most left node
- if (nodes.get(0).getKey().compareTo(newKey) >= 0) {
- children.get(0).addKey(newKey, newValue);
- }
- if (nodes.size() > 0) {
- //Most right node
- if (nodes.get(nodes.size() - 1).getKey().compareTo(newKey) < 0) {
- children.get(children.size() - 1).addKey(newKey, newValue);
- }
- }
- //nodes.size() <= B-1
- for (int i = 1; i < nodes.size(); i++) {
- if (nodes.get(i - 1).getKey().compareTo(newKey) >= 0 && nodes.get(i).getKey().compareTo(newKey) < 0) {
- children.get(i).addKey(newKey, newValue);
- }
- }
- }
- }
- private void add(K newKey, V newValue) {
- this.nodes.add(new Pair<>(newKey, newValue));
- nodes.sort(Comparator.comparing(Pair::getKey));
- if (this.nodes.size() == B)
- split();
- }
- private void split() {
- if (nodes.size() == B) {
- int index = B % 2 == 0 ? B / 2 - 1 : B / 2;
- Pair<K, V> medianNode = nodes.get(index);
- BNode<K, V> leftNode = new BNode<>(parent, tree);
- /// удаляем ноды слева от пивота и добавляем их группой к детям родителя
- for (int i = 0; i < index; i++) {
- //перезаписываем ноды
- leftNode.nodes.add(nodes.get(0));
- nodes.remove(0);
- }
- // перезаписываем детей в leftNode
- if (children.size() != 0) {
- for (int i = 0; i <= index; i++) {
- //перезаписываем детей
- children.get(0).parent = leftNode;
- leftNode.children.add(children.get(0));
- children.remove(0);
- }
- }
- ///Нужно проверить куда он смещает элемент, который был на этом индекс
- if (parent == null) {
- BNode<K, V> newParent = new BNode<>(null, tree);
- parent = newParent;
- leftNode.parent = newParent;
- parent.children.add(leftNode);
- parent.children.add(this);
- tree.root = newParent;
- }
- else
- {
- //перезаписываем родителю leftNode
- parent.children.add(parent.children.indexOf(this), leftNode);
- }
- parent.nodes.add(medianNode);
- // pivot стал нулевым
- nodes.remove(0);
- parent.nodes.sort(Comparator.comparing(Pair::getKey));
- parent.split();
- }
- }
- public V lookup(K key) {
- int index = -1;
- for (int i = 0; i < nodes.size(); i++) {
- if (nodes.get(i).getKey() == key)
- index = i;
- }
- V returnValue = null;
- if (index == -1) {
- if (children.size() > 0) {
- V value;
- if (nodes.get(0).getKey().compareTo(key) >= 0) {
- value = children.get(0).lookup(key);
- if (value != null)
- returnValue = value;
- }
- //Most right node
- if (nodes.get(nodes.size() - 1).getKey().compareTo(key) < 0) {
- value = children.get(children.size() - 1).lookup(key);
- if (value != null)
- returnValue = value;
- }
- //nodes.size() <= B-1
- for (int i = 1; i < nodes.size(); i++) {
- if (nodes.get(i - 1).getKey().compareTo(key) >= 0 && nodes.get(i).getKey().compareTo(key) < 0) {
- value = children.get(i).lookup(key);
- if (value != null)
- returnValue = value;
- }
- }
- }
- } else
- returnValue = nodes.get(index).getValue();
- return returnValue;
- }
- public List<V> lookupRange(K left, K right)
- {
- List<V> answer = new ArrayList<V>();
- if (children.size() != 0)
- {
- /// these nodes do NOT contain keys in range
- //most left case
- if (nodes.get(0).getKey().compareTo(right) > 0)
- answer.addAll(children.get(0).lookupRange(left, right));
- // most right case
- else if (nodes.get(nodes.size() - 1).getKey().compareTo(left) < 0)
- answer.addAll(children.get(children.size() - 1).lookupRange(left, right));
- ///
- else
- {
- /// these nodes contain keys in range
- /*if (nodes.get(0).getKey().compareTo(left) >= 0) {
- answer.addAll(children.get(0).lookupRange(left, right));
- if (nodes.get(0).getKey().compareTo(right) <= 0)
- answer.add(nodes.get(0).getValue());
- }*/
- for (int i = 0; i < nodes.size(); i++)
- {
- // go to left
- if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i).getKey().compareTo(right) <= 0)
- {
- answer.addAll(children.get(i).lookupRange(left, right));
- if (nodes.get(i).getKey().compareTo(right) <= 0)
- answer.add(nodes.get(i).getValue());
- }
- }
- //most right
- if ((nodes.get(nodes.size() - 1).getKey().compareTo(right) < 0))
- {
- // answer.add(nodes.get(nodes.size() - 1).getValue());
- answer.addAll(children.get(nodes.size()).lookupRange(left, right));
- }
- }
- }
- else
- {
- // if (nodes.get(0).getKey().compareTo(right) < 0 && nodes.get(0).getKey().compareTo(left) > 0)
- // добавляем в лист элементы нода без проверки детей
- for (int i = 0; i < nodes.size(); i++)
- {
- if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i).getKey().compareTo(right) <= 0)
- answer.add(nodes.get(i).getValue());
- }
- }
- return answer;
- }
- }
- public BTree(int B) {
- this.B = B;
- }
- @Override
- public int size() {
- return size;
- }
- @Override
- public boolean isEmpty() {
- return size() == 0;
- }
- @Override
- public void add(K key, V value) {
- size++;
- if (root == null)
- root = new BNode<>(null, this);
- root.addKey(key, value);
- }
- @Override
- public boolean contains(K key) {
- return lookup(key) != null;
- }
- @Override
- public V lookup(K key) {
- return root.lookup(key);
- }
- @Override
- public List<V> lookupRange(K from, K to) {
- if (root == null)
- return null;
- return root.lookupRange(from, to);
- }
- @Override
- public Object remove(K key) {
- return null;
- }
- }
- class Pair<K, V> {
- private K key;
- public K getKey() {
- return key;
- }
- private V value;
- public V getValue() {
- return value;
- }
- public Pair(K key, V value) {
- this.key = key;
- this.value = value;
- }
- @Override
- public String toString() {
- return key + "=" + value;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement