Implement Shortest path from map markers positions and short orders

shortestpath.dart

 class Order {
  String? uid;
  String? orderNo;
  String? email;
  String? phoneNumber;
  String? firstName;
  String? lastName;
  String? numberOfAdults;
  String? numberOfChildren;
  String? table;
  bool isDelivered;
  bool? isScheduled;
  List<OrderSku>? orderSkus;
  Address? address;
  Address? addressDelivery;
  double cost;
  bool isPresent;
  String? presentText;
  DateTime? createDate;
  String? customerUid;
  String? merchantUid;
  String paymentStatus;
  String state;
  dynamic paymentDetails;
  String  status;
  String? paymentMethod;
  ShippingNew? shippingNew;
  String? driverUid;
  String? customerComment;
  String? packageSize;
  UserData? customer;
  StripePaymentMethod? payment;
  DateTime? statusUpdateDate;
  num tip;
  num tipAmount;
  bool isPrinted;
  num discount;
  num discountAmount;
  num sittingFee;

  Order(
    this.uid,
    this.orderNo,
    this.email,
    this.phoneNumber,
    this.firstName,
    this.lastName,
    this.numberOfAdults,
    this.numberOfChildren,
    this.table,
    this.isScheduled,
    this.isDelivered,
    this.orderSkus,
    this.address,
    this.addressDelivery,
    this.cost,
    this.isPresent,
    this.presentText,
    this.createDate,
    this.customerUid,
    this.merchantUid,
    this.paymentStatus,
    this.state,
    this.paymentDetails,
    this.status,
    this.paymentMethod,
    // this.shipping,
    this.shippingNew,
    this.driverUid,
    this.customerComment,
    this.packageSize,
    this.customer,
    this.payment,
    this.statusUpdateDate,
    this.tip,
    this.tipAmount,
    this.isPrinted,
    this.discount,
    this.discountAmount,
    this.sittingFee,
  );

  Map<String, dynamic> toJson() {
    return {
      'uid': uid,
      'orderNo': orderNo,
      'email': email,
      'phoneNumber': phoneNumber,
      'firstName': firstName,
      'lastName': lastName,
      'numberOfAdults': numberOfAdults,
      'numberOfChildren': numberOfChildren,
      'table': table,
      'isScheduled':isScheduled == null ?false :isScheduled,
      'isDelivered': isDelivered,
      'orderSkus': orderSkus == null ? [] : jsonEncode(orderSkus),
      'address': address == null ? null : address!.toJson(),
      'addressDelivery':
          addressDelivery == null ? null : addressDelivery!.toJson(),
      'cost': cost,
      'isPresent': isPresent,
      'presentText': presentText,
      'createDate': createDate,
      'customerUid': customerUid,
      'merchantUid': merchantUid,
      'paymentStatus': paymentStatus,
      'state': state,
      'paymentDetails': paymentDetails,
      'status': status,
      'paymentMethod': paymentMethod,
      'shippingNew': shippingNew == null ? null : shippingNew!.toJson(),
      'driverUid': driverUid,
      'customerComment': customerComment,
      'packageSize': packageSize,
      'customer': customer == null ? null : customer!.toJson(),
      'payment': payment == null ? null : payment!.toJson(),
      'statusUpdateDate': statusUpdateDate,
      'tip': tip,
      'tipAmount': tipAmount,
      'isPrinted': isPrinted,
      'discount': discount,
      'discountAmount': discountAmount,
      'sittingFee': sittingFee,
    };
  }

  factory Order.fromJson(Map<String, dynamic> data) {
    return Order(
      data['uid'] ?? '',
      data['orderNo'] ?? '',
      data['email'] ?? '',
      data['phoneNumber'] ?? '',
      data['firstName'] ?? '',
      data['lastName'] ?? '',
      data['numberOfAdults'] ?? '',
      data['numberOfChildren'] ?? '0',
      data['table'] ?? '',
      data['isScheduled']??false,
      data['isDelivered'] ?? false,
      data['orderSkus'] != null
          ? List<OrderSku>.from(
              (json.decode(data['orderSkus'].toString()) as List)
                  .map((i) => OrderSku.fromJson(i)))
          : null,
      data['address'] != null ? Address.fromJson(data['address']) : null,
      data['addressDelivery'] != null
          ? Address.fromJson(data['addressDelivery'])
          : null,
      data['cost']?.toDouble() ?? 0.0,
      data['isPresent'] ?? false,
      data['presentText'],
      data['createDate']?.toDate(),
      data['customerUid'],
      data['merchantUid'],
      data['paymentStatus'] ?? '',
      data['state'] ?? '',
      data['paymentDetails'],
      data['status'] ?? '',
      data['paymentMethod'] ?? '',
      data['shippingNew'] != null
          ? ShippingNew.fromJson(data['shippingNew'])
          : null,
      data['driverUid'] ?? '',
      data['customerComment'] ?? '',
      data['packageSize'] ?? '',
      data['customer'] != null ? UserData.fromJson(data['customer']) : null,
      data['payment'] != null
          ? StripePaymentMethod.fromJson(data['payment'])
          : null,
      data['statusUpdateDate']?.toDate(),
      data['tip'] ?? 0,
      data['tipAmount'] ?? 0,
      data['isPrinted'] ?? false,
      data['discount'] ?? 0,
      data['discountAmount'] ?? 0,
      data['sittingFee'] ?? 0,
    );
  }
}






//---- here sort order according to shortest path.
 
 
 
 
 
 static List<Order> calculateShortestPathOfOrders(
      List<Order> orders, double merchantLatitude, double merchantLongitude) {
    dev.log("merchant Latitude : ${merchantLatitude}, merchant Longitude : ${merchantLongitude}");
    // Calculate the distance between two points using the Haversine formula
    double distance(Address? a1, Address? a2,Order currentorder, Order neighbourOrder,) {
      if (a1?.latLng?.latitude != null &&
          a1?.latLng?.longitude != null &&
          a2?.latLng?.latitude != null &&
          a2?.latLng?.longitude != null) {
       // const p = 0.017453292519943295; // Math.PI / 180
        final lat1 = a1!.latLng!.latitude;
        final lon1 = a1.latLng!.longitude;
        final lat2 = a2!.latLng!.latitude;
        final lon2 = a2.latLng!.longitude;
       return GroupedOrder().calculateDistance(lat1, lon1, lat2, lon2);
       /* final a = 0.5 -
            cos((lat2 - lat1) * p) / 2 +
            cos(lat1 * p) *
                cos(lat2 * p) *
                (1 - cos((lon2 - lon1) * p)) /
                2;
        return 12742 * asin(sqrt(a));*/ // 2 * R; R = 6371 km
      } else {
        dev.log("currentOrderuid:  ${currentorder.uid}"
            "\n cureent order lat: ${currentorder.addressDelivery?.latLng?.latitude}"
            "\n cureent order lng: ${currentorder.addressDelivery?.latLng?.longitude}"
            ",\n neighbour orderUid : ${neighbourOrder?.uid}"
            "  \n neighbour order lat: ${neighbourOrder.addressDelivery?.latLng?.latitude}"
        "\n neighbour order lng: ${neighbourOrder.addressDelivery?.latLng?.longitude}");
        return 0;
      }
    }

    // Calculate the shortest path using Dijkstra's algorithm
    List<Order> shortestPathHelper(List<Order> orders) {
      // Create a set of unvisited orders and set the distances to infinity
      final unvisitedOrders = Set.of(orders);
      final distances = Map.fromIterable(orders,
          key: (order) => order, value: (order) => double.infinity);

      // Set the distance of the first order to 0
      dev.log(" first order uid : ${orders.first.uid}");
      distances[orders.first] = 0;

      // Traverse the graph and update the distances
      while (unvisitedOrders.isNotEmpty) {
        // Find the unvisited order with the smallest distance
        final currentOrder = unvisitedOrders.reduce(
              (a, b) => (distances[a] ?? 0) <
              (distances[b] ?? 0)
              ? a
              : b,
        );

        // Remove the current order from the set of unvisited orders
        unvisitedOrders.remove(currentOrder);

        // Update the distances to the neighboring orders
        for (final neighborOrder in unvisitedOrders) {
          final newDistance = (distances[currentOrder] ?? 0) +
              distance(currentOrder.addressDelivery, neighborOrder.addressDelivery,currentOrder,neighborOrder);

          if (newDistance < (distances[neighborOrder] ?? 0)) {
            distances[neighborOrder] = newDistance;
          }
        }
      }

      // Sort the orders by their distances
      orders.sort(
            (a, b) => (distances[a] ?? 0)
            .compareTo((distances[b] ??0)),
      );
      return orders;
    }

    // Create a dummy order with the merchant's location
    final dummyOrder =Order(
      "merchant_dummy_order",
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      false,
      false,
      [],
      null,
        Address("","","","","", LatLng(merchantLatitude, merchantLongitude)),// add this to address delivery
      0,
      false,
      null,
      null,
      null,
      null,
      PaymentStatus.notPaid,
      OrderState.active,
      null,
      OrderStatus.processing,
      "CARD",
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      0,
      0,
      false,
      0,
      0,
      0,
    );




    // Add the dummy order to the list of orders
    final updatedOrders = List<Order>.from(orders)..insert(0,dummyOrder);
    dev.log("update order length :-- ${updatedOrders.length}");
    // Call the helper function to calculate the shortest path
    final orderedOrders = shortestPathHelper(updatedOrders);

    // Remove the dummy order from the ordered list
    orderedOrders.remove(dummyOrder);

   /* for(var element in orderedOrders) {
      dev.log("soerted orders::   ---    ${element.addressDelivery!.toJson()}");
    }*/

    return orderedOrders;
  }