確定性跳躍表Java實(shí)現(xiàn)

1、1-5確定性跳躍表Java實(shí)現(xiàn)作者：云南大學(xué)軟件學(xué)院09數(shù)字媒體技術(shù) 雒森/* * To change this template, choose Tools | Templates * and open the template in the editor. */package LuoSen.DS.DS;import java.io.Serializable;/* * * author LENOVO */*確定性跳躍表鏈的結(jié)點(diǎn)*/public class DSLLinkNode<S> implements Serializable /*跳躍表鏈結(jié)點(diǎn)的層數(shù)*/ public int

2、 levelNum=1; /*跳躍表鏈結(jié)點(diǎn)的數(shù)據(jù)*/ public S data; /*頂部的鏈*/ public DSLNode<S> top; /*構(gòu)造函數(shù)*/ public DSLLinkNode() data=null; top=null; /*構(gòu)造函數(shù)*/ public DSLLinkNode(S data,DSLNode<S> top) this.data=data; this.top=top; /*構(gòu)造函數(shù)*/ public DSLLinkNode(S data,DSLNode<S> top,int i) this.data=data; thi

3、s.top=top; this.levelNum=i; /*判斷節(jié)點(diǎn)是否相等*/ Override public boolean equals(Object o) if(this=o) return true; if(o=null|!(o instanceof DSLLinkNode) return false; DSLLinkNode<S> a=(DSLLinkNode<S>)o; if(data.equals(a.data) return true; return false; Override public int hashCode() int hash = 7;

4、 hash = 41 * hash + this.levelNum; hash += 41 * hash + (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

5、java.io.Serializable;/* * * author LENOVO */*確定性跳躍表結(jié)點(diǎn)*/public class DSLNode<S> implements Serializable /*向右的鏈*/ public DSLNode<S> right; /*向下的鏈*/ public DSLNode<S> down; /*確定性跳躍表鏈的結(jié)點(diǎn)*/ public DSLLinkNode<S> link; /*默認(rèn)構(gòu)造函數(shù)*/ public DSLNode() right=down=null; link=null; /*構(gòu)造函數(shù)*

6、/ public DSLNode(DSLNode<S> right) this.right=right; this.down=null; link=null; /*構(gòu)造函數(shù)*/ public DSLNode(DSLNode<S> right,DSLNode<S> down) this.right=right; this.down=down; link=null; /*構(gòu)造函數(shù)*/ public DSLNode(DSLNode<S> right,DSLNode<S> down,DSLNode<S> top,int i) th

7、is.right=right; this.down=down; link=new DSLLinkNode<S>(S)new Object(),top,i); /*構(gòu)造函數(shù)*/ public DSLNode(DSLNode<S> right,DSLNode<S> down,DSLLinkNode<S> link) this.right=right; this.down=down; this.link=link; /*判斷節(jié)點(diǎn)是否相等*/ Override public boolean equals(Object o) if(this=o) retu

8、rn 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 = 7; hash = 47 * hash + (this.link != null ? this.link.hashCode() : 0); return hash; Override publ

9、ic 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 LuoSen.DS.Alg.Util.CreateComparator;import LuoSen.DS.Exceptions.IllegalParameterException;i

10、mport 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;import java.util.logging.Logger;/* * * author 云大09數(shù)媒雒森 */*1-5確定性跳躍表*/public class DSkipList&

11、lt;S> implements Serializable,Iterable<S> /*頭結(jié)點(diǎn)*/ protected DSLNode<S> header; /*尾結(jié)點(diǎn)*/ protected DSLNode<S> tailer=null; /*底結(jié)點(diǎn)*/ protected DSLNode<S> bottom=null; /*表中元素的個(gè)數(shù)*/ protected int size=0; /*比較器*/ protected Comparator<S> cp=null; /*構(gòu)造函數(shù)*/ public DSkipList() b

12、ottom=null; tailer=null; header=new DSLNode<S>(tailer,bottom,null, (byte)0); /*構(gòu)造函數(shù)*/ public DSkipList(Comparator<S> cp) bottom=null; tailer=null; header=new DSLNode<S>(tailer,bottom,null,(byte)0); this.cp=cp; /*使用一個(gè)DSkipList跳表初始化，目的是將目標(biāo)復(fù)制到當(dāng)前表中*/ public boolean initial(DSkipList<

13、;S> dsl) if(dsl=null) return false; this.cp=dsl.cp; this.header=dsl.header; this.size=dsl.size; return true; /*返回跳躍表的頭*/ public DSLNode<S> getHeader() return header; /*設(shè)置比較器*/ public void setComparator(Comparator<S> cp) this.cp=cp; /*返回比較器*/ public Comparator<S> getComparator()

14、return cp; /*判斷表中是否有關(guān)鍵字對(duì)應(yīng)值*/ public boolean contain(S data) return this.search(data)!=null; /*查找數(shù)據(jù)為data的數(shù)據(jù)比較關(guān)鍵字封裝在data中*/ public S search(S data) if(data=null|size=0) return null; DSLNode<S> cur=header; while(cur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cu

15、r=cur.right; if(cur.right!=tailer&&pare(cur.right.link.data,data)=0) return cur.right.link.data; cur=cur.down; return null; /*查找數(shù)據(jù)為data的數(shù)據(jù)比較關(guān)鍵字封裝在data中,若查不到則返回位于它之后的第一個(gè)（最底部）結(jié)點(diǎn)*/ public DSLNode<S> searchStart(S data) if(data=null|size=0) return null; DSLNode<S> cur=header; while(c

16、ur!=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; return cur; cur=cur.down; return null; /*查找數(shù)據(jù)為data的數(shù)

17、據(jù)比較關(guān)鍵字封裝在data中,若查不到則返回位于它之前的第一個(gè)（最底部）結(jié)點(diǎn)*/ public DSLNode<S> searchEnd(S data) if(data=null|size=0) return null; DSLNode<S> 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&& pa

18、re(cur.right.link.data,data)=0) cur=cur.right; if(cur!=tailer) while(cur.down!=bottom) cur=cur.down; if(cur.right!=tailer&&pare(cur.right.link.data,data)=0) cur=cur.right; return cur; cur=cur.down; return null; /*插入數(shù)據(jù)data,若已存在返回?cái)?shù)據(jù)鏈結(jié)點(diǎn)，并不插入數(shù)據(jù)，你可以在外面修改*/ public DSLLinkNode<S> insert(S dat

19、a) throws IllegalParameterException if(data=null) return null; if(cp=null) if(Comparable.class.isAssignableFrom(data.getClass() CreateComparator<S> cc =new CreateComparator<S>(); cp=cc.getComparator(); else throw new IllegalParameterException("數(shù)據(jù)不可以比較，請(qǐng)先設(shè)置比較器！"); DSLNode<S&g

20、t; cur=header; DSLNode<S> newNode=null; while(cur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cur=cur.right; if(cur.right!=tailer&&pare(cur.right.link.data,data)=0) newNode=cur.right; break; if(cur.down=bottom) newNode=new DSLNode<S>(cur.right,b

21、ottom); newNode.link=new DSLLinkNode<S>(data,newNode); cur.right=newNode; size+; break; else if(cur.down.right!=tailer&&cur.down.right.right!=tailer &&cur.down.right.right.right!=tailer&& cur.down.right.right.right.right!=tailer&& cur.down.right.right.right.righ

22、t.right!=tailer&& .right.right.link.data,cur.right.link.data)<0) cur.right=new DSLNode<S>(cur.right,cur.down.right.right.right,cur.down.right.right.right.link); cur.right.link.top=cur.right; cur.right.link.levelNum+; cur=cur.down; if(header.right!=tailer) header.link.levelNum+; head

23、er.link.top=header; header=new DSLNode<S>(tailer,header,header.link); return newNode.link; /*刪除數(shù)據(jù)data*/ public boolean remove(S data) throws IllegalParameterException if(data=null|size=0) return false; if(cp=null) if(Comparable.class.isAssignableFrom(data.getClass() CreateComparator<S> c

24、c =new CreateComparator<S>(); cp=cc.getComparator(); else throw new IllegalParameterException("數(shù)據(jù)不可以比較，請(qǐng)先設(shè)置比較器！"); DSLNode<S> cur=header; DSLNode<S> c=null,cc=null,top=null; while(cur!=bottom) while(cur.right!=tailer&&pare(cur.right.link.data,data)<0) cur=cur.r

25、ight; if(cur.down=bottom&&cur.right!=tailer&&pare(cur.right.link.data,data)=0) if(size=1) header=new DSLNode<S>(tailer,bottom,null,(byte)0); else if(cur.link.levelNum<cur.right.link.levelNum)/比較左右位置結(jié)點(diǎn)層數(shù)高低，待刪除的右邊結(jié)點(diǎn) c=cur.right.link.top; top=cur.right.link.top; cur.link.levelN

26、um=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.right!=c

27、ur.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; ret

28、urn false; /*獲取條件一維區(qū)間odr之間的元素集合,該函數(shù)主要服務(wù)于：KDSkipList<S>,用于檢索一維區(qū)間*/ public Collection<S> queryRegion(ODRegion<S> odr) Set<S> s=new HashSet<S>(); if(odr.isNoHasCondition) DSLNode<S> cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; while(cur!=tailer) i

29、f(cur.link.data instanceof KDSLNode) s.addAll(KDSLNode)cur.link.data).set); else s.add(cur.link.data); cur=cur.right; else DSLNode<S> cur=header; DSLNode<S> end=null; if(odr.start!=null) cur=this.searchStart(odr.start); else while(cur.down!=bottom) cur=cur.down; cur=cur.right; end=this.s

30、earchEnd(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 KDSLNode) s.addAll(KDSLNode)cur.link.data).set); else s.add(cur.link.data); cur=cur.right; return s; /*獲取條件一維區(qū)間odr之間的元素滿足多維條件的數(shù)據(jù)集合,inde

31、x為odr在qc中的位置, * 該函數(shù)主要服務(wù)于：MLDSkipList<S> 用于檢索多位區(qū)間*/ public Collection queryRegion(Collection s,ODRegion<S> odr,int index ,List<ODRegion<S>> qc,List<Comparator<S>> cps) if(s=null) return s; if(odr.isNoHasCondition) DSLNode<S> cur=header; while(cur.down!=bottom

32、) 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.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

33、(this.isMeetQC(cur.link.data, 0, qc.size(), qc, cps,index,true) s.add(cur.link.data); cur=cur.right; else DSLNode<S> cur=header; DSLNode<S> 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)

34、; 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.data; if(a.dslsl=null) if(this.isMeetQC(cur.link.data, index, qc.size(), qc, cps,index,true) s.add(a.data);

35、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; /*檢測(cè)元素o是否滿足多位區(qū)間條件qc,start為數(shù)組偏移索引,end為結(jié)束索引， * isFilterCondition表示是否忽略filterIndex標(biāo)識(shí)的位置的一維區(qū)間條件*/ protected boolean isMeetQ

36、C(S o,int start,int end,List<ODRegion<S>> qc,List<Comparator<S>> cps,int filterIndex, boolean isFilterCondition) for(int i=start;i<end;i+) if(qc.get(i).isNoHasCondition|(isFilterCondition&& i=filterIndex)|(qc.get(i).start=null&&qc.get(i).end=null) continue;

37、 if(qc.get(i).start!=null&&cps.get(i).compare(o, qc.get(i).start)<0)|(qc.get(i).end!=null&& cps.get(i).compare(o, qc.get(i).end)>0) return false; return true; /*返回表中元素的個(gè)數(shù)*/ public int size() return size; /*返回確定性跳躍表的層數(shù)*/ public int getLevel() return header.down = null ? 0:header

38、.down.link.levelNum; /*轉(zhuǎn)化為數(shù)組,若表中有0個(gè)元素返回null*/ public Object toArray() if(size=0) return null; Object o=new Objectsize; int i=0; DSLNode<S> 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; /*當(dāng)劃分跳表后更新跳表元素個(gè)數(shù)*/ publi

39、c void updateSize() int i=0; DSLNode<S> 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<S> cur=header; while(cur.down!=bottom) cur=cur.down; cur=cur.right; return cur=null ? null:cur.link.data; /*返回最小的元素并刪除,若不存在返回null*/ public S popMinData() throws IllegalParameterException if(size=0) return null; DSLNode<