Java - Converting a skip list to the ASCII art

Question

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.

Answer 1

"Obviously" no pretty string formatting belongs in the SkipList data structure. That is just a big single responsiblity principle violation. The question is how do you expose the internal skip list structure to an external formatter?

Consider providing a debugging method from SkipList that accepts a debugging/tracing interface as a parameter, to which the SkipList dumps information of all the nodes and values in the list. The debugging interface implementation then does whatever it needs with the data.

The character array seems like a candidate for a standalone component with methods for drawing boxes and arrows.

Answer 2

The automatically found imperfections in SkipList:

• unused import statement import java.util.Random;.
• equals should check the class of its parameter.
• unchecked cast: Objectto `SkipList.Node.
• field levels may be final.

The equals does not need to use Object.equals. Indeed that would recursively call the Node.equals if I am not mistaken (endless loop?).

Correct:

    @Override
    public boolean equals(Object o) {
        return this == o // Heuristic optimization (?).
            && o instanceof Node n // null would yield false.
            && Objects.equals(key, n.key);
    }

For those that did not expect the n as an alias declaration of o of type Node. It is a short form for a safe cast of o to Node.

What you definitely should not do is to create components of SkipList externally (here in SkipListTest). And then you would not need to make Node and Index public, and parametrize them with . In fact all three Ks are different, two of them not Comparable. Better private static class Node {. (And I could imagine without static too.)

So you would maybe need to have a private final List<Node> nodes = new ArrayList<>(); in SkipList.

The definition of the graph could be done by index number, or maybe by JSON or XML. Some small DSL perhaps:

nodes: {
    nx: { key: null, next: "n0" },
    n0: { key: "0", next: "n1" },
    n1: { key: "1", next; "n2" },
    ...
}

This allows/requires checking the validity of all components.

Last but not least: you can make use of Unicode with its box drawing characters. As you know it is even recommended that the java sources are now encoded in UTF-8, so you can just write '┐' for a top right corner.