ADT Signatures

An ADT signature is the description of the characteristics of an ADT, such as it’s operations. Most ADT Signatures define:

• A constructor, to create the ADT
• Methods to add and remove elements
• A boolean method to check if the ADT is full/empty
• A method to ‘get’ an element

length: ADT → int
isFull: ADT → bool
isEmpty: ADT → bool

---

Lists §

Signature §

name: list
import: element, boolean
ops:
	newList : → list; 
	first : list → element; 
	rest : list → list; 
	insert : list × element → list; 
	contains : list × element → boolean; 
	append : list × element → list; 
	isEmpty : list → boolean; 
	etc. (more operations can be defined)

Link to source

---

Arrays §

Signature §

name: Array
import: element,int,bool
ops:
	newArray: → Array
	append: Array x element x int → Array
	get: Array x int -element
	isEmpty/isFull: Array → bool
	length: Array → int

Link to source

---

Sets §

[status: TODO]

Signature §

name: Set
import: element, int, bool
ops:
	

Link to source

---

Stacks §

Signature §

name stack;
import elem, boolean;
ops:
	newStack : → stack; 
	push : stack × elem → stack;
	pop : stack → stack; 
	top : stack → elem; 
	isEmpty : stack → boolean; 
	etc.

Link to source

---

Queues §

Signature §

name queue; 
import elem, boolean; 
ops:
	newQueue : → queue; 
	enqueue : queue × elem → queue; 
	dequeue : queue → queue; 
	front : queue → elem; 
	isEmpty : queue → boolean;
	etc.

Link to source

---

Priority Queues §

Signature §

name PQueue; 
import element; 
ops:
	newPQueue : → PQueue; 
	enqueue : PQueue × element × integer → PQueue; 
	head : PQueue → element; 
	dequeue: PQueue → PQueue; 
	isFull : PQueue → boolean; etc.

Link to source

---

Dictionaries §

Signature §

name Dictionary;
import key, value, integer, boolean;
ops:
	newDict : → dictionary;
	insert : dictionary × key × value → dictionary;
	inDict : dictionary × key → boolean;
	remove : dictionary × key → dictionary;
	lookup : dictionary × key → value;
	update : dictionary × key × value → dictionary;
	length : dictionary → integer;

Link to source

---

Graphs §

Signature §

name: graph; 
import node, edge, list, integer, boolean;  
ops:
	newGraph:→ graph;
	allNodes:graph → list;
	allEdges:graph → list;
	addNode:graph × node → graph;
	deleteNode:graph × node → graph;
	NodeExists:graph × node → boolean;
	addEdge:graph × edge → graph;
	deleteEdge:graph × edge → graph;
	EdgeExists:graph × edge → boolean;
	neighbours:graph × node → list;
	startNode:edge → node;
	endNode:edge → node;
	incident:graph × node → list;

Link to source