//COMPANY CLASS
public class Company
{
    private RentNode _head;

    public Company() {
        _head = null;
    }

    public Company(RentNode rent) {
        _head = rent;
    }

    private boolean empty() {
        return _head == null;
    }

    private boolean RentalExists(Rent r) {
        RentNode ptr = _head;

        while (ptr != null) {
            if (ptr.getRent().equals(r)) {
                return true;
            }
        }
        return false;
    }

    public boolean addRent(String renterName, Car rentedCar, Date pickDate, Date returnDate) {
        Rent rent = new Rent(renterName, rentedCar, pickDate, returnDate);
        if (empty()) {
            _head = new RentNode(rent);
            return true;
        }
        if (RentalExists(rent)) {
            return false;
        }
        RentNode ptr = _head;

        while (ptr.getNext() != null && (ptr.getRent().getPickDate().before(rent.getPickDate())) || (ptr.getRent().getPickDate().equals(rent.getPickDate())) &&
        (ptr.getRent().howManyDays() > rent.howManyDays())) {
            ptr = ptr.getNext();
        }
        RentNode rentNode = new RentNode(rent, ptr.getNext());
        ptr.setNext(rentNode);

        return true;
    }

    public boolean removeRent(Date d) {
        if (empty()) {
            return false;
        } else {
            if (_head.getRent().getPickDate().equals(d)) {
                _head = _head.getNext();
                return true;
            }
         RentNode behind = _head;
         while (behind.getNext() != null) {
             if (behind.getNext().getRent().getPickDate().equals(d)) {
                 behind.setNext(behind.getNext().getNext());
                 return true;
             }
             behind = behind.getNext();
         }
         return false;
        }
    }

    public int getNumOfRents() {
        return getNumOfRents(_head);
    }

    private int getNumOfRents(RentNode r) {
        if (r == null) {
            return 0;
        }
        return 1 + getNumOfRents(r.getNext());
    }

    public int getSumOfPrices() {
        if (empty()) {
            return 0;
        } else {
            RentNode ptr = _head;
            int sum = 0;

            while (ptr.getNext() != null) {
                sum += ptr.getRent().getPrice();
                ptr = ptr.getNext();
            }
            return sum;
        }

    }

    public int getSumOfDays() {
        if (empty()) {
            return 0;
        } else {
            RentNode ptr = _head;
            int totalDays = 0;

            while (ptr.getNext() != null) {
                totalDays += ptr.getRent().howManyDays();
                ptr = ptr.getNext();
            }
            return totalDays;
        }
    }

    public int averageRent() {
        if (empty()) {
            return 0;
        } else {
            return getSumOfDays() / getNumOfRents();
        }
    }

    public Car lastCarRent() {
        if (empty()) {
            return null;
        } else {
            RentNode ptr = _head;

            while (ptr.getNext() != null) {
                ptr = ptr.getNext();
            }

            Car lastCar = new Car(ptr.getRent().getCar());
            return lastCar;
        }
    }

    public Rent longestRent() {
        if (empty()) {
            return null;
        } else {
            Rent longestRent;
            RentNode max = _head;
            RentNode ptr = _head;
            while (ptr.getNext() != null) {
                if (ptr.getRent().howManyDays() > max.getRent().howManyDays()) {
                    max = ptr;
                }
                ptr = ptr.getNext();

                }
            longestRent = new Rent(max.getRent());
            return longestRent;
    }
}

   public char mostCommonRate() {
       if (empty()) {
           return 'N';
       }
       int[] types = new int[4];
       int aCounter = 0, bCounter = 0, cCounter = 0, dCounter = 0;
       RentNode ptr = _head;

       while (ptr.getNext() != null) {
           if (ptr.getRent().getCar().getType() == 'D') {
               dCounter++;
               types[0] = dCounter;
           }
           if (ptr.getRent().getCar().getType() == 'C') {
               cCounter++;
               types[1] = cCounter;
           }
           if (ptr.getRent().getCar().getType() == 'B') {
               bCounter++;
               types[2] = bCounter;
           }
           if (ptr.getRent().getCar().getType() == 'A') {
               aCounter++;
               types[3] = aCounter;
           }

           ptr = ptr.getNext();
       }
       int max = types[0];
       for (int i = 1; i < types.length - 1; i++) {
           if (max < types[i]) {
               max = types[i];
           }
       }

       if (max == types[0]) {
           return 'D';
       } else if (max == types[1]) {
           return 'C';
       } else if (max == types[2]) {
           return 'B';
       } else {
           return 'A';
       }
   }

   public boolean includes(Company c) {
       if (c.empty() || empty()) {
           return false;
       }

       int cLen = c.getNumOfRents();
       boolean[] equalElements = new boolean[cLen];
       RentNode ptr = _head;
       RentNode cPtr = c._head;

       for (int i = 0; i < cLen; i++) {
           while (ptr.getNext() != null) {
               if (ptr.getRent().equals(cPtr.getRent())) {
                  equalElements[i] = true;
                  break;
               }
               ptr = ptr.getNext();
           }
           cPtr = cPtr.getNext();
       }

       for (int i = 0; i < equalElements.length; i++) {
           if (!equalElements[i]) {
               return false;
           }
       }
       return true;
   }

   public Company merge(Company c) {
       Company newRental;
       RentNode ptr = _head;
       RentNode cPtr = c._head;

       newRental = new Company(merge(ptr, cPtr));
       return newRental;
   }

   private RentNode merge(RentNode r1, RentNode r2) {
       if (r1 == null) {
           return r2;
       }
       if (r2 == null) {
           return r1;
       }

       if (r1.getRent().getPickDate().before(r2.getRent().getPickDate())) {
           r1.setNext(merge(r1.getNext(),r2));
           return r1;
       } else {
           r2.setNext(merge(r1, r2.getNext()));
           return r2;
       }
   }

   public void unifyRents() {
       if (empty()) {
           return;
       }
       int nodeLen = getNumOfRents();
       RentNode behind = _head;
       RentNode ptr = _head.getNext();
       Rent overlapped;

       for (int i = 0; i < nodeLen; i++) {
           while (ptr.getNext() != null) {
               overlapped = behind.getRent().overlap(ptr.getRent());
               if (overlapped == null) {
                   break;
               } else {
                   removeRent(overlapped.getPickDate());
               }
               ptr = ptr.getNext();
           }
           behind = behind.getNext();
           ptr = behind.getNext();
       }

   }

   public String toString() {
       if (empty()) {
           return "The company has 0 rents.";
       } else {
           String opening = "The company has " + getNumOfRents() + " rents:\n";
           String rents = "";
           while (_head != null) {
               rents += _head.getRent().toString() + "\n";
               _head = _head.getNext();
           }
           return opening + rents;
       }
   }

}

//RentNode Class
public class RentNode
{
    protected Rent _rent;
    protected RentNode _next;

    public RentNode (Rent r) {
        if (r != null) {
            _rent = r;
            _next = null;
        }
    }

    public RentNode (Rent r, RentNode next) {
        if (r != null && next != null) {
            _rent = r;
            _next = next;
        }
    }

    public RentNode (RentNode other) {
        _rent = other.getRent();
        _next = other.getNext();
    }

    public Rent getRent() {
        return _rent;
    }

    public void setRent(Rent r) {
        if (_rent.equals(r) || r == null) {
            return;
        }
        _rent = r;
    }

    public RentNode getNext() {
        return _next;
    }

    public void setNext(RentNode next) {
        _next = next;
    }
}