Repository files navigation

A collection of data structures implemented in Swift.

The available data structures are:

• LinkedList
• SortedLinkedList
• Stack
• Queue
• Graph
• BinaryHeap
• PriorityQueue*
• BloomFilter*
• Trie*
• Multimap*
• Bimap*
• Bag
• BinarySearchTree
• RedBlackTree*
• AVLTree

To install Carthage, run (using Homebrew):

$ brew update$ brew install carthage

Then add the following line to yourCartfile:

github "alexdrone/DataStructures" "master"

All collection types are implemented as structures with the exception of the LinkedList data structure. This means they are copied when they are assigned to a new constant or variable, or when they are passed to a function or method.

About copying structs:

The behavior you see in your code will always be as if a copy took place. However, Swift only performs an actual copy behind the scenes when it is absolutely necessary to do so. Swift manages all value copying to ensure optimal performance, and you should not avoid assignment to try to preempt this optimization.

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally.

letlinkedList=LinkedList<Int>()linkedList.append(1)linkedList.append(2)print(linkedList) //[1,2]letsortedLinkedList=SortedLinkedList<Int>()linkedList.append(3)linkedList.append(1)linkedList.append(2)print(sortedLinkedList) //[1,2,3]

A graph can be constructed from a array literal, or a dependency list.Operations likeBFS andDFS visit,shortestPath andtopologicalSort are available to the user.

Note that this implementation is not synchronized, it must be synchronized externally.

//Graph (graphs can be directed/undirected and weighted/not weighted)vargraph=Graph<Int>(arrayLiteral:1,7,4,3,5,2,6)graph.addEdge(graph[1], to:graph[2])graph.addEdge(graph[1], to:graph[3])graph.addEdge(graph[1], to:graph[5])graph.addEdge(graph[2], to:graph[4])graph.addEdge(graph[4], to:graph[5])graph.addEdge(graph[5], to:graph[6])        //bfs visit expected [1, 2, 3, 5, 4, 6]letbfs= graph.traverseBreadthFirst().map(){return $0.value}//shortest pathvarg=Graph<Int>(arrayLiteral:1,7,4,3,5,2,6)g.directed=trueg.weighted=trueg.addEdge()g[1], to:g[2], weight:2)g.addEdge(g[1], to:g[3], weight:3)g.addEdge(g[1], to:g[5], weight:6)g.addEdge(g[2], to:g[4], weight:1)g.addEdge(g[4], to:g[5], weight:1)g.addEdge(g[5], to:g[6], weight:10)//..or you can use the shorthand subscript to create an edgegraph[1,2]=2graph[1,3]=3graph[1,5]=6graph[2,4]=1graph[4,5]=1graph[5,6]=10//shortest path from 1 to 5, expected [1, 2, 4, 5] with cost 4letp= g.shortestPath(g[1], to:g[5])(p?.vertices.map(){return $0.value} //[1,2,4,5]///topological sort and cycle checklet noCycle: Dictionary<String,[String]>=["A":[],"B":[],"C":["D"],"D":["A"],"E":["C","B"],"F":["E"]]var g=Graph<String>(directed:true, weighted:false)g.populateFromDependencyList(noCycle)g.isDirectedAcyclic() //trueg.topologicalSort() // ["A", "B", "D", "C", "E", "F"]

Stacks and Queues are implemented through Array and LinkedList extensionNote that this implementation is not synchronized, it must be synchronized externally.

extensionLinkedList:Stack{publicfunc pop()->T?    publicfunc push(element:T)    publicfunc peekStack()->T?}extension Array: Stack{    publicfunc pop()->T?    publicfunc push(element:T)    publicfunc peekStack()->T?}extensionLinkedList:Queue{publicfunc enqueue(element:Q)publicfunc dequeue()->Q?publicfunc peekQueue()->Q?}extensionArray:Queue{publicfunc enqueue(element:Q)publicfunc dequeue()->Q?publicfunc peekQueue()->Q?}

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to the sort closure passed as argument in the constructor.The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.

Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue

varpQueue=PriorityQueue<Int>(<)pQueue.enqueue(3)pQueue.enqueue(1)pQueue.enqueue(2)pQueue.dequeue() // 1

A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set".

varbFilter=BloomFilter<String>(expectedCount:100)bFilter.insert("a")bFilter.contains("a") // true

Is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are strings.Note that this implementation is not synchronized, it must be synchronized externally.

vartrie=Trie()trie.insert("A")trie.insert("AB")trie.findPrefix("A") // ["A", "AB"]

A red–black tree is a kind of self-balancing binary search tree.Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case.

The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.

Note that this implementation is not synchronized, it must be synchronized externally.

import DataStructuresvartree=RedBlackTree<Int>(arrayLiteral:[1,3,5,6,7,8,9]) tree.popFirst()

A generalization of a map or associative array data type in which more than one value may be associated with and returned for a given key.Note that this implementation is not synchronized, it must be synchronized externally.

varmultimap=Multimap<String,Int>()multimap.insertValue(1, forKey:"a")multimap.insertValue(5, forKey:"a")multimap["a"] // [1, 5]

A generalization of a map or associative array data type in which more than one value may be associated with and returned for a given key.Note that this implementation is not synchronized, it must be synchronized externally.

varbimap=Bimap<String,Int>()bimap[key:"a"]=1bimap[value:3]="b"bimap[value:1] // "a"bimap[key:"b"] // 3

Similar to a set but allows repeated ("equal") values (duplicates). This is used in two distinct senses: either equal values are considered identical, and are simply counted, or equal values are considered equivalent, and are stored as distinct items.

varbag=Bag<String>()bag.insert("a")bag.insert("b")bag.insert("a")bag.distinctCount // 2bag.count("a") // 2

The edit distance is a way of quantifying how dissimilar two arrays are to one another by counting the minimum number of operations required to transform one array into the other

publicenum EditDistanceOperation{case Insertion(source:Int, target:Int)case Removal(source:Int)case Substitution(source:Int, target:Int)case AllChangedpublicstaticfunc compute<T:Equatable>(from:[T], to:[T])->[EditDistanceOperation]

publicstructBitMask{        ///Check the bit at the given indexpublicstaticfunc check(n:Int, index:Int)-> Bool        ///Set the bit to 1 at the index passed as argument    public staticfunc set(n:Int, index:Int)-> Int        ///Clear the bit passed as argument    public staticfunc clear(n:Int, index:Int)->Int}

* The PriorityQueue,Multimap,Bimap and BloomFilter data structures are forked from the excellentBuckets github project. I higly suggest to check it out!The RedBlackTree datastructure is adapted fromSwiftDataStructures