Code Monkey home page Code Monkey logo

treemap's Introduction

TreeMap v2

PkgGoDev Unlicense Build Status Coverage Status GoReportCard Mentioned in Awesome Go

TreeMap is a generic key-sorted map using a red-black tree under the hood. It requires and relies on Go 1.18 generics feature. Iterators are designed after C++.

Usage

package main

import (
	"fmt"

	"github.com/igrmk/treemap/v2"
)

func main() {
	tr := treemap.New[int, string]()
	tr.Set(1, "World")
	tr.Set(0, "Hello")
	for it := tr.Iterator(); it.Valid(); it.Next() {
		fmt.Println(it.Key(), it.Value())
	}
}

// Output:
// 0 Hello
// 1 World

Install

go get github.com/igrmk/treemap/v2

Complexity

Name Time
Set O(logN)
Del O(logN)
Get O(logN)
Contains O(logN)
Len O(1)
Clear O(1)
Range O(logN)
Iterator O(1)
Reverse O(logN)
Iterate through the entire map O(N)

Memory usage

TreeMap uses O(N) memory.

TreeMap v1

The previous version of this package used gotemplate library to generate a type specific file in your local directory. Here is the link to this version treemap v1.

Licensing

Copyright © 2022 igrmk. This work is free. You can redistribute it and/or modify it under the terms of the Unlicense. See the LICENSE file for more details.

Thanks to

JetBrains

treemap's People

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

treemap's Issues

ForwardIterator.Prev() causes panic when it is at first element

var unconfirmedMap   *treemap.TreeMap[decimal.Decimal, *wm_model.Block]  = treemap.NewWithKeyCompare[ decimal.Decimal, *wm_model.Block ] (BlockNumberCmp)
		
func BlockNumberCmp(left decimal.Decimal, right decimal.Decimal) bool {
	return left.Cmp(right) < 0
}

func DoSomething(latestFastConfirmNum decimal.Decimal)  []*wm_model.Block{
               var movedBlockList []*wm_model.Block = make([]*wm_model.Block, 0)
                it :=  unconfirmedMap.UpperBound(latestFastConfirmNum)
		if it.Valid() {
			for it.Prev(); it.Valid(); it.Prev() {
				movedBlockList = append(movedBlockList, it.Value())
			}

			for _, item := range movedBlockList {
				unconfirmedMap.Del(item.BlockNumber)
			}
		}
                return movedBlockList
   
}

Panic at it.Prev()
Besides, I would suggest Valid() function would also check if it is before the first element
If the forward iterator just expect to work forward only, I would suggest a function to convert a forward iterator to a reverse iterator

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.