4

Is there a way to move the entire contents of an ArrayList to another instance of ArrayList in O(1)?

I.e.: only the reference to the backing array is passed from one instance to the other (elements are not copied one by one).

For example:

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = new ArrayList<>();
a.moveContentsTo(b);
// 'a' is now empty, while 'b' contains everything that 'a' did before and 'a != b'
// It is desired that the 'moveContentsTo' method is O(1)

Even better, is there an ArrayList#swapContents(ArrayList) method?

Further explanation and use-case:

Further explanation 1: the references of 'a' and 'b' must not be exchanged. I am not looking for tmp = a; a = b; b = tmp; type of solutions.

Further explanation 2: The operation must be ~O(1) in time.

The use-case: This is useful when an object wants to encapsulate a list constructed outside:

public class A {
    private ArrayList<String> items = new ArrayList<>();

    /**
     * This method takes the sole ownership of the contents. Whoever
     * passed the list from the outside will not be able to modify
     * contents of 'this.items' from outside the class.
     */ 
    public AnImmutableObject(ArrayList<String> items) {
        if (items != null) {
            items.moveContentsTo(this.items);
        }
    }

    /**
     * Other collections that do not provide the 'move' functionality
     * must be copied. If we just stored the reference to 'items' we
     * would break encapsulation as whoever called the constructor
     * still have write capabilities to the collection.
     */ 
    public A(Collection<String> items) {
        if (items != null) {
            this.items.addAll(items);
        }
    }

    public List<String> getItems() {
        return Collections.unmodifiableList(items);
    }
}

Notice that we want to avoid making a copy (to increase speed and decrease memory usage). The crucial bit is that the callee must lose the ability to modify the (now encapsulated) ArrayList.

Improve this question
5
  • There is nothing that will copy the backing array reference (and it would be unsafe to do so). Why do you want this? What are you trying to accomplish? Commented Apr 5, 2012 at 3:59
  • Look at the use case--it's supposed to be an efficient way to pass around collections and also move the "ownership". Also, look at C++-11 move semantics, I am trying to do something similar to it. Commented Apr 5, 2012 at 4:15
  • But the immutability of AnImmutableObject becomes compromised if you copy the backing array's reference instead of the the array list contents. If you don't care about that, then copying the reference to the ArrayList will be functionally equivalent to what you want. Commented Apr 5, 2012 at 4:19
  • There must be only one ArrayList that holds the ownership of the backing array. The moveContentsTo must ensure that, and there should be no way for anyone outside of ArrayList to gain access to the backing array (encapsulation should not be broken). For example, C++-11 is quite capable of doing this. Commented Apr 5, 2012 at 4:23
  • You'd have to copy the source code for ArrayList and make your own version. ArrayList does not allow such extensions because the backing array is set to private. Commented Jun 18, 2012 at 2:47

3 Answers 3

Reset to default
2

@Lirik answer is greate +1. However, if you are looking for a real ArrayList#swapContents(ArrayList), here is how you can do it:

public static void swapContents(ArrayList<String> listA, ArrayList<String> listB)
{
    List<String> temp = new ArrayList<String>(listA);
    listA.clear();
    listA.addAll(listB);
    listB.clear();
    listB.addAll(temp);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This is also not up to requirements. The operation should be O(1). Unless the addAll operations are O(1), which, I believe, they aren't.
@sinharaj I believe there is no way to move elements from ArrayList to another as O(1), unless you use multi-threading (By assigning a thread for each element in the list, whose job is to transfer the element to the other list).
@Eng.Fouad even that wouldn't be O(1), you would still perform n number of operations.
@Lirik n number of operations, but concurrently! which I believe it is similar to O(1).
@Eng.Fouad I get what you're trying to say, but time complexity is not calculated based on how many number of cores you have. Furthermore, unless you have n-number of cores, you will not be able to achieve O(1) time.
2

AFAIK, it's very not Java-like to keep track of "ownership" of references (at least on the programmer's side) which is why I doubt that you'll find the std::move()-like functionality that you want. It just isn't very commonly needed in Java. I guess C++ needs to keep track of object ownership explicitly because there is no garbage collection.

I think that your best bet is to create a defensive copy in your constructor and save space by relying on copy constructors of immutable objects:

public class AnImmutableObject {

    private final List<String> items;

    /**
     * Creates a new immutable object with the given list of items.
     * Always deep copy from an outside source, because we can't know if the
     * calling code will modify that collection later.
     */ 
    public AnImmutableObject(Collection<String> items) {
        // It's a constructor. We know items needs to be set.
        // We are creating a new array list, using its constructor which deep
        // copies the collection, and immediately wrapping it to make it truly
        // immutable. We are guaranteed that no one will hold a reference to the
        // mutable view of the new ArrayList.
        this.items = Collections.unmodifiableList(new ArrayList<String>(items));
    }

    /**
     * Creates a new immutable object with the same items as another.
     * Copying the reference here is completely safe because we
     * enforce the immutability of the items array.
     */ 
    public AnImmutableObject(AnImmutableObject source) {
        items = source.items;
    }

    public List<String> getItems() {
        return items;
    }
}

At this point, you can "pass the arrays around" (really share them) in O(1) between your own immutable objects:

ImmutableObject a = new ImmutableObject(Arrays.asList("A", "B", "C")); // O(n)
ImmutableObject b = new ImmutableObject(a); // O(1)

Hopefully, something like this can suit your purposes.

Another route you could go is use Guava's ImmutableList. Since these are immutable, you can safely copy the reference to the ImmutableList in a constructor.

The main approach is about making it safe for you to copy references to the lists rather than taking ownership over them.

Improve this answer

Comments

2

This should do it:

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = a;
a = new ArrayList<>();

Conceptually speaking, a is now empty and b contains what a contained before. There was a single assignment and no copying of data, which is about the fastest you can do it. Does that satisfy your requirement, or do you actually want a to still reference the same array except that the given array should now be empty?

Update

I don't believe that in C++ the time complexity for the move operation is O(1) either. It's also prudent to point out that "because classes in Java use reference semantics, there are never any implicit copies of objects in those languages. The problem move semantics solve does not and has never existed in Java." (see the answer by FredOverflow: C++ Rvalue references and move semantics)

Is there a way to move the entire contents of an ArrayList to another ArrayList so that only the reference to the backing array is passed from one to the other (i.e., so that elements are not copied one by one).

Given the above statement, then if you copy something from array a to array b in Java, both arrays will reference the same data. All that you do with move semantics in C++ is that you save the temporary object which needs to be created in order to make such a copy:

X foo();
X x;
// perhaps use x in various ways
x = foo();

The last one does:

destructs the resource held by x,
clones the resource from the temporary returned by foo,
destructs the temporary and thereby releases its resource.

Move semantics does:

swap resource pointers (handles) between x and the temporary,
temporary's destructor destruct x's original resource.

You save one destruct, but only in C++... the above problem does not exist in Java! See this article for more details on move semantics: http://thbecker.net/articles/rvalue_references/section_02.html

Improve this answer

9 Comments

This does not satisfy the requirements. Please see further explanation (added post factum).
@sinharaj I don't believe you can do this in O(1) time... you can do it in O(n) time...
Yeah, it seems like it. I've spent ages trying to find this functionality. I guess we'll eventually have to concede and say: no, there is no way of doing this in Java.
@sinharaj I don't know if it's O(1) in c++ either, I have not been able to find out what's the time complexity of std::move either. Furthermore, std::move relies on rvalues for the move semantics and that's not available in Java, see this answer: stackoverflow.com/questions/9498381/…
std::move(a) makes sure that a is an r-value reference. Based on this, instead of the copy constructor the move constructor can be called. The latter then simply moves the backing array pointer from one container to the other (clearly O(1)). Well, since there is no r-value concept in Java, we would have to resort to methods that have access to encapsulated data (like the suggested moveContentsTo). This method would do something similar to the move constructor in C++.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.