swi

SwiftDataStructures

Basic data structures (OrderedDictionary, Stack, Queue, LinkedList, List) that supplement the Swift stdlib.

Showing:

Popularity

Downloads/wk

0

GitHub Stars

43

Maintenance

Last Commit

6yrs ago

Contributors

1

Package

Dependencies

1

License

MIT

Categories

Readme

SwiftDataStructures

Build Status CocoaPods CocoaPods CocoaPods GitHub tag

install

It's a CocoaPod. For the time being, only the pre-release beta of CocoaPods 0.36 is capable of working with Swift code. To install it, use gem install cocoapods --pre.

Podfile:

pod 'SwiftDataStructures'

Command line:

$ pod install

Currently implemented:

  • OrderedDictionary: Implemented using LinkedList rather than one of Swift's built-in types. Hopefully a bit faster this way.
  • Stack: Also implemented with a LinkedList.
  • Queue: Like Stack, this has also been implemented using a LinkedList.
  • List: An abstraction over a LinkedList that hides its implementation using LinkedListNodes. A List's interface is basically identical to that of an Array.
  • LinkedList (serves as a base for a lot of the other data structures)

Forthcoming:

  • OrderedSet
  • Tree (I'm curious what types of trees people would be interested in using)
  • A complete test suite
  • Performance tests

Comments, ideas, and pull requests are very welcome!

The tests are coming along, but any contributions towards those would be awesome as well. Even just a second set of eyes would go a long way.

example usage

You can check out the tests for more information (better instructions are continually evolving). It's all pretty intuitive, though ... the types all do pretty much what you would expect.

LinkedList<T>

Initialization:

// Empty list
let list = LinkedList<Int>()

// You can initialize a LinkedList using any type that conforms to Sequence
let someArray = [10, 20, 30]
let list = LinkedList<Int>(someArray)

let someSequence = SequenceOf([10, 20, 30])
let list = LinkedList<Int>(someSequence)

// LinkedList also implements ArrayLiteralConvertible
let list : LinkedList<Int> = [10, 20, 30]

LinkedListNode<T>

LinkedList's elements are LinkedListNode objects, which are simple boxes/wrappers around whatever type T you're storing in the list. A LinkedListNode has an item property for retrieving the wrapped value, as well as previous and next pointers for traversing the list.

public class LinkedListNode<T>
{
    public let item: T

    public private(set) var previous: LinkedListNode<T>?
    public private(set) var next:     LinkedListNode<T>?

    public init(_ theItem:T) {
        item = theItem
    }
}

Accessing elements

LinkedList defines a subscript getter as well as func at(index:Index) -> LinkedListNode<T> for accessing elements at particular indices. The subscript operator will fail when passed an out-of-bounds index, while at() will simply return nil.

let someNode = list[2]
let someNode = list.at(2)

Traversing the list

LinkedList implements SequenceType, allowing you to use for...in loops, among many other things.

for node in list {
    println("node.item = \(node.item)")
}

A list also maintains first and last pointers:

list.first // an optional LinkedListNode<T>
list.last  // an optional LinkedListNode<T>

Finding a particular item

let foundNode = list.find { $0.item == 1337 } // returns an optional LinkedListNode<T>
foundNode?.item // == 1337 (or nil if the node wasn't found)

Manipulating the list

Note: LinkedList's Index type is a simple Int.

Adding new elements (append and prepend):

list.append(LinkedListNode(30))
list.prepend(LinkedListNode(30))
list.insert(LinkedListNode(30), atIndex:5)

Removing elements:

let removed = list.removeAtIndex(3) // removed == the removed LinkedListNode object

contributors / authors

bryn austin bellomy < bryn.bellomy@gmail.com >

Rate & Review

Great Documentation0
Easy to Use0
Performant0
Highly Customizable0
Bleeding Edge0
Responsive Maintainers0
Poor Documentation0
Hard to Use0
Slow0
Buggy0
Abandoned0
Unwelcoming Community0
100
No reviews found
Be the first to rate

Alternatives

No alternatives found

Tutorials

No tutorials found
Add a tutorial