func (s marketStore) record(m emdn.Transaction) {
	k := m.Item
	// Demand
	tree, ok := s.itemDemand[k]
	if !ok {
		tree = llrb.New()
		s.itemDemand[k] = tree
	}
	tree.ReplaceOrInsert(demtrans(m))
	for tree.Len() > maxItems {
		tree.DeleteMin()
	}
	stationPriceUpdate(s.stationDemand, m.Station, k, m.SellPrice)

	// Supply
	tree, ok = s.itemSupply[k]
	if !ok {
		tree = llrb.New()
		s.itemSupply[k] = tree
	}
	if m.BuyPrice == 0 {
		m.BuyPrice = math.MaxInt64
	}
	tree.ReplaceOrInsert(suptrans(m))
	for tree.Len() > maxItems {
		tree.DeleteMax()
	}
	stationPriceUpdate(s.stationSupply, m.Station, k, m.BuyPrice)
}

func InitCache() *MyError.MyError {
	once.Do(func() {
		DomainRRCache = &DomainRRTree{
			LLRB:    llrb.New(),
			RWMutex: &sync.RWMutex{},
		}
		DomainSOACache = &DomainSOATree{
			LLRB:    llrb.New(),
			RWMutex: &sync.RWMutex{},
		}
	})
	return nil
}

func newShardedCache(n int, de time.Duration) *shardedCache {
	max := big.NewInt(0).SetUint64(uint64(math.MaxUint32))
	rnd, err := rand.Int(rand.Reader, max)
	var seed uint32
	if err != nil {
		os.Stderr.Write([]byte("WARNING: go-cache's newShardedCache failed to read from the system CSPRNG (/dev/urandom or equivalent.) Your system's security may be compromised. Continuing with an insecure seed.\n"))
		seed = insecurerand.Uint32()
	} else {
		seed = uint32(rnd.Uint64())
	}
	sc := &shardedCache{
		seed: seed,
		m:    uint32(n),
		cs:   make([]*cache, n),
	}
	for i := 0; i < n; i++ {
		c := &cache{
			defaultExpiration: de,
			items:             map[string]Item{},
			sortedItems:       llrb.New(),
		}
		sc.cs[i] = c
	}
	return sc
}

// NewEnvironment constructs an Environment with the given parent to provide a
// fallback for finding variables. The parent may be nil.
func NewEnvironment(parent Environment) Environment {
	e := new(environment)
	e.writable = true
	e.vars = llrb.New()
	e.parent = parent
	return e
}

// Returns a new task queue.
// The user could submit new task through channel ch.
func NewTaskQueue(ch <-chan Task) *TaskQueue {
	ret := new(TaskQueue)
	ret.tree = llrb.New(taskBefore)
	ret.ch = ch
	ret.waitTime = maxTime
	return ret
}

// Add a term that can be searched on (append or create to an existing term)
func (rfs *RootFileSystem) SearchAddTerm(area string, term string, path string, version string) error {
	searchIndex := rfs.ChangeCache.GetSearchIndex()
	treeNode, ok := searchIndex.Terms[area]
	var searchTree *SearchTree = &SearchTree{}
	var err error
	if !ok {
		// Create a node for this tree
		treeNode = rfs.BlockHandler.GetFreeBlockNode(SEARCHTREE)
		searchIndex.Terms[area] = treeNode
		searchTree.Tree = llrb.New()
		searchTree.Node = treeNode
		// Need to save the searchTree back
		rfs.ChangeCache.SaveSearchIndex(searchIndex)
	} else {
		searchTree, err = rfs.ChangeCache.GetSearchTree(treeNode)
		if err != nil {
			return err
		}
	}
	// Now we have a search tree, add the term
	var searchItem = SearchEntry{term, nil}
	existingValue := searchTree.Tree.Get(searchItem)
	var pointValue SearchEntry
	if existingValue != nil {
		pointValue = existingValue.(SearchEntry)
	} else {
		pointValue = SearchEntry{term, make([]Entry, 0)}
	}
	entry := Entry{path, version}
	pointValue.Matches = append(pointValue.Matches, entry)
	searchTree.Tree.ReplaceOrInsert(pointValue)
	// And save this searchTree back
	rfs.ChangeCache.SaveSearchTree(searchTree)
	return nil
}

// rebuildIndex does the work of regenerating the index
// with the given keys.
func rebuild(less llrb.LessFunc, keys <-chan string) *llrb.Tree {
	tree := llrb.New(less)
	for key := range keys {
		tree.ReplaceOrInsert(key)
	}
	return tree
}

func (tdi *TripleDirectionIndex) GetOrCreate(d graph.Direction, id int64) *llrb.LLRB {
	directionIndex := tdi.GetForDir(d)
	if _, ok := directionIndex[id]; !ok {
		directionIndex[id] = llrb.New()
	}
	return directionIndex[id]
}

func (this *Trellis) insert(t int, s *Bigram, sa *Bigram, kb int, p float64) {
	i, ok := this.trl[t].Get(s)
	if !ok {
		TRACE(4, "    Inserting. Is a new element, init list.", MOD_HMM)
		m := llrb.New()
		m.InsertNoReplace(NewElement(sa, kb, p))
		this.trl[t].Insert(s, m)
	} else {
		TRACE(4, "    Inserting. Not a new element, add. List size="+strconv.Itoa(i.(*llrb.LLRB).Len())+"/"+strconv.Itoa(this.kbest), MOD_HMM)
		j := i.(*llrb.LLRB).Min()
		if i.(*llrb.LLRB).Len() == this.kbest && p < j.(*Element).prob {
			TRACE(4, "    Not worth inserting", MOD_HMM)
			return
		}

		i.(*llrb.LLRB).InsertNoReplace(NewElement(sa, kb, p))

		if i.(*llrb.LLRB).Len() > this.kbest {
			i.(*llrb.LLRB).Delete(i.(*llrb.LLRB).Min())
			TRACE(4, "    list too long. Last erased", MOD_HMM)
		}
	}
	i, ok = this.trl[t].Get(s)
	if ok && i.(*llrb.LLRB).Len() > 0 {
		TRACE(4, "MAX:"+strconv.FormatFloat(i.(*llrb.LLRB).Max().(*Element).prob, 'f', -1, 64)+" MIN:"+strconv.FormatFloat(i.(*llrb.LLRB).Min().(*Element).prob, 'f', -1, 64), MOD_HMM)
	}
}

// NewRegionCache creates a RegionCache.
func NewRegionCache(pdClient pd.Client) *RegionCache {
	return &RegionCache{
		pdClient: pdClient,
		regions:  make(map[RegionVerID]*Region),
		sorted:   llrb.New(),
	}
}

// rebuildIndex does the work of regenerating the index
// with the given keys.
func rebuild(less LessFunction, keys <-chan string) *llrb.LLRB {
	tree := llrb.New()
	for key := range keys {
		tree.ReplaceOrInsert(llrbString{s: key, l: less})
	}
	return tree
}

func NewQTask() *QTask {
	return &QTask{
		tree:     llrb.New(),
		qchan:    make(chan Task, 30),
		waitTime: maxTime,
		mTask:    make(map[string]Task),
	}
}

// NewRegionCache creates a RegionCache.
func NewRegionCache(pdClient pd.Client) *RegionCache {
	c := &RegionCache{
		pdClient: pdClient,
	}
	c.mu.regions = make(map[RegionVerID]*Region)
	c.mu.sorted = llrb.New()
	return c
}

func BenchmarkSortedInsert_InsertNoReplace(b *testing.B) {
	for i := 0; i < b.N; i++ {
		tree := llrb.New()
		for i := 0; i < len(fixture.SortedTestData); i++ {
			tree.InsertNoReplace(llrbItem(fixture.SortedTestData[i]))
		}
	}
}

func BenchmarkInsert(b *testing.B) {
	for i := 0; i < b.N; i++ {
		tree := llrb.New()
		for i := 0; i < len(fixture.TestData); i++ {
			tree.ReplaceOrInsert(llrbItem(fixture.TestData[i]))
		}
	}
}

func newTreeBasedConnMap(maxNrConn, maxNrUsers, maxNrConnsPerUser int) connMap {
	ret := new(treeBasedConnMap)
	ret.tree = llrb.New()
	ret.maxNrConn = maxNrConn
	ret.maxNrUsers = maxNrUsers
	ret.maxNrConnsPerUser = maxNrConnsPerUser
	return ret
}

func main() {
	tree := llrb.New()
	tree.ReplaceOrInsert(llrb.Int(1))
	tree.ReplaceOrInsert(llrb.Int(2))
	tree.ReplaceOrInsert(llrb.Int(3))
	tree.ReplaceOrInsert(llrb.Int(4))
	tree.DeleteMin()
	tree.Delete(llrb.Int(4))
	tree.AscendGreaterOrEqual(tree.Min(), Print)
}

func (this *Set) Insert(item interface{}) {
	bin := this.bins[this.hasher(item)]
	if bin == nil {
		bin = llrb.New(llrb.LessFunc(this.lesser))
		this.bins[this.hasher(item)] = bin
	}
	if bin.ReplaceOrInsert(item) == nil {
		this.count++
	}
}

// NewRestrictedEnvironment constructs an Environment with the given set of
// mappings. The environment cannot be modified.
func NewRestrictedEnvironment(parent Environment, mapping map[Symbol]interface{}) Environment {
	e := new(environment)
	e.writable = false
	e.vars = llrb.New()
	for sym, val := range mapping {
		item := newEnvItem(sym, val)
		e.vars.ReplaceOrInsert(item)
	}
	e.parent = parent
	return e
}

// There's no way back!
func (self *treeBasedConnMap) CloseAll() {
	self.lock.Lock()
	var nilcs *connSet
	self.tree.AscendGreaterOrEqual(nilcs, func(i llrb.Item) bool {
		if cs, ok := i.(*connSet); ok {
			cs.CloseAll()
		}
		return true
	})
	self.tree = llrb.New()
}