src/lib/cord.slate

   1 define: #Cord &parents: {Sequence}
   2 "A Cord is an object representing the binary concatentation of two Sequences,
   3 without allocating a new piece of literal memory for the whole result."
   4 &slots: {#split. "The index where the second half begins."
   5          #firstBranch. "The first half of the cord."
   6          #secondBranch. "The latter half of the cord."
   7          #depth -> 1. "The default for a couple of strings ;;'d."
   8          #size "The incrementally-calculated Cord size."}.
   9
  10 obj ;; seq@(Sequence traits)
  11 [{obj} ;; seq].
  12
  13 seq@(Sequence traits) ;; obj
  14 [seq ;; {obj}].
  15
  16 c1@(Sequence traits) ;; c2@(Sequence traits)
  17 "Build a cord concatenation out of any 2 sequences,
  18 or lazily answer an argument if the other is empty."
  19 [
  20   `conditions: (
  21     [c1 isEmpty] -> [c2].
  22     [c2 isEmpty] -> [c1]
  23   ) otherwise: [
  24     Cord clone `>>
  25       [split := c1 size.
  26        firstBranch := c1.
  27        secondBranch := c2.
  28        size := c1 size + c2 size. ]]
  29 ].
  30
  31 c1@(Sequence traits) ;; c2@(Cord traits)
  32 "Set up the depth if the second element is a cord."
  33 [resend `>> [depth := c2 depth + 1. ]].
  34
  35 c1@(Cord traits) ;; c2@(Sequence traits)
  36 "Set up the depth if the first element is a cord."
  37 [resend `>> [depth := c1 depth + 1. ]].
  38
  39 obj ;; c@(Cord traits)
  40 [{obj} ;; seq].
  41
  42 c@(Cord traits) ;; obj
  43 [c ;; {obj}].
  44
  45 c1@(Cord traits) ;; c2@(Cord traits)
  46 "If both are cords, the deepest counts for the depth."
  47 [resend `>> [depth := (c1 depth max: c2 depth) + 1. ]].
  48
  49 c@(Cord traits) at: n
  50 "Recursively descend the tree to find the element in the base sequences.
  51 Since this is ~O(log n) vs O(0), iterators need to avoid this and use do:
  52 or doWithIndex:."
  53 [
  54   n < c split
  55     ifTrue: [c firstBranch at: n]
  56     ifFalse: [c secondBranch at: n - c split]
  57 ].
  58
  59 c@(Cord traits) do: block
  60 "The major premise of this override is to avoid calling at: for each index,
  61 since it is more expensive for Cords to perform."
  62 [
  63   c firstBranch do: block.
  64   c secondBranch do: block.
  65 ].
  66
  67 c@(Cord traits) doWithIndex: block
  68 "Simulate an index during the traversal."
  69 [| index |
  70   index := 0.
  71   c do: [| :each | block applyWith: each with: index.
  72          index += 1].
  73 ].
  74
  75 c@(Cord traits) collectionType
  76 [
  77   c detect: [| :each | (each isSameAs: c) not]
  78 ].
  79
  80 c@(Cord traits) shouldBeFlattened
  81 "Pick a pretty small number that statistically is easier to just make a new
  82 sequence for, and make sure that it's not just a base Cord."
  83 [
  84   c size < 20 /\ [c depth >= 2]
  85 ].
  86
  87 c@(Cord traits) flatten
  88 [
  89   c as: c collectionType
  90 ].
  91
  92 c@(Cord traits) shouldBeBalanced
  93 [
  94   c depth >= 4
  95 ].
  96
  97 c@(Cord traits) balance
  98 [
  99   c notYetImplemented
 100 ].
 101
 102 s@(Sequence traits) join &separator: delim
 103 "#join is the opposite of #splitWith:, taking a collection of Sequences and
 104 splicing them together. Optionally, a delimiter may be given to use between
 105 each instance. The fact that this is optional is why join is not joinWith:."
 106 [
 107   (s reduce:
 108      (delim
 109         ifNil: [#;;`er]
 110         ifNotNil: [[| :result :each | result ;; delim ;; each]])
 111      ifEmpty: [s])
 112     as: (delim ifNil: [s first])
 113 ].