CMPS 134 Fall 2025
(Optional) Prog. Assg. #8: KeyValPairSet
Due: 11:59pm, Dec. 13

Background

A commonly used concept in computing (and particularly in the realm of databases) is that of the (key,value)-pair. The key component of such a pair is intended to uniquely identify some entity of interest. For example, an SSN (issued by the U.S. federal governemnt) identifies a person; a Royal Number identifies a student or employee of the University of Scranton; a VIN (Vehicle Identification Number) identifies an automobile. The value component of such a pair provides some kind of data or information (possibly of a large volume) about the entity identified by the key. If the entity is a person, such data could include items such as name, birthdate, mailing address, etc., etc.

A ubiquitous kind of software application is one that maintains a (possibly large) quantity of (key,value)-pairs and that, in response to queries, provides information about them. The simplest example of this is one in which each query is (possibly) a key and the expected response is the value associated to that key. For instance, suppose that the set of (key,value)-pairs was

{ ("PA","Pennsylvania,46054"), ("NY","New York,54555"), ("NJ","New Jersey,8723"), ... }

in which each pair's key is a state's postal abbreviation and the associated value is a CSV-string whose first field is the full name of the state and whose second field is the surface area of the state (in square miles). Then the query "IL" should produce the CSV-string "Illinois,57914".

Assignment

In the program to be completed for this assignment, (key-value)-pairs will be represented by instances of the KeyValPairWithCounts class, which is provided, as is its parent class, KeyValPair. The child class augments the parent class by introducing methods getKeyAccessCount() and getValueAccessCount() that, respectively, report how many times the key and value components of an object have been accessed via its getKey() and getValue() methods.

Meanwhile, an instance of the Java class KeyValPairSet will be used for the purpose of maintaining a set of (key,value)-pairs (each of which is represented by instances of the KeyValPairWithCounts class). One of its constructors and one of its methods are left for the student to complete.

The manner in which an instance of KeyValPairSet represents a set is quite simple: it stores the members of the set in the array segment members[0..size), where size is, like members, an instance variable. As you can infer, its value is maintained to be equal to the number of members of the set.

To find a (key,value)-pair with a specified key (for the purpose of responding to a query, for example), its indexOf() method performs a sequential search within members[0..size). If a (key,value)-pair happens to be at location k, the number of comparisons needed to find it will be k+1. Thus, (key,value)-pairs located near the front of the array will be found quickly, while those located closer to the end of the array will take much longer to find (assuming that size is at least a moderately large value).

Another instance variable in the KeyValPairSet class is adjusting, which is of the boolean type. Mutator methods allow a client program to modify the value of this variable, in effect dictating in which of two possible modes —adjusting vs. non-adjusting— a KeyValPairSet object finds itself. The difference between the two modes is that, in the adjusting mode, the order of the elements in the members[] array change as a result of queries being carried out, resulting in (key,value)-pairs that have been sought frequently being located towards the front of the array. (The details are spelled out in the comments preceding the relevant method, which is left for the student to complete.)

Provided in full is the Java application ProcessQueries. Its purpose is not only to provide you with a means of testing your work but also to make the point that the way in which a collection of (key,value)-pairs is organized can have a big influence on how much work must be done by a program whose job is to retrieve them in response to queries.

Here is what it does:

  1. Using the contents of a file whose name is provided via the first command-line argument (args[0]), a set of (key,value)-pairs (each element of which is in the form of an instance of the KeyValPairWithCounts class) is built. This set is in the form of an instance of the KeyValPairSet class. It is assumed that the first line of the file contains a number indicating the maximum number of elements allowed in the set. Each subsequent line contains a description of a (key,value)-pair in a form suitable to be passed to the constructor of the KeyValPairWithCounts class.

  2. The queries in the file whose name is provided via the second command-line argument (args[1]) are processed. Each query is expected to match one of the keys in the set discussed above. The program's response to each such query is a line of output that identifies the components of the (key,value)-pair with the matching key and a measure of how much work the indexOf() method of KeyValPairSet did in order to retrieve that pair. (Note that the KeyValPairSet object is in non-adjusting mode during this pass.) Afterwards, a measure of the total work done in processing all the queries is reported.

  3. The same file of queries is processed for a second time. However, before doing this second pass, the KeyValPairSet object is put into adjusting mode, which means that, in reaction to each query, it (possibly) reorders some of the elements in members[] to move the just-sought (key,value)-pair closer to the front of the array. (Using the (key,value)-pairs and queries provided by the sample input files, you will see that these adjustments make a significant difference in how much work is needed during Pass #2 vs. Pass #1.)

  4. The same file of queries is processed for a third time, this time with the KeyValPairSet object having been put back into non-adjusting mode. However, by the time the third pass has begun, the members[] array will have been adjusted to the point where the queries are carried out using much less work than even during Pass #2.

Sample Data and Resulting Output

For the purpose of providing some concrete data on which to run the ProcessQueries program, these two files are offered:

To run the ProcessQueries application and have it use the data in the two provided data files, you must provide it with the names of those two files via what jGrasp calls "run arguments". (When a program is run from the command line, they are called "command-line arguments".) (Here are instructions for running programs in jGrasp that use run arguments.) ProcessQueries interprets the first run argument it receives as being the name of the file containing the (key,value)-pairs (that's WMI_list.txt) and the second as being the name of the file containing the queries (that's WMI_queries.txt).

Excerpt of file WMI_list.txt 
1600
AAA:Audi South Africa made by Volkswagen of South Africa
AAK:FAW Vehicle Manufacturers SA (PTY) Ltd.
AAM:MAN Automotive (South Africa) (Pty) Ltd. (includes VW Truck & Bus)
AAV:Volkswagen South Africa
ABJ:Mitsubishi Colt & Triton pickups made by Mercedes-Benz South Africa 1994 2011
ACV:Isuzu Motors South Africa 2018-
AC5:Hyundai Automotive South Africa
ADD:UD Trucks Southern Africa (Pty) Ltd.
ADM:General Motors South Africa (includes Isuzu through 2018)
ADN:Nissan South Africa (Pty) Ltd.
ADR:Renault Sandero made by Nissan South Africa (Pty) Ltd.
ADX:Tata Automobile Corporation (SA) Ltd.
AFA:Ford Motor Company of Southern Africa & Samcor
AFB:Mazda BT-50 made by Ford Motor Company of Southern Africa
AHH:Hino South Africa
AHM:Honda Ballade made by Mercedes-Benz South Africa 1982 2000
AHT:Toyota South Africa Motors (Pty.) Ltd.
BR1:Mercedes-Benz Algeria (SAFAV MB)
DF9:Laraki
HES:smart Automobile Co., Ltd. (Mercedes-Geely joint venture)

What follows is the output that should be produced by the ProcessQueries program when applied to the data in the two given input files: 

Pass 1 ...
set cardinality: 1373; set capacity: 1600
Key:JH4; Value: Honda {64}
Key:JT2; Value: Toyota car {110}
Key:PP1; Value: Mazda {416}
Key:PR8; Value: Ford {420}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:PP1; Value: Mazda {416}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:7SA; Value: Tesla, Inc. (US-built MPVs (e.g. Model X, Model Y)) {1278}
Key:7JR; Value: Volvo Cars passenger car {1269}
Key:98M; Value: BMW car/SUV {1357}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {872}
Key:PR8; Value: Ford {420}
Key:PR8; Value: Ford {420}
Key:PR8; Value: Ford {420}
Key:55S; Value: Mercedes-Benz car {1239}
Key:937; Value: Dodge {1334}
Key:PN8; Value: Nissan {413}
Key:PP3; Value: Hyundai {417}
Key:4S3; Value: Subaru car {1143}
Key:2C3; Value: Chrysler brand car 1981 2011 {947}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {872}
Key:PN8; Value: Nissan {413}
Key:PR8; Value: Ford {420}
Key:2G1; Value: Chevrolet car {973}
Key:98M; Value: BMW car/SUV {1357}
Key:4S3; Value: Subaru car {1143}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:1G; Value: General Motors USA {841}
Key:1G; Value: General Motors USA {841}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:PR8; Value: Ford {420}
Key:JT2; Value: Toyota car {110}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:JT2; Value: Toyota car {110}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {872}
Key:1G; Value: General Motors USA {841}
Key:WAU; Value: Audi car {610}
Key:PR8; Value: Ford {420}
Key:4S3; Value: Subaru car {1143}
Key:7JR; Value: Volvo Cars passenger car {1269}
Key:JT8; Value: Lexus car {115}
Key:4S3; Value: Subaru car {1143}
Key:4S3; Value: Subaru car {1143}
Key:LRB; Value: SAIC General Motors Buick {243}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:PR8; Value: Ford {420}
Key:PN8; Value: Nissan {413}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}

# of queries: 48; # of comparisons: 35163; average: 732.56
End of Pass 1

Pass 2 ...
set cardinality: 1373; set capacity: 1600
Key:JH4; Value: Honda {64}
Key:JT2; Value: Toyota car {110}
Key:PP1; Value: Mazda {416}
Key:PR8; Value: Ford {420}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {868}
Key:PP1; Value: Mazda {3}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {5}
Key:7SA; Value: Tesla, Inc. (US-built MPVs (e.g. Model X, Model Y)) {1278}
Key:7JR; Value: Volvo Cars passenger car {1270}
Key:98M; Value: BMW car/SUV {1357}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {875}
Key:PR8; Value: Ford {5}
Key:PR8; Value: Ford {3}
Key:PR8; Value: Ford {1}
Key:55S; Value: Mercedes-Benz car {1242}
Key:937; Value: Dodge {1335}
Key:PN8; Value: Nissan {422}
Key:PP3; Value: Hyundai {425}
Key:4S3; Value: Subaru car {1148}
Key:2C3; Value: Chrysler brand car 1981 2011 {953}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {9}
Key:PN8; Value: Nissan {12}
Key:PR8; Value: Ford {1}
Key:2G1; Value: Chevrolet car {979}
Key:98M; Value: BMW car/SUV {10}
Key:4S3; Value: Subaru car {14}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {3}
Key:1G; Value: General Motors USA {851}
Key:1G; Value: General Motors USA {17}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:PR8; Value: Ford {1}
Key:JT2; Value: Toyota car {10}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:JT2; Value: Toyota car {9}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {5}
Key:1G; Value: General Motors USA {9}
Key:WAU; Value: Audi car {621}
Key:PR8; Value: Ford {1}
Key:4S3; Value: Subaru car {9}
Key:7JR; Value: Volvo Cars passenger car {12}
Key:JT8; Value: Lexus car {131}
Key:4S3; Value: Subaru car {6}
Key:4S3; Value: Subaru car {3}
Key:LRB; Value: SAIC General Motors Buick {259}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:PR8; Value: Ford {1}
Key:PN8; Value: Nissan {8}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}

# of queries: 48; # of comparisons: 15189; average: 316.44
End of Pass 2

Pass 3 ...
set cardinality: 1373; set capacity: 1600
Key:JH4; Value: Honda {11}
Key:JT2; Value: Toyota car {4}
Key:PP1; Value: Mazda {8}
Key:PR8; Value: Ford {1}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:PP1; Value: Mazda {8}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:7SA; Value: Tesla, Inc. (US-built MPVs (e.g. Model X, Model Y)) {12}
Key:7JR; Value: Volvo Cars passenger car {10}
Key:98M; Value: BMW car/SUV {9}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {5}
Key:PR8; Value: Ford {1}
Key:PR8; Value: Ford {1}
Key:PR8; Value: Ford {1}
Key:55S; Value: Mercedes-Benz car {13}
Key:937; Value: Dodge {14}
Key:PN8; Value: Nissan {7}
Key:PP3; Value: Hyundai {15}
Key:4S3; Value: Subaru car {3}
Key:2C3; Value: Chrysler brand car 1981 2011 {16}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {5}
Key:PN8; Value: Nissan {7}
Key:PR8; Value: Ford {1}
Key:2G1; Value: Chevrolet car {17}
Key:98M; Value: BMW car/SUV {9}
Key:4S3; Value: Subaru car {3}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:1G; Value: General Motors USA {6}
Key:1G; Value: General Motors USA {6}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:PR8; Value: Ford {1}
Key:JT2; Value: Toyota car {4}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:JT2; Value: Toyota car {4}
Key:1JC; Value: Jeep SUV 1981 1988 (using AMC-style VIN structure) {5}
Key:1G; Value: General Motors USA {6}
Key:WAU; Value: Audi car {18}
Key:PR8; Value: Ford {1}
Key:4S3; Value: Subaru car {3}
Key:7JR; Value: Volvo Cars passenger car {10}
Key:JT8; Value: Lexus car {19}
Key:4S3; Value: Subaru car {3}
Key:4S3; Value: Subaru car {3}
Key:LRB; Value: SAIC General Motors Buick {20}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}
Key:PR8; Value: Ford {1}
Key:PN8; Value: Nissan {7}
Key:1HG; Value: Honda car made by Honda of America Mfg. in Ohio {2}

# of queries: 48; # of comparisons: 312; average: 6.50
End of Pass 3

Done!!!

Program Submission

Submit your completed KeyValPairSet.java file to the relevant Brightspace dropbox.