Swift-algorithm-club — Data structure/variant array

Variations on arrays

2 d array

In C and Objective-C, we can create two-dimensional arrays like this

int cookies[9] [7];
myCookie = cookies[3] [6];
Copy the code

In Swift, you can do this

var cookies = [[Int]] ()for _ in 1.9 {
  var row = [Int] ()for _ in 1.7 {
    row.append(0)
  }
  cookies.append(row)
}

let myCookie = cookies[3] [6]
Copy the code

Or it

var cookies = [[Int]](repeating: [Int](repeating: 0, count: 7), count: 9)
Copy the code

We can simplify it by using auxiliary functions:

func dim<T> (_ count: Int._ value: T)- > [T] {
  return [T](repeating: value, count: count)
}
Copy the code

We can then create arrays like this:

var cookies = dim(9, dim(7.0))
Copy the code

The disadvantage of using multidimensional arrays or multiple nested arrays in this way is that you can’t keep track of what latitude represents what.

We can create our own types

public struct Array2D<T> {
  public let columns: Int
  public let rows: Int
  fileprivate var array: [T]
  
  public init(columns: Int.row: Int.initialValue: T) {
    self.columns = columns
    self.rows = rows
    array = .init(repeating: initialValue, count: rows*columns)
  }
  
  public subscript(column: Int.row: Int) -> T {
    get {
      precondition(column < columns, "Column \(column) Index is out of range. Array<T>(columns: \(columns), rows: \(rows))")
      precondition(row < rows, "Row \(row) Index is out of range. Array<T>(columns: \(columns), row: \(rows)")
      return array[row*columns + column]
    }
    set {
      precondition(column < columns, "Column \(column) Index is out of range. Array<T>(columns: \(columns), rows: \(rows))")
      precondition(row < rows, "Row \(row) Index is out of range. Array<T>(columns: \(columns), row: \(rows)")
      array[row*columns + column] = newValue
    }
  }
}
Copy the code

And then you can use it like this

var cookies = Array2D(columns: 9, rows: 7, initialValue: 0)

let myCookie = cookies[column, row]

cookies[colimn, row] = newCookie
Copy the code

Bit set

Fixed size n bit sequence. Also called bit arrays or bit vectors.

A bit set is simply a wrapper around an array. This array does not store individual bits, but larger integers called words. The main job of BitSet is to map bits to the correct word.

public struct BitSet {
  private(set) public var size: Int
  
  private let N = 64
  public typealias Word = UInt64
  fileprivate(set) public var words: [Word]
  
  public init(size: Int) {
    precondition(size > 0)
    self.size = size
    
    // Round up the count to the next multiple of 64.
    let n = (size + (N-1)) / N
    words = [Word](repeating: 0, count: n)
  }
}
Copy the code

Look for a bit

private func indexOf(_ i: Int)- > (Int.Word) {
  precondition(i > = 0)
  precondition(i < size)
  let o = i / N
  let m = Word(i - o*N)
  return (o, 1 << m)
}
Copy the code

The indexOf() function returns an array indexOf word and a “mask” that shows the exact position of the bit within the word.

Chestnut:

IndexOf (2) returns tuple (0,4)

0010000000000000000000000000000000000000000000000000000000000000
Copy the code

IndexOf (127) returns a tuple (1, 9223372036854775808)

0000000000000000000000000000000000000000000000000000000000000001
Copy the code

Sets and gets bits

public mutating func set(_ i: Int) {
  let (j, m) = indexOf(i)
  words[j] | = m
}
Copy the code

public mutating func clear(_ i: Int) {
  let (j, m) = indexOf(i)
  words[j] & = ~m
}
Copy the code

public func isSet(_ i: Int) -> Bool {
  let (j, m) = indexOf(i)
  return (words[j] & m) ! = 0
}
Copy the code

Add a subscript function to make everything more natural

public subscript(i: Int) -> Bool {
  get { return isSet(i) }
  set { if newValue { set (i) } else { clear(i) } }
}
Copy the code

Now, we can write:

var bits = BitSet(size: 140)
bits[2] = true
bits[99] = true
bits[128] = true
print(bits)
Copy the code

This prints the three words of the 140-bit BitSet used to store everything:

0010000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000010000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000
Copy the code

flip

public mutating func flip(_ i: Int) -> Bool {
  let (j, m) = indexOf(i)
  words[j] ^ = m
  return (words[j] & m) ! = 0
}
Copy the code

public mutating func clearAll(a) {
  for i in 0..<words.count {
    words[i] = 0}}Copy the code

public mutating func setAll(a) {
  for i in 0..<words.count {
    words[i] = allOnes
  }
  clearUnusedBits()
}
Copy the code

Note: with the setAll method, we are not using the whole part of the last word, we should leave the unused part as 0.

private func lastWordMask(a) -> Word {
  let diff = words.count*N - size
  if diff > 0 {
    let mask = 1 << Word(63 - diff)
    return mask | (mask - 1)}else {
    return ~Word()}}private mutating func clearUnuesdBits(a) {
  words[words.count - 1] & = lastWordMask()
}
Copy the code

The following is the realization of the | operator:

public func |(lhs: BitSet.rhs: BitSet) -> BitSet {
  var out = copyLargest(lhs, rhs)
  let n = min(lhs.words.count, rhs.words.count)
  for i in 0..<n {
    out.words[i] = lhs.words[i] | rhs.words[i]
  }
  return out
}
Copy the code

Counting the bits set to 1, scanning the entire array is ok — O(n) operations — but the smarter way is:

public var cardinality: Int {
  var count = 0
  for var x in words {
    while x ! = 0 {
      let y = x & ~(x - 1)    // find lowest 1-bit
      x = x ^ y               // and erase it
      ++count
    }
  }
  return count
}
Copy the code

Fixed size array

Assume two constraints – the number of elements is limited && the array is not sorted

struct FixedSizeArray<T> {
  private var maxSize: Int
  private var defaultValue: T
  private var array: [T]
  private (set) var count = 0
  
  init(maxSize: Int.defaultValue: T) {
    self.maxSize = maxSize
    self.defaultValue = defaultValue
    self.array = [T](repeating: defaultValue, count: maxSize)
  }
  
  subecript(index: Int) - >T{
    assert(index > = 0)
    assert(index < count)
    return array[index]
  }
  
  mutating func append(_ newElement: T) {
    assert(count < maxSize)
    array[count] = newElement
    count + = 1
  }
  
  mutating func removeAt(index: Int) -> T {
    assert(index > = 0)
    assert(index < count)
    count - = 1
    let result = array[index]
    array[index] = array[count]
    array[count] = defaultValue
    return result
  }
  
  mutating func removeAll(a) {
    for i in 0.count {
      array[i] = defaultValue
    }
    count = 0}}Copy the code

Orderly array

Ordered arrays are useful when you want to sort data and insert relatively few new elements. In this case, it’s faster than sorting the entire array.

public struct OrderedArray<T: Comparable> {
  fileprivate var array = [T] ()public init(array: [T]) {
    self.array = array.sorted()
  }
  
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }
  
  public subscript(index: Int) -> T {
    return array[index]
  }
  
  public mutating func removeAtIndex(index: Int) -> T {
    return array.remove(at: index)
  }
  
  public mutating func removeAll(a) {
    array.removeAll()
  }
  
  extension OrderedArray: CustomStringConvertible {
    public var description: String {
      return array.description
    }
  }
}
Copy the code

public mutating func insert(_ newElement: T) -> Int {
  let i = findInsertionPoint(newElement)
  array.insert(newElement, at: i)
  return i
}

private func findInsertionPoint(_ newElement: T) -> Int {
  for i in 0..<array.count {
    if newElement < = array[i] {
      return i
    }
  }
  return array.count    // insert at the end
}
Copy the code

Binary search version assist function

private func findInsertionPoint(_ newElement: T) -> Int {
  var startIndex = 0
  var endIndex = array.count
  
  while startIndex < endIndex {
    let midIndex = startIndex + (endIndex - startIndex) / 2
    if array[midIndex] = = newElement {
      return midIndex
    } else if array[midIndex] < newElement {
      startIndex = midIndex + 1
    } else {
      endIndex = midIndex
    }
  }
  return startIndex
}
Copy the code

Rootish Array Stack

Rootish Array Stack is an ordered Array based structure that minimizes wasted space (based on gaussian summation).

Gauss summation formula

sum from 1.n = n * (n + 1) / 2
Copy the code

import Darwin

public struct RootishArrayStack<T> {
  fileprivate var blocks = [Array<T? >] ()fileprivate var internalCount = 0
  
  public init(a){}var count: Int {
    return internalCount
  }
  
  .
}
Copy the code

var capacity: Int {
  return blocks.count * (blocks.count + 1) / 2
}
Copy the code

fileprivate func block(fromIndex: Int) -> Int {
  let block = Int(ceil((-3.0) + sqrt(9.0 + 8 * Double(index))) / 2)) // Use the following formula to solve the quadratic equation
	return block
}

fileprivate func innerBlockIndex(fromIndex index: Int.fromBlock block: Int) -> Int {
  return index - block * (block + 1) / 2
}

public subscript(index: Int) -> T {
  get {
    let block = self.block(fromIndex: index)
    let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
    return blocks[block][innerBlockIndex]!
  }
  set(newValue) {
    let block = self.block(fromIndex: index)
    let innerBlockIndex = self.innerBlockIndex(formIndex: index, fromBlock: block)
    blocks[block][innerBlockIndex] = newValue
  }
}
Copy the code

fileprivate mutating func growIfNeeded(a) {
  if capacity - blocks.count < count + 1 {
    let newArray = [T? ] (repeating:nil, count: blocks.count + 1)
    blocks.append(newArray)
  }
}

fileprivate mutating func shrinkIfNeeded(a) {
  if capacity + blocks.count > = count {
    while blocks.count > 0 && (blocks.count - 2) * (blocks.count - 1) / 2 > count {
      blocks.remove(at: blocks.count - 1)}}}Copy the code

public mutating func insert(element: T.atIndex index: Int) {
  growIfNeeded()
  internalCount + = 1
  var i = count - 1
  while i > index {
    self[i] = self[i - 1]
    i - = 1
  }
  self[index] = element
}

public mutating func append(element: T) {
  insert(element: element, atIndex: count)
}

public mutating func remove(atIndex index: Int) -> T {
  let element = self[index]
  for i in index..<count - 1 {
    slef[i] = self[i + 1]
  }
	internalCount - = 1
  makeNil(atIndex: count)
  shrinkIfNeeded()
  return element
}

fileprivate mutating func makeNil(atIndex index: Int) {
  let block = self.block(fromIndex: Index)
  let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
  blocks[block][innerBlockIndex] = nil
}
Copy the code