Add Floor and Ceiling method to Treemap

loxp commented

2018-08-15 09:25:51 +00:00

(Migrated from github.com)

No description provided.

emirpasic commented

2018-09-20 16:48:24 +00:00

(Migrated from github.com)

@loxp Thank you for the input.

May i propose another solution of just exposing the underlying Tree of the TreeMap?

In other words, you could get the same result with

m := treemap.NewWithIntComparator() 
... //  add elements 
m.Tree.Floor(key)

...or do you prefer your solution?

@loxp Thank you for the input. May i propose another solution of just exposing the underlying Tree of the TreeMap? In other words, you could get the same result with ```go m := treemap.NewWithIntComparator() ... // add elements m.Tree.Floor(key) ``` ...or do you prefer your solution?

emirpasic commented

2018-09-20 17:14:25 +00:00

(Migrated from github.com)

perhaps, given I expose the Tree in the TreeMap and implement the seek iterator withing red-black tree, I could kill two flies with this approach w.r.t. #66

loxp commented

2018-09-21 07:11:08 +00:00

(Migrated from github.com)

..or do you prefer your solution?

You are right. Moreover, do you think the solution below is better?

type Map struct {
    rbt.Tree
}

All the methods of Tree struct can be invoked directly through a reference to the Map struct, and all the proxy methods of Map struct can be removed.

> ..or do you prefer your solution? You are right. Moreover, do you think the solution below is better? ``` type Map struct { rbt.Tree } ``` All the methods of Tree struct can be invoked directly through a reference to the Map struct, and all the proxy methods of Map struct can be removed.

emirpasic commented

2018-09-21 15:31:49 +00:00

(Migrated from github.com)

You are right. Moreover, do you think the solution below is better?

That was my question to you as well, what do you think, would that work for you?

On another note, just checked on Java's TreeMap that they do expose a lot of these method directly in TreeMap https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html so I am wondering if GoDS should do the same. Perhaps accessing the Tree within the map would not be to intuitive and evident for most people and creating proxy functions in our treemap, as you have done, would still be the better approach.

Last night I was more inclined towards exposing the Tree, today I am more inclide towards your approach. Perhaps we could do both, since I can't make up my mind? :D

> You are right. Moreover, do you think the solution below is better? That was my question to you as well, what do you think, would that work for you? On another note, just checked on Java's TreeMap that they do expose a lot of these method directly in TreeMap https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html so I am wondering if GoDS should do the same. Perhaps accessing the Tree within the map would not be to intuitive and evident for most people and creating proxy functions in our treemap, as you have done, would still be the better approach. Last night I was more inclined towards exposing the Tree, today I am more inclide towards your approach. Perhaps we could do both, since I can't make up my mind? :D

loxp commented

2018-09-22 02:01:03 +00:00

(Migrated from github.com)

You are right. Moreover, do you think the solution below is better?

That was my question to you as well, what do you think, would that work for you?

On another note, just checked on Java's TreeMap that they do expose a lot of these method directly in TreeMap https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html so I am wondering if GoDS should do the same. Perhaps accessing the Tree within the map would not be to intuitive and evident for most people and creating proxy functions in our treemap, as you have done, would still be the better approach.

Last night I was more inclined towards exposing the Tree, today I am more inclide towards your approach. Perhaps we could do both, since I can't make up my mind? :D

Is it ok that exposing the Node struct to TreeMap user? If ok, I think exposing the Tree struct is better. In Java, a Map.Entry can be exposed, but in gods there isn't a equivalent abstraction.

> > You are right. Moreover, do you think the solution below is better? > > That was my question to you as well, what do you think, would that work for you? > > On another note, just checked on Java's TreeMap that they do expose a lot of these method directly in TreeMap https://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html so I am wondering if GoDS should do the same. Perhaps accessing the Tree within the map would not be to intuitive and evident for most people and creating proxy functions in our treemap, as you have done, would still be the better approach. > > Last night I was more inclined towards exposing the Tree, today I am more inclide towards your approach. Perhaps we could do both, since I can't make up my mind? :D Is it ok that exposing the Node struct to TreeMap user? If ok, I think exposing the Tree struct is better. In Java, a Map.Entry can be exposed, but in gods there isn't a equivalent abstraction.

emirpasic commented

2018-09-22 23:22:31 +00:00

(Migrated from github.com)

after thinking it though a bit, i like your approach better, i.e. creating proxy functions rather than exposing the tree. i will merge this into development branch, make some changes and merge into master thereafter. the changes are minor documentation/comment updates and change of the output parameters to resemble e.g.

// Max returns the maximum key and its value from the tree map.
// Returns nil, nil if map is empty.
func (m *Map) Max() (key interface{}, value interface{}) {
	if node := m.tree.Right(); node != nil {
		return node.Key, node.Value
	}
	return nil, nil
}

in other words removing the thrid output paramter.

after thinking it though a bit, i like your approach better, i.e. creating proxy functions rather than exposing the tree. i will merge this into development branch, make some changes and merge into master thereafter. the changes are minor documentation/comment updates and change of the output parameters to resemble e.g. ```go // Max returns the maximum key and its value from the tree map. // Returns nil, nil if map is empty. func (m *Map) Max() (key interface{}, value interface{}) { if node := m.tree.Right(); node != nil { return node.Key, node.Value } return nil, nil } ``` in other words removing the thrid output paramter.

Rows
Columns

Add Floor and Ceiling method to Treemap #82