ST Using Binary search (ordered array)
#pragma once
using namespace std;
template <typename Key, typename Value>
class ST
{
Key *keys;
Value *vals;
int n;
int elements = 0;
int i = -1; // increment before insertion & decrement after deletion
bool isEmpty();
bool isFull();
public:
ST(int);
int size();
void put(Key, Value);
bool delPair(Key);
bool deleteMin();
bool deleteMax();
void max();
void min();
bool contain(Key);
Value get(Key);
int rank(Key);
void print();
Key getKey(int) ;
};
template <typename Key, typename Value>
int ST<Key, Value>::size()
{
return elements;
}
template <typename Key, typename Value>
Key ST<Key, Value>::getKey(int i)
{
return keys[i];
}
template <typename Key, typename Value>
bool ST<Key, Value>::isEmpty()
{
return elements == 0;
}
template <typename Key, typename Value>
bool ST<Key, Value>::isFull()
{
return elements == n;
}
template <typename Key, typename Value>
ST<Key, Value>::ST(int n)
{
this->n = n;
keys = new Key[n];
vals = new Value[n];
}
template <typename Key, typename Value>
void ST<Key, Value>::put(Key key, Value val)
{
if (elements == 0)
{
i++;
keys[i] = key;
vals[i] = val;
elements++;
return;
}
int j = rank(key); // gives the index where to insert the new key & value or location of the key that's already present
// if Key already in the table, jsut change its value
if (j <= i && keys[j] == key)
{
vals[j] = val;
}
else
{
// resizing array
if (isFull())
{
n = n * 2;
Key *temp1 = new Key[n];
Value *temp2 = new Value[n];
for (int k = 0; k <= i; k++)
{
temp1[k] = keys[k];
temp2[k] = vals[k];
}
keys = temp1;
vals = temp2;
}
// first insert at the end
i++;
keys[i] = key;
vals[i] = val;
// second swap kth element with ith(Last) element until k < i
for (int k = j; k < i; k++)
{
swap(keys[k], keys[i]);
swap(vals[k], vals[i]);
}
// -- slide logic --
// Key Ktemp = keys[j];
// Value Vtemp = vals[j];
// // Insert in the SORT order.
// for (int k = j; k < i; k++)
// {
// swap(Ktemp, keys[k + 1]);
// swap(Vtemp, vals[k + 1]);
// }
// i++;
// keys[i] = Ktemp;
// vals[i] = Vtemp;
// inserting new key and value at its right location.
// keys[j] = key;
// vals[j] = val;
elements++;
}
}
template <typename Key, typename Value>
bool ST<Key, Value>::delPair(Key key)
{
if (isEmpty())
return false;
if (keys[i] == key)
{
return deleteMax();
}
int delIndex = rank(key);
if (keys[delIndex] == key)
{
// shifting one step backward or use the insertion logic
for (int k = i; k > delIndex; k--)
{
swap(keys[delIndex], keys[k]);
swap(vals[delIndex], vals[k]);
}
i--;
elements--;
return true;
}
return false;
}
template <typename Key, typename Value>
bool ST<Key, Value>::deleteMin()
{
return delPair(keys[0]);
}
template <typename Key, typename Value>
bool ST<Key, Value>::deleteMax()
{
if (isEmpty())
{
cout << "Empty symbol table" << endl;
return false;
}
i--;
elements--;
return true;
}
template <typename Key, typename Value>
void ST<Key, Value>::max()
{
if (isEmpty())
cout << "Empty symbol table" << endl;
cout << keys[i] << ":" << vals[i];
}
template <typename Key, typename Value>
void ST<Key, Value>::min()
{
if (isEmpty())
cout << "Empty symbol table" << endl;
cout << keys[0] << ":" << vals[0];
}
template <typename Key, typename Value>
bool ST<Key, Value>::contain(Key key)
{
int k = rank(key);
return k <= i && keys[k] == key;
}
template <typename Key, typename Value>
Value ST<Key, Value>::get(Key key)
{
if (isEmpty())
throw runtime_error("Search operation on empty symbol table.");
int k = rank(key);
if (k <= i && keys[k] == key)
return vals[k];
else
throw invalid_argument("Key not found in the symbol table.");
}
template <typename Key, typename Value>
int ST<Key, Value>::rank(Key key)
{
int s = 0, e = i;
while (s <= e)
{
int mid = s + (e - s) / 2;
if (keys[mid] == key)
return mid;
else if (keys[mid] < key)
s = mid + 1;
else
e = mid - 1;
}
return s;
}
template <typename Key, typename Value>
void ST<Key, Value>::print()
{
for (int j = 0; j < elements; j++)
{
cout << keys[j] << " : " << vals[j] << endl;
}
}
Last updated