Untitled

    public Optional<Pair<DataBox, Long>> put(DataBox key, RecordId rid) {
        // TODO(proj2): implement
        if (this.keys.contains(key)) {
            throw new BPlusTreeException("Duplicate key");
        }
        Optional<Pair<DataBox, Long>> placedPair = Optional.empty();

        int numKeys = this.keys.size();
        if ((numKeys == 0) || (key.getInt() > this.keys.get(numKeys - 1).getInt())) {
            this.keys.add(key);
            this.rids.add(rid);
        } else {
            for (int i = 0; i < numKeys; i++) {
                if (key.getInt() < this.keys.get(i).getInt()) {
                    this.keys.add(i, key);
                    this.rids.add(i, rid);
                    break;
                }
            }
        }

        int maxKeys = this.metadata.getOrder() * 2;
        int newKeysSize = this.keys.size();

        if (this.keys.size() > maxKeys) {
            int currentIndex = this.metadata.getOrder();
            List<DataBox> newNodeKeys = this.keys.subList(currentIndex, newKeysSize);
            this.keys = this.keys.subList(0, currentIndex);
            List<RecordId> newNodeRids = this.rids.subList(currentIndex, newKeysSize);
            this.rids = this.rids.subList(0, currentIndex);
            LeafNode newLeafNode = new LeafNode(this.metadata, this.bufferManager, newNodeKeys, newNodeRids, this.rightSibling, this.treeContext);
            this.rightSibling = Optional.of(newLeafNode.getPage().getPageNum());
            placedPair = Optional.of(new Pair<>(newLeafNode.keys.get(0), newLeafNode.getPage().getPageNum()));
        }
        sync();
        return placedPair;
    }