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?
8
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).
5
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.
3
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);
}
}
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:
- http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.12.html
4
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.
1