/* An instance of this class represents a set of Strings.
** The underlying representation is a hash table in the "open addressing"
** mode and using linear probing as the collision resolution strategy.
** 
** Authors: R. McCloskey and < STUDENTS' names >
** Date: May 2025
*/
public class SetOfStrings {

   // instance variables
   // ------------------

   private String[] table; // where the members of the set are stored
   private int numMembers; // # of members of this set

   // class invariant:
   //   Suppose that table[k] contains string s, and let homeAddressOf(s)
   //   be j.  Then for no i among j, j+1, j+2, ..., k-1 (wrapping around
   //   when/if appropriate) is it the case that table[i] == null.


   // constructor
   // -----------

   /* Initializes this set to be empty.
   */
   public SetOfStrings(int capacity) {
      table = new String[capacity];
      numMembers = 0;
   }


   // observers
   // ---------

   /* Returns the capacity of this set (i.e., the # of members it is
   ** capable of containing)
   */
   public int capacityOf() { return table.length; }


   /* Resports whether or not the given String is a member of this set.
   */
   public boolean isMemberOf(String s) {
      int k = findLoc(s);
      return k != -1  &&  table[k] != null;
   }


   /* Returns the number of members of this set.
   */
   public int numberOfMembers() { return numMembers; }


   /* Reports whether or not the table is full (and thus not
   ** capable of holding any more elements).
   */
   public boolean isFull() { return numberOfMembers() == capacityOf(); }


   /* Displays this set.
   */
   public void display() {
      System.out.printf("The set has %d members:\n", 
                        numberOfMembers());
      for (int i = 0; i != table.length; i++) {
         if (table[i] != null) {
            System.out.println(table[i]);
         }
      }
   }


   /* Displays the table in which the set is stored.
   ** For each table location, it shows the location number.
   ** If the location is occupied, it shows the String that 
   ** occupies it and the home address of that string.
   */
   public void displayTable() {
      final int N = capacityOf();
      for (int i = 0; i != N; i++) {
         System.out.printf("%d: ", i);
         String s = table[i];
         if (s != null) {
            int homeAddr = homeAddressOf(s);
            System.out.printf("\"%s\" (%d)", s, homeAddr);
         }
         System.out.println();
      }
   }


   // mutators
   // --------

   /* Assuming that the given string is not already a member of this
   ** set and there is room in the table to store it, it is inserted
   ** into this set.  Otherwise, nothing changes.
   */
   public void insert(String s) {
      if (isFull()) {
         // do nothing (or a print statement could be inserted here
         // to indicate that no insertion is possible)
      }
      else {
         int k = findLoc(s);

         // < MISSING CODE >  

      }

      // For debugging purposes:
      verifyAll();
   }

   /* Removes the specified string from this set.
   ** Nothing changes if it is not a member.
   */
   public void remove(String s) {
      int k = findLoc(s);

      // < MISSING CODE >


      // For debugging purposes:
      verifyAll();
   }


   // private methods
   // ---------------

   /* Returns the index of the location that immediately follows the 
   ** given one, r, which is to say either r+1 or 0, the latter in 
   ** case r+1 is the capacity of the table.
   */
   private int nextLocation(int r) {
      return (r+1) % table.length;
   }

   /* There are three possibilities.
   ** (1) If the given string occupies some location in the table, the index
   **     of that location is returned.
   ** (2) If the given string is not in the table then
   **     (a) if the table is full, -1 is returned
   **     (b) if the table is not full, the index of the location into
   **         which the given string should be placed (if it were to
   **         be inserted) is returned
   */
   private int findLoc(String s) {
      int count = 0;   // # of locations already probed
      int k = homeAddressOf(s);
      while (count != table.length && table[k] != null && !s.equals(table[k])) {
         k = nextLocation(k);
         count++;
      }
      if (count == table.length) { return -1; }
      else { return k; }
   }


   /* Returns the "home address" of the given string s, which will
   ** be in the range [0..capacityOf()).
   ** That is, this method implements a hash function.
   */
   private int homeAddressOf(String s) {
      final int N = capacityOf();
      long homeAddr = 0;
      for (int i = 0; i != s.length(); i++) {
         long r = Math.abs((int)(Math.pow((int)(s.charAt(i)), (i%5)+1)));
         homeAddr = (homeAddr + r) % N;
      }
      return (int)homeAddr;
   }


   /* Returns the table location at which the string stored in location k
   ** "belongs".  Let s be the string stored in table[k].  Let h be the 
   ** home address of s.  Then the value returned by this method will be the
   ** first number m in the sequence h, h+1, h+2, ..., k  (wrapping around
   ** when necessary) satisfying either m == k or table[m] == null.
   ** pre: table[k] != null
   */
   private int belongsAt(int k) {
      String s = table[k];
      int h = homeAddressOf(s);
      while (h != k  &&  table[h] != null) {
         h = nextLocation(h);
      }
      return h;
   }

   /* Checks each entry in table[] to determine whether it is at the
   ** location at which it "belongs".  A message is printed for each
   ** entry that is not where it belongs.  If all entries are where
   ** they belong, true is returned, else false.
   */
   private boolean verifyAll() {
      boolean allGood = true;
      for (int k = 0; k != table.length; k++) {
         if (table[k] != null) {
            int r = belongsAt(k);
            if (r != k) {
               allGood = false;
               System.out.println("** Hash Table is in error: ");
               System.out.printf("   String at location %d belongs at %d\n",
                                 k, r);

            }
         }
      }
      return allGood;
   }

}