A small implementation of a FIFO queue implemented as a circular
buffer of fixed length:
type 'a circular_buffer = {
mutable pos : int;
mutable count : int;
data : 'a array;
size : int;
}
let create size dummy = {
pos = 0;
count = 0;
data = Array.make size dummy;
size;
}
let push buffer elem =
let k = buffer.pos + buffer.count in
buffer.data.(if k < buffer.size then k else 0) <- elem;
if buffer.count < buffer.size then
buffer.count <- buffer.count + 1
else
buffer.pos <- buffer.pos + 1;
()
let pop buffer =
if buffer.count = 0 then raise Not_found;
let result = buffer.data.(buffer.pos) in
(* if you want to free the buffer content, buffer.data.(pos) <- dummy *)
let pos' = buffer.pos + 1 in
buffer.pos <- (if pos' < buffer.size then pos' else 0);
buffer.count <- buffer.count - 1;
result
(* test *)
let () =
let buf = create 2 '0' in
(* *)
push buf '1';
(* 1 *)
push buf '2';
(* 1 2 *)
push buf '3';
(* 2 3 *)
assert (pop buf = '2');
(* 3 *)
push buf '4';
(* 3 4 *)
assert (pop buf = '3');
(* 4 *)
assert (pop buf = '4');
(* *)
assert (try ignore (pop buf); false with Not_found -> true);
assert (try ignore (pop buf); false with Not_found -> true);
On Mon, Apr 2, 2012 at 5:04 PM, David Allsopp <dra-n...@metastack.com> wrote:
> Hongbo Zhang wrote:
>> Hi List,
>> I want to implement sliding window algorithm (in place, no memory
>> copy), I wonder whether I need to write c code.
>>
>> To make it clear and simple,
>> In c, you can record the head pointer of the array, and do the
>> modulo operations when get and set
>> In ocaml, it seems you have an array a of type int array, you can
>> not do things like this *(&a+5).
>
> Perhaps I'm missing something, but if you're planning on using arrays, what's
> wrong with retrieving the item using the array index modulo the length of the
> array?
>
> i.e.
>
> let a = [| ... or whatever ... |] in
> a.(5 mod Array.length a)
>
> If accessing an array by index instead of by pointer worries you, then you're
> looking at the wrong language ;o)
>
>
> David
>
>
> --
> Caml-list mailing list. Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
