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?
Best Answer
You could use a xor linked list variant (using indexes into an array for the pointer).
Then reversing is easy:
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
).