Answered: kiplistmap class, so it prints out none…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

My code won't print out the desired test cases. For instance, the time and the event did not properly store it in the skiplistmap class, so it prints out none regardless of time and event. Also, when printing out the skiplist, it will just print out empty for each level regardless of the time and event being stored. So, can you take a look at my code and fix it? Also, how do I use a FakeRandheight class for put(k, v)?

mport java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HW5 {
public static void main(String[] args) throws FileNotFoundException {
SkipListMap<Integer, String> slm = new SkipListMap<>();
SkipListMap<Integer, String> cancelEvents = new SkipListMap<>();

File input = new File(args[0]);
Scanner in = new Scanner(input);

while (in.hasNextLine()) {
String line = in.nextLine();
String[] parts = line.split(" ");
if (parts.length == 0) {
continue;
}
String check = parts[0];

if (check.equals("AddEvent")) {
if (parts.length < 3) {
continue;
}
int time = Integer.parseInt(parts[1]); // time is the key
String event = "";
for (int i = 2; i < parts.length; i++) {
event += parts[i];
if (i < parts.length - 1) {
event += " ";
}
}
slm.put(time, event);
System.out.println(check + " " + time + " " + event);
} else if (check.equals("CancelEvent")) {
if (parts.length < 2) {
continue;
}
int time = Integer.parseInt(parts[1]); // time is the key
String event = slm.remove(time);
if (event != null) {
System.out.println(check + " " + time + " " + event);
cancelEvents.put(time, event);
} else {
System.out.println(check + " " + time + " none");
}
} else if (check.equals("GetEvent")) {
if (parts.length < 2) {
continue;
}
int time = Integer.parseInt(parts[1]);
String result = slm.get(time);
System.out.println("GetEvent " + time + " " + (result != null ? result : "none"));
} else if (check.equals("PrintSkipList")) {
System.out.println("PrintSkipList");
System.out.println(slm.toString());
}
}
}
}

public class SkipListMap<K extends Comparable<K>, V> {
private static class Node<K, V> {
K key;
V value;
int level;
Node<K, V>[] next;
Node<K, V> down;
Node (K key, V value, int level) {
this.key = key;
this.value = value;
this.level = level;
this.next = new Node[level];
}
}
private static final int MAX_LEVEL = 32;
private Node<K, V> head;
private int size;
public SkipListMap() {
this.head = new Node<>(null, null, MAX_LEVEL);
this.size = 0;
}

public V get(K key) {
Node<K, V> node = findNode(key);
return (node != null && key.equals(node.key)) ? node.value : null;
}

public void put(K key, V value) {
Node<K, V> node = findNode(key);
if(node != null && key.equals(node.key)) {
node.value = value;
} else {
int level = 1;
while (Math.random() < 0.5 && level < MAX_LEVEL) {
level++;
}
Node<K, V> newNode = new Node<>(key, value, level);

for (int i = 0; i < level; i++) {
if (node != null) {
newNode.next[i] = node.next[i];
node.next[i] = newNode;
}
}
size++;
}
}
public V remove(K key) {
Node<K, V> current = head;
Node<K, V>[] update = new Node[MAX_LEVEL];
for (int i = MAX_LEVEL - 1; i >= 0; i--) {
while (current.next[i] != null && current.next[i].key.compareTo(key) < 0) {
current = current.next[i];
}
update[i] = current;
}

current = current.next[0];
if (current != null && key.equals(current.key)) {
for (int i = 0; i < current.level; i++) {
update[i].next[i] = current.next[i];
}
size--;
return current.value;
}
return null;
}
public SkipListMap<K, V> subMap(K fromkey, K toKey) {
SkipListMap<K, V> subMap = new SkipListMap<>();
Node<K, V> current = findNode(fromkey);

while (current != null && current.key.compareTo(toKey) < 0) {
subMap.put(current.key, current.value);
current = current.next[0];
}

return subMap;
}
private Node<K, V> findNode(K key) {
Node<K, V> current = head;

for (int i = MAX_LEVEL - 1; i >= 0; i--) {
while (current.next[i] != null && current.next[i].key.compareTo(key) < 0) {
current = current.next[i];
}
}
return current.next[0];
}

public String toString() {
StringBuilder sb = new StringBuilder();

for (int i = MAX_LEVEL - 1; i >= 0; i--) {
sb.append("(S" + i + ") ");
Node<K, V> current = head.next[i];

if (current == null) {
sb.append("empty");
} else {
while (current != null) {
sb.append(current.key + ":" + current.value);

if (current.next[i] != null) {
sb.append(" ");
}
current = current.next[i];
}
}
sb.append("\n");
}

return sb.toString();
}
}

public class FakeRandHeight {
static int[] height = {0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4,
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
int count;
// number of times get() has been called
public FakeRandHeight()
{
count = 0;
}
// return the next number in the sequence, recycle the sequence if needed
public int get()
{
return height[count++ % 31];
}

Here is the sample input:

AddEvent 101910 Breakfast
AddEvent 101913 Lunch
AddEvent 101918 Dinner
GetEvent 101914
AddEvent 101911 Data Structures
AddEvent 102007 Exercise
PrintSkipList
AddEvent 101915 Homework
CancelEvent 102007
AddEvent 102013 Relax
AddEvent 102011 Read a Book
GetEvent 101915
AddEvent 101914 Call Mom
PrintSkipList

Expert Solution

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.