package cll

  1. Overview
  2. Docs
Mutable circular doubly linked list

Install

Dune Dependency

Authors

Maintainers

Sources

v0.2.0.tar.gz
md5=534e5defb87dfefab80ad58477ee860b
sha512=3324a8b80a9e642fc729d439fb9ecf9a9d40ea465f53b50f2ad6ac62bddc1a11031ab094e0b1223d0200c982b05604d4e3603e754bf1be2583bc5ba230a8f700

Description

A mutable circular doubly linked list designed for O(1) insertion and removal, O(n) traversal, and close to O(1) search using a backing hashtable.

Tags

circular linked list

Published: 13 Nov 2023

README

ocaml-cll

OCaml circular linked list library

Cll documentation

Opam package

Installation

$ opam install cll

Usage

To be run in the ocaml toplevel

let cll = Cll.init [ 1; 2; 3; 4; 5; 6 ];;

Cll.head cll;;
(* int option = Some 1 *)

Cll.length cll;;
(* int = 6 *)

Cll.next cll;;
Cll.head cll;;
(* int option = Some 2 *)

Cll.prev cll;;
Cll.prev cll;;
Cll.head cll;;
(* int option = Some 6 *)

Cll.add cll 7;;
Cll.head cll;;
(* int option = Some 7 *)

Cll.pop cll;;
(* int option = Some 7 *)
Cll.head cll;;
(* int option = Some 1 *)

Cll.find cll 4;;
(* bool = true *)
Cll.head cll;;
(* int option = Some 4 *)

Cll.iter cll (fun x -> Printf.printf "%i\n")
(*
    4
    5
    6
    1
    2
    3
*)

Cll.to_list cll;;
(* int list = [4; 5; 6; 1; 2; 3] *)

Development requirements

  • OCaml

  • Opam

  • Dune

$ ocaml --version
The OCaml toplevel, version 5.1.0

$ opam --version
2.1.5

$ dune --version
3.11.0

Development setup

Install dependencies

opam install . --deps-only --with-test -y

Build code

dune build

Testing

Run unit tests

$ dune test
.................
Ran: 17 tests in: 0.11 seconds.
OK

Check code coverage

dune test --instrument-with bisect_ppx --force

# show coverage summary
bisect-ppx-report summary

# create html coverage report
bisect-ppx-report html
open _coverage/index.html

Running examples

There aren't many uses I'm aware of for a circular linked list, but I have found two programming puzzles where it's been handy.

Prerequisites

From the project's root directory:

# install utop
$ opam install utop

Codewars: Josephus problem

# run the josphus_problem.ml toplevel script
$ dune utop . -- examples/josephus_problem.ml
4

Advent of Code 2020 day 23: Crab Cups

By default only part one of this puzzle will run, as part two takes about 40 seconds on my laptop when running with utop.

To enable part two, uncomment the last three lines in examples/crab_cups.ml.

# run part one of the crab cups toplevel script
$ dune utop . -- examples/crab_cups.ml
part one: 67384529

Dependencies (2)

  1. dune >= "3.10"
  2. ocaml >= "4.05"

Dev Dependencies (3)

  1. odoc with-doc
  2. bisect_ppx with-test
  3. ounit2 with-test

Used by

None

Conflicts

None

OCaml

Innovation. Community. Security.