Tree data structure with multiple keys for each item

user_7687223 0
Viewed 306

I'm working on a chat application using node js that displays a list of online users. Each user has the following attributes:

ipv4, rank, score, login time

ipv4 is used when accessing a user.

Users should be listed according to this sorting strategy:

  • Users with higher rank should be at the top of the list.
  • If the user rank is equal, the users with the highest score should be at the top of the list after high-rank users.
  • If the user score is equal, users with less login time should be at the top of the list after high-score users.

for example:

1. Login userA (ipv4:1.1.1.1, rank:0, score:3000, loginTime:1631966424070)

  • list: [userA]

2. Login userB (ipv4:2.2.2.2, rank:1, score:2000, loginTime:1631966424080)

  • list: [userB, userA]

3. Login userC (ipv4:3.3.3.3, rank:1, score:1000, loginTime:1631966424090)

  • list: [userB, userC, userA]

4. Login userD (ipv4:4.4.4.4, rank:0, score:3000, loginTime:1631966424100)

  • list: [userB, userC, userA, userD]

Access example:

Get user(ipv4:3.3.3.3) -> return userC

There are many users and I use the functional-red-black-tree data structure to improve performance. In this data structure, each item has a key and a value. The constructor of this tree takes a comparator function -like array sort comparator- with two parameters, each of which are keys, as a parameter.

I have defined the user as follows:

class Key {
    constructor(ipv4, rank, score, loginTime) {
        this.ipv4 = ipv4;
        this.rank = rank;
        this.score = score;
        this.loginTime = loginTime;
    }
}

class OnlineUser {

    constructor(ipv4, rank, score, loginTime, name, avatar, bio, gender) {
        this.key = new Key(ipv4, rank, score, loginTime);
        this.name = name;
        this.avatar = avatar;
        this.bio = bio;
        this.gender = gender;
    }
}
module.exports = { OnlineUser, Key };

And I defined the tree with the comparator function like this:

const createTree = require('functional-red-black-tree');

var tree = createTree((userAKey, userBKey) => {
    if (userAKey.ipv4 == userBKey.ipv4) return 0;
    if (userAKey.rank < userBKey.rank) return 1;
    if (userAKey.rank > userBKey.rank) return -1;
    if (userAKey.score < userBKey.score) return 1;
    if (userAKey.score > userBKey.score) return -1;
    if (userAKey.loginTime < userBKey.loginTime) return -1;
    if (userAKey.loginTime > userBKey.loginTime) return 1;
});

And to add user:

tree = tree.insert(user.key, user);

Problem: All users are added in the correct order. But to access or delete or... users are often returned the undefined:

const OnlineUser = require('./model/OnlineUser').OnlineUser;
const Key = require('./model/OnlineUser').Key;

for (let i = 0; i < 1000; i++) {
    let user = new OnlineUser(i, rand(), rand(), rand(), '', '', '', 1);
    tree = tree.insert(user.key, user);
}
console.log(tree.get(new Key(10, 0, 0, 0)));

function rand() {
    return Math.floor(Math.random() * 100);
}

I think this problem is because the comparator function uses different values for comparison and equality.

The solution that seems to me is to hash all the keys and turn it into a key that is hashed as follows:

function hash(ipv4, rank, score, loginTime){
    let hashCode;
    //How to implement?
    return hashCode;
}
  • If the ipv4 is equal to others, the hash values will be the same regardless of the other keys.
  • If the ipv4 is not equal and the rank is greater than the others, the hash value will be greater than the others (except for the previous conditions) regardless of the other keys.
  • If the ipv4 is not equal and the rank is equal to others and the score is greater than the others, the hash value will be greater than the others (except for the previous conditions) regardless of the other keys.
  • If the ipv4 is not equal and the rank is equal to others and the score is equal to others and the login time is less than others, the hash value will be greater than the others (except for the previous conditions) regardless of the other keys.
node.js binary-tree tree data-structures javascript
1 Answers

In your rand example, it is normal that the key (10, 0, 0, 0) will not match, even though ipv4=10 is somewhere in the tree. This is because that node will be more like (10, 66, 35, 19)... which will not be encountered, as the ordering of the tree is mainly based on rank, not on ipv4. The decision to where to drill down in the tree will be based on rank (0), moving to the left side of the tree, while the node you intend to find may be at the right (higher rank 66).

What you can do is to accompany the tree with a Map, which will map an ipv4 value with an existing Key instance. So every time you insert in the tree, also add the corresponding mapping in that Map. And every time you want to find or want to delete, first retrieve the Key instance from that Map by the ipv4 value you have, and pass that Key instance to the tree's get or remove method.

Here is a wrapper class that makes this combination. Extend it with any other method you want to include:

const createTree = require('functional-red-black-tree');

class Key {
    constructor(ipv4, rank, score, loginTime) {
        this.ipv4 = ipv4;
        this.rank = rank;
        this.score = score;
        this.loginTime = loginTime;
    }
}

class OnlineUser {
    constructor(ipv4, rank, score, loginTime, name, avatar, bio, gender) {
        this.key = new Key(ipv4, rank, score, loginTime);
        this.name = name;
        this.avatar = avatar;
        this.bio = bio;
        this.gender = gender;
    }
}

class Tree {
    constructor(comparator) {
        this.tree = createTree(comparator);
        this.map = new Map;
    }
    insert(user) {
        this.tree = this.tree.insert(user.key, user);
        this.map.set(user.key.ipv4, user.key);
    }
    get(ipv4) {
        let key = this.map.get(ipv4);
        if (key) return this.tree.get(key);
    }
    remove(ipv4) {
        let key = this.map.get(ipv4);
        if (key) return tree.remove(key);
    }
}

let tree = new Tree((userAKey, userBKey) =>
    userBKey.rank - userAKey.rank ||
    userBKey.score - userAKey.score ||
    userBKey.loginTime - userAKey.loginTime
);

// Insert  some data:
let userA = new OnlineUser("1.1.1.1", 0, 3000, 1631966424070, "userA");
let userB = new OnlineUser("2.2.2.2", 1, 2000, 1631966424080, "userB");
let userC = new OnlineUser("3.3.3.3", 1, 1000, 1631966424090, "userC");
let userD = new OnlineUser("4.4.4.4", 0, 3000, 1631966424100, "userD");

for (let user of [userA, userB, userC, userD]) {
    tree.insert(user);
}

// Make use of the redblack `forEach`:
tree.tree.forEach((key, value) => console.log(value.name))
// Use our own `get` method:
console.log(tree.get("3.3.3.3")); // userC
user_54598390
Related