data_structure

Documentation

Index

• type Convertable
• type FRecordSpace
  • func NewFRecordSpace(options ...FRecordSpaceOption) *FRecordSpace
  • func (s *FRecordSpace) Flush() map[string]int
  • func (s *FRecordSpace) Insert(record FileRecord) error
• type FRecordSpaceOption
  • func WithMaxRecordNum(N int) FRecordSpaceOption
  • func WithTempPath(path string) FRecordSpaceOption
• type FileReader
• type FileRecord
• type FileRecordHeap
  • func (frh FileRecordHeap) Len() int
  • func (frh FileRecordHeap) Less(i, j int) bool
  • func (frh *FileRecordHeap) Pop() interface{}
  • func (frh *FileRecordHeap) Push(x interface{})
  • func (frh FileRecordHeap) Swap(i, j int)
• type MergeTree
  • func (mt *MergeTree) Insert(node MergeTreeNode)
  • func (mt *MergeTree) Merge(nodeName string, k int) ([]string, int)
• type MergeTreeNode
• type RaceTree
  • func NewEmptyRaceTree(N int) RaceTree
  • func NewRaceTree(records []FileRecord) RaceTree
  • func (tree RaceTree) Adjust(i int)
  • func (tree RaceTree) Peak() (FileRecord, int)
  • func (tree RaceTree) Put(record FileRecord, idx int)
• type Sortable

Types

type Convertable

type Convertable interface {
	Convert(s string) (FileRecord, error)
}

Convertable 是将文本转化为一条数据记录的工具

type FRecordSpace

type FRecordSpace struct {
	N int // 最大记录数量
	// contains filtered or unexported fields
}

选择置换排序所用空间

func NewFRecordSpace

func NewFRecordSpace(options ...FRecordSpaceOption) *FRecordSpace

func (*FRecordSpace) Flush

func (s *FRecordSpace) Flush() map[string]int

将记录立刻全部保存到磁盘上

func (*FRecordSpace) Insert

func (s *FRecordSpace) Insert(record FileRecord) error

将记录有序插入到游程文件中

type FRecordSpaceOption

type FRecordSpaceOption func(*FRecordSpace)

func WithMaxRecordNum

func WithMaxRecordNum(N int) FRecordSpaceOption

func WithTempPath

func WithTempPath(path string) FRecordSpaceOption

type FileReader

type FileReader interface {
	Read() (string, error)
	ChangeSource(source *os.File)
	Copy() FileReader
}

FileReader 定义了从文件中读取文本, 且一次读取相当于一条记录的文本的方法

type FileRecord

type FileRecord interface {
	Sortable
	String() string
}

FileRecord 是从文件中读取到的文本转化为的数据记录, 一条记录必须满足: 1. 可排序(即, 可以与另一条记录比较大小) 2. 可转化为文本, 从而输出到结果文件中

type FileRecordHeap

type FileRecordHeap []FileRecord

文件类型的小根堆

func (FileRecordHeap) Len

func (frh FileRecordHeap) Len() int

func (FileRecordHeap) Less

func (frh FileRecordHeap) Less(i, j int) bool

func (*FileRecordHeap) Pop

func (frh *FileRecordHeap) Pop() interface{}

func (*FileRecordHeap) Push

func (frh *FileRecordHeap) Push(x interface{})

func (FileRecordHeap) Swap

func (frh FileRecordHeap) Swap(i, j int)

type MergeTree

type MergeTree []MergeTreeNode

MergeTree 合并树数据结构 (Huffman Tree)

func (*MergeTree) Insert

func (mt *MergeTree) Insert(node MergeTreeNode)

Insert 将合并树节点插入合并树

func (*MergeTree) Merge

func (mt *MergeTree) Merge(nodeName string, k int) ([]string, int)

Merge 将合并树中权重最小的K个节点合并, 合并后新的节点名称为nodeName 返回被合并的节点名称和实际合并的节点数量

type MergeTreeNode

type MergeTreeNode struct {
	FileName string // 待合并文件名称
	Weight   int    // 待合并文件在合并树中的权重
}

MergeTreeNode 合并树节点

type RaceTree

type RaceTree []FileRecord

func NewEmptyRaceTree

func NewEmptyRaceTree(N int) RaceTree

func NewRaceTree

func NewRaceTree(records []FileRecord) RaceTree

初始化PK树, 用于初始化的记录数组必须长度为偶数

func (RaceTree) Adjust

func (tree RaceTree) Adjust(i int)

func (RaceTree) Peak

func (tree RaceTree) Peak() (FileRecord, int)

func (RaceTree) Put

func (tree RaceTree) Put(record FileRecord, idx int)

type Sortable

type Sortable interface {
	CompareTo(s Sortable) int
}

Sortable 定义了CompareTo方法, 该方法将本Sortable数据与s比较 返回值>0或=0或<0分别代表本数据大于/等于/小于s