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 +-
tests/tlzss.nim | 51 ++++++++++++----------------------
tests/tlzsshuffman.nim | 8 +++---
9 files changed, 47 insertions(+), 115 deletions(-)
delete mode 100644 src/lzss/listpolyfill.nim
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)
diff --git a/tests/tlzss.nim b/tests/tlzss.nim
index b6b3c51..ad667e5 100644
--- a/tests/tlzss.nim
+++ b/tests/tlzss.nim
@@ -15,33 +15,24 @@
# along with this program. If not, see .
import unittest, sequtils, tables, lists
-import lzss/listpolyfill, lzss/matchtable, lzss/lzssnode, lzss/lzsschain, lzss/lzssencoder
-
-suite "listpolyfill":
- test "append":
- const data = [1, 2, 3, 4, 5, 6]
- var L: SinglyLinkedList[int]
- for d in items(data): listpolyfill.prepend(L, d)
- for d in items(data): listpolyfill.append(L, d)
- check $L == "[6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6]"
- check 4 in L
+import lzss/matchtable, lzss/lzssnode, lzss/lzsschain, lzss/lzssencoder
suite "matchtable":
test "matchList":
let matchTable = initMatchTable(seq[int], int)
- check toSeq(matchTable.matchList(@[0, 1, 2]).items).len == 0
+ check matchTable.matchList(@[0, 1, 2]).len == 0
test "addMatch":
let matchTable = initMatchTable(seq[int], int)
matchTable.addMatch(@[0, 1, 2], 42)
matchTable.addMatch(@[2, 1, 0], 24)
check matchTable.len == 2
- check toSeq(matchTable.matchList(@[0, 1, 2]).items) == @[42]
- check toSeq(matchTable.matchList(@[2, 1, 0]).items) == @[24]
+ check matchTable.matchList(@[0, 1, 2]) == [42]
+ check matchTable.matchList(@[2, 1, 0]) == [24]
matchTable.addMatch(@[0, 1, 2], 1337)
check matchTable.len == 2
- check toSeq(matchTable.matchList(@[0, 1, 2]).items) == @[1337, 42]
- check toSeq(matchTable.matchList(@[2, 1, 0]).items) == @[24]
+ check matchTable.matchList(@[0, 1, 2]) == [1337, 42]
+ check matchTable.matchList(@[2, 1, 0]) == [24]
suite "lzssnode":
test "equality":
@@ -52,19 +43,14 @@ suite "lzssnode":
check lzssCharacter(0) != lzssReference(0, 1)
suite "lzsschain":
- proc chain(): LzssChain =
- let chainArray = [
+ test "decode":
+ let chain = lzssChain([
lzssCharacter(0), lzssCharacter(1), lzssCharacter(2),
lzssCharacter(3), lzssCharacter(4), lzssCharacter(5),
lzssReference(4, 6), lzssCharacter(0), lzssCharacter(1),
lzssReference(3, 8), lzssCharacter(5),
- lzssReference(3, 3), lzssCharacter(5)]
- var chain = lzssChain()
- for node in chainArray: chain.append(node)
- result = chain
-
- test "decode":
- check chain().decode() == @[0'u8, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 4, 5, 0, 5, 5, 0, 5, 5]
+ lzssReference(3, 3), lzssCharacter(5)])
+ check chain.decode() == @[0'u8, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 4, 5, 0, 5, 5, 0, 5, 5]
suite "lzssencoder":
test "commonPrefixLength":
@@ -80,10 +66,7 @@ suite "lzssencoder":
0, 1, 2, 3,
0, 1, 2,
0, 1, 2, 3, 4]
- var candidatePos = initSinglyLinkedList[int]()
- listpolyfill.prepend(candidatePos, 0)
- listpolyfill.prepend(candidatePos, 4)
- listpolyfill.prepend(candidatePos, 8)
+ var candidatePos = [0, 4, 8]
let result = longestPrefix(candidatePos, buffer.toOpenArray(0, 10), buffer.toOpenArray(11, buffer.len - 1))
check result.pos == 4
check result.length == 4
@@ -95,15 +78,15 @@ suite "lzssencoder":
check matchTable.len == 0
matchTable.addGroups(buffer, 2, 9)
check matchTable.len == 5
- check toSeq(matchTable.matchList(@[1'u8, 2, 3]).items).len == 0
- check toSeq(matchTable.matchList(@[7'u8, 8, 9]).items).len == 0
- check toSeq(matchTable.matchList(@[2'u8, 3, 4]).items) == @[2]
- check toSeq(matchTable.matchList(@[4'u8, 5, 6]).items) == @[4]
- check toSeq(matchTable.matchList(@[6'u8, 7, 8]).items) == @[6]
+ check matchTable.matchList(@[1'u8, 2, 3]).len == 0
+ check matchTable.matchList(@[7'u8, 8, 9]).len == 0
+ check matchTable.matchList(@[2'u8, 3, 4]) == [2]
+ check matchTable.matchList(@[4'u8, 5, 6]) == [4]
+ check matchTable.matchList(@[6'u8, 7, 8]) == [6]
test "lzssEncode":
let buffer = [0'u8, 1, 2, 3, 4, 5, 0, 1, 2, 3, 0, 1, 4, 5, 0, 5, 5, 0, 5, 5]
- check toSeq(lzssEncode(buffer).items) == @[
+ check lzssEncode(buffer) == [
lzssCharacter(0), lzssCharacter(1), lzssCharacter(2),
lzssCharacter(3), lzssCharacter(4), lzssCharacter(5),
lzssReference(4, 6), lzssCharacter(0), lzssCharacter(1),
diff --git a/tests/tlzsshuffman.nim b/tests/tlzsshuffman.nim
index f771f31..bd729e6 100644
--- a/tests/tlzsshuffman.nim
+++ b/tests/tlzsshuffman.nim
@@ -14,9 +14,9 @@
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see .
-import unittest, tables, lists, sequtils, streams
+import unittest, tables, sequtils, streams
import bitio/bitwriter, bitio/bitreader
-import lzss/listpolyfill, lzss/lzssnode, lzss/lzsschain
+import lzss/lzssnode, lzss/lzsschain
import huffman/huffmantree, huffman/huffmantreebuilder, huffman/huffmanencoder, huffman/huffmandecoder
import lzsshuffman/lzsshuffmansymbol, lzsshuffman/lzsshuffmanstats, lzsshuffman/lzsshuffmanencoder, lzsshuffman/lzsshuffmandecoder
@@ -109,7 +109,7 @@ suite "lzsshuffmandecoder":
stream.setPosition(0)
let bitReader = stream.bitReader()
let result = readChain(bitReader, symbolTree.decoder(), positionTree.decoder(), 32_000)
- check toSeq(result.items).len == 0
+ check result.len == 0
test "readChain (minimal)":
let symbolTree = huffmanBranch(
@@ -139,6 +139,6 @@ suite "lzsshuffmandecoder":
stream.setPosition(0)
let bitReader = stream.bitReader()
let result = readChain(bitReader, symbolTree.decoder(), positionTree.decoder(), 32_000)
- check toSeq(result.items) == [
+ check result == [
lzssCharacter(0), lzssCharacter(1), lzssCharacter(2),
lzssReference(3, 3), lzssReference(3, 4)]
--
cgit v1.2.3