Project-2-Group-79/QuadProbing.cpp at main · voidborne/Project-2-Group-79 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// QuadProbing.cpp
// quadratic probing using (start + i*i) % tableSize to reduce clustering

#include "QuadProbing.h"

// constructor
QuadHashTable::QuadHashTable(int howManySlots)
    : totalSlots(howManySlots), itemsInserted(0), timesWeCollided(0)
{
    tableSlots.resize(totalSlots);
}

int QuadHashTable::figureOutStartingSlot(long long compositeKey)
{
    return (int)(compositeKey % totalSlots);
}

void QuadHashTable::putInTable(const LapRecord& incomingRecord)
{
    long long keyVal = incomingRecord.getCompositeKey();
    int startingSpot = figureOutStartingSlot(keyVal);
    int jumpCount = 0;

    while (jumpCount < totalSlots)
    {
        int tryingThisSpot = (startingSpot + jumpCount * jumpCount) % totalSlots;
        if (!tableSlots[tryingThisSpot].isOccupied)
        {
            tableSlots[tryingThisSpot] = incomingRecord;
            tableSlots[tryingThisSpot].isOccupied = true;
            itemsInserted++;
            return;
        }
        // collision
        timesWeCollided++;
        jumpCount++;
    }
}

int QuadHashTable::lookUpLap(int raceNum, int driverNum, int lapNum)
{
    LapRecord dummyRecord;
    dummyRecord.raceId = raceNum;
    dummyRecord.driverId = driverNum;
    dummyRecord.lap = lapNum;
    long long keyVal = dummyRecord.getCompositeKey();
    int startingSpot = figureOutStartingSlot(keyVal);
    int jumpCount = 0;

    while (jumpCount < totalSlots)
    {
        int tryingThisSpot = (startingSpot + jumpCount * jumpCount) % totalSlots;
        if (!tableSlots[tryingThisSpot].isOccupied)
            break;
        if (tableSlots[tryingThisSpot].getCompositeKey() == keyVal)
            return tableSlots[tryingThisSpot].milliseconds;
        jumpCount++;
    }
    // not found
    return -1;
}

long long QuadHashTable::getCollisionTotal()
{
    return timesWeCollided;
}

int QuadHashTable::getItemCount()
{
    return itemsInserted;
}
// QuadProbing.cpp