ST Using Binary search (ordered array)

Associative Array Abstraction

Associate one value with each key.

• Method Search() throws an exception if the key is not present.

• Method put() overwrites old value with new value.

Smbol Table.h

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

main.cpp

#include <iostream>
#include "Symbol Table.h"

int main()
{
     try
     {
          // ST<string, int> *st = new ST<string, int>(5);
          // st->put("Banana", 0);
          // st->put("Aapple", 1);
          // st->put("Apple", 2);
          // cout << (boolalpha) << st->delPair("Apple") << endl;

          ST<char, int> *st = new ST<char, int>(5);
          st->put('S', 0);
          st->put('E', 1);
          st->put('A', 2);
          st->put('R', 3);
          st->put('C', 4);
          st->put('H', 5);
          st->put('E', 6);
          st->put('X', 7);
          st->put('A', 8);
          st->put('M', 9);
          st->put('P', 10);
          st->put('L', 11);
          st->put('E', 12);
          cout << (boolalpha) << st->delPair('X') << endl;
          cout << (boolalpha) << st->contain('X') << endl;

          st->deleteMin();
          st->print();
          cout << "Value At Key: " << st->get('A') << endl;
          delete st;
     }
     catch (const runtime_error &e)
     {
          cerr << "Runtime error: " << e.what() << endl; // cerr is the standard error stream, typically used for error messages and diagnostics.
     }
     catch (const invalid_argument &e)
     {
          cerr << "Invalid argument: " << e.what() << endl;
     }
     catch (...)
     {
          cerr << "An unexpected error occurred." << endl;
     }
}