dos

README

DYNAMIC ORDER STATISTIC

Features

1. based on red-black tree

2. O(logn) lookup time

3. Select the i-th largest element

http://en.wikipedia.org/wiki/Order_statistic

Documentation

Index

• Constants
• func Print_helper(n *Node, indent int)
• type Node
  • func (n *Node) Ids() []int32
  • func (n *Node) Score() int32
• type Tree
  • func (t *Tree) Clear()
  • func (t *Tree) Count() int
  • func (t *Tree) Delete(id int32, n *Node)
  • func (t *Tree) Insert(score int32, id int32)
  • func (t *Tree) Locate(score int32, id int32) (int, *Node)
  • func (t *Tree) Rank(rank int) (id int32, node *Node)
  • func (t *Tree) Root() *Node

Constants

const (
	RED   = true
	BLACK = false
)

const INDENT_STEP = 4

---------------------------------------------------------- tree print

Functions

func Print_helper

func Print_helper(n *Node, indent int)

Types

type Node

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

func (*Node) Ids

func (n *Node) Ids() []int32

func (*Node) Score

func (n *Node) Score() int32

type Tree

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

func (*Tree) Clear

func (t *Tree) Clear()

func (*Tree) Count

func (t *Tree) Count() int

--------------------------------------------------------- Lookup by Rank READ-LOCK

func (*Tree) Delete

func (t *Tree) Delete(id int32, n *Node)

---------------------------------------------------------- Delete an id from a node WRITE-LOCK

func (*Tree) Insert

func (t *Tree) Insert(score int32, id int32)

---------------------------------------------------------- Insert an element WRITE-LOCK

func (*Tree) Locate

func (t *Tree) Locate(score int32, id int32) (int, *Node)

---------------------------------------------------------- locate a score & id READ-LOCK

func (*Tree) Rank

func (t *Tree) Rank(rank int) (id int32, node *Node)

--------------------------------------------------------- Lookup by Rank READ-LOCK

func (*Tree) Root

func (t *Tree) Root() *Node