TreeMultiSet does not support object values (non-primitive values)

[upupming]

contest.js/src/treeset.ts

Line 115 in 9852630

counts: Map<T, number>

We count the element using a Map, if I add two array, they are equal using the compare function, but they will not be counted together.

For example:

const s = new TreeMultiSet<[number, number]>([], (a, b) => {
  if (a[0] === b[0]) return a[1] < b[1]
  return a[0] < b[0]
})
s.add([1, 2])
s.add([1, 2])
console.log(s.count([1, 2]))

// outputs: 0
// expected: 2

I am not sure if we should implement a hash function by ourselves, or use something like object-hash

For example, in LeetCode 6030. Longest Substring of One Repeating Character, I have no idea to solve this with current TreeMultiSet using an array as data type T, I have to concat a primitive string to keep it working for me: https://github.com/upupming/algorithm/blob/fb620863e0145034083f6a6f7f324b92e84f2b12/leetcode/contest-285/6030.%20Longest%20Substring%20of%20One%20Repeating%20Character.ts#L33

[harttle]

Moved count into RBTree, now TreeSet and TreeMultiSet work as expected:

TreeSet

contest.js/test/treeset.spec.ts

Lines 84 to 92 in bd0b849

	it('should treat items as equal ones when `compare` returns 0', () => {
	const s = new TreeSet<[number, number]>([], (a: [number, number], b: [number, number]) => {
	if (a[0] !== b[0]) return a[0] - b[0]
	return a[1] - b[1]
	})
	s.add([1, 2])
	s.add([1, 2])
	expect(s.size()).toEqual(1)
	})

TreeMultiSet

contest.js/test/treeset.spec.ts

Lines 183 to 191 in bd0b849

	it('should treat items as equal ones when `compare` returns 0', () => {
	const s = new TreeMultiSet<[number, number]>([], (a: [number, number], b: [number, number]) => {
	if (a[0] !== b[0]) return a[0] - b[0]
	return a[1] - b[1]
	})
	s.add([1, 2])
	s.add([1, 2])
	expect(s.count([1, 2])).toEqual(2)
	})