ef-ds / deque Goto Github PK

Deque is missing the integration tests for mixed PushFront/PushBack and mixed PopFront/PopBack.

Deque already have a good set of integration tests for queue and stack usage. Below, for instance, is the test set for queue usage.

TestFillQueueShouldRetrieveAllElementsInOrder
TestRefillQueueShouldRetrieveAllElementsInOrder
TestRefillFullQueueShouldRetrieveAllElementsInOrder
TestSlowIncreaseQueueShouldRetrieveAllElementsInOrder
TestSlowDecreaseQueueShouldRetrieveAllElementsInOrder
TestStableQueueShouldRetrieveAllElementsInOrder

We need similar tests for mixed usage.

It is suggested the new tests to use a logic similar to "TestMixedPopFrontBackLenShouldReturnAllValuesInOrder" (here) to ensure mixed pushes and pops. The new tests should be written inside the already existing (integration_test.go) Go source file.

We have included only a few open source deques in our benchmark tests. The deques in the tests were chosen due to their different designs (linked list, dynamic array, circular buffer, etc) and their high quality implementations. We also tested many others that had much inferior performance when compared to the ones in the tests. Make no mistake: the deques in the tests are all world-class implementations.

Having said that, a simple search for "deque" in godoc.org reveals there's many deques out there! It's easy to miss an interesting one.

We need help probing and finding strong deque candidates to include in the tests. By strong we mean the ones that can perform better than the ones already in the tests in the Microservice test.

To probe a deque, just clone this deque repo (if you haven't already) locally and create the tests for the deque you wish to test in the Microservice test source file. After that, run the tests and check the results.

Please post the results for the deques you tested as comments in this issue.

The dream goal of this contest is to find a deque that is faster than deque!

The winner, meaning, the person who found a deque that is faster in at least 5 test ranges (out of the 8), will win a glorious amount of virtual thumbs up (👍) and a sincere thanks from us!

Deque's first (and current) version exposes the Init and New methods.

Both methods are very simple and can be replaced with custom code very easily.

Below:

d := deque.New()

Can be replaced with:

d := new(deque.Deque)

Note: Deque's zero value can also be used, but using deque's zero value instead of New have implications as New returns a pointer to the deque which makes it useful to be passed as params to other functions. Consider below.

func pushToDeque(d deque.Deque) {
	d.PushBack(1)
}

func TestDeque(t *testing.T) {
	var d deque.Deque
	pushToDeque(d)
	v, ok := d.PopFront()
	fmt.Println(ok)
	fmt.Println(v)
}

Output:

false
<nil>

In other words, if deque needs to be passed around as a param, a pointer to it have to be used, so the New() method will likely be used more frequently.

Regarding the Init method,

Below:

d.Init()

Can be replaced with:

*d = deque.Deque{}

The Init method, like the New, makes the code look cleaner.

The biggest advantage of removing both methods is a cleaner API, one which contains only the most useful methods, so it's less likely the users will get confused on how to use deque and would have to spend less time learning how to use it.

The biggest downside of removing either methods is a breaking change, besides making using deque a bit more cumbersome. Meaning, anyone already using deque, when they upgrade to a newer version without the methods, they will be forced to update their code as explained above. This is a big inconvenience and a lot of people gets turned away from projects who keeps releasing versions with breaking changes.

The proposal is to remove both New and Init method from the public API and instruct the users to use one of its alternatives as explained above.

If you are for it, please thumbs up the proposal; if you are against, thumbs down. If you feel strongly about your opinion, please consider leaving comments.

Your opinion is really appreciated and will be considered in the final decision.

This panics on the 65th iteration:

package main

import "github.com/ef-ds/deque"

func main() {
	q := deque.New()
	for {
		q.PushFront(1)
		q.PopBack()
	}
}

https://play.golang.org/p/CaG4fu1EY-E

I know that isn't the normal use, but I feel like it should work.

thanks for this package, but for new project i need queue with priority. Does it possible to build queue with priority using this package?