Question

A system of caves is a group of connected underground tunnels. Design an ADT for a cave and a cave system. An archaeologist should be able to add a newly discovered cave to a cave system. He/she can enter this system through only one cave and exit the system only through a different cave. Duplicate caves – based on GPS coordinates – are not permitted. Archaeologists should also be able to list the caves in a given cave system.

File Submission

• Cave.java

Cave object containing Cave Name and Cave GPS coordinates (Latitude and Longitude) and any other appropriate attributes if needed

• CaveInterface.java

Interface containing method definition to add and remove caves

• CaveStack.java

Stack implementation of CaveInterface.java

• CaveStackDemo.java

Demonstrate adding, removing and listing caves. Prompt the user for various cave names and GPS coordinates to show your implementation.

Answer 1

Ans: Since It is asked develop the system in the form of a stack hence removeStack() works as that of a stack but it is also over-ridden and can also be used to remove a particular cave from in between.

Please read comments in the code for better understanding.

import java.util.*;

// --------x Cave.java x---------
class Coordinates{
    double latitude;
    double longitude;
}

class Cave {
    String caveName;
    Coordinates coord;
    
    public Cave(){
        caveName = "";
        coord = new Coordinates();
    }
}

// --------x CaveInterface.java x---------
interface CaveInterface{
    void addCaves(Cave c);
    void removeCave();
    void removeCave(Cave c);
}

// --------x CaveStack.java x---------
class CaveStack implements CaveInterface {
    Stack<Cave> caveSys;
    HashSet<String> caveSet;
    
    public CaveStack(){
        caveSys = new Stack<Cave>();
        caveSet = new HashSet();
    }
    
    // Add unique Caves
    public void addCaves(Cave c){
        // Storing coordinates as string
        String coordinates = c.coord.latitude + " "+c.coord.longitude;

        if(caveSet.contains(coordinates) == false){
            caveSys.push(c);
            caveSet.add(coordinates);
        }
    }
    
    // Remove the top cave from Cave stack
    public void removeCave(){
        
        if(caveSys.empty() == false){
            Coordinates cd = caveSys.peek().coord;
            // Get coordinate string
            String coordinates = cd.latitude + " "+cd.longitude;
            caveSys.pop();
            caveSet.remove(cd);
        }
    }
    
    // Remove a given Cave from the Cave System
    public void removeCave(Cave c){
        int location = caveSys.search(c);
        
        if(caveSys.empty() == false && location != -1){
            Cave temp;
            Stack<Cave> tempStack = new Stack();
            
            // Reach the cave
            while(location > 1){
                temp = caveSys.peek();
                caveSys.pop();
                tempStack.push(temp);
                location--;
            }
            
            // Remove the cave
            String coordinates = c.coord.latitude + " "+c.coord.longitude;
            caveSys.pop();
            caveSet.remove(coordinates);
            
            // Restore the rest of the cave
            while(tempStack.empty() == false){
                temp = tempStack.peek();
                tempStack.pop();
                caveSys.push(temp);
            }
        }
    }
    
    // Lists all the caves present in the given Cave System
    public void listCaves(){
        
        caveSys.forEach(cave -> {
            System.out.println("Name: "+ cave.caveName);
            System.out.println("Coordinates are :-");
            System.out.print("Latitude: "+cave.coord.latitude+" ");
            System.out.println("Longitude: "+cave.coord.longitude);
        });
    }
}

// --------x CaveStackDemo.java x---------
class CaveStackDemo{
    
    // Driver Method
    public static void main(String args[]){
        // First Input
        Scanner sc = new Scanner(System.in); 
        
        Cave c1 = new Cave();
        Cave c2 = new Cave();
        // Reads string before the space
        System.out.print("Enter cave name: ");
        c1.caveName = sc.next();
        System.out.print("Enter Latitude: ");
        c1.coord.latitude = sc.nextDouble();
        System.out.print("Enter Longitude: ");
        c1.coord.longitude = sc.nextDouble();
        
        System.out.print("Enter cave name: ");
        c2.caveName = sc.next();
        System.out.print("Enter Latitude: ");
        c2.coord.latitude = sc.nextDouble();
        System.out.print("Enter Longitude: ");
        c2.coord.longitude = sc.nextDouble();
        
        // Create new cave system
        CaveStack cs = new CaveStack();
        cs.addCaves(c1);
        cs.addCaves(c2);
        
        cs.listCaves();
        
        cs.removeCave();
        cs.listCaves();
    }
}