Question 3

Question 3

Type: Methods & Control Structures

Note: You would think that this is 2D arrays because it talks about it, but it is actually methods and control structures because we are using object-oriented programming to answer the question, not 2D array manipulation.

A two-dimensional array of integers in which most elements are zero is called a sparse array. Because most elements have a value of zero, memory can be saved by storing only the non-zero values along with their row and column indexes. The following complete SparseArrayEntry class is used to represent non-zero elements in a sparse array. A SparseArrayEntry object cannot be modified after it has been constructed.

The SparseArray class represents a sparse array. It contains a list of SparseArrayEntry objects, each of which represents one of the non-zero elements in the array. The entries representing the non-zero elements are stored in the list in no particular order. Each non-zero element is represented by exactly one entry in the list.

The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values.

The sample array can be represented by a SparseArray object, sparse, with the following instance variable values. The items in entries are in no particular order; one possible ordering is shown below.

(a) Write the SparseArray method getValueAt. The method returns the value of the sparse array element at a given row and column in the sparse array. If the list entries contains an entry with the specified row and column, the value associated with the entry is returned. If there is no entry in entries corresponding to the specified row and column, 0 is returned. In the example above, the call sparse.getValueAt(3, 1) would return -9, and sparse.getValueAt(3, 3) would return 0.

Complete method getValueAt below.

(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray:

All entries in the list entries with column indexes matching col are removed from the list.

All entries in the list entries with column indexes greater than col are replaced by entries with column indexes that are decremented by one (moved one column to the left).

The number of columns in the sparse array is adjusted to reflect the column removed.

The sample object sparse from the beginning of the question is repeated for your convenience.

The shaded entries in entries, below, correspond to the shaded column above.

When sparse has the state shown above, the call sparse.removeColumn(1) could result insparse having the following values in its instance variables (since entries is in no particular order, itwould be equally valid to reverse the order of its two items). The shaded areas below show the changes.

SparseArrayEntry class:

public class SparseArrayEntry {
    private int row;
    private int col;
    private int value;
    
    public SparseArrayEntry(int r, int c, int v) {
        row = r;
        col = c;
        value = v;
    }

    public int getRow() {return row;}

    public int getCol() {return col;}

    public int getValue() {return value;}


}

SparseArray class:

public class SparseArray {
    private int numRows;
    private int numCols;
    private List<SparseArrayEntry> entries;

    public SparseArray() {
        entries = new ArrayList<SparseArrayEntry>();
    }

    public int getNumRows() {return numRows;}

    public int getNumCols() {return numCols;}

    public int getValueAt(int row, int col) {
        // Code here
    }

    public void removeColumn(int col) {
        // Code here
    }
}

Skills I’m Familiar With:

Iterate through an ArrayList
Check properties of instantiated elements and compare them between ArrayLists

My Solution (Without Research)

public int getValueAt(int _row, int _col) {
    for (int i = 0; i <= entries.size(); i++) {
        if (entries[i].row == _row && entries[i].col == _col) {
            return entries[i].value;
        }
    }
    return 0;
}

public void removeColumn(int _col) {
    for (int i = 0; i <= entries.size(); i++) {
        if (entries[i].col == _col) {
            entries.remove(entries[i]);
        }
    }
}

My Solution (With Research)

public int getValueAt(int _row, int _col) {
    for (int i = 0; i < entries.size(); i++) {
        if (entries.get(i).getCol() == _col && entries.get(i).getRow() == _row) {
            return entries.get(i).getValue();
        }
    }
    return 0;
}

public void removeColumn(int _col) {
    List<SparseArrayEntry> newEntries = new ArrayList<>();

    for (SparseArrayEntry entry : entries) {
        if (entry.getCol() != _col) {
            if (entry.getCol() > _col) {
                // Adjust column index for entries with columns greater than _col
                entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
            }
            newEntries.add(entry);
        }
    }

    entries = newEntries;
    numCols--;
}

/* KEY ALGORITHM

 The key algorithm here is utilising the properties of child and parent classes through the methods we are required to write for, which effectively completes the understanding of the type of FRQ it is, Methods and Control Structures.
  
*/

To Test My Code

import java.util.ArrayList;
import java.util.List;

public class SparseArrayEntry {
    private int row;
    private int col;
    private int value;

    public SparseArrayEntry(int r, int c, int v) {
        row = r;
        col = c;
        value = v;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getValue() {
        return value;
    }
}

public class SparseArray {
    private int numRows;
    private int numCols;
    private List<SparseArrayEntry> entries;

    public SparseArray() {
        entries = new ArrayList<>();
    }

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    public int getValueAt(int row, int col) {
        for (int i = 0; i < entries.size(); i++) {
            if (entries.get(i).getCol() == col && entries.get(i).getRow() == row) {
                return entries.get(i).getValue();
            }
        }
        return 0;
    }

    public void removeColumn(int col) {
        List<SparseArrayEntry> newEntries = new ArrayList<>();

        for (SparseArrayEntry entry : entries) {
            if (entry.getCol() != col) {
                if (entry.getCol() > col) {
                    // Adjust column index for entries with columns greater than col
                    entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
                }
                newEntries.add(entry);
            }
        }

        entries = newEntries;
        numCols--;
    }

    // Additional method to add an entry
    public void addEntry(SparseArrayEntry entry) {
        entries.add(entry);
        numRows = Math.max(numRows, entry.getRow() + 1);
        numCols = Math.max(numCols, entry.getCol() + 1);
    }

    // Additional method to print the SparseArray
    public void printSparseArray() {
        for (SparseArrayEntry entry : entries) {
            System.out.println("(" + entry.getRow() + ", " + entry.getCol() + "): " + entry.getValue());
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // Example usage and testing for SparseArray class

        // Creating a SparseArray object
        SparseArray sparseArray = new SparseArray();

        // Adding some entries to the SparseArray
        sparseArray.addEntry(new SparseArrayEntry(0, 0, 1));
        sparseArray.addEntry(new SparseArrayEntry(1, 1, 2));
        sparseArray.addEntry(new SparseArrayEntry(2, 2, 3));

        // Testing getValueAt method
        System.out.println("Value at (1, 1): " + sparseArray.getValueAt(1, 1));

        // Testing removeColumn method
        System.out.println("Before removing column:");
        sparseArray.printSparseArray();

        int columnToRemove = 1;
        sparseArray.removeColumn(columnToRemove);

        System.out.println("\nAfter removing column " + columnToRemove + ":");
        sparseArray.printSparseArray();
    }
}
Main.main(null);

Value at (1, 1): 2
Before removing column:
(0, 0): 1
(1, 1): 2
(2, 2): 3

After removing column 1:
(0, 0): 1
(2, 1): 3

Notes

Pay attention to the use of ArrayLists. If you’re gonna use ArrayLists, don’t use regular list operations or methods. Instead of arr[index], use arr.get().
Don’t get the property of a class like class.property, use its getter method. It usually has one.

From APCSA FRQs to Our Project

How the methods and control structure algorithms relates to our in-class project

There is no question of whether or not we incorporate methods and control structures. Everything in our backend is object-oriented programming, therefore methods and control structures will never not be present. However, the algorithms present in this particular FRQ have specific examples in our project backend.

Below is a specific example in CompanyController.java of how we use our own getValueAt() method, but for our database instead:

package com.nighthawk.spring_portfolio.mvc.linkr;

import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

import org.modelmapper.ModelMapper;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.http.HttpStatus;
import org.springframework.http.ResponseEntity;
import org.springframework.web.bind.annotation.CrossOrigin;
import org.springframework.web.bind.annotation.DeleteMapping;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.PathVariable;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

import lombok.extern.slf4j.Slf4j;

// Using lombok to automatically generate a logger
@Slf4j
@RestController
@RequestMapping("/api/companies") // Base URL for all endpoints in this controller
@CrossOrigin(origins = "*") // Allowing cross-origin requests from any origin
public class CompanyController {

    private final CompanyService companyService; // Service to handle business logic
    private final ModelMapper modelMapper; // For entity-to-DTO mapping

    @Autowired
    public CompanyController(CompanyService companyService, ModelMapper modelMapper) {
        this.companyService = companyService;
        this.modelMapper = modelMapper;
    }

    // Endpoint to get all companies
    @GetMapping
    public ResponseEntity<List<CompanyDTO>> getAllCompanies() {
        List<Company> companies = companyService.getAllCompanies(); // Retrieve companies from the service
        List<CompanyDTO> companyDTOs = companies.stream()
                .map(company -> modelMapper.map(company, CompanyDTO.class)) // Map entities to DTOs
                .collect(Collectors.toList()); // Collect DTOs into a list
        return new ResponseEntity<>(companyDTOs, HttpStatus.OK); // Return DTO list with OK status
    }

    // Endpoint to get a company by its ID
    @GetMapping("/{companyId}")
    public ResponseEntity<Company> getCompanyById(@PathVariable Long companyId) {
        log.info("Attempting to retrieve company with ID: {}", companyId); // Log the attempt
        Optional<Company> company = companyService.getCompanyById(companyId); // Retrieve the company by ID
        if (company.isPresent()) { // If company is found
            log.info("Found company with ID: {}", companyId); // Log successful retrieval
            return ResponseEntity.ok().body(company.get()); // Return company with OK status
        } else { // If company is not found
            log.warn("Company with ID {} not found", companyId); // Log warning for not found
            return ResponseEntity.status(HttpStatus.NOT_FOUND).build(); // Return NOT_FOUND status
        }
    }

    // Endpoint to add a new company
    @PostMapping
    public ResponseEntity<Company> addCompany(@RequestBody Company company) {
        log.info("Attempting to add company: {}", company); // Log the attempt
        Company addedCompany = companyService.createCompany(company); // Create the company
        log.info("Company added successfully: {}", addedCompany); // Log successful addition
        return new ResponseEntity<>(addedCompany, HttpStatus.CREATED); // Return the added company with CREATED status
    }

    // Endpoint to delete a company by its ID
    @DeleteMapping("/{companyId}")
    public ResponseEntity<Void> deleteCompany(@PathVariable Long companyId) {
        System.out.println("Attempting to delete company with ID: " + companyId); // Log the attempt
        companyService.deleteCompany(companyId); // Delete the company
        System.out.println("Company with ID {} deleted successfully" + companyId); // Log successful deletion
        return ResponseEntity.noContent().build(); // Return NO_CONTENT status
    }
}

And an example of our own version of the removeColumn() from the FRQ in our own project, found in an example I’d like to give from EmployeeController.java:

package com.nighthawk.spring_portfolio.mvc.linkr;

import lombok.extern.slf4j.Slf4j;
import org.modelmapper.ModelMapper;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.http.HttpStatus;
import org.springframework.http.ResponseEntity;
import org.springframework.web.bind.annotation.*;
import com.nighthawk.spring_portfolio.mvc.person.Person;
import com.nighthawk.spring_portfolio.mvc.person.PersonDetailsService;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

// Using lombok to automatically generate a logger
@Slf4j
@RestController
@RequestMapping("/api/employees") // Base URL for all endpoints in this controller
public class EmployeeController {

    private final EmployeeService employeeService; // Service for employee-related operations
    private final ModelMapper modelMapper; // For entity-to-DTO mapping
    private final PersonDetailsService personDetailsService; // Service for managing person details

    @Autowired
    public EmployeeController(EmployeeService employeeService, ModelMapper modelMapper, PersonDetailsService personDetailsService) {
        this.employeeService = employeeService;
        this.modelMapper = modelMapper;
        this.personDetailsService = personDetailsService;
    }

    // Endpoint to get all employees
    @GetMapping
    public ResponseEntity<List<EmployeeDTO>> getAllEmployees() {
        // Retrieving all employees and mapping them to DTOs
        List<Employee> employees = employeeService.getAllEmployees();
        List<EmployeeDTO> employeeDTOs = employees.stream()
                .map(employee -> modelMapper.map(employee, EmployeeDTO.class))
                .collect(Collectors.toList());
        return new ResponseEntity<>(employeeDTOs, HttpStatus.OK); // Returning DTO list with OK status
    }

    // Endpoint to get an employee by their ID
    @GetMapping("/{employeeId}")
    public ResponseEntity<Employee> getEmployeeById(@PathVariable Long employeeId) {
        log.info("Attempting to retrieve employee with ID: {}", employeeId); // Logging the attempt
        Optional<Employee> employee = employeeService.getEmployeeById(employeeId); // Retrieving employee by ID
        if (employee.isPresent()) { // If employee is found
            log.info("Found employee with ID: {}", employeeId); // Logging successful retrieval
            return ResponseEntity.ok().body(employee.get()); // Returning employee with OK status
        } else { // If employee is not found
            log.warn("Employee with ID {} not found", employeeId); // Logging warning for not found
            return ResponseEntity.status(HttpStatus.NOT_FOUND).build(); // Returning NOT_FOUND status
        }
    }

    // Endpoint to add a new employee
    @PostMapping
    public ResponseEntity<Employee> addEmployee(@RequestBody Employee employee) {
        log.info("Attempting to add employee: {}", employee); // Logging the attempt
        Employee addedEmployee = employeeService.createEmployee(employee); // Creating the employee
        log.info("Employee added successfully: {}", addedEmployee); // Logging successful addition
        
        // Creating a Person object and saving person details
        Person p6 = new Person();
        p6.setName("No Name");
        p6.setEmail(employee.getEmail());
        p6.setPassword(employee.getPassword());
        try {
            Date d = new SimpleDateFormat("MM-dd-yyyy").parse("05-15-2007");
            p6.setDob(d);
        } catch (Exception e) {
        }
        personDetailsService.save(p6); // Saving person details
        
        System.out.println("Hello"); // Printing a message
        
        return new ResponseEntity<>(addedEmployee, HttpStatus.CREATED); // Returning the added employee with CREATED status
    }

    // Endpoint to delete an employee by their ID
    @DeleteMapping("/{employeeId}")
    public ResponseEntity<Void> deleteEmployee(@PathVariable Long employeeId) {
        log.info("Attempting to delete employee with ID: {}", employeeId); // Logging the attempt
        employeeService.deleteEmployee(employeeId); // Deleting the employee
        log.info("Employee with ID {} deleted successfully", employeeId); // Logging successful deletion
        return ResponseEntity.noContent().build(); // Returning NO_CONTENT status
    }
}

As you can see, the @GetMapping methods in CompanyController.java use the same algorithmic logic as the getValueAt() method in the FRQ, and the @DeleteMapping annotated methods in EmployeeController.java are parallel to removeColumn() in the FRQ.