Untitled

 avatar
unknown
plain_text
a year ago
3.9 kB
6
Indexable
/**
 * Create a hash table of Person records based on given relations.
 * @precondition All ids appearing in relations are in the people list.
 * @param people peoples ids and names
 * @param relations parent-child relations
 * @return Returns a hash table with a Person record for each person from people
 *     that includes all relationships according relations.
 */
export function toHashtable(people: People, relations: Relations): PersonTable {


// 1. convert to new format People & Relations -> Person

/*
People: list(pair(id1, name1), pair(id2, name2))

*/
function convertValues(people, relations){

}


//information lagras i hashtablen som [key, value] (UTGÅNGSPUNKT)


function createHashTable(size) {
    const hashTable = new Array(size);


    function hashMethod(key) { //identity hash function
        return key;
        }


   //probing function här; FÖR SET: insertar om null ELLER undefined
            // för get: tillåter null, inte undefined
    
    function setKey(key, value) { //values kmr från den array som skapats när ingångsvärdena har processerats key = person.id, value = person
        function probeForSet(key) {
            let index = hashMethod(key) % size;
            let startIndex = index;
    
            while (hashTable[index] !== undefined && hashTable[index]!== null) {
                index = (index + 1) % size;
                if (index === startIndex) {
                    return -1; // table is full
                }
            }
            return index;
        }

        const indexToSetAt = probeForSet(key);
        if (indexToSetAt === -1) {
            return 'Error: Hash table is full.'
        }
        
        hashTable[indexToSetAt] = [key, value]; //key = person.id, value = person object


    }

//usage: setKey(person.id, person); => placed in hash table at (probed) index

    function getKey(key) {
        function probeForGet(key) {
            let index = hashMethod(key) % size;
            let startIndex = index;

            while (hashTable[index][0] !== key) { //hanterar null implicit
                if (hashTable[index] === undefined) {
                    return 'Error: Key not found or deleted';
                } 
                index = (index + 1) % size;
        //        if (index === startIndex) {
        //            return -1; // table is full
        //        }
            }
            return index;
        }

        //probing function här; fail om UNDEFINED påträffas (standard vid skapandet av hashtablen), så betyder det att keyn inte finns. Om keyn har probats vid set, så kommer indexet som getats inte vara undefined; kmr antingen innehålla key eller null

    }

    //


    function deleteKey(key) {
        function probeForDel(key) {
            let index = hashMethod(key) % size;
            let startIndex = index;

            while (hashTable[index][0] !== key) { //hanterar null implicit
                if (hashTable[index] === undefined) { //hanterar undefined
                    return 'Error: Key not found or deleted';
                } 
                index = (index + 1) % size;
                if (index === startIndex) { //hanterar om ej funnen; ej undefined
                    return -1; // table is full
               }
            }
            return index;
        }

        const keyToDel = probeForDel(key);
        if (keyToDel === -1){
            return 'Error: Key not found or deleted.'
        }
        hashTable[keyToDel] = null;
        return console.log("Key" + keyToDel + "deleted.")


        //if key != key
        //när key är hittad -> hashTable[key] = null;


        //probing function här; VIKTIGT med NULL ist. för undefined(?)
    }


}

createHashTable(300000000000);

// 0. Persons + Relations -> personTable (~array)

// 1. hash identity function

// 2. hash functions: get, set, delete

// 3. implement BCE, etc.
Editor is loading...
Leave a Comment