This code is SkipList sort Min to Max. How to convert this SkipList to sort Max to Min.??

File : SkipList.java

/**
  Skip List
  Using integer key
 */
 
import static java.lang.Math.*;

public class SkipList {
	private static final double PROB = 0.5D;
	private static final int MAX_VALUE = Integer.MAX_VALUE;
	private static final int MIN_VALUE = Integer.MIN_VALUE;
	private double prob;
	private int level;
	private int maxLevel;
	private SkipNode header, nil;
	
	public SkipList(int max) {
		this(PROB, (int)ceil(log(max)/log(1/PROB)) - 1);
	}
		
	//user must provide probability and max nodes	
	public SkipList(double prob, int maxLevel) {
		this.level = 0;
		this.prob = prob;
		this.maxLevel = maxLevel-1;
		
		//header node with min value
		header = new SkipNode(this.maxLevel, MIN_VALUE);
		//nil node with max value
		nil = new SkipNode(this.maxLevel, MAX_VALUE);
		
		//attach nil to header
		for(int i = 0; i <= this.maxLevel; i++)
			header.forward[i] = nil;
	}
	
	//calculate random level
	private int randomLevel() {
		int level = 0;
		
		while(level < maxLevel && Math.random() < prob)
			level++;
			
		return level;
	}
		
	//insert key into list
	public void insert(int key) {
		//update stores pointers to keys on each level
		SkipNode []update = new SkipNode[maxLevel+1];
		SkipNode x = header;
		
		//locate a place to insert
		for(int i = level; i >= 0; i--) {
			while(x.forward[i].key < key)
				x = x.forward[i];
			update[i] = x;
		}
		x = x.forward[0]; //reset level to the lowest
		
		//insert key
		if(x.key == key)
			; //no duplicates allowed
		else {
			//flip the coin
			int newLevel = randomLevel();
			//new key has more level than this one, update list
			if(newLevel > level) {
				for(int i = level+1; i <= newLevel; i++)
					update[i] = header;
				//current level seen so far
				level = newLevel;
			}
			//create new node with key and update links
			x = new SkipNode(newLevel, key);
			for(int i = 0; i <= newLevel; i++) {
				x.forward[i] = update[i].forward[i];
				update[i].forward[i] = x;
			}
		}
	}
	
	//delete a node in the list
	public void delete(int key) {
		SkipNode[] update = new SkipNode[maxLevel+1];
		SkipNode x = header;
		
		//search for key in list
		for(int i = level; i >= 0; i--) {
			while(x.forward[i].key < key)
				x = x.forward[i];
			update[i] = x;
		}
		x = x.forward[0]; // reset level to the lowest
		
		//found key to delete, rebuild list
		if(x.key == key) {
			for(int i = 0; i <= level; i++) {
				if(update[i].forward[i] == x)
					update[i].forward[i] = x.forward[i];
			}
			x = null; //destroy this node
			//reset level
			while(level > 0 && header.forward[level].key == MAX_VALUE)
				level--;
		}
	}
	
	//seach for a key
	public boolean search(int key) {
		SkipNode x = header;
		
		for(int i = level; i >= 0; i--) {
			while(x.forward[i].key < key)
				x = x.forward[i];
		}
		x = x.forward[0];
		
		return x.key == key ? true : false;
	}
	
	//calculate keys in list
	private int[] keys() {
		int[] countKeys = new int[maxLevel+1];
		SkipNode x = header.forward[0];
		
		while(x.key != MAX_VALUE) {
			countKeys[x.forward.length-1]++;
			x = x.forward[0];
		}
		
		return countKeys;
	}
	
	//display list in the form:
	//level[i]keys:(nn) x	x	x	x	x	x	x
	//where i = level, nn = number of keys on that level
	//and x = key
	public void show() {
		int[] key = keys();
		for(int i = maxLevel; i >= 0; i--) {
			System.out.printf("level[%d]keys:(%02d):", i, key[i]);
			SkipNode x = header.forward[i];
			SkipNode y = header.forward[0];
			while(x != nil) {
				if(x == y) {
					System.out.printf("%4d", x.key);
					x = x.forward[i];
				}
				else
					System.out.printf("%4c", '-');
				y = y.forward[0];
			}
			System.out.println();
		}
		System.out.println();
	}
}

File SkipNode.java

public class SkipNode {
	int key;					//key to insert
	SkipNode []forward;	//links
	
	public SkipNode(int level, int key) {
		this.key = key;
		forward = new SkipNode[level+1];
	}
}

File TestSkipList.java

/**
  Testing module for Skip List
 */

public class TestSkipList {
	public static void main(String[] args) {
		//create skip list with probvability of 5with 5 levels
		SkipList list = new SkipList(0.5, 5);
		
		//randomly generate numbers for insertion
		for(int i = 0; i < 14; i++) {
			int n = (int)(Math.random() * 100) + 1;
			list.insert(n);
		}
	}
}

How to convert this code Please Tell me? Thanks

Recommended Answers

All 2 Replies

I don't see any comments in the code showing where the sort is happening.
Can you comment the code to show where the sort logic is?

Can't you just flip the array when it is sorted? Sure, it is not optimized, but it works.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.