streching storage manager

[Marcin 'Qrczak' Kowalczyk]

Sat, 29 Sep 2001 10:24:52 +0800 (GMT-8), Saswat Anand <saswatan@comp.nus.edu.sg> 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