Why does creating a copy of an object still alter instance variables of original object?

Question

I have two classes. Class Algorithm implements a method findIntersections() which is a sweep line algorithm to check for intersections in O(nLogN) time.

It also implements a function addSegments which adds objects of type Segment (two points) to a priority Queue based on the x coordinate.

public class Algorithm {
 
    public PriorityQueue pQueue = new PriortiyQueue();

    //This function adds objects of type Segments to a priority queue
    public void addSegments(List<Segment> segments) {
        pQueue.add(segments);
        //do something
    }

    //This function implements a sweep line algorithm to check for Intersections.
    public void findIntersection() {
        while (!pQueue.isEmpty()) {
            p.poll(); //removes element from Queue
            // do something
        }
    }
}

The other class Model loads data from a CSV file into the priority Queue. This is an intensive process which I only want to do once.

On the other hand, checkForCollissions is called millions of times.

• I want to check for collisions between the supplied segment and the rest of the segments added in the priority queue from the csv file

• I do not want to be adding elements to the priority queue from scratch each time. This would not be feasible.

   public class Model  {
       public Algorithm algoObj = new Algorithm();
       public ArrayList<Segment> algoObj = new ArrayList<>();
       public ArrayList<Segment> segments = new ArrayList<>();
       public ArrayList<Segment> single_segment = new ArrayList<>();
  
       public boolean loadCSV() {
           //read csv file
           while ((strLine = br.readLine()) != null) {
             segments.add(new Segment()); //Add all segments in CSV file to ArrayLisyt
             algo.addSegments(segments);  //Adds 4000 objects of type segment to priority Queue
           }
       }
  
       //This function is called millions of times
       public boolean checkForCollisions(segment_to_check) {
           single_segment.add(segment_to_check);    //Add 1 segment. 
           algoObj.addSegments(single_segment);     //Adds 1 object of type segment to priority Queue
           algoObj.findIntersection();
           single_segment.remove(new Segment()); //Remove above segment to get back to original data
       }
   }
  

TL;DR

The problem I am having is that after the first call of checkForCollisions the priority queue has changed since findIntersection() works by polling elements from the queue, thus altering the queue.

How do I keep the priority queue created by algoObj.addSegments() from changing between function calls?

Does this have to do witch shallow and deep copying as explained here?

---

I tried creating a copy of the queue at the beginning of the function and then altering the copy:

        public boolean checkForCollisions(segment_to_check) {
            Algorithm copy = algoObj;
            single_segment.add(segment_to_check);    //Add 1 segment. 
            copy.addSegments(single_segment);     //Adds 1 object of type segment to priority Queue
            copy.findIntersection();
            single_segment.remove(new Segment()); //Remove above segment to get back to original data
        }
    }

This however does not work as it still alters the priority queue of the original algoObj.

I believe this is a beginner's question and stems from my lack of proper understanding when working with OO languages. Any help would be appreciated.

Answer 1

First of all, it is crucial to know that assigning an existing object to another variable does not create a copy of the original object:

MyObject a = new MyObject();
MyObject b = a; // does NOT create a copy!
// now a and b "point" to the same single instance of MyObject!

Some thoughts about your actual problem:

Your priority queue is just a working data structure that is used for the intersection algorithm, and just while the algorithm is running. When its done (so the intersection(s) have been found), it is empty or at least altered, as you already wrote. So the priority queue must be recreated for every algorithm run.

So what you should do:

1. Load the segments from the CSV file into your ArrayList, but don't pass it to the priority queue yet.

2. Refill (or recreate) the priority queue every time before calling findIntersection(). This is best be done by passing all segments to the method and creating a new prioerity queue from scratch:

   public void findIntersection(Collection<Segment> segments) {
       PriorityQueue<Segment> pQueue = new PrioerityQueue<Segment>(segments);
       while (!pQueue.isEmpty()) {
           p.poll(); //removes element from Queue
           // do something
       }
   }
   

Hint: As I've already wrote at the beginning, this does not copy the individual segments nor the segment collection. It just passes a references. Of course, the priority queue will have to create internal structures at construction time, so if the segments collection is huge, this may take some time.

If this solution is too slow for your needs, you will have to work on your algorithms. Do you really need to check for intersections so often? If you add just one segment to the list, it should be sufficient to check intersections with the other segments, but not if the other segments intersect each other. Probably you could store your segments in a binary search tree similar to the one used by the Bentley–Ottmann algorithm. Whenever a new segment "arrives", it can be checked against the search tree, which should be doable with a time complexity of about O(log n). After that, the segment can be inserted into the tree, if necessary.

Or maybe you can add all segments first and then check for intersections just once.