Re: [Caml-list] kth smallest element

[Bruno De Fraine <Bruno.De.Fraine@vub.ac.be>]

[-- Attachment #1: Type: text/plain, Size: 469 bytes --]

On 15 Jan 2007, at 20:56, Jon Harrop wrote:
> Anyone got code for the kth smallest element in a list that I can  
> borrow?

I have code for a set that can be limited to a certain size. While  
you add a potentially very large number of elements, the set will  
retain the 30 largest elements it has seen up to that point (given  
that the set was initialized with bound 30). You could modify the  
code to keep track of the smallest elements instead.

Regards,
Bruno


[-- Attachment #2: extSet.ml --]
[-- Type: application/octet-stream, Size: 1157 bytes --]

module type KeyedType =
sig
	type t
	type key
	val get_key : t -> key
end ;;

module type S =
sig
	type elt
	type t
	val empty : int option -> t
	val add : elt -> t -> t
	val cardinal : t -> int
	val iter : (elt -> unit) -> t -> unit
	val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
end ;;

let at_bound b c = match b with
	| Some m -> c >= m
	| None -> false
;;

module Make(Kyd: KeyedType) =
struct
	type elt = Kyd.t ;;
	
	module Ord =
	struct
		type t = Kyd.t ;;
		let compare a b =
			let k1 = Kyd.get_key a and k2 = Kyd.get_key b in
			let res = Pervasives.compare k1 k2 in
			if res <> 0 then res
			else Pervasives.compare a b
		;;
	end ;;
	
	module OrdSet = Set.Make(Ord) ;;
	
	(* implementation through bound, count and set *)
	type t = (int option * int * OrdSet.t) ;;
	
	let empty b = (b,0,OrdSet.empty) ;;

	let add x (b,c,s) =
		if c <> 0 && at_bound b c then
			let cand = OrdSet.min_elt s in
			if (Ord.compare x cand) < 0 then (b,c,s)
			else (b,c,OrdSet.add x (OrdSet.remove cand s))
		else (b,c+1,OrdSet.add x s)
	;;
	
	let cardinal (_,c,_) = c ;;
	
	let iter f (_,_,s) = OrdSet.iter f s ;;
	
	let fold f (_,_,s) a = OrdSet.fold f s a ;;
end

[-- Attachment #3: extSet.mli --]
[-- Type: application/octet-stream, Size: 422 bytes --]

(* A set, ordered according to some key, and optionally bounded to a certain size *)

module type KeyedType =
sig
	type t
	type key
	val get_key : t -> key
end

module type S =
sig
	type elt
	type t
	val empty : int option -> t
	val add : elt -> t -> t
	val cardinal : t -> int
	val iter : (elt -> unit) -> t -> unit
	val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
end

module Make(Kyd: KeyedType): S with type elt = Kyd.t

[-- Attachment #4: Type: text/plain, Size: 215 bytes --]



-- 
Bruno De Fraine
Vrije Universiteit Brussel
Faculty of Applied Sciences, INFO - SSEL
Room 4K208, Pleinlaan 2, B-1050 Brussels
tel: +32 (0)2 629 29 75
fax: +32 (0)2 629 28 70
e-mail: Bruno.De.Fraine@vub.ac.be