mtsatellite/common/spans.go

// 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()
}