3
\$\begingroup\$

I have this short program for simulating a random packet routing algorithm:

Packet.java

package net.coderodde.simulation.network;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 * This class implements a packet being transmitted in the network.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jun 23, 2016)
 */
public class Packet {

    private final int sourceNetworkNodeId;
    private final int targetNetworkNodeId;

    private final List<NetworkNode> history = new ArrayList<>();
    private int cycles;

    public Packet(final int id, 
                  final int sourceNetworkNodeId, 
                  final int targetNetworkNodeId) {
        this.sourceNetworkNodeId = sourceNetworkNodeId;
        this.targetNetworkNodeId = targetNetworkNodeId;
    }

    public boolean isDelivered() {
        if (history.isEmpty()) {
            return false;
        }

        return history.get(history.size() - 1).getId() == targetNetworkNodeId;
    }

    public final void mark(final NetworkNode networkNode) {
        history.add(networkNode);
    }

    public final void incrementCycleCounter() {
        cycles++;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();

        sb.append("[")
          .append(sourceNetworkNodeId)
          .append(" -> ")
          .append(targetNetworkNodeId)
          .append("; cycles: ")
          .append(cycles)
          .append("; history: [");

        final Map<Integer, Integer> map = compressPath(history);

        final Iterator<Map.Entry<Integer, Integer>> iterator = 
                map.entrySet().iterator();

        if (iterator.hasNext()) {
            final Map.Entry<Integer, Integer> entry = iterator.next();

            if (entry.getValue() == 1) {
                sb.append(entry.getKey());
            } else {
                sb.append(entry.getKey())
                  .append("(")
                  .append(entry.getValue())
                  .append(")");
            }
        }

        while (iterator.hasNext()) {
            final Map.Entry<Integer, Integer> entry = iterator.next();

            sb.append(", ");

            if (entry.getValue() == 1) {
                sb.append(entry.getKey());
            } else {
                sb.append(entry.getKey())
                  .append("(")
                  .append(entry.getValue())
                  .append(")");
            }
        }

        return sb.append("]]").toString();
    }

    private Map<Integer, Integer> compressPath(final List<NetworkNode> path) {
        final Map<Integer, Integer> map = new LinkedHashMap<>();

        for (final NetworkNode networkNode : path) {
            final int networkNodeId = networkNode.getId();
            map.put(networkNodeId, map.getOrDefault(networkNodeId, 0) + 1);
        }

        return map;
    }
}

NetworkNode.java:

package net.coderodde.simulation.network;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Random;

/**
 * This class implements a simulated network node. Each node maintains a queue 
 * of packets that have been received but not yet sent away. 
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jun 23, 2016)
 */
public class NetworkNode {

    private final int id;
    private final List<NetworkNode> neighbors = new ArrayList<>();
    private final Deque<Packet> queue = new ArrayDeque<>();
    private final Random random = new Random();

    private int maximumQueueLength;

    public NetworkNode(final int id) {
        this.id = id;
    }

    public final void connect(final NetworkNode node) {
        Objects.requireNonNull(node, "The input node is null.");

        if (!neighbors.contains(node)) {
            neighbors.add(node);
            node.neighbors.add(this);
        }
    }

    public final List<NetworkNode> getNeighborList() {
        return Collections.<NetworkNode>unmodifiableList(neighbors);
    }

    public final int getId() {
        return id;
    }

    public void offetPacket(final Packet packet) {
        queue.add(packet);
    }

    public void sendPacket() {
        maximumQueueLength = Math.max(maximumQueueLength, queue.size());

        for (final Packet packet : queue) {
            packet.incrementCycleCounter();
            packet.mark(this);
        }

        final Iterator<Packet> iterator = queue.iterator();

        while (iterator.hasNext()) {
            final Packet packet = iterator.next();

            if (packet.isDelivered()) {
                iterator.remove();
            }
        }

        if (!queue.isEmpty()) {
            final Packet packet = queue.removeFirst();
            final NetworkNode nextNetworkNode = randomNeighbor();
            nextNetworkNode.queue.addLast(packet);
        }
    }

    @Override
    public String toString() {
        return "[ID = " + id + "; maximum queue length: " +
               maximumQueueLength + "]";
    }

    private final NetworkNode randomNeighbor() {
        return neighbors.get(random.nextInt(neighbors.size()));
    }
}

Main.java:

package net.coderodde.simulation.network;

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

public class Main {

    private static final int NETWORK_SIZE = 10;
    private static final int NUMBER_OF_LINKS = 50;
    private static final int PACKETS = 30;

    public static void main(final String[] args) {
        final List<NetworkNode> network = createRandomNetwork(NETWORK_SIZE,
                                                              NUMBER_OF_LINKS);
        final List<Packet> packets = createInitialPackets(network,
                                                          PACKETS);

        while (somePacketsUndelivered(packets)) {
            for (final NetworkNode networkNode : network) {
                networkNode.sendPacket();
            }
        }

        System.out.println("=== Packet statistics ===");
        packets.forEach(System.out::println);

        System.out.println();
        System.out.println("=== Node statistics ===");
        network.forEach(System.out::println);
    }

    private static boolean somePacketsUndelivered(final List<Packet> packets) {
        for (final Packet packet : packets) {
            if (!packet.isDelivered()) {
                return true;
            }
        }

        return false;
    }

    private static List<NetworkNode> createRandomNetwork(final int size,
                                                         final int edges) {
        final List<NetworkNode> network = new ArrayList<>(size);

        for (int id = 0; id < NETWORK_SIZE; ++id) {
            network.add(new NetworkNode(id));
        }

        final Random random = new Random();

        for (int i = 0; i < edges; ++i) {
            network.get(random.nextInt(NETWORK_SIZE))
                   .connect(network.get(random.nextInt(NETWORK_SIZE)));
        }

        return network;
    }

    private static List<Packet>
         createInitialPackets(final List<NetworkNode> network,
                              final int packets) {
        final Random random = new Random();
        final List<Packet> packetList = new ArrayList<>(packets);

        for (int id = 0; id < packets; ++id) {
            final NetworkNode source = 
                    network.get(random.nextInt(network.size()));

            final NetworkNode target = 
                    network.get(random.nextInt(network.size()));

            final Packet packet = new Packet(id,
                                             source.getId(),
                                             target.getId());
            packetList.add(packet);
            source.offetPacket(packet);
        }

        return packetList;
    }
}

As always, any critique is much appreciated.

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$
public boolean isDelivered() {
    if (history.isEmpty()) {
        return false;
    }

    return history.get(history.size() - 1).getId() == targetNetworkNodeId;
}

No need for explicitly handling empty case here, just combine:

return !history.isEmpty() && history.get(history.size() - 1).getId() == targetNetworkNodeId;

        if (entry.getValue() == 1) {
            sb.append(entry.getKey());
        } else {
            sb.append(entry.getKey())
              .append("(")
              .append(entry.getValue())
              .append(")");
        }

Take what is similar and extract out of the if-statement...

sb.append(entry.getKey());
if (entry.getValue() == 1) {

} else {
    sb.append("(")
      .append(entry.getValue())
      .append(")");
}

You're left with an empty if, so invert it and remove the else.

sb.append(entry.getKey());
if (entry.getValue() != 1) {
    sb.append("(")
      .append(entry.getValue())
      .append(")");
}

The entirety of this is duplicate code, however - you have an if-statement containing this, and a while-loop containing this. Extract to method appendEntryToStringBuilder:

private void appendEntryToStringBuilder(Map.Entry<Integer, Integer> entry, StringBuilder sb){
    sb.append(entry.getKey());
    if (entry.getValue() != 1) {
        sb.append("(")
          .append(entry.getValue())
          .append(")");
    }
}

public void offetPacket

Did you mean offerPacket?


network.get(random.nextInt(network.size()));

This, or something like it, is used A LOT through out your code. Consider making a method getRandomNode(Random rngSource) which returns a random node.

\$\endgroup\$
-1
\$\begingroup\$

It is almost perfect. There are a few things I would like to point out, correct me if I am wrong:

MAIN CLASS ONLY:

  1. You have some constants that seem unnecessary, because they are only used once in the class and are private

    private static final int NETWORK_SIZE = 10;
    private static final int NUMBER_OF_LINKS = 50;
    private static final int PACKETS = 30;
    
    public static void main(final String[] args) {
        final List<NetworkNode> network = createRandomNetwork(NETWORK_SIZE,
                                                              NUMBER_OF_LINKS);
        final List<Packet> packets = createInitialPackets(network,
                                                          PACKETS);
    

    could be simply replaced with:

    private static final int NETWORK_SIZE = 10;
    
    public static void main(final String[] args){
        final List<NetworkNode> network = createRandomNetwork(NETWORK_SIZE, 50);
        final List<Packet> packets = createInitialPackets(network, 30);
    

    Because the NUMBER_OF_LINKS and PACKETS constants are only used once.

  2. Your method variables (inside the brackets) are used purposely in the createInitialPacket method but not in the createRandomNetwork method. I would change:

    private static List<NetworkNode> createRandomNetwork(final int size,
                                                     final int edges) {
        final List<NetworkNode> network = new ArrayList<>(size);
    
        for (int id = 0; id < NETWORK_SIZE; ++id) {
            network.add(new NetworkNode(id));
        }
    
        final Random random = new Random();
    
        for (int i = 0; i < edges; ++i) {
            network.get(random.nextInt(NETWORK_SIZE))
               .connect(network.get(random.nextInt(NETWORK_SIZE)));
        }
    
        return network;
    }
    

    into:

    private static List<NetworkNode> createRandomNetwork(final int size,
                                                     final int edges) {
        final List<NetworkNode> network = new ArrayList<>(size);
    
        for (int id = 0; id < size; ++id) {
            network.add(new NetworkNode(id));
        }
    
        final Random random = new Random();
    
        for (int i = 0; i < edges; ++i) {
            network.get(random.nextInt(size))
               .connect(network.get(random.nextInt(size)));
        }
    
        return network;
    }
    

    and if you do that step you could do back to point 1 and remove the NETWORK_SIZE constant in the same way.

ALL CLASSES:

  1. It is always good to give both ends of your list a type.

    (constants in order from top to bottom) Packet.java:

    private final List<NetworkNode> history = new ArrayList<NetworkNode>();
    
    final Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
    

    NetworkNode.java:

    private final List<NetworkNode> neighbors = new ArrayList<>();
    private final Deque<Packet> queue = new ArrayDeque<>();
    

    Main.java

    final List<NetworkNode> network = new ArrayList<NetworkNode>(size);
    final List<Packet> packetList = new ArrayList<Packet>(packets);
    

As I said above, please correct me if I am wrong.

\$\endgroup\$
6
  • \$\begingroup\$ Point 3: I completely disagree with this, it's a bothersome effort and doesn't add any new information; my IDE will warn me that the declaration is useless; the only time I'd like to see this is if the type specified DOESN'T match the type of the variable it's going to be put in. \$\endgroup\$
    – Pimgd
    Jun 28, 2016 at 7:43
  • \$\begingroup\$ Also disagreeing with point 1 because that's not a constructor, it's a main method! It's an in-code configuration file and values like that should be constants because then you can infer more sense from them than without the constants. \$\endgroup\$
    – Pimgd
    Jun 28, 2016 at 7:46
  • \$\begingroup\$ Point 2a is correct; I'd say it's a possible bug, but the comment that you can then remove NETWORK_SIZE is misguided to me. All in all, you've got 1 point that seems to make sense, and the rest just plain... doesn't. \$\endgroup\$
    – Pimgd
    Jun 28, 2016 at 7:48
  • \$\begingroup\$ I never said that Point 1 was a constructor. Because the constants are only used once, all you are really doing is giving names to numbers. If the numbers are going to be the same, why have a constant for them? \$\endgroup\$
    – JD9999
    Jun 28, 2016 at 10:26
  • \$\begingroup\$ And as for point 3 you are probably right, but I try to stay on the good side of my IDE. \$\endgroup\$
    – JD9999
    Jun 28, 2016 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.