// Copyright 2014, 2015 by Sascha L. Teichmann // Use of this source code is governed by the MIT license // that can be found in the LICENSE file. package common import ( "bytes" "fmt" ) const chunkSize = 1024 type Span struct { Value int32 From int32 To int32 Next *Span } type SpanPool struct { freeList *Span } func NewSpanPool() *SpanPool { return &SpanPool{} } func (sp *SpanPool) Alloc() *Span { if sp.freeList != nil { next := sp.freeList sp.freeList = next.Next return next } spans := make([]Span, chunkSize) for i := chunkSize - 1; i > 0; i-- { spans[i].Next = sp.freeList sp.freeList = &spans[i] } return &spans[0] } func (sp *SpanPool) Free(s *Span) { if s != nil { s.Next = sp.freeList sp.freeList = s } } func (sp *SpanPool) FreeAll(s *Span) { if s == nil { return } head, prev := s, s for ; s != nil; s = s.Next { prev = s } prev.Next = sp.freeList sp.freeList = head } func (sp *SpanPool) Insert(s *Span, pos, value int32) *Span { // No head -> create. if s == nil { s = sp.Alloc() s.From = pos s.To = pos s.Value = value s.Next = nil return s } if pos < s.From { // Same value and directly neighbored -> extend head. if value == s.Value && pos == s.From-1 { s.From = pos return s } // Disjunct -> create new head. prev := sp.Alloc() prev.From = pos prev.To = pos prev.Value = value prev.Next = s return prev } head := s for ; s != nil && pos > s.To; s = s.Next { next := s.Next if pos == s.To+1 && value == s.Value { // directly neighbored s.To = pos // Check if a gap has to be closed if next != nil && next.From == s.To+1 && value == next.Value { s.To = next.To s.Next = next.Next sp.Free(next) } return head } // Extend next? if next != nil && pos == next.From-1 && value == next.Value { next.From = pos return head } // Before next -> New between current and next if next == nil || pos < next.From { sn := sp.Alloc() sn.From = pos sn.To = pos sn.Value = value sn.Next = next s.Next = sn return head } } return head } func (s *Span) Visit(v func(*Span)) { for ; s != nil; s = s.Next { v(s) } } func (s *Span) Len() int { n := 0 for ; s != nil; s = s.Next { n++ } return n } func (s *Span) Top() int32 { for ; s.Next != nil; s = s.Next { } return s.To } func (s *Span) String() string { var buf bytes.Buffer first := true s.Visit(func(s1 *Span) { if !first { buf.WriteString(", ") } else { first = false } buf.WriteString(fmt.Sprintf("(%d, %d)", s1.From, s1.To)) }) return buf.String() }