Add Insert ignore duplicates method, no comparator option, and a way to enumerate SplayTree

NEW
Unassigned

Status

()

Core
MFBT
5 years ago
4 years ago

People

(Reporter: Mina Almasry, Unassigned)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(4 attachments)

(Reporter)

Description

5 years ago
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

5 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)
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

5 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

5 years ago
Assignee: nobody → almasry.mina
QA Contact: almasry.mina
(Reporter)

Comment 4

5 years ago
Created attachment 790480 [details] [diff] [review]
Part 1 - Add no comparator option
Attachment #790480 - Flags: review?(jwalden+bmo)
(Reporter)

Comment 5

5 years ago
Created attachment 790482 [details] [diff] [review]
Part 2 - Add ways to iterate over values
Attachment #790482 - Flags: review?(jwalden+bmo)
(Reporter)

Comment 6

5 years ago
Created attachment 790483 [details] [diff] [review]
Part 3 - Add method to ignore duplicates
Attachment #790483 - Flags: review?(jwalden+bmo)
(Reporter)

Comment 7

5 years ago
Created attachment 790485 [details] [diff] [review]
Part 4 - Tests
Attachment #790485 - Flags: review?(jwalden+bmo)
(Reporter)

Comment 8

5 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 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

4 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

4 years ago
Attachment #790482 - Flags: review?(jwalden+bmo)
(Reporter)

Updated

4 years ago
Attachment #790483 - Flags: review?(jwalden+bmo)
(Reporter)

Updated

4 years ago
Attachment #790485 - Flags: review?(jwalden+bmo)
You need to log in before you can comment on or make changes to this bug.