Thread: Ordering items but a bit more complex then just swapping items

The initial order comes from an external source that I have no control over. The order is initially defined by that system. This process is a bespoke way to customly adjust the order of the list.

The processAfter methods are called after, they should change the order in the list yes.

There are no other conditions, only that ID property that can adjust the order. There is no concern for height, age etc etc.

one.processAfterEmployee(three) makes sense to avoid looking up the instance.

Can you point me to what kind of datastructure can help me, and potentially an example?

Hi Nord - yes you're right about the comments.

In terms of your comment:

"That implies the that the order of the calls to the processAfter method needs to be ordered.
For this example: move 3 after 4 then move 1 after 3"

This is exactly my point, this is the challenge, how would we define the rule for the order of the call? And I'm thinking we might need some recursive function in here somewhere too? This is the bit I'm stuck on, not sure how to approach this?

Assumption is that if we have the above scenario where two processAfter occur on the same target, then the first call to the target should take precedence

one.processAfterEmployeeId(four); would result in 2, 3 ,4, 1
three.processAfterEmployeeId(four); would result in 2, 4, 1, 3 (1 takes priority as it was already requested to be set after 4)

Originally Posted by Norm

Given those two processAfter received in that order, to get the correct order would require
3 to be moved after 4: 4, 3
and then
1 to be moved after 4: 4, 1, 3

Agree that for all processAfter's that have the same target, processing them in "last in first out" order makes sense.

On your other questions:
when do you get the list of employees <-- they come from an external system.

when do you get the list of processAfter rules <-- a user inputs this in an adhoc manner, if the user wants to process employee one after employee four, he will set this flag on employee one in his system (i.e, the user will set a flag on employee one indicating that it should be processed after employee four)

when do you reorder the list based on the processAfter rules <-- this is the bit I'm trying to figure out, my illustration/question is based on accumlating all of the processAfter's - the challenge is 1) what order to process them in 2) if shuffling items in the order have already been processed by a previous processAfter then we may need a recursive function somewhere? Or do you see this being as straight forward as just being able to execute the processAfter's in a specific order and that's it?

Hey Norm, apologies for the lack of clarity - answers below

Originally Posted by Norm

You didn't really give a when value for the questions.
Let me try another way. Are these assumptions correct:
All the employee information is given before any ordering of the employees is done. All received employees are placed in a list in the order they are received. Yes exactly right
All of the processAfter rules are given before any ordering is done. Yes - correct
All employees and all processAfter rules are received before the employee list is reordered. Yes, correct
There will not be any more employees or processAfter rules received once the ordering of the list is started. Yes, correct, all employees are received, all processAfter rules are stored, now we are ready to apply the reorder..
The processAfter rules are ordered to give the correct result. Not sure I understood this question, the processAfter rules are NOT explicitly ordered in the code, they could be programmaticly set in any random order. What I presented is just an accumulation of the what the user input in the GUI. It is the users intention to flip the order of the employees. What's important is to be able to process the processAfter's in some critical order to achieve the right output order
The employee list is ordered according to the processAfter rules. Yes - correct
Once the list is reordered, the employees in the list are in the order that they are to be processed.

--- Update ---

I thought I would have a crack at coding it, but you see my problem.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
 
public class JavaTestPlugin 
{
	public static void main(String[] args) 
	{
		Employee one = new Employee(1);
		Employee two = new Employee(2);
		Employee three = new Employee(3);
		Employee four = new Employee(4);
 
		// Add to linked list in the order defined above
		LinkedList<Employee> originalList = new LinkedList<>();
		originalList.add(one);
		originalList.add(two);
		originalList.add(three);
		originalList.add(four);
 
		System.out.println("Before:");
		for (Employee e : originalList)
		{
			System.out.println(e.employeeId); // [1, 2, 3, 4]
		}
 
		// set flags to flip the order
		one.processAfterEmployeeId(three);
		three.processAfterEmployeeId(four);
 
 
		List<Employee> impactedEmployees = new ArrayList<>();
		impactedEmployees.add(one);
		impactedEmployees.add(three);
 
		for (Employee sourceEmployee : impactedEmployees)
		{
			Employee targetEmployee = sourceEmployee.getProcessAfterEmployeeValue();
 
			int sourceIndex = getIndex(originalList, sourceEmployee);
			int targetIndex = getIndex(originalList, targetEmployee);
 
			originalList.remove(sourceEmployee);
			originalList.add(targetIndex, sourceEmployee);	
		}
 
		System.out.println("After:");
		for (Employee e : originalList)
		{
			System.out.println(e.employeeId); 
		}
	}
 
	private static int getIndex(LinkedList<Employee> list, Employee e)
	{
		for (int i = 0; i < list.size(); i++) 
		{
			Employee employee = list.get(i);
 
			if (employee.employeeId == e.employeeId)
			{
				return i;
			}
		}
 
		throw new RuntimeException("No id found");
	}
}

public class Employee
{
	int employeeId;
	Employee proessAfterEmployeeId;
 
	public Employee(int employeeId)
	{
		this.employeeId = employeeId;
	}	
 
	public void processAfterEmployeeId(Employee id)
	{
		this.proessAfterEmployeeId = id;
	}
 
	public Employee getProcessAfterEmployeeValue()
	{
 
		return this.proessAfterEmployeeId;
	}
}

Before:
1
2
3
4
After:
2
1
4
3

The After should read 2, 4, 3, 1 - but i'm just not sure how to to amend the list when iterating through each object. Kinda seems like I have to re-loop and shuffle all the items that have been previously set, but impacted by the current adjustment

You're right, I've been playing around with this in my head. The rules can be sorted to achieve the final output order.

If the rules are set like this initially:

two.processAfterEmployeeId(one);
one.processAfterEmployeeId(three);
three.processAfterEmployeeId(four);

To get the final order of [1,2 3,4] - > [4, 3, 1, 2]

The execuiton of the order adjustment needs to take place in this order
three.processAfterEmployeeId(four);
one.processAfterEmployeeId(three);
two.processAfterEmployeeId(one);

What's the best way to be able to do this? Looks like we need a seperate linkedlist to store the rules and then to adjust the rule order based on the source and target employee values

Logically though, is it enough to look at the run after value and sort that descending simply?

for e.g if we take the following rules (note that I have created a very simplistic rule class for this issue)

Rule rule1 = new Rule(2, 1);
Rule rule2 = new Rule(1, 3);
Rule rule3 = new Rule(3, 4);

they should be sorted in order: rule3, rule2, rule1 - this is simply to take the "runAfter" value and sort the objects descending (4, 3, 1). Seems too simple, have I missed a trick amidst all of this?

public class Rule 
{
	private int employeeId;
	private int runAfter;
 
	public Rule (int employeeId, int runAfter)
	{
		this.employeeId = employeeId;
		this.runAfter = runAfter;
	}
 
	public int getEmployeeId()
	{
		return this.employeeId;
	}
 
	public int getRunAfter()
	{
		return this.runAfter;
	}
}

it was too simple.

the original list can be of any order, e.g 8,3,6,2 so ordering descending on the "after" value wont really work. Think I am stuck on the design of this.

I think I've just done a full round and back to square one.

I can't seem to think of a way to sort a list of rules the way that would give me the output.

if I iterate around the rules, i can place the current processing item at a specific index in the list, but the one I am processing may have impacted other items that were previously moved (so they all need moving again) - can someone help me with a java example of this please?

Norm, yes I understand the position of the record needs to be used as opposed to the employee value. Given this example;

// 8,3,6,2
// rules in no particular order
// rule1: move 8 after 6 (8 is at index 0)
// rule2: move 3 after 8 (3 is at index 1)
// rule3: move 2 after 3 (2 is at index 3)

// if i start with the highest source index, which is rule 3, this gives me: 8,3,2,6
// next is rule 2 (3 is already after 8 so nothing to do)
// next is rule 1, this gives me: 3,2,6,8 (HOWEVER, notice that this has conflicted with rule 2 because 3 should be after 8)

Can you see a way or algorithmn to apply the order of rules reliably? This is what I'm trying to seek help with

Originally Posted by Norm

Is there a solution for that set of rules? I think it is possible to have a set of rules that is invalid.
For a simple example:
2 after 4
4 after 2

This is an algorithm problem, not a java programming problem. You need to try asking this question on a forum that is better at finding algorithms than I am.
Try this one: http://www.coderanch.com/forums

The solution for my example is 6,8,3,2

This is an algorithm problem, i have posted on coderanch.