Array concatenation

Question

I have two (very large) arrays foo and bar the same type. To write some good code, I would like to get only a fragment for reading the result concatenating two arrays. This operation must be performed in O (1) time and space.

Array access for result should also be in O (1). In the more general case, if result was the concatenation of slices of array k , random access to the array for result should be done in O ( k ).

I do not want to copy any elements of foo and bar .

It would seem that this is easy to implement in the Rust core, but no number of searches brought me a solution.

Answer 1

There is no predefined type, but you can easily create your own by implementing the Index trait for a type that contains both of your fragments:

 use std::ops::Index; struct Slice<'a, T: 'a>(&'a[T], &'a[T]); impl<'a, T: 'a> Index<usize> for Slice<'a, T> { type Output = T; fn index(&self, index: usize) -> &T { if index < self.0.len() { &self.0[index] } else { &self.1[index - self.0.len()] } } } 

In the general case, if result was the concatenation of slices of the array k , random access to the array for result should be performed in O ( k ).

You can access the slice in O(log(k)) if the fragment is concatenated to O(k) by creating an array that contains the cumulative lengths of the slices, and using a binary search to find the actual slice for indexing.

This will require a macro, because we do not yet have a sufficient constant evaluator and no generics of values.

Answer 2

For n arrays, you can implement it with Vec , as shown below:

 use std::ops::Index; struct VecSlice<'a, T: 'a>(Vec<&'a [T]>); impl<'a, T> Index<usize> for VecSlice<'a, T> { type Output = T; fn index(&self, mut index: usize) -> &T { for slice in self.0.iter() { if index < slice.len() { return &slice[index]; } else { index -= slice.len(); } } panic!("out of bound"); } } 

And then refer to it as an array, just stay in the box.

 fn main() { let a1 = [0, 1, 2]; let a2 = [7, 8, 9]; let a = VecSlice(vec!(&a1, &a2)); println!("{}", a[4]); } 

Will print

 8 

Answer 3

I am afraid that what you ask is almost impossible if you demand that the result be an actual fragment. A slice is a view in a memory block. Continuous memory. If you want a new fragment by combining the other two fragments, you need to copy the contents to a new location so that you get a new contiguous block of memory.

If you are only satisfied with concatenation by copying SliceConcatExt , you provide concat and join methods on slices that can be used on custom type concat if they implement Clone :

 #[derive(Clone, PartialEq, Debug)] struct A { a: u64, } fn main() { assert_eq!(["hello", "world"].concat(), "helloworld"); assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]); assert_eq!([[A { a: 1 }, A { a: 2 }], [A { a: 3 }, A { a: 4 }]].concat(), [A { a: 1 }, A { a: 2 }, A { a: 3 }, A { a: 4 }]); } 

Please note that even if SliceConcatExt unstable, the methods themselves are stable. Therefore, there is no reason not to use them if copying is in order. If you cannot copy, you cannot get a slice. In this case, you need to create a wrapper type as described in the ker answer .