replace linkedlists by seqs

9 files changed, 47 insertions, 115 deletions

diff --git a/src/lzss/listpolyfill.nim b/src/lzss/listpolyfill.nim
deleted file mode 100644
index 00b30ee..0000000
--- a/src/lzss/listpolyfill.nim
+++ /dev/null
@@ -1,42 +0,0 @@
-# gzip-like LZSS compressor
-# Copyright (C) 2018  Pacien TRAN-GIRARD
-#
-# This program is free software: you can redistribute it and/or modify
-# it under the terms of the GNU Affero General Public License as
-# published by the Free Software Foundation, either version 3 of the
-# License, or (at your option) any later version.
-#
-# This program is distributed in the hope that it will be useful,
-# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-# GNU Affero General Public License for more details.
-#
-# You should have received a copy of the GNU Affero General Public License
-# along with this program.  If not, see <https://www.gnu.org/licenses/>.
-
-import lists
-
-# https://github.com/nim-lang/Nim/pull/9805
-
-proc prepend*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) =
-  ## prepends a node to `L`. Efficiency: O(1).
-  n.next = L.head
-  L.head = n
-  if L.tail == nil: L.tail = n
-
-proc prepend*[T](L: var SinglyLinkedList[T], value: T) =
-  ## prepends a node to `L`. Efficiency: O(1).
-  listpolyfill.prepend(L, newSinglyLinkedNode(value))
-
-proc append*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) =
-  ## appends a node `n` to `L`. Efficiency: O(1).
-  n.next = nil
-  if L.tail != nil:
-    assert(L.tail.next == nil)
-    L.tail.next = n
-  L.tail = n
-  if L.head == nil: L.head = n
-
-proc append*[T](L: var SinglyLinkedList[T], value: T) =
-  ## appends a value to `L`. Efficiency: O(1).
-  append(L, newSinglyLinkedNode(value))
diff --git a/src/lzss/lzsschain.nim b/src/lzss/lzsschain.nim
index 8ebcb1a..ab03655 100644
--- a/src/lzss/lzsschain.nim
+++ b/src/lzss/lzsschain.nim
@@ -14,26 +14,23 @@
 # You should have received a copy of the GNU Affero General Public License
 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
-import lists, tables, sugar
+import tables, sugar
 import ../bitio/integers
-import listpolyfill, lzssnode
+import lzssnode
 
-const maxChainByteLength = 32_000 * wordBitLength
+const maxChainByteLength = 32_000
 
-type LzssChain* =
-  SinglyLinkedList[LzssNode]
+type LzssChain* = seq[LzssNode]
 
 proc lzssChain*(): LzssChain =
-  initSinglyLinkedList[LzssNode]()
+  newSeq[LzssNode]()
 
 proc lzssChain*(chainArray: openArray[LzssNode]): LzssChain =
-  var chain = lzssChain()
-  for node in chainArray: chain.append(node)
-  chain
+  @chainArray
 
 proc decode*(lzssChain: LzssChain): seq[uint8] =
   result = newSeqOfCap[uint8](maxChainByteLength)
-  for node in lzssChain.items:
+  for node in lzssChain:
     case node.kind:
       of character:
         result.add(node.character)
diff --git a/src/lzss/lzssencoder.nim b/src/lzss/lzssencoder.nim
index 82fbe7b..36e0c7e 100644
--- a/src/lzss/lzssencoder.nim
+++ b/src/lzss/lzssencoder.nim
@@ -14,20 +14,18 @@
 # You should have received a copy of the GNU Affero General Public License
 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
-import lists
-import listpolyfill, matchtable, lzssnode, lzsschain
+import matchtable, lzssnode, lzsschain
 
 const matchGroupLength* = 3
 const maxRefByteLength = high(uint8).int + matchGroupLength
-let emptySinglyLinkedList = initSinglyLinkedList[int]()
 
 proc commonPrefixLength*(a, b: openArray[uint8], skipFirst, maxLength: int): int =
   result = skipFirst
   let maxPrefixLength = min(min(a.len, b.len), maxLength)
   while result < maxPrefixLength and a[result] == b[result]: result += 1
 
-proc longestPrefix*(candidatePos: SinglyLinkedList[int], searchBuf, lookAheadBuf: openArray[uint8]): tuple[length, pos: int] =
-  for startIndex in candidatePos.items:
+proc longestPrefix*(candidatePos: openArray[int], searchBuf, lookAheadBuf: openArray[uint8]): tuple[length, pos: int] =
+  for startIndex in candidatePos:
     let prefixLength = commonPrefixLength(
       searchBuf.toOpenArray(startIndex, searchBuf.len - 1), lookAheadBuf, matchGroupLength, maxRefByteLength)
     if prefixLength > result.length: result = (prefixLength, startIndex)
@@ -39,20 +37,20 @@ proc addGroups*(matchTable: MatchTable[seq[uint8], int], buffer: openArray[uint8
     matchTable.addMatch(group, cursor)
 
 proc lzssEncode*(buf: openArray[uint8]): LzssChain =
-  result = initSinglyLinkedList[LzssNode]()
+  result = newSeqOfCap[LzssNode](buf.len)
   let matchTable = initMatchTable(seq[uint8], int)
   var cursor = 0
   while cursor < buf.len() - matchGroupLength:
     let matches = matchTable.matchList(buf[cursor..<(cursor + matchGroupLength)])
     let prefix = matches.longestPrefix(buf.toOpenArray(0, cursor - 1), buf.toOpenArray(cursor, buf.len - 1))
     if prefix.length > 0:
-      result.append(lzssReference(prefix.length, cursor - prefix.pos))
+      result.add(lzssReference(prefix.length, cursor - prefix.pos))
       cursor += prefix.length
     else:
-      result.append(lzssCharacter(buf[cursor]))
+      result.add(lzssCharacter(buf[cursor]))
       cursor += 1
     if cursor - prefix.length >= matchGroupLength:
       matchTable.addGroups(buf, cursor - prefix.length - matchGroupLength, cursor)
   while cursor < buf.len:
-    result.append(lzssCharacter(buf[cursor]))
+    result.add(lzssCharacter(buf[cursor]))
     cursor += 1
diff --git a/src/lzss/matchtable.nim b/src/lzss/matchtable.nim
index b17ce68..94fe208 100644
--- a/src/lzss/matchtable.nim
+++ b/src/lzss/matchtable.nim
@@ -14,19 +14,17 @@
 # You should have received a copy of the GNU Affero General Public License
 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
-import tables, lists
-import listpolyfill
+import tables
 
-type MatchTable*[K, V] =
-  TableRef[K, SinglyLinkedList[V]]
+type MatchTable*[K, V] = TableRef[K, seq[V]]
 
 proc initMatchTable*[K, V](keyType: typedesc[K], valueType: typedesc[V]): MatchTable[K, V] =
-  newTable[K, SinglyLinkedList[V]]()
+  newTable[K, seq[V]]()
 
-proc matchList*[K, V](matchTable: MatchTable[K, V], pattern: K): SinglyLinkedList[V] =
-  matchTable.getOrDefault(pattern, initSinglyLinkedList[V]())
+proc matchList*[K, V](matchTable: MatchTable[K, V], pattern: K): seq[V] =
+  matchTable.getOrDefault(pattern, newSeq[V]())
 
 proc addMatch*[K, V](matchTable: MatchTable[K, V], pattern: K, value: V) =
   var matchList = matchTable.matchList(pattern)
-  listpolyfill.prepend(matchList, value)
+  matchList.insert(value)
   matchTable[pattern] = matchList
diff --git a/src/lzsshuffman/lzsshuffmandecoder.nim b/src/lzsshuffman/lzsshuffmandecoder.nim
index cd71914..a307774 100644
--- a/src/lzsshuffman/lzsshuffmandecoder.nim
+++ b/src/lzsshuffman/lzsshuffmandecoder.nim
@@ -14,9 +14,8 @@
 # You should have received a copy of the GNU Affero General Public License
 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
-import lists
 import ../bitio/bitreader
-import ../lzss/listpolyfill, ../lzss/lzssnode, ../lzss/lzsschain
+import ../lzss/lzssnode, ../lzss/lzsschain
 import ../huffman/huffmantree, ../huffman/huffmandecoder
 import lzsshuffmansymbol
 
@@ -26,9 +25,9 @@ proc readChain*(bitReader: BitReader, symbolDecoder, positionDecoder: HuffmanDec
   while not symbol.isEndMarker():
     if byteCursor > maxDataByteLength: raise newException(IOError, "lzss block too long")
     if symbol.isCharacter():
-      chain.append(lzssCharacter(symbol.uint8))
+      chain.add(lzssCharacter(symbol.uint8))
     else:
       let position = positionDecoder.decode(bitReader)
-      chain.append(unpackLzssReference(symbol, position))
+      chain.add(unpackLzssReference(symbol, position))
     (symbol, byteCursor) = (symbolDecoder.decode(bitReader).Symbol, byteCursor + 1)
   chain
diff --git a/src/lzsshuffman/lzsshuffmanencoder.nim b/src/lzsshuffman/lzsshuffmanencoder.nim
index ea89f85..205f464 100644
--- a/src/lzsshuffman/lzsshuffmanencoder.nim
+++ b/src/lzsshuffman/lzsshuffmanencoder.nim
@@ -14,9 +14,8 @@
 # You should have received a copy of the GNU Affero General Public License
 # along with this program.  If not, see <https://www.gnu.org/licenses/>.
 
-import lists