确定性跳跃表Java实现（Word）

1、1-5确定性跳跃表Java实现作者：云南大学软件学院09数字媒体技术 雒森/* * To change this template, choose Tools | Templates * and open the template in the editor. */package LuoSen.DS.DS;import java.io.Serializable;/* * * author LENOVO */*确定性跳跃表链的结点*/public class DSLLinkNode implements Serializable /*跳跃表链结点的层数*/ public int levelNum

2、=1; /*跳跃表链结点的数据*/ public S data; /*顶部的链*/ public DSLNode top; /*构造函数*/ public DSLLinkNode() data=null; top=null; /*构造函数*/ public DSLLinkNode(S data,DSLNode top) this.data=data; this.top=top; /*构造函数*/ public DSLLinkNode(S data,DSLNode top,int i) this.data=data; this.top=top; this.levelNum=i; /*判断节点是否

3、相等*/ Override public boolean equals(Object o) if(this=o) return true; if(o=null|!(o instanceof DSLLinkNode) return false; DSLLinkNode a=(DSLLinkNode)o; if(data.equals(a.data) return true; return false; Override public int hashCode() int hash = 7; hash = 41 * hash + this.levelNum; hash += 41 * hash +

4、 (this.data != null ? this.data.hashCode() : 0); return hash; Override public String toString() return +data; /* * To change this template, choose Tools | Templates * and open the template in the editor. */package LuoSen.DS.DS;import java.io.Serializable;/* * * author LENOVO */*确定性跳跃表结点*/public clas

5、s DSLNode implements Serializable /*向右的链*/ public DSLNode right; /*向下的链*/ public DSLNode down; /*确定性跳跃表链的结点*/ public DSLLinkNode link; /*默认构造函数*/ public DSLNode() right=down=null; link=null; /*构造函数*/ public DSLNode(DSLNode right) this.right=right; this.down=null; link=null; /*构造函数*/ public DSLNode(D

6、SLNode right,DSLNode down) this.right=right; this.down=down; link=null; /*构造函数*/ public DSLNode(DSLNode right,DSLNode down,DSLNode top,int i) this.right=right; this.down=down; link=new DSLLinkNode(S)new Object(),top,i); /*构造函数*/ public DSLNode(DSLNode right,DSLNode down,DSLLinkNode link) this.right=

7、right; this.down=down; this.link=link; /*判断节点是否相等*/ Override public boolean equals(Object o) if(this=o) return true; if(o=null|!(o instanceof DSLNode) return false; DSLNode a=(DSLNode)o; if(link=a.link|(link!=null&link.equals(a.link) return true; return false; Override public int hashCode() int hash

8、 = 7; hash = 47 * hash + (this.link != null ? this.link.hashCode() : 0); return hash; Override public String toString() if(link!=null) return link.toString(); else return ; /* * To change this template, choose Tools | Templates * and open the template in the editor. */package LuoSen.DS.DS;import Luo

9、Sen.DS.Alg.Util.CreateComparator;import LuoSen.DS.Exceptions.IllegalParameterException;import java.io.Serializable;import java.util.Collection;import java.util.Comparator;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Set;import java.util.logging.Level;impo

10、rt java.util.logging.Logger;/* * * author 云大09数媒雒森 */*1-5确定性跳跃表*/public class DSkipList implements Serializable,Iterable /*头结点*/ protected DSLNode header; /*尾结点*/ protected DSLNode tailer=null; /*底结点*/ protected DSLNode bottom=null; /*表中元素的个数*/ protected int size=0; /*比较器*/ protected Comparator cp=n

11、ull; /*构造函数*/ public DSkipList() bottom=null; tailer=null; header=new DSLNode(tailer,bottom,null, (byte)0); /*构造函数*/ public DSkipList(Comparator cp) bottom=null; tailer=null; header=new DSLNode(tailer,bottom,null,(byte)0); this.cp=cp; /*使用一个DSkipList跳表初始化，目的是将目标复制到当前表中*/ public boolean initial(DSkip

12、List dsl) if(dsl=null) return false; this.cp=dsl.cp; this.header=dsl.header; this.size=dsl.size; return true; /*返回跳跃表的头*/ public DSLNode getHeader() return header; /*设置比较器*/ public void setComparator(Comparator cp) this.cp=cp; /*返回比较器*/ public Comparator getComparator() return cp; /*判断表中是否有关键字对应值*/

13、public boolean contain(S data) return this.search(data)!=null; /*查找数据为data的数据比较关键字封装在data中*/ public S search(S data) if(data=null|size=0) return null; DSLNode cur=header; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data,data)0) cur=cur.right; if(cur.right!=tailer&pare(

14、cur.right.link.data,data)=0) return cur.right.link.data; cur=cur.down; return null; /*查找数据为data的数据比较关键字封装在data中,若查不到则返回位于它之后的第一个（最底部）结点*/ public DSLNode searchStart(S data) if(data=null|size=0) return null; DSLNode cur=header; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data

15、,data)0) cur=cur.right; if(cur.down=bottom|(cur.right!=tailer& pare(cur.right.link.data,data)=0) cur=cur.right; if(cur!=tailer) while(cur.down!=bottom) cur=cur.down; return cur; cur=cur.down; return null; /*查找数据为data的数据比较关键字封装在data中,若查不到则返回位于它之前的第一个（最底部）结点*/ public DSLNode searchEnd(S data) if

16、(data=null|size=0) return null; DSLNode cur=header; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data,data)0) cur=cur.right; if(cur.down=bottom|(cur.right!=tailer& pare(cur.right.link.data,data)=0) cur=cur.right; if(cur!=tailer) while(cur.down!=bottom) cur=cur.down; if(

17、cur.right!=tailer&pare(cur.right.link.data,data)=0) cur=cur.right; return cur; cur=cur.down; return null; /*插入数据data,若已存在返回数据链结点，并不插入数据，你可以在外面修改*/ public DSLLinkNode insert(S data) throws IllegalParameterException if(data=null) return null; if(cp=null) if(Comparable.class.isAssignableFrom(data

18、.getClass() CreateComparator cc =new CreateComparator(); cp=cc.getComparator(); else throw new IllegalParameterException(数据不可以比较，请先设置比较器！); DSLNode cur=header; DSLNode newNode=null; while(cur!=bottom) while(cur.right!=tailer&pare(cur.right.link.data,data)0) cur=cur.right; if(cur.right!=tailer&

19、pare(cur.right.link.data,data)=0) newNode=cur.right; break; if(cur.down=bottom) newNode=new DSLNode(cur.right,bottom); newNode.link=new DSLLinkNode(data,newNode); cur.right=newNode; size+; break; else if(cur.down.right!=tailer&cur.down.right.right!=tailer &cur.down.right.right.right!=tailer& c

20、ur.down.right.right.right.right!=tailer& cur.down.right.right.right.right.right!=tailer& (cur.right=tailer|pare(cur.down.right.right.right .right.right.link.data,cur.right.link.data)0) cur.right=new DSLNode(cur.right,cur.down.right.right.right,cur.down.right.right.right.link); cur.right.link.t

21、op=cur.right; cur.right.link.levelNum+; cur=cur.down; if(header.right!=tailer) header.link.levelNum+; header.link.top=header; header=new DSLNode(tailer,header,header.link); return newNode.link; /*删除数据data*/ public boolean remove(S data) throws IllegalParameterException if(data=null|size=0) return fa

22、lse; if(cp=null) if(Comparable.class.isAssignableFrom(data.getClass() CreateComparator cc =new CreateComparator(); cp=cc.getComparator(); else throw new IllegalParameterException(数据不可以比较，请先设置比较器！); DSLNode cur=header; DSLNode c=null,cc=null,top=null; while(cur!=bottom) while(cur.right!=tailer&

23、pare(cur.right.link.data,data)0) cur=cur.right; if(cur.down=bottom&cur.right!=tailer&pare(cur.right.link.data,data)=0) if(size=1) header=new DSLNode(tailer,bottom,null,(byte)0); else if(cur.link.levelNumcur.right.link.levelNum)/比较左右位置结点层数高低，待删除的右边结点 c=cur.right.link.top; top=cur.right.link.top

24、; cur.link.levelNum=cur.right.link.levelNum; while(c.down!=cur.link.top.right) c.link=cur.link; c=c.down; c.link=cur.link; c.down=cur.link.top; c=cur.link.top.right; cc=cur.link.top; while(c!=bottom&cc!=bottom) cc.right=c.right; cc=cc.down; c=c.down; cur.link.top=top; else cc=cur.link.top; while(cc.

25、right!=cur.right.link.top) cc=cc.down; c=cur.right.link.top; while(c!=bottom&cc!=bottom) cc.right=c.right; cc=cc.down; c=c.down; size-; while(header.down!=bottom&header.down.right=tailer) header=header.down; header.link.levelNum-; header.link.top=header.down; return true; cur=cur.down; return false;

26、 /*获取条件一维区间odr之间的元素集合,该函数主要服务于：KDSkipList,用于检索一维区间*/ public Collection queryRegion(ODRegion odr) Set s=new HashSet(); if(odr.isNoHasCondition) DSLNode cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) if(cur.link.data instanceof KDSLNode) s.addAll(KDSLNode)cur.link.

27、data).set); else s.add(cur.link.data); cur=cur.right; else DSLNode cur=header; DSLNode end=null; if(odr.start!=null) cur=this.searchStart(odr.start); else while(cur.down!=bottom) cur=cur.down; cur=cur.right; end=this.searchEnd(odr.end); if(cur=null|(cur!=null&end!=null&pare(cur.link.data, end.

28、link.data)0) return s; while(cur!=end) if(cur.link.data instanceof KDSLNode) s.addAll(KDSLNode)cur.link.data).set); else s.add(cur.link.data); cur=cur.right; return s; /*获取条件一维区间odr之间的元素满足多维条件的数据集合,index为odr在qc中的位置, * 该函数主要服务于：MLDSkipList 用于检索多位区间*/ public Collection queryRegion(Collection s,ODRegio

29、n odr,int index ,ListODRegion qc,ListComparator cps) if(s=null) return s; if(odr.isNoHasCondition) DSLNode cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) if(cur.link.data instanceof MLDSLNode) MLDSLNode a=(MLDSLNode) cur.link.data; if(a.dslsl=null) if(this.isMeet

30、QC(cur.link.data, index, qc.size(), qc, cps,index,true) s.add(a.data); else a.dslsl.queryRegion(s,qc.get(index+1), index+1, qc, cps); else if(this.isMeetQC(cur.link.data, 0, qc.size(), qc, cps,index,true) s.add(cur.link.data); cur=cur.right; else DSLNode cur=header; DSLNode end=null; if(odr.start!=n

31、ull) cur=this.searchStart(odr.start); else while(cur.down!=bottom) cur=cur.down; cur=cur.right; end=this.searchEnd(odr.end); if(cur=null|(cur!=null&end!=null&pare(cur.link.data, end.link.data)0) return s; while(cur!=end) if(cur.link.data instanceof MLDSLNode) MLDSLNode a=(MLDSLNode) cur.link.d

32、ata; if(a.dslsl=null) if(this.isMeetQC(cur.link.data, index, qc.size(), qc, cps,index,true) s.add(a.data); else a.dslsl.queryRegion(s,qc.get(index+1), index+1, qc, cps); else if(this.isMeetQC(cur.link.data, 0, qc.size(), qc, cps,index,true) s.add(cur.link.data); cur=cur.right; return s; /*检测元素o是否满足多

33、位区间条件qc,start为数组偏移索引,end为结束索引， * isFilterCondition表示是否忽略filterIndex标识的位置的一维区间条件*/ protected boolean isMeetQC(S o,int start,int end,ListODRegion qc,ListComparator cps,int filterIndex, boolean isFilterCondition) for(int i=start;iend;i+) if(qc.get(i).isNoHasCondition|(isFilterCondition& i=filterIndex)|

34、(qc.get(i).start=null&qc.get(i).end=null) continue; if(qc.get(i).start!=null&cps.get(i).compare(o, qc.get(i).start)0) return false; return true; /*返回表中元素的个数*/ public int size() return size; /*返回确定性跳跃表的层数*/ public int getLevel() return header.down = null ? 0:header.down.link.levelNum; /*转化为数组,若表中有0个元

35、素返回null*/ public Object toArray() if(size=0) return null; Object o=new Objectsize; int i=0; DSLNode cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) oi=cur.link.data; cur=cur.right; i+; return o; /*当划分跳表后更新跳表元素个数*/ public void updateSize() int i=0; DSLNode cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) cur=cur.right; i+; size=i; /*返回最小的元素,若不存在返回null*/ public S minData() if(size=0) return null; DSLNode cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; return cur=null ? null:cur.link.data; /*返回最小的元素并删除,若不