avltree

package module
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Dec 17, 2021 License: MIT Imports: 0 Imported by: 1

README

avltree

概要

AVL木の構築と操作をするパッケージ？

注意点
  • 本パッケージが正しくAVL木として機能しているかは未確認
  • 性能(実行速度やメモリの扱い)が壊滅的なので実用性は皆無
  • キーや値の型の検査などは一切していないので利用者側で統一させる必要がある
  • キーの不変性も利用者側で確保する必要がある
  • サブツリーやノードを操作するための処理は無い
利用方法

利用者側でインターフェースのRealTree,RealNode,Keyの実装を用意しそれを本パッケージの関数で操作などをする

RealTree,RealNodeの実装例を以下のサブパッケージに置いてある

github.com/neetsdkasu/avltree/simpletree        最低限の実装のみ
github.com/neetsdkasu/avltree/standardtree      ノード数の保持や親ノード参照などの機能がある
github.com/neetsdkasu/avltree/immutabletree     木の構造の部分だけは不変ぽくなるように実装されている(キーと値の不変性は取り扱わない)
github.com/neetsdkasu/avltree/intarraytree      int型の配列上に木が構築されるように実装(キーはintkeyの実装のみ、値もint型のみ)

Keyの実装例を以下のサブパッケージに置いてある

github.com/neetsdkasu/avltree/intkey            int型をKeyとして使えるよう実装
github.com/neetsdkasu/avltree/stringkey         string型をKeyとして使えるよう実装

木の実装を内包し本パッケージの関数をメソッド経由で呼び出す、所謂"ラッパー"の実装例を以下のサブパッケージに置いてある

github.com/neetsdkasu/avltree/simplewrapper     簡易に実装したラッパー
github.com/neetsdkasu/avltree/intwrapper        キーも値もint型に強制するラッパー

コード例


import (
	"fmt"

	"github.com/neetsdkasu/avltree"
	. "github.com/neetsdkasu/avltree/intkey"
	"github.com/neetsdkasu/avltree/simpletree"
)

func Example() {
	tree := simpletree.New(false)
	avltree.Insert(tree, false, IntKey(12), 345)
	avltree.Insert(tree, false, IntKey(67), 890)
	avltree.Insert(tree, false, IntKey(333), 666)
	avltree.Insert(tree, false, IntKey(-5), 12345)
	avltree.Delete(tree, IntKey(67))
	avltree.Update(tree, IntKey(333), func(key avltree.Key, oldValue interface{}) (newValue interface{}, keepOldValue bool) {
		newValue = oldValue.(int) * 3
		return
	})
	if node := avltree.Find(tree, IntKey(12)); node != nil {
		fmt.Println("Find!", node.Key(), node.Value())
	}
	avltree.Iterate(tree, false, func(node avltree.Node) (breakIteration bool) {
		fmt.Println("Iterate!", node.Key(), node.Value())
		return
	})
	// Output:
	// Find! 12 345
	// Iterate! -5 12345
	// Iterate! 12 345
	// Iterate! 333 1998
}

ラッパーを使ったコード例


import (
	"fmt"

	"github.com/neetsdkasu/avltree"
	. "github.com/neetsdkasu/avltree/intkey"
	"github.com/neetsdkasu/avltree/simpletree"
	"github.com/neetsdkasu/avltree/simplewrapper"
)

func Example_wrapper() {
	tree := simpletree.New(false)
	w := simplewrapper.New(tree)
	w.Insert(IntKey(12), 345)
	w.Insert(IntKey(67), 890)
	w.Insert(IntKey(333), 666)
	w.Insert(IntKey(-5), 12345)
	w.Delete(IntKey(67))
	w.Update(IntKey(333), func(key avltree.Key, oldValue interface{}) (newValue interface{}, keepOldValue bool) {
		newValue = oldValue.(int) * 3
		return
	})
	if node := w.Find(IntKey(12)); node != nil {
		fmt.Println("Find!", node.Key(), node.Value())
	}
	w.Iterate(func(node avltree.Node) (breakIteration bool) {
		fmt.Println("Iterate!", node.Key(), node.Value())
		return
	})
	// Output:
	// Find! 12 345
	// Iterate! -5 12345
	// Iterate! 12 345
	// Iterate! 333 1998
}

Documentation

Overview

概要 AVL木の構築と操作をするパッケージ？

注意点 本パッケージが正しくAVL木として機能しているかは未確認 性能(実行速度やメモリの扱い)が壊滅的なので実用性は皆無 キーや値の型の検査などは一切していないので利用者側で統一させる必要がある キーの不変性も利用者側で確保する必要がある サブツリーやノードを操作するための処理は無い

利用方法 利用者側でインターフェースのRealTree,RealNode,Keyの実装を用意しそれを本パッケージの関数で操作などをする

RealTree,RealNodeの実装例を以下のサブパッケージに置いてある 

github.com/neetsdkasu/avltree/simpletree        最低限の実装のみ
github.com/neetsdkasu/avltree/standardtree      ノード数の保持や親ノード参照などの機能がある
github.com/neetsdkasu/avltree/immutabletree     木の構造の部分だけは不変性になるように実装されている(キーと値の不変性は取り扱わない)
github.com/neetsdkasu/avltree/intarraytree      int型の配列上に木が構築されるように実装(キーはintkeyの実装のみ、値もint型のみ)

Keyの実装例を以下のサブパッケージに置いてある 

github.com/neetsdkasu/avltree/intkey            int型をKeyとして使えるよう実装
github.com/neetsdkasu/avltree/stringkey         string型をKeyとして使えるよう実装

木の実装を内包し本パッケージの関数をメソッド経由で呼び出す、所謂"ラッパー"の実装例を以下のサブパッケージにおいてある 

github.com/neetsdkasu/avltree/simplewrapper     簡易に実装したラッパー
github.com/neetsdkasu/avltree/intwrapper        キーも値もint型に強制するラッパー

コード例 

import (
	"fmt"
	"github.com/neetsdkasu/avltree"
	. "github.com/neetsdkasu/avltree/intkey"
	"github.com/neetsdkasu/avltree/simpletree"
)
func Example() {
	tree := simpletree.New(false)
	avltree.Insert(tree, false, IntKey(12), 345)
	avltree.Insert(tree, false, IntKey(67), 890)
	avltree.Insert(tree, false, IntKey(333), 666)
	avltree.Insert(tree, false, IntKey(-5), 12345)
	avltree.Delete(tree, IntKey(67))
	avltree.Update(tree, IntKey(333), func(key avltree.Key, oldValue interface{}) (newValue interface{}, keepOldValue bool) {
		newValue = oldValue.(int) * 3
		return
	})
	if node := avltree.Find(tree, IntKey(12)); node != nil {
		fmt.Println("Find!", node.Key(), node.Value())
	}
	avltree.Iterate(tree, false, func(node avltree.Node) (breakIteration bool) {
		fmt.Println("Iterate!", node.Key(), node.Value())
		return
	})
	// Output:
	// Find! 12 345
	// Iterate! -5 12345
	// Iterate! 12 345
	// Iterate! 333 1998
}

ラッパーを使ったコード例 

import (
	"fmt"
	"github.com/neetsdkasu/avltree"
	. "github.com/neetsdkasu/avltree/intkey"
	"github.com/neetsdkasu/avltree/simpletree"
	"github.com/neetsdkasu/avltree/simplewrapper"
)
func Example_wrapper() {
	tree := simpletree.New(false)
	w := simplewrapper.New(tree)
	w.Insert(IntKey(12), 345)
	w.Insert(IntKey(67), 890)
	w.Insert(IntKey(333), 666)
	w.Insert(IntKey(-5), 12345)
	w.Delete(IntKey(67))
	w.Update(IntKey(333), func(key avltree.Key, oldValue interface{}) (newValue interface{}, keepOldValue bool) {
		newValue = oldValue.(int) * 3
		return
	})
	if node := w.Find(IntKey(12)); node != nil {
		fmt.Println("Find!", node.Key(), node.Value())
	}
	w.Iterate(func(node avltree.Node) (breakIteration bool) {
		fmt.Println("Iterate!", node.Key(), node.Value())
		return
	})
	// Output:
	// Find! 12 345
	// Iterate! -5 12345
	// Iterate! 12 345
	// Iterate! 333 1998
}

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Alter 

func Alter(tree Tree, key Key, callBack AlterNodeCallBack) (modified Tree, deletedValue KeyAndValue, ok bool)

指定したキーを持つノードの値を変更またはノードを削除する 指定のキーが存在しない場合は木に変更は加えない 木が同一キーのノードを許可している場合は指定キーを持つノードのうち最初に見つかったノード(同一キーのノードのうち高さが最も高いノード)が変更の対象となる 戻り値のmodifiedは対象のノードが存在しコールバックの戻り値で変更か削除を指定された場合はRealTreeのSetRootメソッドの戻り値となり、それ以外の場合は引数のtreeがそのまま返却される 戻り値のdeletedValueは削除したノードのキーと値を持っている 戻り値のokは対象のノードが存在しコールバックの戻り値で変更か削除を指定された場合にtrueとなり、それ以外の場合はfalseとなる

func AlterAll 

func AlterAll(tree Tree, key Key, callBack AlterNodeCallBack) (modified Tree, deletedValues []KeyAndValue, ok bool)

同一キーを持つノードが複数ある場合のAlterの強化版 指定したキーを持つ全てのノードに対してコールバックが呼び出される

func AlterIterate 

func AlterIterate(tree Tree, descOrder bool, callBack AlterIterateCallBack) (modified Tree, deletedValues []KeyAndValue, ok bool)

AlterとIterateを組み合わせた感じ 巡っていく各ノードに対してコールバックが呼ばれる

func AlterRange 

func AlterRange(tree Tree, descOrder bool, lower, upper Key, callBack AlterNodeCallBack) (modified Tree, deletedValues []KeyAndValue, ok bool)

AlterとRangeを組み合わせた感じ lower以上upper以下のキーを持つノードそれぞれに順にコールバックが呼ばれる

func AlterRangeIterate 

func AlterRangeIterate(tree Tree, descOrder bool, lower, upper Key, callBack AlterIterateCallBack) (modified Tree, deletedValues []KeyAndValue, ok bool)

UpdateとRangeIterateを組み合わせた感じ lower以上upper以下のキーを持つノードに順にコールバックが呼ばれる

func Count 

func Count(tree Tree) int

木を構成するノードの総数を求める 木またはノードがインターフェースNodeCounterを実装している場合はNodeCountメソッドの戻り値をそのまま返す

func CountRange 

func CountRange(tree Tree, lower, upper Key) int

キーの順序でlower以上upper以下の範囲にあるノード総数を求める

func Delete 

func Delete(tree Tree, key Key) (modified Tree, deleteValue KeyAndValue)

指定のキーを持つノードを木から削除する(木から取り除く) 指定のキーが存在しない場合は木に変更は加えない 木が同一キーのノードを許可している場合は指定キーを持つノードのうち最初に見つかったノード(同一キーのノードのうち高さが最も高いノード)が削除される 戻り値のmodifiedは木に変更があった場合はRealTreeのSetRootメソッドの戻り値となり、変更がない場合は引数のtreeがそのまま返却される 戻り値のdeletedValueは削除したノードのキーと値を持っている

func DeleteAll 

func DeleteAll(tree Tree, key Key) (modified Tree, deletedvalues []KeyAndValue)

同一キーを持つノードが複数ある場合のDeleteの強化版 指定したキーを持つ全てのノードを木から削除する

func DeleteIterate 

func DeleteIterate(tree Tree, descOrder bool, callBack DeleteIterateCallBack) (modified Tree, values []KeyAndValue)

DeleteとIterateを組み合わせた感じ コールバックの戻り値で削除対象となるノードを決定していく

func DeleteRange 

func DeleteRange(tree Tree, descOrder bool, lower, upper Key) (modified Tree, values []KeyAndValue)

DeleteとRangeを組み合わせた感じ lower以上upper以下のキーを持つノード全てを削除する

func DeleteRangeIterate 

func DeleteRangeIterate(tree Tree, descOrder bool, lower, upper Key, callBack DeleteIterateCallBack) (modified Tree, values []KeyAndValue)

DeleteとRangeIterateを組み合わせた感じ lower以上upper以下のキーを持つノードに対して順にコールバックが呼ばれる コールバックの戻り値で削除対象となるノードを決定していく

func Iterate 

func Iterate(tree Tree, descOrder bool, callBack IterateCallBack) (ok bool)

木のノードを順に巡ってコールバックを呼び出す descOrderがfalseのときはキーの昇順 descOrderがtrueのときはキーの降順 戻り値のokはコールバックから中断を要求されなかった場合はtrue、中断を要求された場合はfalse

func RangeIterate 

func RangeIterate(tree Tree, descOrder bool, lower, upper Key, callBack IterateCallBack) (ok bool)

木のノードをキーの順序でlower以上upper以下の範囲を順に巡ってコールバックを呼び出す descOrderがfalseのときはキーの昇順 descOrderがtrueのときはキーの降順 戻り値のokはコールバックから中断を要求されなかった場合はtrue、中断を要求された場合はfalse

func Release 

func Release(tree *Tree)

木のインスタンスを解放(または破棄)する 木がインターフェースTreeReleaserを実装している場合にのみ機能する 解放の全ての処理が終わったあと引数のtreeの参照先にはnilが代入される

Types

type AlterIterateCallBack 

type AlterIterateCallBack = func(node AlterNode) (request AlterRequest, breakIteration bool)

木のノードを順に巡りノードの値の更新またはノードを削除をするAlterIterate,AlterRangeIterateの引数で渡す return node.Keep()またはrequest.Keep()でノードに変更を加えない指示となる return node.Replace(newValue)またはrequest.Replace(newValue)で値をnewValueに更新する指示となる return node.Delete()またはrequest.Delete()でノードを削除をする指示となる breakIterationをtrueにしたときにイテレーションを中断する

type AlterNode 

type AlterNode interface {
	KeyAndValue

	// ノードに対して変更や削除の操作をしないことを指定するAlterRequestを生成する
	Keep() AlterRequest

	// ノードの値を指定した値へ置き換えることを指定するAlterRequestを生成する
	Replace(newValue interface{}) AlterRequest

	// ノードを削除することを指定するAlterRequestを生成する
	Delete() AlterRequest
}

Alterのコールバックの引数で受け取るノード情報 コールバックの戻り値のAlterRequestを生成できるメソッドも実装している

type AlterNodeCallBack 

type AlterNodeCallBack = func(node AlterNode) (request AlterRequest)

指定のキーの値の更新またはノードを削除をするAlter,AlterAll,AlterRangeの引数で渡す return node.Keep()またはrequest.Keep()でノードに変更を加えない指示となる return node.Replace(newValue)またはrequest.Replace(newValue)で値をnewValueに更新する指示となる return node.Delete()またはrequest.Delete()でノードを削除をする指示となる

type AlterRequest 

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

Alterのコールバックの戻り値で使用する ノードに対する処理の情報を保持する

func (*AlterRequest) Delete 

func (request *AlterRequest) Delete() (ret AlterRequest)

ノードを削除することを指定する

func (*AlterRequest) Keep 

func (request *AlterRequest) Keep() (ret AlterRequest)

ノードを変更も削除もせず維持することを指定する

func (*AlterRequest) Replace 

func (request *AlterRequest) Replace(newValue interface{}) (ret AlterRequest)

ノードの値をnewValueに置き換えることを指定する

type DeleteIterateCallBack 

type DeleteIterateCallBack = func(key Key, value interface{}) (deleteNode, breakIteration bool)

木のノードを順に巡りノードの削除判定をするDeleteIterate,DeleteRangeIterateの引数で渡す deleteNodeをtrueに設定すると当該ノードを削除する breakIterationをtrueにしたときにイテレーションを中断する

type IterateCallBack 

type IterateCallBack = func(node Node) (breakIteration bool)

木のノードを順に参照するIterate,RangeIterateの引数で渡す breakIterationをtrueにしたときにイテレーションを中断する

type Key 

type Key interface {
	// キーの順序(比較結果)を返却する必要がある
	CompareTo(other Key) KeyOrdering

	// キーのコピーが返却されることが期待される
	// RealTreeのNewNodeメソッドの引数に渡すときにこのCopyメソッドが呼ばれる
	Copy() Key
}

AVL木でノードの比較に使うキーのインターフェース

type KeyAndValue 

type KeyAndValue interface {
	// ノードに設定されたキーを返却する
	Key() Key

	// ノードに設定された値を返却する
	Value() interface{}
}

type KeyOrdering 

type KeyOrdering int

キーの比較結果を表す型 

const (
	// CompareToメソッドの引数のotherよりレシーバのほうが小さい
	LessThanOtherKey KeyOrdering = -1

	// CompareToメソッドの引数のotherとレシーバは同じキー
	EqualToOtherKey KeyOrdering = 0

	// CompareToメソッドの引数のotherよりレシーバのほうが大きい
	GreaterThanOtherKey KeyOrdering = 1
)

func (KeyOrdering) EqualTo 

func (ordering KeyOrdering) EqualTo() bool

キーが比較対象(CompareToの引数のキー)と等しい場合にtrue、それ以外はfalse

func (KeyOrdering) Greater 

func (ordering KeyOrdering) Greater(orEqual bool) bool

GreaterThanメソッドとGreaterThanOrEqualToメソッドを引数のorEqualで使い分ける orEqualがtrueの場合、GreaterThanOrEqualToが呼ばれる orEqualがfalseの場合、GreaterThanが呼ばれる

func (KeyOrdering) GreaterThan 

func (ordering KeyOrdering) GreaterThan() bool

キーが比較対象(CompareToの引数のキー)より大きい場合にtrue、それ以外はfalse

func (KeyOrdering) GreaterThanOrEqualTo 

func (ordering KeyOrdering) GreaterThanOrEqualTo() bool

キーが比較対象(CompareToの引数のキー)以上の場合にtrue、それ以外はfalse

func (KeyOrdering) Less 

func (ordering KeyOrdering) Less(orEqual bool) bool

LessThanメソッドとLessThanOrEqualToメソッドを引数のorEqualで使い分ける orEqualがtrueの場合、LessThanOrEqualToが呼ばれる orEqualがfalseの場合、LessThanが呼ばれる

func (KeyOrdering) LessThan 

func (ordering KeyOrdering) LessThan() bool

キーが比較対象(CompareToの引数のキー)より小さい場合にtrue、それ以外はfalse

func (KeyOrdering) LessThanOrEqualTo 

func (ordering KeyOrdering) LessThanOrEqualTo() bool

キーが比較対象(CompareToの引数のキー)以下の場合にtrue、それ以外はfalse

func (KeyOrdering) NotEqualTo 

func (ordering KeyOrdering) NotEqualTo() bool

キーが比較対象(CompareToの引数のキー)と等しくない場合にtrue、それ以外はfalse

type Node 

type Node interface {
	KeyAndValue

	// このノードの左の子ノードが返却されることが期待される
	// 返却されるNodeはRealNodeを実装している必要がある
	// 左の子ノードが無い場合はreturn nilでnilを返却する必要がある
	LeftChild() Node

	// このノードの右の子のノードが返却されることが期待される
	// 返却されるNodeはRealNodeを実装している必要がある
	// 右の子ノードが無い場合はreturn nilでnilを返却する必要がある
	RightChild() Node

	// このノードに新しい値を設定する
	// 可変(mutable)の木の場合にはレシーバであるノード自身のインスタンスが返却されることが期待される
	// 不変(immutable)の木の場合にはレシーバと同じ設定を持ちnewValueの値を持つ新しいインスタンスのノードが返却されることが期待される
	// 返却されるNodeはRealNodeを実装している必要がある
	SetValue(newValue interface{}) Node
}

ノードの公開用の基本的なインターフェース デフォルトでアクセスできる範囲を制限するためだけの用途

func Find 

func Find(tree Tree, key Key) (node Node)

指定のキーを持つノードを取得する 指定のキーを持つノードが無い場合は戻り値nodeはnilになる 戻り値nodeは木の一部のままなのでこのnodeを編集すると木にも影響する 可変(mutable)の木の場合にはnodeの内容を変更する操作は木にも影響する 不変(immutable)の木の場合にはnodeのインターフェスNodeやRealNodeのメソッド呼び出しでは木に影響がないことが期待される

func FindAll 

func FindAll(tree Tree, key Key) (nodes []Node)

同一キーを持つノードが複数ある場合のFindの強化版 指定したキーを持つ全てのノードを取得する 指定のキーが存在しない場合はnilを返す

func Max 

func Max(tree Tree) (maximum Node)

キーの順序で最大となるキーを持つノードを返す 木にひとつもノードが無い場合はnilを返す 戻り値は木の一部のままなので編集すると木にも影響する

func MaxAll 

func MaxAll(tree Tree) (maximums []Node)

同一キーを持つノードが複数ある場合のMaxの強化版 最大のキーを持つ全てのノードを取得する 木にノードが存在しない場合はnilを返す

func Min 

func Min(tree Tree) (minimum Node)

キーの順序で最小となるキーを持つノードを返す 木にひとつもノードが無い場合はnilを返す 戻り値は木の一部のままなので編集すると木にも影響する

func MinAll 

func MinAll(tree Tree) (minimums []Node)

同一キーを持つノードが複数ある場合のMinの強化版 最小のキーを持つ全てのノードを取得する 木にノードが存在しない場合はnilを返す

func Range 

func Range(tree Tree, descOrder bool, lower, upper Key) (nodes []Node)

キーの順序でlower以上upper以下の範囲にあるノード全てを指定の順序で取得する descOrderがfalseのときはキーの昇順 descOrderがtrueのときはキーの降順

type NodeCounter 

type NodeCounter interface{ NodeCount() int }

木またはサブツリーのルートノードがノード数を保持する実装でその値を公開するためのメソッド このインターフェースが実装されている場合にCount,CountRangeの内部でNodeCountメソッドが呼び出される

type NodeReleaser 

type NodeReleaser interface {
	RealTree
	ReleaseNode(node RealNode)
}

木がこのインターフェースを実装している場合にDeleteなどの内部でRelaseNodeメソッドが呼び出される ノードが木から切り離された際にそのノードのインスタンスに対して何らかの処理をしたい場合に木側で実装する必要がある 例えばデータの切り離しやインスタンスの再利用やメモリの再利用・解放など(ノード本体のインスタンスやメモリのみの処理が実行されることが期待される) インターフェースRealNodeのNewNodeメソッドでのノード生成と対になる処理になることが期待される サブパッケージのintarraytreeではReleaseNodeでメモリの再利用のための処理を行っている

type ParentGetter 

type ParentGetter interface {
	Node
	Parent() Node
}

子ノードが親のノードを参照できる実装でその参照を公開するためのメソッド 本パッケージ内で使用される予定は今のところ無い…

type RealNode 

type RealNode interface {
	Node

	// このノードの高さを返却する必要がある
	// 高さはRealTreeのNewNodeメソッドまたはRealNodeのSetChildre,Setメソッドで設定された値
	Height() int

	// このノードの新しい高さとこのノードの左右の子を設定する
	// 引数のnewHeightは計算後の値なのでノードはそのままの値を保持する必要がある
	// newLeftChildで対応するノードが無い場合は引数にnilが渡される
	// newRightChildで対応するノードが無い場合は引数にnilが渡される
	// 可変(mutable)の木の場合にはレシーバであるノード自身のインスタンスが返却されることが期待される
	// 不変(immutable)の木の場合にはレシーバと同じ設定を持ち渡された引数の情報を持つ新しいインスタンスのノードが返却されることが期待される
	SetChildren(newLeftChild, newRightChild Node, newHeight int) RealNode

	// このノードの新しい値とこのノードの新しい高さとこのノードの左右の子を設定する
	// 引数のnewHeightは計算後の値なのでノードはそのままの値を保持する必要がある
	// newLeftChildで対応するノードが無い場合は引数にnilが渡される
	// newRightChildで対応するノードが無い場合は引数にnilが渡される
	// 可変(mutable)の木の場合にはレシーバであるノード自身のインスタンスが返却されることが期待される
	// 不変(immutable)の木の場合にはレシーバと同じ設定を持ち渡された引数の情報を持つ新しいインスタンスのノードが返却されることが期待される
	Set(newLeftChild, newRightChild Node, newHeight int, newValue interface{}) RealNode
}

本パッケージで操作するためにノードが実装するべきメソッド

type RealTree 

type RealTree interface {
	Tree

	// Insertなどで木に新しいノードを作る場合に呼び出される
	// 引数で渡された情報を持つノードが返却されることが期待される
	// leftChildで対応するノードが無い場合は引数にnilが渡される
	// rightChildで対応するノードが無い場合は引数にnilが渡される
	NewNode(leftChild, rightChild Node, height int, key Key, value interface{}) RealNode

	// 木のルートノードを設定する場合に呼び出される
	// 木にノードが全く無くなった場合はnewRootにnilが渡される
	// 可変(mutable)の木の場合にはレシーバである木自身のインスタンスが返却されることが期待される
	// 不変(immutable)の木の場合にはレシーバと同じ設定を持ちnewRootのルートノードを持つ新しいインスタンスの木が返却されることが期待される
	SetRoot(newRoot RealNode) RealTree

	// 木が同一のキーのノードを複数保持できるかどうかを返す
	// trueの場合、木が同一キーのノードを複数保持することを許可することを表す
	// falseの場合、木が同一キーのノードを複数保持することを許可しないことを表す
	// 同一キーを許可する場合、キー指定操作(Findなど)において同一キーのノードのどのノードが取得されるかは不定である
	AllowDuplicateKeys() bool
}

本パッケージで操作するために木が実装するべきメソッド

type Tree 

type Tree interface {
	// 木のルートノードを返却されることが期待される
	// 返却されるNodeはRealNodeを実装している必要がある
	// 木のルートノードが無い場合はreturn nilでnilを返却する必要がある
	Root() Node
}

木の公開用の基本的なインターフェース デフォルトでアクセスできる範囲を制限するためだけの用途

func Clear 

func Clear(tree Tree) (modified Tree)

木のインスタンスを再利用するために木が保持するノードを全て削除し空にする 戻り値のmodifiedはRealTreeのSetRootメソッドの戻り値となる

func Insert 

func Insert(tree Tree, replaceIfExists bool, key Key, value interface{}) (modified Tree, ok bool)

木に指定のキーと値を持つ新しいノードを追加する 既に指定キーが木に存在する場合は 木が同一キーのノードを許可しておらずreplaceIfExistsがfalseのときは木にノードを追加しない 木が同一キーのノードを許可しておらずreplaceIfExistsがtrueのときは既に存在するノードの値をvalueに置き換える 木が同一キーのノードを許可しておりreplaceIfExistsがfalseのときは木に新たにノードを追加する 木が同一キーのノードを許可しておりreplaceIfExistsがtrueのときは既に存在するノードのうち最初に見つかったノード(同一キーのノードのうち高さが最も高いノード)の値をvalueに置き換える 戻り値のmodifiedは木に変更があった場合はRealTreeのSetRootメソッドの戻り値となり、変更がない場合は引数のtreeがそのまま返却される 戻り値のokは木へのノード追加あるいはノードの値の更新があった場合にtrue、木に変化がなかった場合はfalseを返却する

func Replace 

func Replace(tree Tree, key Key, newValue interface{}) (modified Tree, ok bool)

指定のキーを持つノードの値を別の値に置き換える 指定のキーが存在しない場合は木に変更は加えない 木が同一キーのノードを許可している場合は指定キーを持つノードのうち最初に見つかったノード(同一キーのノードのうち高さが最も高いノード)が変更の対象となる 戻り値のmodifiedは指定したキーが存在する場合はRealTreeのSetRootメソッドの戻り値となり、キーが存在しない場合は引数のtreeがそのまま返却される 戻り値のokは指定のキーを持つノードが存在する場合にtrueとなる

func ReplaceAll 

func ReplaceAll(tree Tree, key Key, newValue interface{}) (modified Tree, ok bool)

同一キーを持つノードが複数ある場合のReplaceの強化版 指定したキーを持つ全てのノードの値をnewValueに変更する

func ReplaceRange 

func ReplaceRange(tree Tree, lower, upper Key, newValue interface{}) (modified Tree, ok bool)

ReplaceとRangeを組み合わせた感じ lower以上upper以下のキーを持つ全てのノードの値をnewValueに変更する

func Update 

func Update(tree Tree, key Key, callBack UpdateValueCallBack) (modified Tree, ok bool)

指定のキーを持つノードの値を変更する 指定のキーが存在しない場合は木に変更は加えない 木が同一キーのノードを許可している場合は指定キーを持つノードのうち最初に見つかったノード(同一キーのノードのうち高さが最も高いノード)が変更の対象となる 戻り値のmodifiedは変更があった場合はRealTreeのSetRootメソッドの戻り値となり、変更がない場合は引数のtreeがそのまま返却される 戻り値のokは変更があった場合にtrueとなる 変更があった場合とは、指定のキーを持つノードが存在し、かつコールバックの戻り値keepOldValueがfalseであったときのことを指す 変更が無かった場合とは、指定のキーを持つノードが存在しなかった場合もしくはコールバックの戻り値keepOldValueがtrueであった場合

func UpdateAll 

func UpdateAll(tree Tree, key Key, callBack UpdateValueCallBack) (modified Tree, ok bool)

同一キーを持つノードが複数ある場合のUpdateの強化版 指定したキーを持つ全てのノードに対してコールバックが呼び出される

func UpdateIterate 

func UpdateIterate(tree Tree, descOrder bool, callBack UpdateIterateCallBack) (modified Tree, ok bool)

UpdateとIterateを組み合わせた感じ 巡っていく各ノードに対してコールバックが呼ばれる

func UpdateRange 

func UpdateRange(tree Tree, descOrder bool, lower, upper Key, callBack UpdateValueCallBack) (modified Tree, ok bool)

UpdateとRangeを組み合わせた感じ lower以上upper以下のキーを持つノードそれぞれに順にコールバックが呼ばれる

func UpdateRangeIterate 

func UpdateRangeIterate(tree Tree, descOrder bool, lower, upper Key, callBack UpdateIterateCallBack) (modified Tree, ok bool)

UpdateとRangeIterateを組み合わせた感じ lower以上upper以下のキーを持つノードに順にコールバックが呼ばれる

type TreeCleaner 

type TreeCleaner interface {
	Tree
	CleanUpTree()
}

このインターフェースが実装されている場合にClearの内部で木のノードを全て削除したあとでCleanUpTreeメソッドを呼び出す Delete系やAlter系で木のノードが全部削除されてもこのメソッドは呼び出されずClearのみで呼び出される 利用シーンは全く思い至らないのに何故か用意してしまった謎インターフェース サブパッケージのintarraytreeではCleanUpTreeでメモリ再利用のためのノードのチェーンを破棄するための処理を行っている

type TreeReleaser 

type TreeReleaser interface {
	Tree
	ReleaseTree()
}

木のメモリの解放処理を行うためのメソッド(？) ReleaseTreeメソッドが呼び出された場合に木の再利用が不可能な状態であることが期待される(panicを起こすなど) このインターフェースが実装されている場合にReleaseの内部でReleaseTreeメソッドを呼び出す

type UpdateIterateCallBack 

type UpdateIterateCallBack = func(key Key, oldValue interface{}) (newValue interface{}, keepOldValue, breakIteration bool)

木のノードを順に巡りノードの値を更新するUpdateIterate,UpdateRangeIterateの引数で渡す newValueに値を代入することでキーに対する新しい値を設定する 値を変更しない場合はkeepOldValueをtrueに設定する breakIterationをtrueにしたときにイテレーションを中断する

type UpdateValueCallBack 

type UpdateValueCallBack = func(key Key, oldValue interface{}) (newValue interface{}, keepOldValue bool)

指定のキーの値の更新をするUpdate,UpdateAll,UpdateRangeの引数で渡す newValueに値を代入することでキーに対する新しい値を設定する 値を変更しない場合はkeepOldValueをtrueに設定する

Source Files

View all Source files

Directories

Path Synopsis
github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 不変(immutable)ぽい木を構築する コード例 import ( "fmt" "github.com/neetsdkasu/avltree" "github.com/neetsdkasu/avltree/immutabletree" .
 github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 不変(immutable)ぽい木を構築する コード例 import ( "fmt" "github.com/neetsdkasu/avltree" "github.com/neetsdkasu/avltree/immutabletree" .
github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 int型の可変長配列(スライス)上にAVL木を構築する 扱えるキーはintkeyのIntKeyのみ 扱える値はint型のみ int型は32bitマシンだと4bytes、64bitマシンだと8bytesになるので実行環境によって必要メモリ量が変わる 配列の最初の３要素は以下の木に関する情報を保持 + ルートノードのインデックス + 同一キーを許可するかどうかの値 + 再利用可能なノードのインデックス １つのノードは７個分の要素で構成され、以下の情報を保持 + 左の子ノードのインデックス + 右の子ノードのインデックス + 木におけるノードの高さ + 親ノードのインデックス + 左右の子孫も合わせたノード総数 + ノードのキー + ノードの値 コード例 import ( "fmt" "github.com/neetsdkasu/avltree" "github.com/neetsdkasu/avltree/intarraytree" .
 github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 int型の可変長配列(スライス)上にAVL木を構築する 扱えるキーはintkeyのIntKeyのみ 扱える値はint型のみ int型は32bitマシンだと4bytes、64bitマシンだと8bytesになるので実行環境によって必要メモリ量が変わる 配列の最初の３要素は以下の木に関する情報を保持 + ルートノードのインデックス + 同一キーを許可するかどうかの値 + 再利用可能なノードのインデックス １つのノードは７個分の要素で構成され、以下の情報を保持 + 左の子ノードのインデックス + 右の子ノードのインデックス + 木におけるノードの高さ + 親ノードのインデックス + 左右の子孫も合わせたノード総数 + ノードのキー + ノードの値 コード例 import ( "fmt" "github.com/neetsdkasu/avltree" "github.com/neetsdkasu/avltree/intarraytree" .
github.com/neetsdkasu/avltreeのKeyの実装例 int型をそのままキーにしてある int型の自然順序をそのままキーの順序としてある
 github.com/neetsdkasu/avltreeのKeyの実装例 int型をそのままキーにしてある int型の自然順序をそのままキーの順序としてある
github.com/neetsdkasu/avltreeのためのラッパーの実装例 キーと値のやりとりをint型に制限する 内部での実際のキーはintkeyのIntKeyを使用している int型に制限するのはラッパーのメソッドの引数や戻り値だけではなく KeyAndValue,Node,AlterNode,AlterRequestもintwrapper独自でint型用に定義しなおされている コード例 import ( "fmt" "github.com/neetsdkasu/avltree/intwrapper" "github.com/neetsdkasu/avltree/simpletree" ) func Example_intwrapper() { tree := simpletree.New(false) w := intwrapper.New(tree) w.Insert(12, 345) w.Insert(67, 890) w.Insert(333, 666) w.Insert(-5, 12345) w.Delete(67) w.Update(333, func(key, oldValue int) (newValue int, keepOldValue bool) { newValue = oldValue * 3 return }) if node := w.Find(12); node != nil { fmt.Println("Find!", node.Key(), node.Value()) } w.Iterate(func(node intwrapper.Node) (breakIteration bool) { fmt.Println("Iterate!", node.Key(), node.Value()) return }) // Output: // Find! 12 345 // Iterate! -5 12345 // Iterate! 12 345 // Iterate! 333 1998 }
 github.com/neetsdkasu/avltreeのためのラッパーの実装例 キーと値のやりとりをint型に制限する 内部での実際のキーはintkeyのIntKeyを使用している int型に制限するのはラッパーのメソッドの引数や戻り値だけではなく KeyAndValue,Node,AlterNode,AlterRequestもintwrapper独自でint型用に定義しなおされている コード例 import ( "fmt" "github.com/neetsdkasu/avltree/intwrapper" "github.com/neetsdkasu/avltree/simpletree" ) func Example_intwrapper() { tree := simpletree.New(false) w := intwrapper.New(tree) w.Insert(12, 345) w.Insert(67, 890) w.Insert(333, 666) w.Insert(-5, 12345) w.Delete(67) w.Update(333, func(key, oldValue int) (newValue int, keepOldValue bool) { newValue = oldValue * 3 return }) if node := w.Find(12); node != nil { fmt.Println("Find!", node.Key(), node.Value()) } w.Iterate(func(node intwrapper.Node) (breakIteration bool) { fmt.Println("Iterate!", node.Key(), node.Value()) return }) // Output: // Find! 12 345 // Iterate! -5 12345 // Iterate! 12 345 // Iterate! 333 1998 }
github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 実装に必要な最小限の構成になっている コード例 import ( "fmt" "github.com/neetsdkasu/avltree" .
 github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 実装に必要な最小限の構成になっている コード例 import ( "fmt" "github.com/neetsdkasu/avltree" .
github.com/neetsdkasu/avltreeのためのラッパーの実装例 コード例 import ( "fmt" "github.com/neetsdkasu/avltree" .
 github.com/neetsdkasu/avltreeのためのラッパーの実装例 コード例 import ( "fmt" "github.com/neetsdkasu/avltree" .
github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 simpletreeと比較した場合standardtreeは以下の機能を持っている + 各ノードが親ノードの情報を持っている (avltree.ParentGetterを実装している) + 各ノードがそのノードをサブツリーとしたときのノード総数の情報を持っている(avltree.NodeCounterを実装している) コード例 import ( "fmt" "github.com/neetsdkasu/avltree" .
 github.com/neetsdkasu/avltreeのRealTree,RealNodeの実装例 simpletreeと比較した場合standardtreeは以下の機能を持っている + 各ノードが親ノードの情報を持っている (avltree.ParentGetterを実装している) + 各ノードがそのノードをサブツリーとしたときのノード総数の情報を持っている(avltree.NodeCounterを実装している) コード例 import ( "fmt" "github.com/neetsdkasu/avltree" .
github.com/neetsdkasu/avltreeのKeyの実装例 string型をそのままキーにしてある 標準パッケージのstrings.Compareの結果をそのままキーの比較の値として使っている
 github.com/neetsdkasu/avltreeのKeyの実装例 string型をそのままキーにしてある 標準パッケージのstrings.Compareの結果をそのままキーの比較の値として使っている

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.