-1

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

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by Cort3z
0

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?

0

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.