注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

民主与科学

独立之人格,自由之思想

 
 
 

日志

 
 

id生成器  

2010-07-28 14:23:46|  分类: 数据存储 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
在android的Sqlite 中对于INTEGER PRIMARY KEY,
如果插入数据A,B,C,它们的_id为1,2,3,那么如果把他们都删除了,再插入一条数据,那么它的id为1而不是4。
因此我就写了这个工具来生成id,它能让生成相同的id相隔尽量的远。

SerialManager.java文件
package com.teleca;

public class SerialManager {
 Node root=null;
 long min=Long.MIN_VALUE;
 long max=Long.MAX_VALUE;
 long cursor=1;
 public SerialManager()
 {
 }
 public SerialManager(long min,long max)
 {
  if(min>max)
  {
   long temp=min;
   min=max;
   max=temp;
  }
  this.min=min;
  this.max=max;
 }
 
public void setSerial(long id,boolean flag)
 {
  long temp=0;
  Node node=findNode(id);
 
 if(flag)
  {
   if(node==null)
   {
    node=findNode(id-1);
   
 if(node!=null)
    {
     node.data.end=id;
     Node node2=findNode(id+1);
     
if(node2!=null)
     {
      node.data.end=node2.data.end;
      this.removeNode(node2);
     }
    }
    else
    {
     Node node2=findNode(id+1);
     if(node2!=null)
     {
      node2.data.start=id;
     }
     else
      addNewNode(id,id);
    }
   }
   return;
  }
  else
  {
   if(node==null)
    return;
   Block data=node.data;
   if(data.start==data.end)
   {
    removeNode(node);
   }
   else if(id==data.start)
    data.start=id+1;
   else if(id==data.end)
    data.end=id-1;
   else
   {
    temp=data.end;
    data.end=id-1;
    addNewNode(id+1,temp);
   }
   
  }
 }
 public void setSerial(long id1,long id2)
 {
  long temp=0;
  if(id1>id2)
  {
   temp=id1;
   id1=id2;
   id2=temp;
  }
  Node node1=findNode(id1);
  Node node2=null;
  if(node1==null)
  {
   node1=findNode(id1-1);
   if(node1!=null)
   {
    node1.data.end=id2;
    node2=findNode(id2+1);
    if(node2!=null)
    {
     node1.data.end=node2.data.end;
     this.removeNode(node2);
    }
    return;
   }
   else
   {
    node2=findNode(id2);
    if(node2==null)
    {
     node2=findNode(id2+1);
     if(node2!=null)
      node2.data.start=id1;
     else
      addNewNode(id1,id2);
     return;
    }
    else
    {
     node2.data.start=id1;
      return;
    }
   }
    
  }
  else
  {
   Block data=node1.data;
   if(id2<=data.end)
   {
    return;
   }
   else
   {
    node2=findNode(id2);
    if(node2==null)
    {
     data.end=id2;
     return;
    }
    else
    { 
     data.end=node2.data.end;
     removeNode(node2);
    }
   }
  }
 }
 public long getSerial()
 {
  
  Node node=findNode(cursor);
  long start=cursor;
  while(node!=null)
  {
   cursor=node.data.end+1;
   if(cursor>max)
    cursor=min;
   else if (cursor==0)
    cursor++;
   if(cursor==start)
   {
    return 0;
   }
   node=findNode(cursor);
  }
  long res=cursor;
  cursor++;
  if(cursor>max)
   cursor=min;
  else if (cursor==0)
   cursor++;
  return res; 
 }
 public boolean isKeyUsed(long id)
 {
  return findNode(id)!=null;
 }
 private Node findNode(long id)
 {
  Node node=null;
  Node tempNode=root;
  Block block=null;
  while(tempNode!=null)
  {
   block=tempNode.data;
   if(block.start<=id&&id<=block.end)
   {
    node=tempNode;
    break;
   }
   tempNode=tempNode.next;
  }
  return node;
 }
 private void addNewNode(long id1,long id2)
 {
  Node node=new Node();
  node.data=new Block(id1,id2);
  addNode(node);
 }
 private void addNode(Node node)
 {
  if(root==null)
  {
   root=node;
   node.prev=null;
   node.next=null;
   return;
  }
  Node tempNode=root;
  while(tempNode!=null)
  {
   if(tempNode.data.start>node.data.end)
   {
    if(tempNode==root)
    {
     node.prev=null;
     node.next=root;
     tempNode.prev=node;
     root=node;
    }
    else
    {
    node.prev=tempNode.prev;
    node.next=tempNode;
    tempNode.prev.next=node;
    tempNode.prev=node;
    }
    break;
   }
   else if(tempNode.next==null)
   {
    tempNode.next=node;
    node.prev=tempNode;
    node.next=null;
    break;
   }
   tempNode=tempNode.next;
   
  }
   
 }
 private void removeNode(Node node)
 {
  Node prev=node.prev;
  if(prev==null)
  {
   root=node.next;
  }
  else
  {
   prev.next=node.next;
  }
  if(node.next!=null)
   node.next.prev=prev;
  node.prev=null;
  node.next=null;
 }
 public void clear()
 {
  Node tempNode=root;
  Node node=null;
  while(tempNode!=null)
  {
   node=tempNode;
   tempNode=tempNode.next;
   node.prev=null;
   node.next=null;
   
  }
  root=null;
  cursor=1;
 }
 public void println()
 {
  Node tempNode=root;
  while(tempNode!=null)
  {
   System.out.println("start:"+tempNode.data.start+"end:"+tempNode.data.end);
   tempNode=tempNode.next;
   
  }  
 }
}
class Node
{
 Node prev=null;
 Block data;
 Node next=null;
}
class Block
{
 long start=0;
 long end=0;
 Block(long id1,long id2)
 {
  start=id1;
  end=id2;
 }
 public long getStart() {
  return start;
 }
 public void setStart(long start) {
  this.start = start;
 }
 public long getEnd() {
  return end;
 }
 public void setEnd(long end) {
  this.end = end;
 }
}

测试程序如下:
import java.util.Random;
import com.teleca.SerialManager;

public class test implements Runnable{
static Random random =new Random(System.currentTimeMillis());
static long buffer[]=new long [10];
static int index=0;
static long counter[]=new long [100];
static int countIndex=0;
static SerialManager serialManager= new SerialManager(Short.MIN_VALUE,Short.MAX_VALUE);
public void run()
{
 int i=0;
 for(i=0;i<100;i++)
  serialManager.setSerial(random.nextLong()%Short.MAX_VALUE, true);
 long temp=0;
 boolean blErro=false;
 boolean blRun=true;
 while(blRun)
 {
  temp=serialManager.getSerial();
  for(int j=0;j<buffer.length;j++)
  {
   if(buffer[j]!=0&&buffer[j]==temp)
   {
    
    blErro=true;
    break;
   }
  }
  if(temp==0)
  {
   blErro=true;
   System.out.println("all serial has been used");
  }
  if(blErro)
   break;
  buffer[index]=temp;
  serialManager.setSerial(buffer[index], true);
  long val=0;
  for(i=0;i<buffer.length;i++)
  {
   val=random.nextLong()%buffer.length;
   if(val<0)
    val=-val;
   val=buffer[(int)val];
   if(val==0||serialManager.isKeyUsed(val))
    break;
  }
  serialManager.setSerial(val, false);
  index++;
  index=index%buffer.length;
  if(counter[countIndex]++>=Short.MAX_VALUE)
  {
   countIndex++;
   System.out.println("countIndex:"+countIndex);
   if(countIndex>=counter.length)
   {
    blRun=false;
    countIndex=counter.length-1;
   }
  }
  if(counter[countIndex]%1000==0)
  {
   System.out.println(temp+"countIndex:"+countIndex+"num:"+counter[countIndex]);
   try{
    Thread.sleep(1);
   }catch(Exception e)
   {
    e.printStackTrace();
   }
  }
 
 }
 if(blErro)
 {
  System.out.println("erro:---------"+temp);
  serialManager.println();
 }
 else
  System.out.println("It passed the test!");
}
 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub 
  Thread t=new Thread(new test());
  t.start();
 }
}
  评论这张
 
阅读(1200)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017