云风的个人空间 : GoSegment

首页 :: 索引 :: 修订历史 :: 你好, 3.92.28.52
你的足迹: » GoSegment
对比 2011-03-09 02:18:26
2011-03-09 02:18:26 CloudWu
1: 1:
 +%%
 +package main
 +import "fmt"
 +
 +type segment struct {
 + length int64
 + data []int64
 +}
 +
 +func newSegment(length int64) * segment {
 + s := &segment { length , make([]int64,1,8) }
 + s.data[0] = length
 + return s
 +}
 +
 +func (s *segment) insert(from int64 , size int64) (large bool) {
 + large = false
 + if size <= 0 {
 + panic("invalid argment")
 + }
 + if from > s.length {
 + panic("invalid argment")
 + }
 + if from < 0 {
 + panic("invalid argment")
 + }
 + end := from + size
 + if end > s.length {
 + panic("invalid argment")
 + }
 + var i int
 + for i=0;i<len(s.data);i++ {
 + if from < s.data[i] {
 + break
 + }
 + }
 + if i%2 == 0 {
 + if end <= s.data[i] {
 + if cap(s.data) < len(s.data)+2 {
 + t:=make([]int64, len(s.data)+2)
 + copy(t,s.data)
 + s.data = t
 + } else {
 + s.data = s.data[:len(s.data)+2]
 + }
 + copy(s.data[i+2:],s.data[i:])
 + s.data[i] = from
 + s.data[i+1] = end
 + } else {
 + s.data[i] = from
 + if end <= s.data[i+1] {
 + return
 + } else if end <= s.data[i+2] {
 + s.data[i+1] = end;
 + return
 + } else {
 + var j int
 + for j=i+3;j<len(s.data);j++ {
 + if end <= s.data[j] {
 + break
 + }
 + }
 + i++
 + if j%2 == 0 {
 + s.data[i] = end
 + i++
 + }
 + copy(s.data[i:],s.data[j:])
 + s.data = s.data[:len(s.data)-(j-i)]
 + }
 + }
 + } else {
 + if end <= s.data[i] {
 + return
 + }
 + if end <= s.data[i+1] {
 + s.data[i] = end
 + return
 + }
 + var j int
 + for j=i+2;j<len(s.data);j++ {
 + if end <= s.data[j] {
 + break
 + }
 + }
 + if j%2 == 0 {
 + s.data[i] = end
 + i++
 + }
 + copy(s.data[i:],s.data[j:])
 + s.data = s.data[:len(s.data)-(j-i)]
 + }
 +
 + return
 +}
 +
 +func (s *segment) white() int64 {
 + t := s.data[0]
 + for i:=2;i<len(s.data);i+=2 {
 + t+=s.data[i]-s.data[i-1]
 + }
 + return t
 +}
 +
 +func (s *segment) dump() {
 + fmt.Printf("[0,%d) ",s.data[0])
 + for i:=2;i<len(s.data);i+=2 {
 + fmt.Printf("[%d,%d) ",s.data[i-1],s.data[i])
 + }
 + fmt.Printf("%d\n",s.white())
 +}
 +
 +func (s *segment)ins(from int64,end int64) {
 + fmt.Printf("insert %d,%d ",from,end)
 + s.insert(from,end-from)
 + s.dump()
 +}
 +
 +func main() {
 + s := newSegment(100)
 + s.ins(0,100)
 + s.ins(20,50)
 + s.ins(30,40)
 + s.ins(0,10)
 + s.ins(45,60)
 + s.ins(70,80)
 + s.ins(5,75)
 + s.ins(15,75)
 +}
 +%%