Advertisement
habur331

Untitled

Apr 5th, 2022
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.23 KB | None | 0 0
  1. import java.text.ParseException;
  2. import java.text.SimpleDateFormat;
  3. import java.util.*;
  4.  
  5. public class Program {
  6.  
  7. public static void main(String[] args) {
  8.  
  9. BTree<Integer, Integer> tree = new BTree<>(3);
  10. int n = 10976, i = 0;
  11. for ( i = 0; i < n; i++) {
  12. int k = i % 17 + (i+78)%3;
  13. try {
  14. tree.add(k, i);
  15. }
  16. catch (Exception e)
  17. {
  18. System.out.println(i + " " +k);;
  19. }
  20. }
  21. /* for (int i = 0; i < n; i++) {
  22. if(i % 213 == 0)
  23. for (int j = i; j < n; j++) {
  24. if (j % 25 == 0) {
  25. List<Integer> list = tree.lookupRange(i, j);
  26. for (int k = i; k <= j; k++) {
  27. if (!list.contains(k))
  28. System.out.println("Program has failed in range [" + i + "," + j + "]\n");
  29. }
  30. }
  31. }
  32. }*/
  33.  
  34. }
  35.  
  36. void SolveRangeQueries ()
  37. { BTree<Date, Integer> tree = new BTree<>(48);
  38. Integer number;
  39. SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
  40.  
  41. //tree.add(new Date(2000-12-01), 1);
  42.  
  43. try (Scanner in = new Scanner(System.in)) {
  44. number = Integer.parseInt(in.next());
  45.  
  46. for (int i = 0; i < number; i++) {
  47. String firstWord;
  48. String command;
  49. Date date;
  50. Date dateFrom;
  51. Date dateTo;
  52. Integer amount;
  53.  
  54. firstWord = in.next();
  55. if (firstWord.equals("REPORT")) {
  56. command = in.next();
  57. dateFrom = dateFormat.parse(in.next());
  58. command = in.next();
  59. dateTo = dateFormat.parse(in.next());
  60.  
  61.  
  62. List<Integer> list = tree.lookupRange(dateFrom, dateTo);
  63.  
  64. if (list == null)
  65. System.out.println(0);
  66.  
  67. else if (list.size() == 0)
  68. System.out.println(0);
  69.  
  70. else {
  71. Integer answer = 0;
  72. for (int k = 0; k < list.size(); k++) {
  73. answer += list.get(k);
  74. }
  75. System.out.println(answer);
  76.  
  77. }
  78. } else {
  79. date = dateFormat.parse(firstWord);
  80. command = in.next();
  81. amount = Integer.parseInt(in.next());
  82.  
  83. if (command.equals("DEPOSIT"))
  84. tree.add(date, amount);
  85. else if (command.equals("WITHDRAW"))
  86.  
  87. tree.add(date, -amount);
  88. }
  89. }
  90. } catch (ParseException e) {
  91. e.printStackTrace();
  92. }
  93.  
  94.  
  95. }
  96. }
  97.  
  98.  
  99. class MyDate implements Comparable<MyDate> {
  100. public int year;
  101. public int month;
  102. public int day;
  103.  
  104. public MyDate(int y, int m, int d) {
  105. this.year = y;
  106. this.month = m;
  107. this.day = d;
  108. }
  109.  
  110. @Override
  111. public int compareTo(MyDate o) {
  112. if (this.year == o.year)
  113. {
  114. if (this.month == o.month)
  115. {
  116. if (this.day == o.day)
  117. return 0;
  118. else
  119. return this.day - o.day;
  120. }
  121. else
  122. return this.month - o.month;
  123. }
  124. else
  125. return this.year - o.year;
  126.  
  127. }
  128. }
  129.  
  130. interface RangeMap<K, V> {
  131. int size();
  132.  
  133. boolean isEmpty();
  134.  
  135. void add(K key, V value); // insert new item into the map
  136.  
  137. boolean contains(K key); // check if a key is present
  138.  
  139. V lookup(K key); // lookup a value by the key
  140.  
  141. List<V> lookupRange(K from, K to); // lookup values for a range of keys
  142.  
  143. // optional: remove an item from a map (+1% extra credit)
  144. Object remove(K key);
  145. }
  146.  
  147. class BTree<K extends Comparable<K>, V extends Number> implements RangeMap<K, V> {
  148. private BNode<K, V> root = null;
  149.  
  150. public final int B;
  151. private int size = 0;
  152.  
  153. static class BNode<K extends Comparable<K>, V extends Number> {
  154. private final BTree<K, V> tree;
  155. private final int B;
  156. private BNode<K, V> parent;
  157. private final List<Pair<K, V>> nodes;
  158. private final List<BNode<K, V>> children;
  159.  
  160. public BNode(BNode<K, V> parent, BTree<K, V> tree) {
  161. this.tree = tree;
  162. this.B = tree.B;
  163. this.parent = parent;
  164. this.nodes = new ArrayList<>(B);
  165. this.children = new ArrayList<>(B + 1);
  166. }
  167.  
  168. public void addKey(K newKey, V newValue) {
  169. if (children.size() == 0) {
  170. add(newKey, newValue);
  171. } else {
  172. //Most left node
  173. if (nodes.get(0).getKey().compareTo(newKey) >= 0) {
  174. children.get(0).addKey(newKey, newValue);
  175. }
  176.  
  177. if (nodes.size() > 0) {
  178. //Most right node
  179. if (nodes.get(nodes.size() - 1).getKey().compareTo(newKey) < 0) {
  180. children.get(children.size() - 1).addKey(newKey, newValue);
  181. }
  182. }
  183.  
  184.  
  185. //nodes.size() <= B-1
  186. for (int i = 1; i < nodes.size(); i++) {
  187. if (nodes.get(i - 1).getKey().compareTo(newKey) >= 0 && nodes.get(i).getKey().compareTo(newKey) < 0) {
  188. children.get(i).addKey(newKey, newValue);
  189. }
  190. }
  191. }
  192. }
  193.  
  194. private void add(K newKey, V newValue) {
  195. this.nodes.add(new Pair<>(newKey, newValue));
  196. nodes.sort(Comparator.comparing(Pair::getKey));
  197.  
  198. if (this.nodes.size() == B)
  199. split();
  200. }
  201.  
  202. private void split() {
  203. if (nodes.size() == B) {
  204. int index = B % 2 == 0 ? B / 2 - 1 : B / 2;
  205. Pair<K, V> medianNode = nodes.get(index);
  206.  
  207. BNode<K, V> leftNode = new BNode<>(parent, tree);
  208. /// удаляем ноды слева от пивота и добавляем их группой к детям родителя
  209. for (int i = 0; i < index; i++) {
  210. //перезаписываем ноды
  211. leftNode.nodes.add(nodes.get(0));
  212. nodes.remove(0);
  213. }
  214.  
  215. // перезаписываем детей в leftNode
  216. if (children.size() != 0) {
  217. for (int i = 0; i <= index; i++) {
  218. //перезаписываем детей
  219. children.get(0).parent = leftNode;
  220. leftNode.children.add(children.get(0));
  221. children.remove(0);
  222. }
  223. }
  224. ///Нужно проверить куда он смещает элемент, который был на этом индекс
  225. if (parent == null) {
  226. BNode<K, V> newParent = new BNode<>(null, tree);
  227. parent = newParent;
  228. leftNode.parent = newParent;
  229. parent.children.add(leftNode);
  230. parent.children.add(this);
  231. tree.root = newParent;
  232. }
  233. else
  234. {
  235. //перезаписываем родителю leftNode
  236. parent.children.add(parent.children.indexOf(this), leftNode);
  237. }
  238.  
  239. parent.nodes.add(medianNode);
  240.  
  241. // pivot стал нулевым
  242. nodes.remove(0);
  243. parent.nodes.sort(Comparator.comparing(Pair::getKey));
  244.  
  245. parent.split();
  246. }
  247. }
  248.  
  249. public V lookup(K key) {
  250. int index = -1;
  251. for (int i = 0; i < nodes.size(); i++) {
  252. if (nodes.get(i).getKey() == key)
  253. index = i;
  254. }
  255.  
  256. V returnValue = null;
  257.  
  258. if (index == -1) {
  259. if (children.size() > 0) {
  260. V value;
  261. if (nodes.get(0).getKey().compareTo(key) >= 0) {
  262. value = children.get(0).lookup(key);
  263. if (value != null)
  264. returnValue = value;
  265. }
  266.  
  267. //Most right node
  268. if (nodes.get(nodes.size() - 1).getKey().compareTo(key) < 0) {
  269. value = children.get(children.size() - 1).lookup(key);
  270. if (value != null)
  271. returnValue = value;
  272. }
  273.  
  274. //nodes.size() <= B-1
  275. for (int i = 1; i < nodes.size(); i++) {
  276. if (nodes.get(i - 1).getKey().compareTo(key) >= 0 && nodes.get(i).getKey().compareTo(key) < 0) {
  277. value = children.get(i).lookup(key);
  278. if (value != null)
  279. returnValue = value;
  280. }
  281. }
  282. }
  283. } else
  284. returnValue = nodes.get(index).getValue();
  285.  
  286.  
  287. return returnValue;
  288. }
  289.  
  290. public List<V> lookupRange(K left, K right)
  291. {
  292. List<V> answer = new ArrayList<V>();
  293.  
  294. if (children.size() != 0)
  295. {
  296. /// these nodes do NOT contain keys in range
  297. //most left case
  298. if (nodes.get(0).getKey().compareTo(right) > 0)
  299. answer.addAll(children.get(0).lookupRange(left, right));
  300. // most right case
  301. else if (nodes.get(nodes.size() - 1).getKey().compareTo(left) < 0)
  302. answer.addAll(children.get(children.size() - 1).lookupRange(left, right));
  303. ///
  304.  
  305. else
  306. {
  307. /// these nodes contain keys in range
  308. /*if (nodes.get(0).getKey().compareTo(left) >= 0) {
  309. answer.addAll(children.get(0).lookupRange(left, right));
  310. if (nodes.get(0).getKey().compareTo(right) <= 0)
  311. answer.add(nodes.get(0).getValue());
  312. }*/
  313.  
  314. for (int i = 0; i < nodes.size(); i++)
  315. {
  316. // go to left
  317. if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i).getKey().compareTo(right) <= 0)
  318. {
  319. answer.addAll(children.get(i).lookupRange(left, right));
  320. if (nodes.get(i).getKey().compareTo(right) <= 0)
  321. answer.add(nodes.get(i).getValue());
  322. }
  323. }
  324. //most right
  325. if ((nodes.get(nodes.size() - 1).getKey().compareTo(right) < 0))
  326. {
  327. // answer.add(nodes.get(nodes.size() - 1).getValue());
  328. answer.addAll(children.get(nodes.size()).lookupRange(left, right));
  329. }
  330. }
  331. }
  332. else
  333. {
  334. // if (nodes.get(0).getKey().compareTo(right) < 0 && nodes.get(0).getKey().compareTo(left) > 0)
  335. // добавляем в лист элементы нода без проверки детей
  336. for (int i = 0; i < nodes.size(); i++)
  337. {
  338. if (nodes.get(i).getKey().compareTo(left) >= 0 && nodes.get(i).getKey().compareTo(right) <= 0)
  339. answer.add(nodes.get(i).getValue());
  340. }
  341. }
  342.  
  343. return answer;
  344. }
  345.  
  346. }
  347.  
  348. public BTree(int B) {
  349. this.B = B;
  350. }
  351.  
  352. @Override
  353. public int size() {
  354. return size;
  355. }
  356.  
  357. @Override
  358. public boolean isEmpty() {
  359. return size() == 0;
  360. }
  361.  
  362. @Override
  363. public void add(K key, V value) {
  364. size++;
  365.  
  366. if (root == null)
  367. root = new BNode<>(null, this);
  368.  
  369. root.addKey(key, value);
  370.  
  371. }
  372.  
  373. @Override
  374. public boolean contains(K key) {
  375. return lookup(key) != null;
  376. }
  377.  
  378. @Override
  379. public V lookup(K key) {
  380. return root.lookup(key);
  381. }
  382.  
  383. @Override
  384. public List<V> lookupRange(K from, K to) {
  385. if (root == null)
  386. return null;
  387. return root.lookupRange(from, to);
  388. }
  389.  
  390. @Override
  391. public Object remove(K key) {
  392. return null;
  393. }
  394. }
  395.  
  396. class Pair<K, V> {
  397. private K key;
  398.  
  399. public K getKey() {
  400. return key;
  401. }
  402.  
  403. private V value;
  404.  
  405. public V getValue() {
  406. return value;
  407. }
  408.  
  409. public Pair(K key, V value) {
  410. this.key = key;
  411. this.value = value;
  412. }
  413.  
  414. @Override
  415. public String toString() {
  416. return key + "=" + value;
  417. }
  418. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement