Advertisement
habur331

Untitled

Apr 24th, 2022
1,316
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Zamira Galyautdinova B-01 z.galyautdinova@innopolis.university
  3.  */
  4.  
  5. import java.text.SimpleDateFormat;
  6. import java.util.ArrayList;
  7. import java.util.Comparator;
  8. import java.util.List;
  9. import java.util.Scanner;
  10.  
  11. public class Programm {
  12.  
  13.     public static void main(String[] args) {
  14.         SolveRangeQueries();
  15.     }
  16.  
  17.     /**
  18.      * Class that describe the date
  19.      *
  20.      * @param string
  21.      * @return
  22.      */
  23.     static Date_ ParseToMyDate(String string) {
  24.         int year = Integer.parseInt(string.substring(0, 4));
  25.         int month = Integer.parseInt(string.substring(5, 7));
  26.         int day = Integer.parseInt(string.substring(8, 10));
  27.         Date_ date = new Date_(year, month, day);
  28.         return date;
  29.     }
  30.  
  31.     /**
  32.      * Class that solve Task B
  33.      */
  34.     static void SolveRangeQueries() {
  35.         BTree<Date_, Integer> tree = new BTree<>(80);
  36.         Integer number;
  37.         SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
  38.  
  39.         //Read Data
  40.         try (Scanner in = new Scanner(System.in)) {
  41.             number = Integer.parseInt(in.next());
  42.  
  43.             for (int i = 0; i < number; i++) {
  44.                 String firstWord;
  45.                 String command;
  46.                 String dateString;
  47.                 String dateFromString;
  48.                 String dateToString;
  49.                 Integer amount;
  50.  
  51.                 firstWord = in.next();
  52.                 if (firstWord.equals("REPORT")) {
  53.                     command = in.next();
  54.                     dateFromString = in.next();
  55.                     command = in.next();
  56.                     dateToString = in.next();
  57.  
  58.                     List<Integer> answerList = tree.lookupRange(ParseToMyDate(dateFromString), ParseToMyDate(dateToString));
  59.  
  60.                     // does not have operations at all
  61.                     if (answerList == null)
  62.                         System.out.println(0);
  63.  
  64.                     // does not have operations at this period
  65.                     else if (answerList.size() == 0)
  66.                         System.out.println(0);
  67.  
  68.                     else {
  69.                         Integer answer = 0;
  70.                         for (int k = 0; k < answerList.size(); k++) {
  71.                             answer += answerList.get(k);
  72.                         }
  73.                         System.out.println(answer);
  74.                     }
  75.                 } else {
  76.                     dateString = firstWord;
  77.                     command = in.next();
  78.                     amount = Integer.parseInt(in.next());
  79.  
  80.                     if (command.equals("DEPOSIT"))
  81.                         tree.add(ParseToMyDate(dateString), amount);
  82.  
  83.                     else if (command.equals("WITHDRAW"))
  84.                         tree.add(ParseToMyDate(dateString), -amount);
  85.                 }
  86.             }
  87.         }
  88.     }
  89. }
  90.  
  91. class Date_ implements Comparable<Date_> {
  92.     public int year;
  93.     public int month;
  94.     public int day;
  95.  
  96.     public Date_(int y, int m, int d) {
  97.         this.year = y;
  98.         this.month = m;
  99.         this.day = d;
  100.     }
  101.  
  102.     @Override
  103.     public int compareTo(Date_ o) {
  104.         if (this.year == o.year) {
  105.             if (this.month == o.month) {
  106.                 if (this.day == o.day)
  107.                     return 0;
  108.                 else
  109.                     return this.day - o.day;
  110.             } else
  111.                 return this.month - o.month;
  112.         } else
  113.             return this.year - o.year;
  114.  
  115.     }
  116. }
  117.  
  118. interface RangeMap<K, V> {
  119.     int size();
  120.  
  121.     boolean isEmpty();
  122.  
  123.     void add(K key, V value); // insert new item into the map
  124.  
  125.     boolean contains(K key); // check if a key is present
  126.  
  127.     V lookup(K key); // lookup a value by the key
  128.  
  129.     List<V> lookupRange(K from, K to); // lookup values for a range of keys
  130.  
  131.     // optional: remove an item from a map (+1% extra credit)
  132.     Object remove(K key);
  133. }
  134.  
  135. class BTree<K extends Comparable<K>, V extends Comparable<V>> implements RangeMap<K, V> {
  136.     private BTreeNode<K, V> root = null;
  137.  
  138.     public final int B;
  139.     private int size = 0;
  140.  
  141.     /**
  142.      * Elements of three
  143.      * @param <K>
  144.      * @param <V>
  145.      */
  146.     static class BTreeNode<K extends Comparable<K>, V extends Comparable<V>> {
  147.         private final BTree<K, V> tree;
  148.         private final int B;
  149.         private BTreeNode<K, V> parent;
  150.         //nodes inside B-tree Node
  151.         private final List<Pair<K, V>> nodes;
  152.         private final List<BTreeNode<K, V>> children;
  153.  
  154.         public BTreeNode(BTreeNode<K, V> parent, BTree<K, V> tree) {
  155.             this.tree = tree;
  156.             this.B = tree.B;
  157.             this.parent = parent;
  158.             this.nodes = new ArrayList<>();
  159.             this.children = new ArrayList<>();
  160.         }
  161.  
  162.         /** recursively go deep and calculate number of elements
  163.          *
  164.          * @return
  165.          */
  166.         public int size() {
  167.             int sum = nodes.size();
  168.  
  169.             if (children.size() != 0)
  170.                 for (BTreeNode<K, V> node : children)
  171.                     sum += node.size();
  172.  
  173.             return sum;
  174.         }
  175.  
  176.         /**
  177.          * add new key trying to find appropriate place
  178.          * @param newKey
  179.          * @param newValue
  180.          */
  181.         public void addKey(K newKey, V newValue) {
  182.             Boolean is_already_added = false;
  183.             if (children.size() == 0) {
  184.                 this.nodes.add(new Pair<>(newKey, newValue));
  185.                 nodes.sort(Comparator.comparing(Pair::getKey));
  186.  
  187.                 if (this.nodes.size() == B)
  188.                     split();
  189.                 is_already_added = true;
  190.             } else {
  191.                 //We make decision to which we will add
  192.  
  193.                 //Most left node
  194.                 if (nodes.get(0).getKey().compareTo(newKey) >= 0 && !is_already_added) {
  195.                     is_already_added = true;
  196.                     children.get(0).addKey(newKey, newValue);
  197.                 } else if (nodes.size() > 0) {
  198.                     //Most right node
  199.                     if (nodes.get(nodes.size() - 1).getKey().compareTo(newKey) < 0 && !is_already_added) {
  200.                         children.get(nodes.size()).addKey(newKey, newValue);
  201.                         is_already_added = true;
  202.                     }
  203.                 }
  204.  
  205.                 //nodes.size() <= B-1
  206.                 //Consider children between nodes (always looking to child by left side of node)
  207.                 for (int i = 1; i < nodes.size() && !is_already_added; i++) {
  208.                     if (nodes.get(i - 1).getKey().compareTo(newKey) < 0 && nodes.get(i).getKey().compareTo(newKey) >= 0) {
  209.                         children.get(i).addKey(newKey, newValue);
  210.                         is_already_added = true;
  211.                     }
  212.                 }
  213.             }
  214.         }
  215.  
  216.         /**
  217.          * As we always add new node without checking size, we need split to large B tree Node
  218.          */
  219.         private void split() {
  220.             if (nodes.size() == B) {
  221.                 int index = B % 2 == 0 ? B / 2 - 1 : B / 2;
  222.                 Pair<K, V> middleNod = nodes.get(index);
  223.  
  224.                 BTreeNode<K, V> leftNode = new BTreeNode<>(parent, tree);
  225.                 //we remove the notes to the left of the pivot and add them as a group to the children parents
  226.                 for (int i = 0; i < index; i++) {
  227.                     //rewrite nodes
  228.                     leftNode.nodes.add(nodes.get(0));
  229.                     nodes.remove(0);
  230.                 }
  231.  
  232.                 ///rewrite root root
  233.                 if (parent == null) {
  234.                     BTreeNode<K, V> newParent = new BTreeNode<>(null, tree);
  235.                     parent = newParent;
  236.                     parent.children.add(leftNode);
  237.                     parent.children.add(this);
  238.                     tree.root = newParent;
  239.                     leftNode.parent = newParent;
  240.                 } else {
  241.                     //rewrite parent for leftNode
  242.                     parent.children.add(parent.children.indexOf(this), leftNode);
  243.                     // pivot has become first
  244.                 }
  245.  
  246.                 // rewrite children to leftNode
  247.                 if (children.size() != 0) {
  248.                     for (int i = 0; i <= index; i++) {
  249.                         //rewrite children
  250.                         leftNode.children.add(children.get(0));
  251.                         children.get(0).parent = leftNode;
  252.                         children.remove(0);
  253.                     }
  254.                 }
  255.                 parent.nodes.add(middleNod);
  256.                 parent.nodes.sort(Comparator.comparing(Pair::getKey));
  257.                 //delete middle node
  258.                 nodes.remove(0);
  259.                 parent.split();
  260.             }
  261.         }
  262.  
  263.         /**
  264.          * finds element with given key
  265.          * @param key
  266.          * @return
  267.          */
  268.         public V lookup(K key) {
  269.             int index = -1;
  270.             for (int i = 0; i < nodes.size(); i++) {
  271.                 if (nodes.get(i).getKey() == key)
  272.                     index = i;
  273.             }
  274.  
  275.             V returnValue = null;
  276.  
  277.             if (index == -1) {
  278.                 if (children.size() > 0) {
  279.                     V value;
  280.                     if (nodes.get(0).getKey().compareTo(key) >= 0) {
  281.                         value = children.get(0).lookup(key);
  282.                         if (value != null)
  283.                             returnValue = value;
  284.                     }
  285.  
  286.                     //Most right node
  287.                     if (nodes.get(nodes.size() - 1).getKey().compareTo(key) < 0) {
  288.                         value = children.get(children.size() - 1).lookup(key);
  289.                         if (value != null)
  290.                             returnValue = value;
  291.                     }
  292.  
  293.                     //Consider children between nodes (always looking to child by left side of node)
  294.                     for (int i = 1; i < nodes.size(); i++) {
  295.                         if (nodes.get(i - 1).getKey().compareTo(key) >= 0 && nodes.get(i).getKey().compareTo(key) < 0) {
  296.                             value = children.get(i).lookup(key);
  297.                             if (value != null)
  298.                                 returnValue = value;
  299.                         }
  300.                     }
  301.                 }
  302.             } else
  303.                 returnValue = nodes.get(index).getValue();
  304.  
  305.  
  306.             return returnValue;
  307.         }
  308.  
  309.         public List<V> lookupRange(K left, K right) {
  310.             List<V> answer = new ArrayList<V>();
  311.  
  312.             if (children.size() != 0) {
  313.                 /// these nodes do NOT contain keys in range
  314.                 //most left case
  315.                 if (nodes.get(0).getKey().compareTo(right) > 0)
  316.                     answer.addAll(children.get(0).lookupRange(left, right));
  317.                     // most right case
  318.                 else if (nodes.get(nodes.size() - 1).getKey().compareTo(left) < 0)
  319.                     answer.addAll(children.get(children.size() - 1).lookupRange(left, right));
  320.  
  321.                     /// these nodes CAN contain keys in range
  322.                 else {
  323.                     for (int i = 0; i < nodes.size(); i++) {
  324.                         // go to left
  325.                         if (nodes.get(i).getKey().compareTo(left) >= 0) {
  326.                             answer.addAll(children.get(i).lookupRange(left, right));
  327.                             if (nodes.get(i).getKey().compareTo(right) <= 0)
  328.                                 answer.add(nodes.get(i).getValue());
  329.                         }
  330.                     }
  331.                     //most right
  332.                     if ((nodes.get(nodes.size() - 1).getKey().compareTo(right) <= 0)) {
  333.                         answer.addAll(children.get(nodes.size()).lookupRange(left, right));
  334.                     }
  335.                 }
  336.             } else {
  337.                 // add to list nodes without checking their children
  338.                 for (int i = 0; i < nodes.size(); i++) {
  339.                     if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i).getKey().compareTo(right) <= 0)
  340.                         answer.add(nodes.get(i).getValue());
  341.                 }
  342.             }
  343.             return answer;
  344.         }
  345.     }
  346.  
  347.     public BTree(int B) {
  348.         this.B = B;
  349.     }
  350.  
  351.     @Override
  352.     public int size() {
  353.         return root.size();
  354.     }
  355.  
  356.     @Override
  357.     public boolean isEmpty() {
  358.         return size() == 0;
  359.     }
  360.  
  361.     @Override
  362.     public void add(K key, V value) {
  363.         size++;
  364.  
  365.         if (root == null)
  366.             root = new BTreeNode<>(null, this);
  367.  
  368.         root.addKey(key, value);
  369.     }
  370.  
  371.     @Override
  372.     public boolean contains(K key) {
  373.         return lookup(key) != null;
  374.     }
  375.  
  376.     @Override
  377.     public V lookup(K key) {
  378.         return root.lookup(key);
  379.     }
  380.  
  381.     /**
  382.      *
  383.      * @param from the left border of the interval
  384.      * @param to the right border of the interval
  385.      * @return list of elements which keys belong to the interval
  386.      */
  387.     @Override
  388.     public List<V> lookupRange(K from, K to) {
  389.         if (root == null)
  390.             return null;
  391.         // start with root element
  392.         return root.lookupRange(from, to);
  393.     }
  394.  
  395.     @Override
  396.     public Object remove(K key) {
  397.         return null;
  398.     }
  399. }
  400.  
  401. /**
  402.  * Library class
  403.  *
  404.  * @param <K>
  405.  * @param <V>
  406.  */
  407. class Pair<K, V> {
  408.     private K key;
  409.  
  410.     public K getKey() {
  411.         return key;
  412.     }
  413.  
  414.     private V value;
  415.  
  416.     public V getValue() {
  417.         return value;
  418.     }
  419.  
  420.     public Pair(K key, V value) {
  421.         this.key = key;
  422.         this.value = value;
  423.     }
  424.  
  425.     @Override
  426.     public String toString() {
  427.         return key + "=" + value;
  428.     }
  429. }
  430.  
  431. /**
  432.  * Class that help to debug code
  433.  */
  434. class Test {
  435.     /** add many the same elements
  436.      *
  437.      * @param n
  438.      */
  439.     static void t1(int n) {
  440.         BTree<Integer, Integer> tree = new BTree<>(4);
  441.         for (int i = 0; i < n; i++)
  442.             tree.add(1, 1);
  443.  
  444.         List<Integer> list = tree.lookupRange(1, 1);
  445.         int sum = 0;
  446.         for (int i = 0; i < list.size(); i++)
  447.             sum += list.get(i);
  448.  
  449.         if (sum != n)
  450.             System.out.println(sum + " " + n);
  451.     }
  452.  
  453.     /**
  454.      * add random numbers to three and check number of "1"
  455.      * @param n
  456.      */
  457.     static void t2(int n) {
  458.         BTree<Integer, Integer> tree = new BTree<>(13);
  459.         List<Integer> listK = new ArrayList<>();
  460.         int i = 0;
  461.         for (i = 0; i < n; i++) {
  462.             int k = i % 1787 + (i + 78) % 13;
  463.             try {
  464.                 tree.add(k, k);
  465.                 listK.add(k);
  466.             } catch (Exception e) {
  467.                 System.out.println(i + " " + k);
  468.             }
  469.         }
  470.         List<Integer> list = tree.lookupRange(1, 1);
  471.         int sum = 0;
  472.         for (i = 0; i < list.size(); i++)
  473.             sum += list.get(i);
  474.  
  475.         if (sum != n)
  476.             System.out.println(sum + " " + n);
  477.  
  478.     }
  479.  
  480.     /**
  481.      * add many elements with the same key but in different order
  482.      * @param n
  483.      */
  484.     static void t3(int n) {
  485.         BTree<Integer, Integer> tree = new BTree<>(3);
  486.         List<Integer> listK = new ArrayList<>();
  487.         int i = 0;
  488.         for (i = 0; i < n; i++) {
  489.             int k = i % 17 + (i + 78) % 13;
  490.             if (i == 37)
  491.                 System.out.println(k);
  492.             if (k % 3 == 0) {
  493.                 //           System.out.println(k);
  494.                 listK.add(k);
  495.                 tree.add(k, 1);
  496.             } else
  497.                 tree.add(k, 0);
  498.             if (tree.size() != (i + 1))
  499.                 System.out.println(tree.size() + " размеееееееер " + (i + 1));
  500.         }
  501.  
  502.         List<Integer> list = tree.lookupRange(-100, 1000000);
  503.         int sum = 0;
  504.         for (i = 0; i < list.size(); i++)
  505.             sum += list.get(i);
  506.  
  507.         System.out.println(sum + " " + listK.size());
  508.     }
  509. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement