Sat, 29 Sep 2001 10:24:52 +0800 (GMT-8), Saswat Anand pisze:

As regard to Marcin's suggestion of using a list of compact arrays, although elements can be accessed faster, there will be a lot if redundancy since windows are overlapping. So consecutive arrays will contain almost same data.

I didn't mean to make them overlapping. Splitting into arrays is arbitrary. This can be made an abstract type. One possibility (perhaps another is needed): data CompactQueue a = CL [Array Int a] -- front [Array Int a] -- rear; becomes front (reversed) after front empty !Int -- block size, set during creation !Int -- offset in the head of front - this many elements -- logically don't exist !Int -- similarly, offset in the head of rear emptyQueue :: Int -> CompactQueue a -- Argument is block size. push :: CompactQueue a -> [a] -> CompactQueue a -- Add elements to the end. -- O(block_size) because it must copy one array. (!!) :: CompactQueue a -> Int -> a -- O(index/block_size). drop :: Int -> CompactQueue a -> CompactQueue a -- This can keep up to block_size elements too many in memory -- (in the head of front). Amortized O(n/block_size). When block_size is 1, it degenerates to a plain list or queue (implemented using one-element arrays). -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK