import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.BufferedWriter;
import java.io.IOException;

/* An instance of this class represents a set of KeyValPairWithCounts
** objects in which no two of those objects have the same key value.
** Thus, an instance of this class represents what is commonly
** referred to as a "map" or "mapping".
**
** Authors: P.M.J., R.W.M., and < STUDENT's Name >
** Collaborated with: ...
** Known defects: ...
*/

public class KeyValPairSet { 

   // instance variables (fields/attributes)
   // --------------------------------------

   private int size;                        // # elements in this set
   private KeyValPairWithCounts[] members; // members[0..size) holds the set's members 
   private int comparisonCount = 0;         // # of comparisions performed
   private boolean adjusting = false;       // When true, a search for a key tends to
                                            // cause the member with that key to be
                                            // moved closer to the "front" of members[]
   
   private static final int DEFAULT_CAPACITY = 256;
   
   // constructors
   // ------------

   /* Initializes this set to be empty and for its maximum possible
   ** cardinality to be the larger of the specified capacity and the
   ** default capacity.
   */
   public KeyValPairSet(int capacity) {
      capacity = Math.max(DEFAULT_CAPACITY, capacity);
      this.members = new KeyValPairWithCounts[capacity];
      this.size = 0;
   }

   /* Initializes this set to have the capacity specified on the first line
   ** of the file identified by the given argument and having as members the
   ** KeyValPair objects described on subsequent lines in that file.
   ** Each such description is assumed to be suitable for use by the
   ** constructor in the KeyValPairWithCounts class to recreate the
   ** described object.
   */
   public KeyValPairSet(String fileName) throws FileNotFoundException {
      // Create a Scanner object capable of reading from the 
      // file with the specified name.
      Scanner input = new Scanner(new File(fileName));

      // Read the first line of the file, which contains a number 
      // indicating the intended capacity of the set of (key,value)-pairs
      // that is to be populated by those pairs described in the rest
      // of the file.
      int capacity = Integer.parseInt(input.nextLine().trim());


      // Stubbed
      
   }


   // observers
   // ---------
   
   /* Returns the capacity of this set (meaning its maximum possible size).
   */
   public int getCapacity() { return this.members.length; }

   /* Returns the cardinality (i.e., size) of this set (meaning the number
   ** of members).
   */
   public int getCardinality() { return this.size; }

   /* Returns the number of comparisions performed since the last time
   ** resetComparisonCount() was applied to this set.
   */
   public int getComparisonCount() { return this.comparisonCount; }
   
   /* If this set contains an KeyValPair object with the given key,
   ** the value associated to that key (i.e., the value component
   ** of that KeyValPair object) is returned.  Otherwise the empty
   ** string is returned.
   */
   public String getValue(String key) {
      String result = "";
      int index = indexOf(key,true);
      if (index != -1) {
         result = members[index].getValue();
         if (adjusting) { adjustOrdering(index); }
      }
      return result;
   }


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

   /* Resets (to zero) the overall comparision count as well as the
   ** key and value access counts in each KeyValPair object that is
   ** a member of this set.
   */
   public void resetComparisonCounts() {
      this.comparisonCount = 0;
      for(int index = 0; (index < size); index++) {
         members[index].resetKeyAccessCount();
         members[index].resetValueAccessCount();
      }
   }

   /* If this set's cardinality is less than its capacity and none of 
   ** its members has the same key as the given KeyValPair object,
   ** that KeyValPair object becomes a member of this set. 
   ** Otherwise there is no effect.
   */
   public void addKeyValPair(KeyValPairWithCounts a) {
      if (size < members.length) {
         int index = indexOf(a.getKey(), false);
         if (index == -1) {
            members[size] = a;
            size = size + 1;
         }
      }
   }


   /* Changes the state of this object so that subsequent calls to the
   ** getValue() observer cause some reordering of elements in the members[]
   ** array (placing members whose value components are frequently sought
   ** closer to location zero), resulting in searches requiring fewer
   ** comparisons.
   */
   public void turnAdjustingOn() { adjusting = true; }

   /* Changes the state of this object so that subsequent calls to the
   ** getValue() observer will not cause any reordering of elements in
   ** members[].
   */
   public void turnAdjustingOff() { adjusting = false; }

   /* Creates (or overwrites) a file with the given name, writing into it
   ** descriptions of all the KeyValPair objects that are members of this
   ** set.  Each such description is in a form suitable for use by the
   ** constructor in the KeyValPairsWithCounts class to recreate the
   ** object.  Which means that the file produced here is suitable for
   ** use by the constructor of this class to reconstitute this set at a 
   ** later time.
   */
   public void toFile(String fileName) throws IOException {
      final String NEW_LINE = "\n";
      BufferedWriter BW = new BufferedWriter(new FileWriter(fileName));
      BW.write(members.length + NEW_LINE);
      for (int index = 0; index != size; index++) {
         String line = members[index].toString();
         BW.write(line + NEW_LINE);
      }
      BW.close();
   }
   
   // private methods
   // ---------------

   /* Returns the index/location within the members[] array at which
   ** is stored the KeyValPair having the given key, or -1 if there
   ** is no such location.  The second parameter indicates whether or
   ** not the comparisons made during the search should be counted
   ** towards those reported by the getComparisonCount() method.
   */
   private int indexOf(String key, boolean incrementComparisons) {
      int result = -1;
      for  (int index = 0; (result == -1) && (index < size); index++) {
         if (incrementComparisons) { comparisonCount = comparisonCount + 1; }
         if (members[index].equalsKey(key)) { result = index; }
      }
      return result;
   }

   /* Let k be the largest number less than 'index' such that either k = -1 or 
   ** members[k].getValueAccessCount() >= members[index].getValueAccesscount().
   ** This method reorders the elements of members[k+1..index] by placing the
   ** element that had been at location 'index' into location k+1 and by
   ** shifting the elements in members[k+1..index-1] into members[k+2..index].
   ** (In the case k = index-1, this describes no change being made.)
   **
   ** In less technical language, the element members[index] is moved towards
   ** the "front" of the array until such time as it either reaches location
   ** zero or immediately follows an element whose value access count is at
   ** least as large as its own.  Each of the elements that it "passes by"
   ** moves one position "downward" within members[].
   */
   private void adjustOrdering(int index) {

      // Stubbed

   }

   /* Swaps the elements at locations j and k of members[]
   */
   private void swap(int j, int k) {
      KeyValPairWithCounts temp = members[j];
      members[j] = members[k];
      members[k] = temp;
   }

}