Intro
This post won't present the actual mechanics of the skip list. Instead, all I got here is the facility for converting skip lists to funky ASCII art. For example, the unit test prints:
+-+ +-+
| |------------------------>| |
+-+ +-+
| |
V V
+-+ +-+ +-+ +-+
| |----------->| |--------->| |-------------->| |
+-+ +-+ +-+ +-+
| | | |
V V V V
+-+ +-+ +-+ +-+ +----+ +-+ +---------+ +-+ +-+
| |->|0|->|1|->|2|->|3000|->|4|->|5\n6\n\n7|->|6|->|7|
+-+ +-+ +-+ +-+ +----+ +-+ +---------+ +-+ +-+
Code
com.github.coderodde.util.SkipList.java:
package com.github.coderodde.util;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Random;
public final class SkipList<K extends Comparable<? super K>> {
static final class Node<K> {
public K key;
public Node<K> next;
Node(K key, Node<K> next) {
this.key = key;
this.next = next;
}
@Override
public int hashCode() {
return Objects.hashCode(key);
}
@Override
public boolean equals(Object o) {
return Objects.equals(((Node<K>) o).key, this.key);
}
}
static final class Index<K> {
Node<K> node;
Index<K> down;
Index<K> right;
Index(Node<K> node, Index<K> down, Index<K> right) {
this.node = node;
this.down = down;
this.right = right;
}
}
Index<K> head;
int size;
@Override
public String toString() {
return new ToStringConverter().convert();
}
private final class ToStringConverter {
private int levels;
private char[][] charMatrix;
private final Map<Node<K>, Integer> columnIndexMap = new HashMap<>();
ToStringConverter() {
this.levels = getLevels();
}
String convert() {
charMatrix = getCharacterMatrix();
applyNodeChain();
for (int l = 0; l < levels; l++) {
applyIndexChainImpl(l);
}
return convertMatrixToString();
}
private Index<K> getStartIndex(int level) {
Index<K> target = head;
while (level-- > 0) {
target = target.down;
}
return target;
}
private void setBox(int x, int y) {
charMatrix[y - 1][x - 1] = '+';
charMatrix[y - 1][x] = '-';
charMatrix[y - 1][x + 1] = '+';
charMatrix[y ][x - 1] = '|';
charMatrix[y ][x + 1] = '|';
charMatrix[y + 1][x - 1] = '+';
charMatrix[y + 1][x] = '-';
charMatrix[y + 1][x + 1] = '+';
}
private void applyIndexChainImpl(int level) {
Index<K> index = getStartIndex(level);
Index<K> next = index.right;
int startRowIndex = level * 5;
while (index != null) {
// Print the box:
int x = columnIndexMap.get(index.node);
setBox(x, startRowIndex + 1);
// Print the arrow to the node:
charMatrix[startRowIndex + 3][x] = '|';
charMatrix[startRowIndex + 4][x] = 'V';
if (next != null) {
// Print the arrow to the right:
int arrowLength = columnIndexMap.get(next.node)
- columnIndexMap.get(index.node)
- 4;
int xx = columnIndexMap.get(index.node) + 2;
for (int i = 0; i < arrowLength; i++) {
charMatrix[startRowIndex + 1][xx++] = '-';
}
charMatrix[startRowIndex + 1][xx] = '>';
next = next.right;
}
index = index.right;
}
}
private void applyNodeChain() {
int startRowIndex = levels * 5;
int startColIndex = 0;
for (Node<K> n = head.node; n != null; n = n.next) {
columnIndexMap.put(n, startColIndex + 1);
String nodeContent =
Objects.toString(
n.key == null ? " " : n.key)
.replaceAll("\n", "\\\\n");
int nodeContentLength = nodeContent.length();
charMatrix[startRowIndex][startColIndex] = '+';
charMatrix[startRowIndex + 1][startColIndex] = '|';
charMatrix[startRowIndex + 2][startColIndex] = '+';
startColIndex++;
for (int i = 0; i < nodeContentLength; i++) {
charMatrix[startRowIndex][startColIndex] = '-';
charMatrix[startRowIndex + 1][startColIndex] =
nodeContent.charAt(i);
charMatrix[startRowIndex + 2][startColIndex] = '-';
startColIndex++;
}
charMatrix[startRowIndex][startColIndex] = '+';
charMatrix[startRowIndex + 1][startColIndex] = '|';
charMatrix[startRowIndex + 2][startColIndex] = '+';
startColIndex++;
if (n.next != null) {
charMatrix[startRowIndex + 1][startColIndex++] = '-';
charMatrix[startRowIndex + 1][startColIndex++] = '>';
}
}
}
private String convertMatrixToString() {
StringBuilder sb =
new StringBuilder(
charMatrix.length * (charMatrix[0].length + 1));
for (char[] row : charMatrix) {
for (char ch : row) {
sb.append(ch);
}
sb.append("\n");
}
return sb.toString();
}
private int getLevels() {
int levels = 0;
Index<K> index = SkipList.this.head;
while (index != null) {
levels++;
index = index.down;
}
return levels;
}
private char[][] getCharacterMatrix() {
int height = getCharMatrixHeight();
int width = getCharMatrixWidth();
char[][] charMatrix = new char[height][width];
for (char[] row : charMatrix) {
Arrays.fill(row, ' ');
}
return charMatrix;
}
private int getCharMatrixHeight() {
return 5 * levels + 3;
}
private int getCharMatrixWidth() {
int totalTextLength = 0;
Node<K> node = head.node;
while (node != null) {
totalTextLength += 4; // Count box borders and arrow.
String nodeText =
node.key == null ?
" " :
node.key.toString();
nodeText = nodeText.replaceAll("\n", "\\\\n");
totalTextLength += nodeText.length();
node = node.next;
}
return totalTextLength;
}
}
}
com.github.coderodde.util.SkipListTest.java:
package com.github.coderodde.util;
import com.github.coderodde.util.SkipList.Index;
import com.github.coderodde.util.SkipList.Node;
import org.junit.Test;
public class SkipListTest {
@Test
public void test1() {
SkipList<String> sl = getSkipList1();
System.out.println("Print test:");
System.out.println(sl);
}
private static SkipList<String> getSkipList1() {
SkipList<String> sl = new SkipList<>();
sl.size = 8;
Node<String> nx = new Node<>(null, null);
Node<String> n0 = new Node<>(null, null);
Node<String> n1 = new Node<>(null, null);
Node<String> n2 = new Node<>(null, null);
Node<String> n3 = new Node<>(null, null);
Node<String> n4 = new Node<>(null, null);
Node<String> n5 = new Node<>(null, null);
Node<String> n6 = new Node<>(null, null);
Node<String> n7 = new Node<>(null, null);
n0.key = "0";
n1.key = "1";
n2.key = "2";
n3.key = "3000";
n4.key = "4";
n5.key = "5\n6\n\n7";
n6.key = "6";
n7.key = "7";
nx.next = n0;
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n6;
n6.next = n7;
n7.next = null;
Index<String> il10 = new Index<>(null, null, null);
Index<String> il11 = new Index<>(null, null, null);
Index<String> il20 = new Index<>(null, null, null);
Index<String> il21 = new Index<>(null, null, null);
Index<String> il22 = new Index<>(null, null, null);
Index<String> il23 = new Index<>(null, null, null);
// Top index layer:
il10.down = il20;
il10.node = nx;
il10.right = il11;
il11.down = il22;
il11.node = n4;
il11.right = null;
// Bottom index layer:
il20.node = nx;
il20.down = null;
il20.right = il21;
il21.node = n2;
il21.down = null;
il21.right = il22;
il22.node = n4;
il22.down = null;
il22.right = il23;
il23.node = n6;
il23.down = null;
il23.right = null;
sl.head = il10;
return sl;
}
}
Critique request##
As always, I would like to receive any commentary how to make my code better.
