streching storage manager
Marcin 'Qrczak' Kowalczyk
29 Sep 2001 07:39:39 GMT
Sat, 29 Sep 2001 10:24:52 +0800 (GMT-8), Saswat Anand <[email protected]> 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
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 * [email protected] http://qrczak.ids.net.pl/
^^ SYGNATURA ZASTĘPCZA