Question: Can someone teach me how to write the following code (what it does is simply construct and search a B tree) in Scheme using Dr.Racket?
Can someone teach me how to write the following code (what it does is simply construct and search a B tree) in Scheme using Dr.Racket? (R5RS language) The original code is in Java but I have no idea how to convert it into Scheme code. Help is much appreciated!
Code:
-----------------------------------------------------------Node.java---------------------------------------------------------------
/**
* The node base class that will be inherited by RootNode and LeafNode.
*/
public class Node {
/**
* Constructor for class Node. It does nothing.
*/
public Node() {}
/**
* Default implementation for a search method.
* It will take a parameter {@code value} and search
* for it in the node or the children of the node.
* It will always return false.
* @return False.
*/
public boolean search(int value) {
return false;
}
}
------------------------------------------------------------LeafNode.java---------------------------------------------------------
import java.util.*;
/**
* The leaf node class. It stores the values in a collection of integers. */
public class LeafNode extends Node{
/**
* The collection of integers values that the leaf node stores. */
private Collection
/** Constructor for class LeafNode
* @param values The Collection of leaf node values that the node stores
*/
public LeafNode(Collection
this.values = values;
}
/**
* The search method that takes a parameter {@code value} to be searched in the node.
* It uses the Collection.contains() method to search.
* @param value The value to be searched
* @return True if the value is found in the LeafNode else False.
*/
@Override
public boolean search(int value) {
return values.contains(value);
}
}
---------------------------------------------------RootNode.java-----------------------------------------------------------------
import java.util.*;
/**
* The RootNode class. It has min and max values that define the range of values that
* can be searched in this node, and a collection of nodes which are its child nodes.
*/
public class RootNode extends Node {
/**
* The min(start) of the range of values for the RootNode
*/
private int min;
/**
* The max(end) of the range of values for the RootNode
*/
private int max;
/**
* The collection of child nodes for the root node.
*/
private Collection
/**
* The constructor for the class RootNode.
* @param min The start of the range of values
* @param max The end of the range of values
* @param nodes The collection of child nodes of the root node
*/
public RootNode(int min, int max, Collection
this.min = min;
this.max = max;
this.nodes = nodes;
}
/**
* The search method that takes a parameter {@code value} to be searched in the node.
* It goes through all the child nodes and searches for the value accordingly.
*
- If the node is a RootNode and if the value to be searched
* lies in the range specified by the root node, the search is transferred to this node.
- Else if the node is a LeafNode, we search if it contains the value or not.
*
*
*
* We use the concept of overriding to search.
* @param value The value to be searched
* @return True if the value is found in the RootNode else False.
*/
@Override
public boolean search(int value) {
for(Node node: this.nodes) {
if(node instanceof RootNode) {
if(value < this.min || value > this.max) {
continue;
}
}
if(node.search(value) == true) {
return true;
}
}
return false;
}
}
-------------------------------------------------------------Driver.java-------------------------------------------------------------
import java.util.*;
/**
* Driver class for testing the implemetation.
*/
public class Driver {
public static void main(String args[]) {
/**
* We define the Leafnodes and RootNodes according to the diagram given in the
* problem statement.
*/
LeafNode l1, l2, l3;
RootNode r1, r2, r3, r4;
l1 = new LeafNode(new ArrayList
{
add(100);
add(120);
add(140);
add(160);
}
});
l2 = new LeafNode(new ArrayList
{
add(200);
add(220);
add(240);
add(260);
}
});
l3 = new LeafNode(new ArrayList
{
add(300);
add(320);
add(340);
add(360);
}
});
/**
* The root nodes are defined in top down order, since the children of a node
* need to be initialised before the parent
*/
r4 = new RootNode(300, 399, new ArrayList
{
add(l3);
}
});
r3 = new RootNode(200, 399, new ArrayList
{
add(l2);
add(r4);
}
});
r2 = new RootNode(100, 199, new ArrayList
{
add(l1);
}
});
r1 = new RootNode(1, 1000, new ArrayList
{
add(r2);
add(r3);
}
});
/** We now search the integers and verify our implementation. */
System.out.println("Searching for values in the B-Tree implementation: ");
System.out.println("Value 100: " + r1.search(100));
System.out.println("Value 150: " + r1.search(150));
System.out.println("Value 220: " + r1.search(220));
System.out.println("Value 270: " + r1.search(270));
System.out.println("Value 360: " + r1.search(360));
System.out.println("Value 399: " + r1.search(399));
}
}
--------------------------------------------------------------------------------------------------------------------------
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help