云风的个人空间 : GoSegment

你的足迹: » GoSegment

对比 2011-03-09 02:18:26 和

To Top ::

XHTML 1.0 ::构建于

CooCooWakka 0.0.9rc1

@@ 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)
+}
+%%