merge

package
Version: v0.0.0-...-59788d5 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Feb 11, 2015 License: Apache-2.0 Imports: 4 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Comparator

type Comparator interface {
	// Compare will return a value indicating how this comparator
	// compares with the provided comparator.  A negative number
	// indicates this comparator is less than the provided comparator,
	// a 0 indicates equality, and a positive number indicates this
	// comparator is greater than the provided comparator.
	Compare(Comparator) int
}

Comparator defines items that can be sorted. It contains a single method allowing the compare logic to compare one comparator to another.

type Comparators

type Comparators []Comparator

Comparators defines a typed list of type Comparator.

func MultithreadedSortComparators

func MultithreadedSortComparators(comparators Comparators) Comparators

MultithreadedSortComparators will take a list of comparators and sort it using as many threads as are available. The list is split into buckets for a bucket sort and then recursively merged using SymMerge.

func SymMerge

func SymMerge(u, w Comparators) Comparators

SymMerge will perform a symmetrical merge of the two provided lists. It is expected that these lists are pre-sorted. Failure to do so will result in undefined behavior. This function does make use of goroutines, so multithreading can aid merge time. This makes M*log(N/M+1) comparisons where M is the length of the shorter list and N is the length of the longer list.

func (Comparators) Len

func (c Comparators) Len() int

Len returns an int indicating the length of this list of comparators.

func (Comparators) Less

func (c Comparators) Less(i, j int) bool

Less returns a bool indicating if the comparator at index i is less than the comparator at index j.

func (Comparators) Swap

func (c Comparators) Swap(i, j int)

Swap swaps the values at positions i and j.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL