Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have an idea how to implement sub array reverse with O(1), not including precalculation such as reading the input. I will have many reverse operations, and I can't use the trivial solution of O(N).

Edit: To be more clear I want to build data structure behind the array with access layer that knows about reversing requests and inverts the indexing logic as necessary when someone wants to iterate over the array.

Edit 2: The data structure will only be used for iterations

I been reading this and this and even this questions but they aren't helping.

There are 3 cases that need to be taking care of:

  • Regular reverse operation
  • Reverse that including reversed area
  • Intersection between reverse and part of other reversed area in the array

Here is my implementation for the first two parts, I will need your help with the last one.

This is the rule class:

class Rule {
    public int startingIndex;
    public int weight;
}

It is used in my basic data structure City:

public class City {
    Rule rule;
    private static AtomicInteger _counter = new AtomicInteger(-1);
    public final int id = _counter.incrementAndGet();

    @Override
    public String toString() {
        return "" + id;
    }
}

This is the main class:

public class CitiesList implements Iterable<City>, Iterator<City> {

    private int position;
    private int direction = 1;
    private ArrayList<City> cities;
    private ArrayDeque<City> citiesQeque = new ArrayDeque<>();
    private LinkedList<Rule> rulesQeque = new LinkedList<>();


    public void init(ArrayList<City> cities) {
        this.cities = cities;
    }

    public void swap(int index1, int index2){
        Rule rule = new Rule();
        rule.weight = Math.abs(index2 - index1);
        cities.get(index1).rule = rule;
        cities.get(index2 + 1).rule = rule;
    }

    @Override
    public void remove() {
        throw new IllegalStateException("Not implemented");
    }

    @Override
    public City next() {
        City city = cities.get(position);
        if (citiesQeque.peek() == city){
            citiesQeque.pop();
            changeDirection();
            position += (city.rule.weight + 1) * direction;
            city = cities.get(position);
        }
        if(city.rule != null){
            if(city.rule != rulesQeque.peekLast()){
                rulesQeque.add(city.rule);
                position += city.rule.weight * direction;
                changeDirection();
                citiesQeque.push(city);
            }
            else{
                rulesQeque.removeLast();
                position += direction;
            }
        }
        else{
            position += direction;
        }
        return city;
    }

    private void changeDirection() {
        direction *= -1;
    }

    @Override
    public boolean hasNext() {
        return position < cities.size();
    }

    @Override
    public Iterator<City> iterator() {
        position = 0;
        return this;
    }

}

And here is a sample program:

public static void main(String[] args) {
        ArrayList<City> list = new ArrayList<>();
        for(int i = 0 ; i < 20; i++){
            list.add(new City());
        }
        CitiesList citiesList = new CitiesList();
        citiesList.init(list);

        for (City city : citiesList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        citiesList.swap(4, 8);

        for (City city : citiesList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        citiesList.swap(2, 15);

        for (City city : citiesList) {
            System.out.print(city + " ");
        }
    }

How do I handle reverse intersections?

share|improve this question
1  
the bigger question is why do you need so many reverse operations and can you eliminate that –  ratchet freak Oct 31 '13 at 12:26
    
@ratchetfreak Can't, this is the core of my software, it will take me a lot of time to explain its full operation, and I do not want to loose the question context. Invite me to chat if you are interested and I will explain it to you. –  Ilya_Gazman Oct 31 '13 at 12:34
1  
Hi! I think you'll probably get better help if you explain what your algorithm intends to achieve, and then asking if someone can improve on your algorithm. –  Gustav Bertram Oct 31 '13 at 13:37
    
@GustavBertram Read the edit, I think it is all there. If not tell me and I try to figure some thing. –  Ilya_Gazman Oct 31 '13 at 13:44
    
No, I mean the algorithm for the entire program. What is your software attempting to achieve? You see, we need more context. A linked list with reversible sections so it has O(1) to reverse will have slow access. An array with indexes into objects is already very fast to reverse parts of, and it's also fast to access. So there are trade-offs. That's why I ask about the total algorithm. You say you can't remove the reverse operations - you can't know that unless you explain your algorithm. –  Gustav Bertram Oct 31 '13 at 13:48

5 Answers 5

up vote 5 down vote accepted

You could use a xor linked list variant (using indexes into an array for the pointer).

Then reversing is easy:

reverse(int city1prev, int city1index, int city2prev, int city2index)
{

    int city1next = array[city1index].ptr^city1prev;
    int city2next = array[city2index].ptr^city2prev;

    city1.ptr = city2next^city1next;
    city2.ptr = city2prev^city1prev;

    array[city1prev].ptr^= city1index^city2index;
    array[city2next].ptr^= city1index^city2index;

}

The downside is (as with all linked list implementations) that indexing into it is O(n).

This will reverse the sub array due to how the xor link works: city2 will be where city1 used to be and city2prev will be after it and so on. So the new sequence becomes: city1prev, city2, city2prev,..., city1next, city1, city2next.

Key point is that there is no difference between traversing a xor linked list forward or backward (you keep a index to the current and the previous items and you get the next by doing array[current].ptr^previous).

share|improve this answer
    
This is not a sub array reverse but a simple reverse between two indexes, this is not what I am looking for. –  Ilya_Gazman Oct 31 '13 at 14:32
    
no it isn't this will also reverse the sub array due to how the xor link works: city2 will be where city1 used to be and city2prev will be after it and so on. so the new sequence becomes: city1prev, city2, city2prev,..., city1next, city1, city2next –  ratchet freak Oct 31 '13 at 14:36
    
I don't understand this completely, I will learn more about it and award your answer once I understand it. Thank you –  Ilya_Gazman Oct 31 '13 at 14:46
    
@Babibu key point is that there is no difference between traversing a xor linked list forward or backward (you keep a index to the current and the previous items and you get the next by doing array[current].ptr^previous) –  ratchet freak Oct 31 '13 at 15:06
    
This is absolutely brilliant! –  Ilya_Gazman Oct 31 '13 at 16:44

There is no point in seeking an efficient mechanism to actually reverse things in an array over and over. You can never get below linear complexity doing that, because you must touch (almost) all items in the subrange.

What you can do is encapsulate your data structure behind an access layer that knows about reversing requests and inverts the indexing logic as necessary when someone wants to iterate over the array. That can get you near-normal performance even for partially reversed arrays, as long as the number of reversing requests is small, i.e. the additional look-up logic is not more expensive than the memory accesses that it saves you. How soon this point is reached depends very much on circumstances such as the actual size of your arrays, likely access patterns, etc.

share|improve this answer
    
If you look in two my code you will see that this is what I am doing. I do not modify the array but adding rules that will represent my reverse over iteration. The problem is that I don't know how to deal with reverses of common places in the array, this is what the question about. –  Ilya_Gazman Oct 31 '13 at 13:10
1  
You cannot implement this solution with generality (i.e. so that it works no matter how many reverses occur) without recursion - either explicitly or implicitly (by simulating stack frames manually). This means that you must have either a self-invocation, or a dynamic data structure and a loop in your access method. So far you have the dynamic data structure, but no loop. –  Kilian Foth Oct 31 '13 at 13:35
    
Yeah, this is the final part that I can't figure. The idea to implement this will be: "fixing" the rules in between the the latest reverse operation that have a weight that put them out side of the reverse scope. For example: reverse(3,19) will create 2 rules: 3,19, than if I do: reverse(10, 30), i will need to add the rules: 10,30 and "fix" the rules: 3,19. It's very hard for me to explain this in worlds, I hope you understand my example. –  Ilya_Gazman Oct 31 '13 at 13:42

I think what you are looking for is an undirected graph. If you use an adjacency list representation to store the route, then if you swap two links in the route (because they were crossing), you need to update the adjacency list for the four nodes that you are affecting.

This is a constant time operation - no matter how big your route, no matter how many links in between nodes, you only have to change the four nodes you're affecting.

In addition, it may be possible to represent the links as a system of linear equations. If there are any solutions to the system of equations, there are links crossing over. Don't quote me on this - you'll have to ask better mathematicians than myself how you'd go about doing this. That way you won't need O(n^2) to check for crossings.

Another way is to have two arrays that store respectively the latitude and the longitude of your nodes. You take the subset A of nodes that is within the latitude +/- the length L of the link you are currently checking. You do the same with the longitude and form set B. The set C that is the intersection of A and B is the set of nodes that are close enough to bother checking.

LatArray = Sorted array of node latitudes

LongArray = Sorted array of node longitudes

L = length of the current link you are checking

A = The set of nodes from LatArray that are in latitude +/- L of the first node of the link you are checking

B = The set of nodes from LongArray that are in longitude +/- L of the first node of the link you are checking

C = intersection of sets A and B

D = Same as C, but for the second node of the link you are checking

What the above does is give you a fast way to determine which other nodes should be checked because they are in the range of the current link. The search function for LatArray and LongArray can be binary.

The above becomes useful when you are dealing with millions of nodes.

However, be warned that the algorithm that you link to here is not sufficient to ensure good routes. Just because an optimal route has no intersections, does not mean that if a route has no intersections it is optimal.

Something like the Clarke-Wright algorithm is probably closer to what you're looking for. There's an explanation and a textbook with more background here:

share|improve this answer
    
The idea with system of linear equations not working. Or may be I did not understand you probably, please take a look. –  Ilya_Gazman Nov 1 '13 at 15:43
    
You misunderstood. A system of linear equations would be useful to detect collisions. You're optimizing your array reversal which will not happen often, but you are not optimizing the code that searches for array reversals. –  Gustav Bertram Nov 3 '13 at 13:34
    
I mean, essentially your original algorithm is O(n^3) because you embed a O(n) algorithm (array subset swapping) inside a O(n^2) algorithm (detecting path collision). Yet you're trying to optimize the O(n) algorithm? You're optimizing in the wrong place. –  Gustav Bertram Nov 3 '13 at 13:45
    
O(N^2) could be optimized to O(N*Log(n)). How ever just today I discovered that there is a name to what I am doing. It'c called 2-opt and this method of optimization will not work with not euclidean TSP. –  Ilya_Gazman Nov 3 '13 at 13:54

Using ratchet freak idea with xor linked list, I came to my own Java implementation with O(1) time complexity for sub array rotation not including pre calculation(such as reading the input).

I call this data structure Directed linked list.

public class Node {
    Node next = null;
    Node previous = null;


    Node getNext(Node node){
        if(node == next){
            return previous;
        }

        if(node == previous){
            return next;
        }

        throw new IllegalStateException("How did you got here?");
    }

    void setNext(Node node, Node next){
        if(node == previous){
            previous = next;
        }
        else if(node == this.next){
            this.next = next;
        }
        else{
            throw new IllegalStateException("How did you got here?");
        }
    }
}

DirectedLinkedList class

public class DirectedLinkedList implements Iterable<Node>, Iterator<Node> {

    private Node head = new Node();
    private Node tail = head;
    private Node current;
    private Node previuse;

    @Override
    public Iterator<Node> iterator() {
        prepareForIteration();
        return this;
    }

    public void addToHead(Node node) {
        Node next = head.getNext(null);
        Node previuse = head.getNext(next);
        head.setNext(previuse, node);
        node.setNext(null, head);
        head = node;
    }

    public void swap(Node a, Node i, Node c, Node j){
        System.out.println("Swaping " + i + " , " + j);
        Node jNext;

        jNext = j.getNext(c);
        jNext.setNext(j, i);

        j.setNext(jNext, a);
        i.setNext(a, jNext);

        a.setNext(i, j);

        System.out.println();

    }

    private void prepareForIteration() {
        current = head;
        previuse = null;
    }

    @Override
    public boolean hasNext() {
        return current != tail;
    }

    @Override
    public Node next() {
        Node tmp = previuse;
        previuse = current;
        current = current.getNext(tmp);
        return previuse;
    }

    @Override
    public void remove() {
        // TODO Auto-generated method stub

    }
}

And here is a sample program: I use City for Node

public class City extends Node{
    private static AtomicInteger _counter = new AtomicInteger(-1);
    public final int id = _counter.incrementAndGet();

    @Override
    public String toString() {
        return "" + id;
    }
}

Main

public class Sample{

    private static DirectedLinkedList directedLinkedList;

    public static void main(String[] args) {
        directedLinkedList = new DirectedLinkedList();
        ArrayList<City> list = new ArrayList<City>();

        for (int i = 0; i < 20; i++) {
            City city = new City();
            directedLinkedList.addToHead(city);
            list.add(city);
        }

        for (Node city : directedLinkedList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        swap(4, 8);

        for (Node city : directedLinkedList) {
            System.out.print(city + " ");
        }
        System.out.println("\n******************");
        swap(6, 12);

        for (Node city : directedLinkedList) {
            System.out.print(city + " ");
        }
    }

    private static void swap(int i, int j) {
        Node a = null, b = null, c = null, d = null;

        int count = 0;
        for (Node city : directedLinkedList) {
            if (count == i) {
                a = city;
            }
            else if (count == i + 1) {
                b = city;
            }
            else if (count == j) {
                c = city;
            }
            else if (count == j + 1) {
                d = city;
            }
            count++;
        }

        directedLinkedList.swap(a, b, c, d);
    }
}
share|improve this answer

Well, what about O(N) for traversal, O(1) for reversal, but with a special O(N*P) for a calculation before doing any traversals?

In the above, N is the size of the array, P is the number of operations you've performed on the array?

Each operation - a reversal - would push into another array a pair, representing the first and last items to be swapped.

So, given an array ABCDE

we would represent the swap BACDE as

(1,2)

Then we could represent the swap to EDCAB ( a full reversal ) as

(1,5)

However, we won't worry about updating the original array for the transitive period, so we can represent the sequence of events as

[(1,2),(1,5)]

And then a final swap to EDACB as

(3,4)

to give us

[(1,2),(1,5),(3,4)]

Obviously so far we've only had O(1) operations, because each is just an insertion of a tuple into our array. Or list, or whatever.

Finally, to produce the EDACB we get

[ABCDE] * [(1,2),(1,5),(3,4)]

Where for each point in the initial array we determine its new position by

Xnew = [(1,2),(1,5),(3,4)].Xorig

 = ( (3,4).( (1,5).( (1,2).Xorig)))

 Where each element of our array, the tuple (defined as (α,β), actions like so:

 Xnew = α-Xorig+β
    where  α>Xorig>β (that is, don't do anything if Xorig isn't in (α,β) )

So this will take (all elements in our set) * (number of tuples we have to worry about)

However, you're always going to be dependent on the number of operations you've executed on the array...

There might be a way to break the array into "bits", so for each element in N you apply a discrete value to it (ie if N < 2, +3, if N >= 2 & N < 5 -1, +3) but right now i don't know how you'd do that.

Still, the above will be a lot simpler than writing a new collection, and for small P just as effective.

share|improve this answer
1  
Read my answer. Its always O(1). It's better then this as you need to read from the events array –  Ilya_Gazman Nov 1 '13 at 17:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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