Skip to content

Instantly share code, notes, and snippets.

@WetHat

WetHat/CL-Queues.ipynb

Last active February 11, 2025 16:44
Show Gist options
  • Save WetHat/8d871f1e73223e7f8cee7c94a5b795ea to your computer and use it in GitHub Desktop.
Save WetHat/8d871f1e73223e7f8cee7c94a5b795ea to your computer and use it in GitHub Desktop.
Download ZIP
Implementing the QUEUE abstract data type while exploring Common Lisp generic functions.
Display the source blob
Display the rendered blob
Raw
CL-Queues.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Two Queue Data Structures Implemented in Common Lisp\n",
"\n",
"In this notebook we will be implementing frequently used queue data structures.\n",
"While queues are useful datastructure by themselves we use them here to explore\n",
"_Common Lisp_ generic functions.\n",
"\n",
"Generic functions are used to establish contracts similar to _interfaces_ in other programming languages\n",
"such as _C#_ and _Java_. In _Lisp_, however, generic functions are much\n",
"more _informal_ than interfaces:\n",
"* Each generic function stands by itself. A number of\n",
" generic functions can be grouped together by a naming convention or documentation\n",
" to form a contract, but it is possible to implement just an arbitrary subset of the contract\n",
" for a particular class.\n",
"* Unlike interfaces, generic functions are not tied to a particular class.\n",
" One generic function can specify the behavior of more than one class.\n",
"* _Methods_ are used to specialize generic functions for concrete classes.\n",
"\n",
"To demonstrate the specialization of generic functions in oder establish a coherent\n",
"_interface_ across different implementations we implement these queue-like classes:\n",
"* A first-in-first-out (FIFO) queue:\n",
"\n",
" <img src=\"https://techdifferences.com/wp-content/uploads/2017/07/queue.jpg\" alt=\"Fifo Queue\" width=\"200px\"/> \n",
"\n",
"* A binary max heap based priority queue:\n",
"\n",
" <img src=\"http://www.codingfriends.com/wp-content/uploads/2010/06/assignment4-part2.jpg\" alt=\"Priority Queue\" width=\"200px\"/>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## About this Jupyter Notebook\n",
"\n",
"This _Gist_ was created using:\n",
"* the [Jupyter Lab](https://jupyter.org/) computational notebook.\n",
"* the [common-lisp-jupyter](https://yitzchak.github.io/common-lisp-jupyter/) kernel by Frederic Peschanski.\n",
"* [Steel Bank Common Lisp](http://www.sbcl.org/) (SBCL)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Coding Style\n",
"\n",
"For the most part the [Google Common Lisp Style Guide](https://google.github.io/styleguide/lispguide.xml) is used."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The _Queue_ Abstract Data Type\n",
"\n",
"In computer science, a [queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type))\n",
"is a collection of entities in which the entities are kept in order (order\n",
"of entry or priority order).\n",
"\n",
"Typically queues are first-in first-out (FIFO), but other dequeueing strategies are often used\n",
"too (e.g. in [priority queues](https://en.wikipedia.org/wiki/Priority_queue))"
]
},
{
"cell_type": "markdown",
"metadata": {
"toc-hr-collapsed": true,
"toc-nb-collapsed": true
},
"source": [
"# Generic Queue Functions\n",
"\n",
"The typical operations on the collection are the addition\n",
"of entities, known as **enqueue**, and removal of entities, known as **dequeue**. In this section the\n",
"corresponding generic functions are defined.\n",
"\n",
"Technically it is not neccessary to explicitely define generic functions because they are defined automatically when a method is defined. However, for the sake emphasizing the abstract data type aspect, we define and document the generic functions explicitely.\n",
"\n",
"In addition to the basic queue functions some generic _convenience_ functions are specified as well."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## enqueue [Generic Function]\n",
"\n",
"Enqueue an object.\n",
"\n",
"It is the responsibility of the implementing methods\n",
"to decide whether `null` objects can be enqueued.\n",
"\n",
"#### Arguments\n",
"\n",
"cls {`standard-class`}\n",
": A class implementing a queue-like behavior.\n",
"\n",
"obj {`object`}\n",
": The object to enqueue (payload).\n",
"\n",
"#### Returns\n",
"\n",
"The enqueued object"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-GENERIC-FUNCTION COMMON-LISP-USER::ENQUEUE (0)>"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defgeneric enqueue (cls obj))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## dequeue [Generic Function]\n",
"\n",
"Dequeue an object.\n",
"\n",
"#### Arguments\n",
"\n",
"cls {`standard-class`}\n",
": A class implementing queue-like behavior.\n",
"\n",
"#### Returns\n",
"\n",
"The dequeued object or `NIL` if the queue is empty or the\n",
"queue head was a `null` object - in case the queue implementation supports\n",
"`null` objects. To safely decide if queue is empty use the generic function\n",
"`queue-empty-p`."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-GENERIC-FUNCTION COMMON-LISP-USER::DEQUEUE (0)>"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defgeneric dequeue (queue-class))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## peek [Generic Function]\n",
"\n",
"Get the object at the _head_ (front) of a queue without removing (dequeueing) it.\n",
"\n",
"#### Arguments\n",
"\n",
"cls {`standard-class`}\n",
": An class implementing a queue-like behavior.\n",
"\n",
"#### Returns\n",
"\n",
"The object at the front of the queue (same object that would\n",
"be returned by `dequeue`) ."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-GENERIC-FUNCTION COMMON-LISP-USER::PEEK (0)>"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defgeneric peek (cls))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## queue-empty-p [Generic Function]\n",
" Predicate to determine if a queue is empty.\n",
"\n",
"#### Arguments\n",
"\n",
"cls {`standard-class`}\n",
": A queue-like class.\n",
"\n",
"#### Returns\n",
"\n",
"`T` if the given queue is empty. `NIL` otherwise."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-GENERIC-FUNCTION COMMON-LISP-USER::QUEUE-EMPTY-P (0)>"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defgeneric queue-empty-p (cls))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## pprint-queue [Generic Function]\n",
"\n",
"Pretty print a queue.\n",
"\n",
"#### Arguments\n",
"\n",
"cls {`standard-class`}\n",
": A queue-like class.\n",
"\n",
"stream {`output-stream`}\n",
": Optional stream to print to. If omitted\n",
" `*standard-output*` is used.\n",
"\n",
"option {`object`}\n",
": ptional implementation specific printing option.\n",
"\n",
"#### Returns\n",
"\n",
"The queue instance."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-GENERIC-FUNCTION COMMON-LISP-USER::PPRINT-QUEUE (0)>"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"SIMPLE-STYLE-WARNING: \n",
" &OPTIONAL and &KEY found in the same lambda list: (QUEUE-CLASS &OPTIONAL STREAM &KEY &ALLOW-OTHER-KEYS)\n"
]
}
],
"source": [
"(defgeneric pprint-queue (queue-class &optional stream &key &allow-other-keys))"
]
},
{
"cell_type": "markdown",
"metadata": {
"toc-hr-collapsed": false
},
"source": [
"# QUEUE [class] - A Simple First-In-First-Out Queue\n",
"\n",
"This queue implentation adds (enqueues) elements at the rear terminal position (tail)\n",
"and removes (dequeues) them from the front terminal position (head).\n",
"\n",
"![Queue operation](https://upload.wikimedia.org/wikipedia/commons/d/d3/Fifo_queue.png)\n",
"\n",
"To achive this we will be using a list based implementation where\n",
"references to list _head_ and _tail_ are maintained so that items can be added at\n",
"the _tail_ and removed from the _head_ efficiently:\n",
"\n",
"~~~bob\n",
" ╭───┬───╮\n",
" │ o │ #─────╮\n",
" ╰───┴───╯ ⁞\n",
" ^ │\n",
"head ─────╯ v\n",
" ╭───╮\n",
" │ o │\n",
" ├───┤ <- list body\n",
"tail ─────╮ │ # │\n",
" v ╰─│─╯\n",
" ╭───┬───╮ ⁞\n",
" │ Ø │ o <───╯\n",
" ╰───┴───╯\n",
"~~~\n",
" \n",
" Legend:\n",
" o = enqueued object (car)\n",
" ■ - next pointer (cdr)\n",
" Ø - nil\n",
" \n",
"#### Constructor\n",
"\n",
"Construct an queue from a list of items.\n",
"\n",
"~~~ Lisp\n",
"(make-instance 'QUEUE [:items {list}])\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"items {`list`}\n",
"> Optional list of intial members. If omitted an empty queue is created."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-CLASS COMMON-LISP-USER::QUEUE>"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP:INITIALIZE-INSTANCE :AFTER (QUEUE) {1005397243}>"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defclass QUEUE ()\n",
" ((.head. :type list\n",
" :initform nil\n",
" :documentation \"queue head\")\n",
" (.tail. :type list\n",
" :initform nil\n",
" :documentation \"queue tail\"))\n",
")\n",
"\n",
"(defmethod initialize-instance :after ((q QUEUE) &key items)\n",
" (when (consp items)\n",
" (setf (slot-value q '.head.) items)\n",
" (setf (slot-value q '.tail.) (last items))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## pprint-queue [Method]\n",
"\n",
"Most importantly we need a way to pretty print a queue.\n",
"\n",
"~~~ Lisp\n",
"(pprint-queue instance [stream] [:line-width {integer}])\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"instance {`queue`}\n",
": Queue object to print.\n",
"\n",
"stream {`output-stream [*standard-output*]`}\n",
": An output stream designator such as `*standard-output*` (default).\n",
"\n",
"line-width {`integer`} default is `70`\n",
": Optimal maximum line width.\n",
"#### Returns\n",
"\n",
"The input object."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::PPRINT-QUEUE (QUEUE) {1005704C93}>"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod pprint-queue ((instance QUEUE) &optional (stream *standard-output*)\n",
" &key (line-width 70))\n",
" (let ((line \"\"))\n",
" (dolist (obj (slot-value instance '.head.)) ; for all items in the queue\n",
" (setq line (format nil \"~A~A\" line obj))\n",
" (let ((l (length line)))\n",
" (if (<= line-width l)\n",
" (progn ; line is getting too long, print it out\n",
" (format stream \"~A ←╮~%\" line)\n",
" ; draw a line back\n",
" (format stream \"╭─→~v@{~A~:*~}→─╯~%\" (- l 3) \"─\")\n",
" (setq line \"╰← \"))\n",
" ;else grow the current line\n",
" (setq line (concatenate 'string line \" ← \")))))\n",
" (format stream \"~A~%\" line ))\n",
" instance) ; return the input queue"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With this let's create a queue and pretty-print it with different line widths:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"tags": [
"test"
]
},
"outputs": [
{
"data": {
"text/plain": [
"#<QUEUE {100582E763}>"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"1 ← RHABARBER ← STREUSELKUCHEN ← POLARFORSCHER ← LASTWAGEN ← BLUMENTOPF ←╮\n",
"╭─→────────────────────────────────────────────────────────────────────→─╯\n",
"╰← BAHNHOF ← 2 ← 3 ← 4 ← \n",
"1 ← RHABARBER ← STREUSELKUCHEN ← POLARFORSCHER ←╮\n",
"╭─→───────────────────────────────────────────→─╯\n",
"╰← LASTWAGEN ← BLUMENTOPF ← BAHNHOF ← 2 ← 3 ←╮\n",
"╭─→────────────────────────────────────────→─╯\n",
"╰← 4 ← \n"
]
}
],
"source": [
"; Pretty printing a long queue\n",
"(let ((q (make-instance 'QUEUE :items '(1 rhabarber streuselkuchen\n",
" Polarforscher Lastwagen Blumentopf\n",
" Bahnhof 2 3 4))))\n",
" (pprint-queue q)\n",
" (pprint-queue q *standard-output* :line-width 40)) ; now we must specify the stream as well"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## peek [Method]\n",
"\n",
"Get the first element in the queue without removing it.\n",
"\n",
"~~~ Lisp\n",
"(peek instance)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"instance {`queue`}\n",
": Instance of a queue.\n",
"\n",
"#### Returns\n",
"\n",
"The first element in the queue."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::PEEK (QUEUE) {1005EE0FA3}>"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod peek ((instance queue))\n",
" (car (slot-value instance '.head.)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try this out:"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"tags": [
"test"
]
},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(let ((q (make-instance 'QUEUE :items '(1 b c))))\n",
" (assert (= (peek q) 1)) ; queue head = 1\n",
" (assert (eq (car (slot-value q '.tail.)) 'c))) ; queue tail = 'c"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## queue-empty-p [Method]\n",
"\n",
"Predicate to determine if a queue is empty.\n",
"\n",
"~~~ Lisp\n",
"(queue-empty-p instance)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"instance {`queue`}\n",
": The queue to check.\n",
"\n",
"#### Returns\n",
"\n",
"`T` if the given queue is empty. `NIL` otherwise."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::QUEUE-EMPTY-P (QUEUE) {1006147663}>"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod queue-empty-p ((instance QUEUE))\n",
" (null (slot-value instance '.head.)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## enqueue [Method]\n",
"\n",
"Add an object to the end (tail) of the queue.\n",
"\n",
"~~~ Lisp\n",
"(enqueue instance obj)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"instance {`queue`}\n",
": A queue object.\n",
"\n",
"obj {`object`}\n",
": An object to enqueue.\n",
"\n",
"#### Returns\n",
"\n",
"The enqueued object.\""
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::ENQUEUE (QUEUE T) {100636C5B3}>"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod enqueue ((instance QUEUE) obj)\n",
" (let ((l (list obj)) ; prepare for concatenation\n",
" (tail (slot-value instance '.tail.)))\n",
" (if tail\n",
" (rplacd tail l)\n",
" ;else empty queue\n",
" (setf (slot-value instance '.head.) l)) ; set queue head\n",
" (setf (slot-value instance '.tail.) l)) ; point to the new list tail\n",
" obj)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try this out too and:\n",
"* create an empty queue\n",
"* assert that it is indeed empty using the `queue-empty-p` predicate.\n",
"* enqueue an object\n",
"* peek at the queue head"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"tags": [
"test"
]
},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(let ((q (make-instance 'QUEUE))) ; empty queue\n",
" (assert (queue-empty-p q))\n",
" (enqueue q 'a)\n",
" (assert (eq 'a (peek q))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## dequeue [Method]\n",
"\n",
"Extract an object from the front of the queue.\n",
"\n",
"~~~ Lisp\n",
"(dequeue instance)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"instance {`queue`}\n",
": The queue object.\n",
"\n",
"#### Returns\n",
"\n",
"An object from the front (head) of the queue."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::DEQUEUE (QUEUE) {1003B086D3}>"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod dequeue ((instance queue))\n",
" (let ((h (slot-value instance '.head.)))\n",
" (when (consp h)\n",
" (setf (slot-value instance '.head.) (cdr h)) ; pop head\n",
" (unless (cdr h)\n",
" (setf (slot-value instance '.tail.) nil) ; set tail to nil\n",
" )\n",
" )\n",
" (car h))) ; return queue head"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now let's try that out:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"tags": [
"test"
]
},
"outputs": [
{
"data": {
"text/plain": [
"#<QUEUE {1004595753}>"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"\"Original Queue:\" 1 ← 2 ← 3 ← 4 ← 5 ← \n",
"\n",
"\n",
"\"Shortened Queue:\" 2 ← 3 ← 4 ← 5 ← \n"
]
}
],
"source": [
"(let ((q (make-instance 'queue :items '(1 2 3 4 5))))\n",
" (print \"Original Queue:\")\n",
" (pprint-queue q)\n",
" (terpri)\n",
" (assert (eql 1 (dequeue q)))\n",
" (assert (= 4 (length (slot-value q '.head.))))\n",
" (print \"Shortened Queue:\")\n",
" (pprint-queue q))"
]
},
{
"cell_type": "markdown",
"metadata": {
"toc-hr-collapsed": false
},
"source": [
"# A Priority Queue based on the Heap Abstract Data Type\n",
"\n",
"A [heap](https://en.wikipedia.org/wiki/Heap_%28data_structure%29) is a specialized tree-based data structure which satisfies the heap property:\n",
"* In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. The root node has the _greatest_ key of all nodes in the tree.\n",
"* In a min heap, the key of P is less than or equal to the key of C.\n",
" The root node has the _smallest_ key of all nodes in the tree.\n",
"\n",
"The heap is one maximally efficient implementation of an abstract data type called a priority queue, and in fact, priority queues are often referred to as _heaps_.\n",
"\n",
"Here we choose a binary tree implementation. For this we need to define a data structure first which represents\n",
"a node in the binary tree."
]
},
{
"cell_type": "markdown",
"metadata": {
"toc-hr-collapsed": false
},
"source": [
"## BTREE-NODE [Structure] - A Node in a Binary Tree \n",
"\n",
"#### Slots\n",
"\n",
"value {`object`}\n",
": Value object (payload) of the node.\n",
"\n",
"l {`BTREE_NODE`} default is `NIL`\n",
": Optional left child node.\n",
"\n",
"r {`BTREE_NODE`} default is `NIL`\n",
": Optional right child node."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"BTREE-NODE"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defstruct BTREE-NODE\n",
" (value nil)\n",
" (l nil)\n",
" (r nil))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### btree-node-leaf-p [Function] - Testing for Leaf Nodes"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"BTREE-NODE-LEAF-P"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defun btree-node-leaf-p (node)\n",
" (and (null (btree-node-l node)) (null (btree-node-r node))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pretty Printing Binary Trees\n",
"\n",
"Before we can start exploring priority queues we need a way to visualize them. Fortunately we have this\n",
"GitHub gist:\n",
"[Pretty Printing Tree Data Structures in Common Lisp](https://gist.github.com/WetHat/9682b8f70f0241c37cd5d732784d1577#file-cl-prettyprinttrees-ipynb)\n",
"\n",
"This gist explains in great detail how pretty printing of trees works, so we just create a local copy of the code here and use that in the implementation of the priority queue pretty printer without further explanation."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"+SPACE+"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"+UPPER-KNEE+"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"+PIPE+"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"+TEE+"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"+LOWER-KNEE+"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"FORMAT-TREE-SEGMENTS"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"FORMAT-TREE"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defconstant +space+ \" \")\n",
"(defconstant +upper-knee+ \" ╭─ \")\n",
"(defconstant +pipe+ \" │ \")\n",
"(defconstant +tee+ \" ├─ \")\n",
"(defconstant +lower-knee+ \" ╰─ \")\n",
"(defun format-tree-segments (node &key (layout :centered)\n",
" (node-formatter #'write-to-string))\n",
" (unless node\n",
" (return-from format-tree-segments nil)) ; nothing to do here\n",
" (flet ((prefix-node-strings (child-node &key layout node-formatter\n",
" (upper-connector +pipe+)\n",
" (root-connector +tee+)\n",
" (lower-connector +pipe+))\n",
" \"A local utility to add connectors to a string representation\n",
" of a tree segment to connect it to other tree segments.\"\n",
" (multiple-value-bind (u r l)\n",
" (format-tree-segments child-node\n",
" :layout layout\n",
" :node-formatter node-formatter)\n",
" ; prefix tree segment with connector glyphs to connect it to\n",
" ; other segments.\n",
" (nconc\n",
" (mapcar\n",
" (lambda (str)\n",
" (concatenate 'string upper-connector str)) u)\n",
" (list (concatenate 'string root-connector r))\n",
" (mapcar\n",
" (lambda (str)\n",
" (concatenate 'string lower-connector str))\n",
" l)))))\n",
" (let* ((children (rest node))\n",
" (pivot (case layout ; the split point of the list of children\n",
" (:up (length children)) ; split at top\n",
" (:down 0) ; split at bottom\n",
" (otherwise (round (/ (length children) 2))))) ; bisect\n",
" (upper-children (reverse (subseq children 0 pivot))) ; above root\n",
" (lower-children (subseq children pivot))) ; nodes below root\n",
" (values\n",
" (when (and upper-children (car upper-children))\n",
" (loop for child-node in (rest upper-children)\n",
" ; topmost node has special connectors\n",
" with top = (prefix-node-strings\n",
" (first upper-children)\n",
" :layout layout\n",
" :node-formatter node-formatter\n",
" :upper-connector +space+\n",
" :root-connector +upper-knee+)\n",
" collect (prefix-node-strings\n",
" child-node\n",
" :layout layout\n",
" :node-formatter node-formatter)\n",
" into strlist\n",
" finally (return (nconc top (apply #'nconc strlist)))))\n",
" (let ((root-name (funcall node-formatter (car node))))\n",
" (if (= 1 (length root-name))\n",
" (concatenate 'string \" \" root-name) ; at least 2 chars needed\n",
" ;else\n",
" root-name))\n",
" (when (and lower-children (car lower-children))\n",
" (loop for child-node on lower-children by #'cdr\n",
" while (cdr child-node) ; omit the last child\n",
" collect (prefix-node-strings (car child-node)\n",
" :layout layout\n",
" :node-formatter node-formatter)\n",
" into strlist\n",
" finally (return\n",
" (nconc\n",
" (apply #'nconc strlist)\n",
" ; bottom node has special connectors\n",
" (prefix-node-strings\n",
" (car child-node)\n",
" :layout layout\n",
" :node-formatter node-formatter\n",
" :root-connector +lower-knee+\n",
" :lower-connector +space+))))))))\n",
")\n",
"(defun format-tree (stream root &key (layout :centered)\n",
" (node-formatter #'write-to-string))\n",
" (multiple-value-bind (u r l)\n",
" (format-tree-segments root\n",
" :layout layout\n",
" :node-formatter node-formatter)\n",
" (format stream \"~{~A~%~}\" (nconc u (list r) l)))\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The tree pretty printer above uses a tree representation bases on nested lists. Therefore, we need a way to\n",
"convert a tree made with `btree-node` instances to nested lists: "
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"BTREE-TO-LIST"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defun btree-to-list (node) ; recurively convert the priority queue\n",
" (when node\n",
" (list\n",
" (btree-node-value node)\n",
" (btree-to-list (btree-node-l node))\n",
" (btree-to-list (btree-node-r node)))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try that out:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" ╭─ 2.1\n",
" ╭─ 2\n",
" │ ╰─ 2.2\n",
" 1\n",
" ╰─ 3\n"
]
}
],
"source": [
"(let ((btree (make-btree-node\n",
" :value 1\n",
" :l (make-btree-node\n",
" :value 2\n",
" :l (make-btree-node :value 2.1)\n",
" :r (make-btree-node :value 2.2))\n",
" :r (make-btree-node :value 3))))\n",
" (format-tree t (btree-to-list btree)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Priority-Queue [Class]\n",
"\n",
"Now we have all the tools to set up a binary tree based heap.\n",
"\n",
"#### Constructor\n",
"\n",
"~~~ Lisp\n",
"(make-instance 'PRIORITY-QUEUE [:items {`list`}] [:test {`function`}])\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"test {`function` [`#'<`]}\n",
"> The test (lambda) function to compare two values.\n",
"> The function takes two parameters `a`, `b` and returns `T` if\n",
"> `b` is _greater_ than `a`.\n",
"\n",
"items {`list`}\n",
"> The initial items to put into the priority queue."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-CLASS COMMON-LISP-USER::PRIORITY-QUEUE>"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP:INITIALIZE-INSTANCE :AFTER (PRIORITY-QUEUE) {1005277653}>"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defclass PRIORITY-QUEUE ()\n",
" ((.test. :type function\n",
" :initarg :test\n",
" :initform #'<\n",
" :documentation \"Value comparator.\")\n",
" (.root. :type list\n",
" :initform nil\n",
" :documentation \"Root node of the tree\"))\n",
")\n",
"\n",
"(defmethod initialize-instance :after ((instance PRIORITY-QUEUE) &key items test)\n",
" (when test\n",
" (setf (slot-value instance '.test.) test))\n",
" (dolist (i items)\n",
" (enqueue instance i))\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The easiest thing to implement at this point would be a\n",
"redicate to determine if a priority queue is empty."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"###queue-empty-p [Method]\n",
"\n",
"~~~ Lisp\n",
"(queue-empty-p heap)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"_heap_ {`PRIORITY-QUEUE`}\n",
": The priority queue to check.\n",
"\n",
"# Returns\n",
"\n",
"`T` if the given priority queue is empty. `NIL` otherwise.\""
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::QUEUE-EMPTY-P (PRIORITY-QUEUE) {10053ACF63}>"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod queue-empty-p ((heap PRIORITY-QUEUE))\n",
" (null (slot-value heap '.root.)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now let's try this:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"tags": [
"test"
]
},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(assert (queue-empty-p (make-instance 'PRIORITY-QUEUE)))"
]
},
{
"cell_type": "markdown",
"metadata": {
"toc-hr-collapsed": false
},
"source": [
"## enqueue [Method]\n",
"\n",
"Before we can do anything more exiting we need a way to add items to a priority queue."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Recursively _Trickling_ Down New Values\n",
"To implement the enqueue method we create a recursive helper function which\n",
"finds the right place of a new object in the queue by _trickling_ it\n",
"down the priority queue until the right place is found.\n",
"\n",
"#### Arguments\n",
"\n",
"node {`BTREE-NODE`}\n",
"> The start node for the trickling process\n",
"\n",
"value {`BTREE-NODE`}\n",
"> The value to trickle down.\n",
"\n",
"test {`function`}\n",
"> The value comparator function."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
".TRICKLE-DOWN."
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defun .trickle-down. (node value test)\n",
" (let ((node-value (btree-node-value node)))\n",
"\n",
" (if (funcall test (btree-node-value node) value)\n",
" (progn ; given value replaces the node value\n",
" (setf (btree-node-value node) value)\n",
" ;; trickle down the replaced node value\n",
" (.trickle-down. node node-value test))\n",
" ;else examine child nodes\n",
" (cond\n",
" ((null (btree-node-l node)) ; no left child\n",
" (setf (btree-node-l node) (make-btree-node :value value))) ; insert value\n",
"\n",
" ((null (btree-node-r node)) ; no right child\n",
" (setf (btree-node-r node) (make-btree-node :value value))) ; insert value\n",
"\n",
" ((funcall test (btree-node-value (btree-node-l node)) value)\n",
" (setq node-value (btree-node-value (btree-node-l node)))\n",
" ; given value replaces the left child value\n",
" (setf (btree-node-value (btree-node-l node)) value)\n",
" (.trickle-down. (btree-node-l node ) node-value test))\n",
"\n",
" ((funcall test (btree-node-value (btree-node-r node)) value)\n",
" (setq node-value (btree-node-value (btree-node-r node)))\n",
" ; given value replaces the child 1 value\n",
" (setf (btree-node-value (btree-node-r node)) value)\n",
" (.trickle-down. (btree-node-r node) node-value test))\n",
"\n",
" (t (.trickle-down. (if (zerop (random 2))\n",
" (btree-node-l node)\n",
" ;else\n",
" (btree-node-r node))\n",
" value test)))))\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we are ready for adding an item to the priority queue.\n",
"\n",
"~~~ Lisp\n",
"(enqueue heap item)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"heap {`PRIORITY-QUEUE`}\n",
"> The priority queue object.\n",
"\n",
"item {`object`}\n",
"> The object to add\n",
"\n",
"#### Returns\n",
"\n",
"The item just added."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::ENQUEUE (PRIORITY-QUEUE T) {10058036D3}>"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod enqueue ((heap PRIORITY-QUEUE) value)\n",
" (let ((root (slot-value heap '.root.)))\n",
" (if root\n",
" (.trickle-down. root value (slot-value heap '.test.))\n",
" ;else\n",
" (setf (slot-value heap '.root.) (make-btree-node :value value))))\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can actually build a priority queue now. But without a way to visualize them we only can do simple things,\n",
"like inspecting the value at the top of the heap."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## peek [Method]\n",
"Get the object at the _front_ of a priority queue without removing it.\n",
"\n",
"~~~ Lisp\n",
"(peek heap)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"heap {`PRIORITY-QUEUE`}\n",
": A priority queue.\n",
"\n",
"#### Returns\n",
"\n",
"The object at the front of the priority queue (same object that would\n",
"be returned by `dequeue`)."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::PEEK (PRIORITY-QUEUE) {100593C073}>"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod peek ((heap PRIORITY-QUEUE))\n",
" (let ((root (slot-value heap '.root.)))\n",
" (when root\n",
" (btree-node-value root)))\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before we test that some sample values are needed:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"*PRIORITY-QUEUE-ITEMS*"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defparameter *PRIORITY-QUEUE-ITEMS* (loop for i from 1 to 10 collect (random 100)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we build a heap and check if the correct value is at the top."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Higest priority Value=96; Priority Queue Front=96\n"
]
}
],
"source": [
"(let ((h (make-instance 'PRIORITY-QUEUE :items *PRIORITY-QUEUE-ITEMS*))\n",
" (highest-priority (apply #'max *PRIORITY-QUEUE-ITEMS*)))\n",
" (format t \"Higest priority Value=~A; Priority Queue Front=~A~%\"\n",
" highest-priority (peek h))\n",
" (assert (= highest-priority (peek h))))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## pprint-queue [Method]\n",
"~~~ Lisp\n",
"(pprint-queue instance [stream] [:layout {keyword}])\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"instance {`queue`}\n",
"> Queue object to print.\n",
"\n",
"stream {`output-stream [*standard-output*]`}\n",
"> An output stream designator such as `*standard-output*` (default).\n",
"\n",
"layout {`keyword`} default is `:centered`\n",
"> Optional print layout. Possible values are: `:up`, `:centered`, or `:down` \n",
"\n",
"#### Returns\n",
"\n",
"The input object."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::PPRINT-QUEUE (PRIORITY-QUEUE) {1005D0E0F3}>"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod pprint-queue ((instance PRIORITY-QUEUE) &optional (stream *standard-output*)\n",
" &key (layout :centered))\n",
"\n",
" (format-tree stream\n",
" (btree-to-list (slot-value instance '.root.))\n",
" :layout layout)\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With these items we build a priorty queue:"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" ╭─ 22\n",
" ╭─ 34\n",
" ╭─ 57\n",
" │ ╰─ 15\n",
" ╭─ 74\n",
" │ ╰─ 22\n",
"96\n",
" │ ╭─ 31\n",
" ╰─ 42\n",
" ╰─ 42\n"
]
}
],
"source": [
"(pprint-queue (make-instance 'PRIORITY-QUEUE :items *PRIORITY-QUEUE-ITEMS*))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Creating a priority queue with lowest value first is also possible:"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
" ╭─ 31\n",
" ╭─ 22\n",
"15\n",
" │ ╭─ 57\n",
" │ ╭─ 34\n",
" │ │ │ ╭─ 74\n",
" │ │ ╰─ 42\n",
" ╰─ 22\n",
" │ ╭─ 96\n",
" ╰─ 42\n"
]
}
],
"source": [
"(pprint-queue (make-instance 'PRIORITY-QUEUE :items *PRIORITY-QUEUE-ITEMS* :test #'>))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## dequeue[Method]\n",
"\n",
"Similar to `enqueue` we need a resursive helper function too which removes\n",
"the _top_ item from the priority queue and replaces it by _bubbling_ up a\n",
"node from _below_."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Recursively Bubbling up Node Values\n",
"\n",
"Replace a node's value by bubbling up the largest value from its children.\n",
"\n",
"#### Arguments\n",
"\n",
"node {`BTREE-NODE`}\n",
"> A node whose value to replace\n",
"\n",
"test {`function`}\n",
"> The node value comparison function."
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
".BUBBLE-UP."
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defun .bubble-up. (node test)\n",
"\n",
" (let ((l (btree-node-l node ))\n",
" (r (btree-node-r node)))\n",
" (cond\n",
" ((and l r) ; both child nodes present\n",
" (if (funcall test (btree-node-value l) (btree-node-value r))\n",
" (progn ; bubble up right child's value\n",
" (setf (btree-node-value node) (btree-node-value r))\n",
" (if (btree-node-leaf-p r)\n",
" (setf (btree-node-r node) nil) ;; drop right child\n",
" ;else\n",
" (.bubble-up. r test)))\n",
" ;else bubble up left child's value\n",
" (progn ; pull up child 0 value\n",
" (setf (btree-node-value node) (btree-node-value l))\n",
" (if (btree-node-leaf-p l)\n",
" (setf (btree-node-l node) nil) ;; drop left child\n",
" ;else\n",
" (.bubble-up. l test)))))\n",
"\n",
" (l ; bubble up the left child's value\n",
" (setf (btree-node-value node) (btree-node-value l))\n",
" (if (btree-node-leaf-p l)\n",
" (setf (btree-node-l node) nil) ;; drop left child\n",
" ;else\n",
" (.bubble-up. l test)))\n",
"\n",
" (r ;; pull up the right child's value\n",
" (setf (btree-node-value node) (btree-node-value r))\n",
" (if (btree-node-leaf-p r)\n",
" (setf (btree-node-r node) nil) ;; drop right child\n",
" ;else\n",
" (.bubble-up. r test)))))\n",
")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With this helper function we can finally remove item from the top of the heap.\n",
"\n",
"~~~ Lisp\n",
"(dequeue heap)\n",
"~~~\n",
"\n",
"#### Arguments\n",
"\n",
"_heap_ {`PRIORITY-QUEUE`}\n",
"> Instance of a priority queue.\n",
"\n",
"#### Returns\n",
"\n",
"The item from the heap top (largest item for a max-heap or\n",
"smallest item for a min-heap).\""
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"#<STANDARD-METHOD COMMON-LISP-USER::DEQUEUE (PRIORITY-QUEUE) {10061647C3}>"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(defmethod dequeue ((heap PRIORITY-QUEUE))\n",
" (let* ((root (slot-value heap '.root.))\n",
" (head-value (btree-node-value root)))\n",
"\n",
" (if (btree-node-leaf-p root)\n",
" (setf (slot-value heap '.root.) nil)\n",
" ;else pull up new value\n",
" (.bubble-up. root (slot-value heap '.test.)))\n",
" head-value)\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"tags": [
"test"
]
},
"outputs": [
{
"data": {
"text/plain": [
"NIL"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(let ((h (make-instance 'PRIORITY-QUEUE :items *PRIORITY-QUEUE-ITEMS*))\n",
" (sorted-items (sort *PRIORITY-QUEUE-ITEMS* #'>)))\n",
" ; check that all values can be retrieved in max order (largest first)\n",
" (assert (equal sorted-items\n",
" (loop while (not (queue-empty-p h))\n",
" collect (dequeue h))))\n",
")"
]
}
],
"metadata": {
"celltoolbar": "Tags",
"hide_input": false,
"kernelspec": {
"display_name": "Common Lisp",
"language": "common-lisp",
"name": "common-lisp"
},
"language_info": {
"codemirror_mode": "text/x-common-lisp",
"file_extension": ".lisp",
"mimetype": "text/x-common-lisp",
"name": "common-lisp",
"pygments_lexer": "common-lisp",
"version": "1.4.14"
},
"latex_envs": {
"LaTeX_envs_menu_present": true,
"autoclose": false,
"autocomplete": true,
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 1,
"hotkeys": {
"equation": "Ctrl-E",
"itemize": "Ctrl-I"
},
"labels_anchors": false,
"latex_user_defs": false,
"report_style_numbering": false,
"user_envs_cfg": false
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {
"height": "436px",
"left": "96px",
"top": "71px",
"width": "237.99px"
},
"toc_section_display": true,
"toc_window_display": true
},
"toc-autonumbering": false,
"toc-showcode": false,
"toc-showmarkdowntxt": false,
"toc-showtags": false,
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment