Program för att rita skiplistor

SkipDraw

Detta är ett litet javaprogram som kan rita upp skiplistor på skärmen. Det kan underlätta vid felsökning. För varje nod ritas en låda i vilken nyckelns och elementets värde skrivs ut (nyckeln ovanför elementet). Från varje låda ritas också pilar till de lådor som vänster-, höger-, upp-, och ner-referenserna går. Om en referens är null så ritas ingen pil. Om en referens går till ett oväntat ställe (utanför skiplistan) så ritas pilen till ett svart punkt på skärmen.

Så här kan det se ut:

En hel och fin skiplista

En trasig och inte alls bra skiplista

Programfiler

Nedan finns några länkar till ett program som kan rita upp skiplistor på skärmen, så att man kan se hur de ser ut och att alla pekare i dem går till rätt platser.

SkipDraw.java -- huvudfilen

QuadNode.java -- gränssnittsdefinition

SkipMain.java -- testprogram

Ändringar som krävs

För att det ska fungera måste noderna implementera ett gränssnitt som beskriver hur man går från en nod till en granne i skiplistan. Detta finns i filen QuadNode.java ovan. Gränssnittet ser ut så här:

//Filen QuadNode.java
public interface QuadNode {
    QuadNode Up();
    QuadNode Down();
    QuadNode Left();
    QuadNode Right();

    Object Key();
    Object Data();
}

Det borde inte vara svårt att låta noderna implementera detta gränssnitt. Det handlar bara om att lägga till ett par rader. Här är ett exempel:

// Nodklass till skiplistan.
class Node implements QuadNode {
// Denna bit ser ut som förut och behöver inte ändras
  Node after, before, below, above;
  Object key, element;

  Node(...) { ... }

// Raderna nedanför har lagts till. Notera att alla
// metoder deklarerats public.
  public QuadNode Left()  { return before; }
  public QuadNode Right() { return after; }
  public QuadNode Up()    { return above; }
  public QuadNode Down()  { return below; }

  public Object Key()  { return key; }
  public Object Data() { return element; }
}

Testprogram

Testprogrammet SkipMain.java tar ett heltalsargument på kommandoraden och stoppar in lika många slumpmässiga heltal i skiplistan. Därefter ritas en bild av skiplistan upp på skärmen. Om fönstret är litet och inget syns i det är det bara att göra det större.

Testprogrammet måste få tag till en av noderna i skiplistan, det spelar ingen roll vilken. I SkipMain.java antas att en sådan finns i variabeln theTop. Namnet kan enkelt bytas ut.

Så här ser SkipMain.java ut:

//Filen SkipMain.java

public class SkipMain {
    public static void main(String[] args) {
	int nElem = Integer.parseInt(args[0]);

	SkipList s = new SkipList();

	for(int i = 0; i<nElem; i++)
	    s.insert("" + ((int) (Math.random() * 10000.0)), "--");

	new SkipDraw(s.theTop); // Byt s.theTop mot övre vänsta hörnet i er skiplista
    }
}

Lycka till, och hoppas att det blir fina bilder av skiplistorna!

Senast ändrad av Tomas Oppelstrup, 2001-01-24