Open
Bug 901422
Opened 11 years ago
Updated 2 years ago
Add Insert ignore duplicates method, no comparator option, and a way to enumerate SplayTree
Categories
(Core :: MFBT, defect)
Tracking
()
NEW
People
(Reporter: almasry.mina, Unassigned)
Details
Attachments
(4 files)
12.28 KB,
patch
|
Details | Diff | Splinter Review | |
2.39 KB,
patch
|
Details | Diff | Splinter Review | |
2.01 KB,
patch
|
Details | Diff | Splinter Review | |
1.98 KB,
patch
|
Details | Diff | Splinter Review |
SplayTree is a very useful data structure that I would like to use, but there are features missing from it that make that hard. It would be nice to add: - A no-comparator version of the SplayTree that simply assumes whatever equalities are defined on the template type. - Currently to insert an item into the splay tree you must: if (!splayTree.contains(itemIWantToInsert)) { splayTree.insert(itemIWantToInsert); } .contains transverses the tree once, and .insert two more times, which is a waste in my humble opinion. It would be nice to add a method |insertIgnoreIfDuplicate(const T*)| that simply ignores the insert order if there is a duplicate. - It would be nice to be able to loop over items in the SplayTree. I suggest doing that with: for(SplayTreeNode* min = splayTree.minimum(); min != nullptr; min = min.next()) { // Do something with min. } For that we will need |SplayTreeNode* SplayTree::minimum()| which returns the smallest item in the tree in O(log n) time, and a |SplayTreeNode* SplayTreeNode::next()| which returns the successor to this item also in O(log n) time.
Reporter | ||
Comment 1•11 years ago
|
||
Jeff, I'm willing to work on these changes, maybe with a little mentoring, please (I shouldn't need much). I just wanted to check these are welcome changes before I start work.
Flags: needinfo?(jwalden+bmo)
Comment 2•11 years ago
|
||
These additions seem fairly reasonable. (If we're adding minimum(), we should add maximum() too.) Dunno for sure about the names -- insertIgnoreIfDuplicate in particular seems cumbersome -- but those are window dressing, more or less, that can be quickly dealt with when there's a patch in hand.
Flags: needinfo?(jwalden+bmo)
Reporter | ||
Comment 3•11 years ago
|
||
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #2) > These additions seem fairly reasonable. (If we're adding minimum(), we > should add maximum() too.) Dunno for sure about the names -- > insertIgnoreIfDuplicate in particular seems cumbersome -- but those are > window dressing, more or less, that can be quickly dealt with when there's a > patch in hand. Sounds great. They are just window dressing, and maximum() is doable too, and maybe if we're gonna have SplayTree::Maximum we can also have SplayTreeNode::prev returns the predecessor of the current node. I'll work on this when I have the time and then we'll have a patch on hand.
QA Contact: almasry.mina
Reporter | ||
Updated•11 years ago
|
Assignee: nobody → almasry.mina
QA Contact: almasry.mina
Reporter | ||
Comment 4•11 years ago
|
||
Attachment #790480 -
Flags: review?(jwalden+bmo)
Reporter | ||
Comment 5•11 years ago
|
||
Attachment #790482 -
Flags: review?(jwalden+bmo)
Reporter | ||
Comment 6•11 years ago
|
||
Attachment #790483 -
Flags: review?(jwalden+bmo)
Reporter | ||
Comment 7•11 years ago
|
||
Attachment #790485 -
Flags: review?(jwalden+bmo)
Reporter | ||
Comment 8•11 years ago
|
||
I also changed the semantics of the container a little so that clients don't have to do their own memory management and don't have to be aware of SplayTreeNode except for iterating through the tree.
Comment 9•11 years ago
|
||
Comment on attachment 790480 [details] [diff] [review] Part 1 - Add no comparator option Review of attachment 790480 [details] [diff] [review]: ----------------------------------------------------------------- Sorry for the delay here, too many other things in the works lately. :-( Could you post a new patch that makes *only* the no-comparator change, and a separate patch that makes the changes noted in comment 8? There are too many changes in this one patch for it to be simply reviewable with me having much confidence in my review's correctness. Also note that mfbt's style rules are documented in mfbt/STYLE. The most notable things are that single-line if/loop/etc. bodies aren't braced.
Attachment #790480 -
Flags: review?(jwalden+bmo)
Reporter | ||
Comment 10•11 years ago
|
||
I don't think I can finish this, so I'm unassigning myself. I'll leave it open because someone should probably look into giving gecko programmers an alternative to nsTArray for a container, but feel free to mark it WONTFIX.
Assignee: malmasry → nobody
Reporter | ||
Updated•11 years ago
|
Attachment #790482 -
Flags: review?(jwalden+bmo)
Reporter | ||
Updated•11 years ago
|
Attachment #790483 -
Flags: review?(jwalden+bmo)
Reporter | ||
Updated•11 years ago
|
Attachment #790485 -
Flags: review?(jwalden+bmo)
Updated•2 years ago
|
Severity: normal → S3
You need to log in
before you can comment on or make changes to this bug.
Description
•