CODEWITHSUNDEEP
javascriptnode.jsdata-structurestreebinary-tree
Hussein Yaqoobi
Hussein Yaqoobi

Reputation: 492

Tree data structure with multiple keys for each item

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:

for example:

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

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

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

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

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;
}

Upvotes: 2

Views: 664

Answers (1)

trincot
trincot

Reputation: 350477

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

Upvotes: 1

Related Questions