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

Status: NEW

(Core :: MFBT, defect)

Description

[Mina Almasry]

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.

Comment 1

[Mina Almasry]

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.

Comment 2

[Jeff Walden [:Waldo]]

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.

Comment 3

[Mina Almasry]

(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.

Comment 4

[Mina Almasry]

Attachment: Part 1 - Add no comparator option

Comment 5

[Mina Almasry]

Attachment: Part 2 - Add ways to iterate over values

Comment 6

[Mina Almasry]

Attachment: Part 3 - Add method to ignore duplicates

Comment 7

[Mina Almasry]

Attachment: Part 4 - Tests

Comment 8

[Mina Almasry]

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

[Jeff Walden [:Waldo]]

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.

Comment 10

[Mina Almasry]

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.