segmenttree

Documentation

Overview

*

• 这是线段树的内部类，用于实现单维线段树

*

• 仅在包内使用，因此对于负无穷和正无穷的判断会省略掉

Index

• Constants
• Variables
• type Cut
• type Endpoint
• type EndpointType
• type Entry
• type ImmutableSegmentTree
• type IntegerRange
• type Interval
• type Intervals
• type SegmentTree
  • func (t *SegmentTree) Query(intervals ...Interval) []Value
• type SortableEndpoints
  • func (s *SortableEndpoints) Len() int
  • func (s *SortableEndpoints) Less(i, j int) bool
  • func (s *SortableEndpoints) Swap(i, j int)
• type SubTree
• type Tree
  • func New(dimension int, entries ...Entry) (Tree, error)
• type TypedEndpoint
• type Value

Constants

const (
	POSITIVE_INFINITY = int64(^uint64(0) >> 1)
	NEGATIVE_INFINITY = -POSITIVE_INFINITY - 1
)

Variables

var (
	RANGE_ALL   = IntegerRange{Cut{NEGATIVE_INFINITY, false}, Cut{POSITIVE_INFINITY, false}}
	RANGE_EMPTY = IntegerRange{Cut{0, false}, Cut{0, false}}
)

var (
	InvalidDimension           = errors.New("Invalid dimension")
	InsufficientIntervalLength = errors.New("Insufficient interval length")
)

Types

type Cut

type Cut struct {
	// contains filtered or unexported fields
}

type Endpoint

type Endpoint = int64

type EndpointType

type EndpointType = int

const (
	OPEN         EndpointType = iota // ...) endpoint (...
	LEFT_CLOSED                      // ...) [endpoint ...
	RIGHT_CLOSED                     // ... endpoint] (...
)

type Entry

type Entry struct {
	Intervals Intervals
	Value     Value
}

type ImmutableSegmentTree

type ImmutableSegmentTree struct {
	// contains filtered or unexported fields
}

type IntegerRange

type IntegerRange struct {
	// contains filtered or unexported fields
}

type Interval

type Interval interface {
	Lower() (Endpoint, bool)
	Upper() (Endpoint, bool)
}

type Intervals

type Intervals = []Interval

type SegmentTree

type SegmentTree struct {
	// contains filtered or unexported fields
}

func (*SegmentTree) Query

func (t *SegmentTree) Query(intervals ...Interval) []Value

type SortableEndpoints

type SortableEndpoints struct {
	// contains filtered or unexported fields
}

func (*SortableEndpoints) Len

func (s *SortableEndpoints) Len() int

func (*SortableEndpoints) Less

func (s *SortableEndpoints) Less(i, j int) bool

func (*SortableEndpoints) Swap

func (s *SortableEndpoints) Swap(i, j int)

type SubTree

type SubTree struct {
	// contains filtered or unexported fields
}

type Tree

type Tree interface {
	Query(...Interval) []Value
}

func New

func New(dimension int, entries ...Entry) (Tree, error)

type TypedEndpoint

type TypedEndpoint struct {
	// contains filtered or unexported fields
}

type Value

type Value interface {
	Id() uint64 // unique number for identification
}