Reverse subarray of an array with O(1)
- by Babibu
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?
