From 56bfed7e2cdd44dc4ad0c5e233224cf0080e05ac Mon Sep 17 00:00:00 2001
From: pacien
Date: Sun, 2 Dec 2018 00:38:12 +0100
Subject: replace linkedlists by seqs
---
src/lzss/listpolyfill.nim | 42 ----------------------------------
src/lzss/lzsschain.nim | 17 ++++++--------
src/lzss/lzssencoder.nim | 16 ++++++-------
src/lzss/matchtable.nim | 14 +++++-------
src/lzsshuffman/lzsshuffmandecoder.nim | 7 +++---
src/lzsshuffman/lzsshuffmanencoder.nim | 5 ++--
src/lzsshuffman/lzsshuffmanstats.nim | 2 +-
7 files changed, 26 insertions(+), 77 deletions(-)
delete mode 100644 src/lzss/listpolyfill.nim
(limited to 'src')
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 .
-
-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 .
-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 .
-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 .
-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 .
-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 .
-import lists
import ../bitio/bitwriter
-import ../lzss/listpolyfill, ../lzss/lzssnode, ../lzss/lzsschain, ../lzss/lzssencoder
+import ../lzss/lzssnode, ../lzss/lzsschain, ../lzss/lzssencoder
import ../huffman/huffmantree, ../huffman/huffmantreebuilder, ../huffman/huffmanencoder
import lzsshuffmansymbol
@@ -24,7 +23,7 @@ proc writeSymbol(bitWriter: BitWriter, encodedSymbol: tuple[bitLength: int, valu
bitWriter.writeBits(encodedSymbol.bitLength, encodedSymbol.value)
proc writeChain*(lzssChain: LzssChain, symbolEncoder, positionEncoder: HuffmanEncoder[uint16, uint16], bitWriter: BitWriter) =
- for node in lzssChain.items:
+ for node in lzssChain:
case node.kind:
of character:
bitWriter.writeSymbol(symbolEncoder.encode(node.character))
diff --git a/src/lzsshuffman/lzsshuffmanstats.nim b/src/lzsshuffman/lzsshuffmanstats.nim
index 037ce5f..d5c1f3e 100644
--- a/src/lzsshuffman/lzsshuffmanstats.nim
+++ b/src/lzsshuffman/lzsshuffmanstats.nim
@@ -20,7 +20,7 @@ import lzsshuffmansymbol
proc aggregateStats*(chain: LzssChain): tuple[symbolTable, positionTable: CountTableRef[uint16]] =
var (symbolTable, positionTable) = (newCountTable[uint16](), newCountTable[uint16]())
- for node in chain.items:
+ for node in chain:
case node.kind:
of character:
symbolTable.inc(node.character)
--
cgit v1.2.3