Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Zamira Galyautdinova B-01 z.galyautdinova@innopolis.university
- */
- import java.text.SimpleDateFormat;
- import java.util.ArrayList;
- import java.util.Comparator;
- import java.util.List;
- import java.util.Scanner;
- public class Programm {
- public static void main(String[] args) {
- SolveRangeQueries();
- }
- /**
- * Class that describe the date
- *
- * @param string
- * @return
- */
- static Date_ ParseToMyDate(String string) {
- int year = Integer.parseInt(string.substring(0, 4));
- int month = Integer.parseInt(string.substring(5, 7));
- int day = Integer.parseInt(string.substring(8, 10));
- Date_ date = new Date_(year, month, day);
- return date;
- }
- /**
- * Class that solve Task B
- */
- static void SolveRangeQueries() {
- BTree<Date_, Integer> tree = new BTree<>(80);
- Integer number;
- SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
- //Read Data
- try (Scanner in = new Scanner(System.in)) {
- number = Integer.parseInt(in.next());
- for (int i = 0; i < number; i++) {
- String firstWord;
- String command;
- String dateString;
- String dateFromString;
- String dateToString;
- Integer amount;
- firstWord = in.next();
- if (firstWord.equals("REPORT")) {
- command = in.next();
- dateFromString = in.next();
- command = in.next();
- dateToString = in.next();
- List<Integer> answerList = tree.lookupRange(ParseToMyDate(dateFromString), ParseToMyDate(dateToString));
- // does not have operations at all
- if (answerList == null)
- System.out.println(0);
- // does not have operations at this period
- else if (answerList.size() == 0)
- System.out.println(0);
- else {
- Integer answer = 0;
- for (int k = 0; k < answerList.size(); k++) {
- answer += answerList.get(k);
- }
- System.out.println(answer);
- }
- } else {
- dateString = firstWord;
- command = in.next();
- amount = Integer.parseInt(in.next());
- if (command.equals("DEPOSIT"))
- tree.add(ParseToMyDate(dateString), amount);
- else if (command.equals("WITHDRAW"))
- tree.add(ParseToMyDate(dateString), -amount);
- }
- }
- }
- }
- }
- class Date_ implements Comparable<Date_> {
- public int year;
- public int month;
- public int day;
- public Date_(int y, int m, int d) {
- this.year = y;
- this.month = m;
- this.day = d;
- }
- @Override
- public int compareTo(Date_ 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 Comparable<V>> implements RangeMap<K, V> {
- private BTreeNode<K, V> root = null;
- public final int B;
- private int size = 0;
- /**
- * Elements of three
- * @param <K>
- * @param <V>
- */
- static class BTreeNode<K extends Comparable<K>, V extends Comparable<V>> {
- private final BTree<K, V> tree;
- private final int B;
- private BTreeNode<K, V> parent;
- //nodes inside B-tree Node
- private final List<Pair<K, V>> nodes;
- private final List<BTreeNode<K, V>> children;
- public BTreeNode(BTreeNode<K, V> parent, BTree<K, V> tree) {
- this.tree = tree;
- this.B = tree.B;
- this.parent = parent;
- this.nodes = new ArrayList<>();
- this.children = new ArrayList<>();
- }
- /** recursively go deep and calculate number of elements
- *
- * @return
- */
- public int size() {
- int sum = nodes.size();
- if (children.size() != 0)
- for (BTreeNode<K, V> node : children)
- sum += node.size();
- return sum;
- }
- /**
- * add new key trying to find appropriate place
- * @param newKey
- * @param newValue
- */
- public void addKey(K newKey, V newValue) {
- Boolean is_already_added = false;
- if (children.size() == 0) {
- this.nodes.add(new Pair<>(newKey, newValue));
- nodes.sort(Comparator.comparing(Pair::getKey));
- if (this.nodes.size() == B)
- split();
- is_already_added = true;
- } else {
- //We make decision to which we will add
- //Most left node
- if (nodes.get(0).getKey().compareTo(newKey) >= 0 && !is_already_added) {
- is_already_added = true;
- children.get(0).addKey(newKey, newValue);
- } else if (nodes.size() > 0) {
- //Most right node
- if (nodes.get(nodes.size() - 1).getKey().compareTo(newKey) < 0 && !is_already_added) {
- children.get(nodes.size()).addKey(newKey, newValue);
- is_already_added = true;
- }
- }
- //nodes.size() <= B-1
- //Consider children between nodes (always looking to child by left side of node)
- for (int i = 1; i < nodes.size() && !is_already_added; i++) {
- if (nodes.get(i - 1).getKey().compareTo(newKey) < 0 && nodes.get(i).getKey().compareTo(newKey) >= 0) {
- children.get(i).addKey(newKey, newValue);
- is_already_added = true;
- }
- }
- }
- }
- /**
- * As we always add new node without checking size, we need split to large B tree Node
- */
- private void split() {
- if (nodes.size() == B) {
- int index = B % 2 == 0 ? B / 2 - 1 : B / 2;
- Pair<K, V> middleNod = nodes.get(index);
- BTreeNode<K, V> leftNode = new BTreeNode<>(parent, tree);
- //we remove the notes to the left of the pivot and add them as a group to the children parents
- for (int i = 0; i < index; i++) {
- //rewrite nodes
- leftNode.nodes.add(nodes.get(0));
- nodes.remove(0);
- }
- ///rewrite root root
- if (parent == null) {
- BTreeNode<K, V> newParent = new BTreeNode<>(null, tree);
- parent = newParent;
- parent.children.add(leftNode);
- parent.children.add(this);
- tree.root = newParent;
- leftNode.parent = newParent;
- } else {
- //rewrite parent for leftNode
- parent.children.add(parent.children.indexOf(this), leftNode);
- // pivot has become first
- }
- // rewrite children to leftNode
- if (children.size() != 0) {
- for (int i = 0; i <= index; i++) {
- //rewrite children
- leftNode.children.add(children.get(0));
- children.get(0).parent = leftNode;
- children.remove(0);
- }
- }
- parent.nodes.add(middleNod);
- parent.nodes.sort(Comparator.comparing(Pair::getKey));
- //delete middle node
- nodes.remove(0);
- parent.split();
- }
- }
- /**
- * finds element with given key
- * @param key
- * @return
- */
- 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;
- }
- //Consider children between nodes (always looking to child by left side of node)
- 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));
- /// these nodes CAN contain keys in range
- else {
- for (int i = 0; i < nodes.size(); i++) {
- // go to left
- if (nodes.get(i).getKey().compareTo(left) >= 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.addAll(children.get(nodes.size()).lookupRange(left, right));
- }
- }
- } else {
- // add to list nodes without checking their children
- 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 root.size();
- }
- @Override
- public boolean isEmpty() {
- return size() == 0;
- }
- @Override
- public void add(K key, V value) {
- size++;
- if (root == null)
- root = new BTreeNode<>(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);
- }
- /**
- *
- * @param from the left border of the interval
- * @param to the right border of the interval
- * @return list of elements which keys belong to the interval
- */
- @Override
- public List<V> lookupRange(K from, K to) {
- if (root == null)
- return null;
- // start with root element
- return root.lookupRange(from, to);
- }
- @Override
- public Object remove(K key) {
- return null;
- }
- }
- /**
- * Library class
- *
- * @param <K>
- * @param <V>
- */
- 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;
- }
- }
- /**
- * Class that help to debug code
- */
- class Test {
- /** add many the same elements
- *
- * @param n
- */
- static void t1(int n) {
- BTree<Integer, Integer> tree = new BTree<>(4);
- for (int i = 0; i < n; i++)
- tree.add(1, 1);
- List<Integer> list = tree.lookupRange(1, 1);
- int sum = 0;
- for (int i = 0; i < list.size(); i++)
- sum += list.get(i);
- if (sum != n)
- System.out.println(sum + " " + n);
- }
- /**
- * add random numbers to three and check number of "1"
- * @param n
- */
- static void t2(int n) {
- BTree<Integer, Integer> tree = new BTree<>(13);
- List<Integer> listK = new ArrayList<>();
- int i = 0;
- for (i = 0; i < n; i++) {
- int k = i % 1787 + (i + 78) % 13;
- try {
- tree.add(k, k);
- listK.add(k);
- } catch (Exception e) {
- System.out.println(i + " " + k);
- }
- }
- List<Integer> list = tree.lookupRange(1, 1);
- int sum = 0;
- for (i = 0; i < list.size(); i++)
- sum += list.get(i);
- if (sum != n)
- System.out.println(sum + " " + n);
- }
- /**
- * add many elements with the same key but in different order
- * @param n
- */
- static void t3(int n) {
- BTree<Integer, Integer> tree = new BTree<>(3);
- List<Integer> listK = new ArrayList<>();
- int i = 0;
- for (i = 0; i < n; i++) {
- int k = i % 17 + (i + 78) % 13;
- if (i == 37)
- System.out.println(k);
- if (k % 3 == 0) {
- // System.out.println(k);
- listK.add(k);
- tree.add(k, 1);
- } else
- tree.add(k, 0);
- if (tree.size() != (i + 1))
- System.out.println(tree.size() + " размеееееееер " + (i + 1));
- }
- List<Integer> list = tree.lookupRange(-100, 1000000);
- int sum = 0;
- for (i = 0; i < list.size(); i++)
- sum += list.get(i);
- System.out.println(sum + " " + listK.size());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement