     } else {
       (children, endHere) = ([:], true)
     }
-  }
-
-  private mutating func insert<
-    G : GeneratorType where G.Element == Element
-    >(var gen: G) {
-      if let head = gen.next() {
-        children[head]?.insert(gen) ?? {children[head] = Trie(gen: gen)}()
-      } else {
-        endHere = true
-      }
   }
 
   /// Construct from an arbitrary sequence of sequences with elements of type `Element`.

    (_ seq: S) {
      self.init(gen: seq.generate())
  }
  
  // MARK: Instance Properties
  
  /// A textual representation of `self`, suitable for debugging.
  public var debugDescription: String {
    return ", ".join(map {"".join($0.map { String(reflecting: $0) })})
  }
  
  /**
  Returns the number of members of `self`.
  
  - Complexity: O(`count`)
  */
  public var count: Int {
    return children.values.reduce(endHere ? 1 : 0) { $0 + $1.count }
  }
  
  // MARK: Instance Methods
  
  /// Insert a member into the Trie.
  public mutating func insert
    <S : SequenceType where S.Generator.Element == Element>
    (seq: S) {
      insert(seq.generate())
  }
  
  /// Return a *generator* over the members.

  public func generate() -> TrieGenerator<Element>  {
    return TrieGenerator(self)
  }

  private func completions
    <G : GeneratorType where G.Element == Element>
    (var start: G) -> Trie<Element> {
      guard let head = start.next() else  { return self }
      guard let child = children[head] else { return Trie() }
      return child.completions(start)
  }
  /**
  Returns a Trie of the suffixes of the members of `self` which start with `start`.
  
  ```swift
  let words = ["hello", "hiya", "hell", "jonah", "jolly", "joseph"].map{$0.characters}
  
  let store = Trie(words)
  
  store
    .completions("jo".characters)
    .map(String.init)
  
  // ["lly", "seph", "nah"]
  ```
  */
  public func completions<S : SequenceType where S.Generator.Element == Element>(start: S) -> Trie<Element> {
    return completions(start.generate())
  }

  private mutating func remove<
    G : GeneratorType where G.Element == Element
    >(var gen g: G) -> RemoveState {
      guard let head = g.next() else {
        endHere = false
        return children.isEmpty ? .Removable : .NotRemovable
      }
      guard let removeState = children[head]?.remove(gen: g) else { return .NotPresent }
      guard removeState == .Removable else { return removeState }
      children.removeValueForKey(head)
      return (!endHere && children.isEmpty) ? .Removable : .NotRemovable   
  }
  
  /// Remove the member from the Trie and return it if it was present.
  public mutating func remove<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) -> [Element]? {
      let result = Array(seq)
      if remove(gen: result.generate()) == .NotPresent { return nil }
      return result
  }
  
  private mutating func XOR<
    G : GeneratorType where G.Element == Element
    >(var gen g: G) -> Bool {
      guard let head = g.next() else {
        defer { endHere = !endHere }
        return endHere && children.isEmpty
      }
      guard let removable = children[head]?.XOR(gen: g) else {
        children[head] = Trie(gen: g)
        return false
      }
      if removable {
        children.removeValueForKey(head)
        return !endHere && children.isEmpty
      }
      return false
  }
  
  /// Remove the member if it was present, insert it if it was not.
  
  public mutating func XOR<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) {
      XOR(gen: seq.generate())
  }
    
  private func contains<
    G : GeneratorType where G.Element == Element
    >(var gen: G) -> Bool {
      guard let head = gen.next() else { return endHere }
      return children[head]?.contains(gen) ?? false
  }
  
  /// Returns `true` if the Trie contains a member.
  public func contains<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) -> Bool {
      return contains(seq.generate())
  }
  
  /// Insert elements of a `Trie` into this `Trie`.
  public mutating func unionInPlace(with: Trie<Element>) {
    endHere = endHere || with.endHere
    for (head, child) in with.children {
      if case nil = children[head]?.unionInPlace(child) { children[head] = child }
    }
  }
  
  /// Return a new Trie with items in both this set and a finite sequence.
  public func union(var with: Trie<Element>) -> Trie<Element> {
    with.unionInPlace(self)
    return with
  }
  
  /**
  Returns a Trie which contains the results of applying `transform` to the members of
  `self`
  */
  public func map<S : SequenceType>(@noescape transform: [Element] -> S) -> Trie<S.Generator.Element> {
    var result = Trie<S.Generator.Element>()
    for seq in self {
      result.insert(transform(seq))
    }
    return result
  }

  /**
  Returns a Trie which contains the non-nil results of applying `transform` to the members
  of `self`
  */
  public func flatMap<S : SequenceType>(@noescape transform: [Element] -> S?) -> Trie<S.Generator.Element> {
    var result = Trie<S.Generator.Element>()
    for seq in self {
      if let transformed = transform(seq) {
        result.insert(transformed)
      }
    }
    return result
  }
  /**
  Returns a Trie which contains the merged results of applying `transform` to `self`.
  */
  public func flatMap<T>(@noescape transform: [Element] -> Trie<T>) -> Trie<T> {
    var ret = Trie<T>()
    for seq in self {
      ret.unionInPlace(transform(seq))
    }
    return ret
  }

  /**
  Returns a Trie which contains the members of `self` which satisfy `includeElement`.
  */
  public func filter(@noescape includeElement: [Element] -> Bool) -> Trie<Element> {
    var ret = Trie()
    for element in self where includeElement(element) { ret.insert(element) }
    return ret
  }
}


Full documentation is available [here](http://oisdk.github.io/SwiftDataStructures/Structs/Trie.html).
*/

public struct Trie<Element : Hashable> : Equatable {
  private var children: [Element:Trie<Element>]
  private var endHere : Bool
}

/// :nodoc:
public func ==<T>(lhs: Trie<T>, rhs: Trie<T>) -> Bool {
  return lhs.endHere == rhs.endHere && lhs.children == rhs.children
}

// MARK: DebugDescription

extension Trie : CustomDebugStringConvertible {
  /// A textual representation of `self`, suitable for debugging.
  public var debugDescription: String {
    return ", ".join(map {"".join($0.map { String(reflecting: $0) })})
  }
}

// MARK: Insert

extension Trie {
  private mutating func insert<
    G : GeneratorType where G.Element == Element
    >(var gen: G) {
    if let head = gen.next() {
      children[head]?.insert(gen) ?? {children[head] = Trie(gen: gen)}()
    } else {
      endHere = true
    }
  }
  
  /// Insert a member into the Trie.
  public mutating func insert<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) {
    insert(seq.generate())
  }
}

// MARK: Initializers

extension Trie {
  
  /// Create an empty `Trie`
  public init() {
